SkelGIS
3.0
|
00001 /*! \file ddag_impl.hpp 00002 * \brief Definitions of the object DDAG_impl used by the user. Three template specializations are available. 00003 * DDAG_impl is the structure of the tree, not data. data are stored in DProperty objects. 00004 */ 00005 #ifndef DDAG_IMPL_H 00006 #define DDAG_IMPL_H 00007 00008 #include "../../util/mpi_.hpp" 00009 #include "../../iterators/DDAG/iterator.hpp" 00010 #include <math.h> 00011 #include<vector> 00012 00013 namespace skelgis{ 00014 00015 //------------------------------------------------------------------------------- 00016 //! base template class of Distributed DAG 00017 /*! 00018 This template class defines the base distributed dag 00019 This basic template does not have an implementation, only specializations have 00020 direction of the DAG is not usefull the input file of the user precise the direction 00021 no parameter on the physical border because roots and leafs nodes are always managed in a different way than standard elements (different neighborhood etc.) 00022 \tparam node is a boolean parameter to indicate if computations on nodes are needed for this DDAG_impl 00023 \tparam edge is a boolean parameter to indicate if computations on edges are needed for this DDAG_impl 00024 */ 00025 //------------------------------------------------------------------------------- 00026 template<bool node, bool edge> struct DDAG_impl; 00027 //------------------------------------------------------------------------------- 00028 00029 //------------------------------------------------------------------------------- 00030 //! First specialization of the DDAG_impl class 00031 /*! 00032 This is the more complex case where both nodes and edges have to be computed 00033 */ 00034 //------------------------------------------------------------------------------- 00035 template<> struct DDAG_impl<true,true> 00036 //------------------------------------------------------------------------------- 00037 { 00038 protected: 00039 00040 /*!< to manage physical border 00041 physical border in DDAG_impl for scientific simulations are leafs and roots of the global DDAG_impl */ 00042 unsigned int dim_roots; //! number of roots elements in the local DDAG_impl (global notion of roots) 00043 unsigned int dim_leafs; //! number of leafs elements int the local DDAG_impl (global notion of leafs) 00044 /*!< As distribution is not perfect, especially for huge DDAG_impl, it is important to make an overlap of communications by local computations 00045 For this reason pure local elements (except roots and leafs) are distinguished from elements that need communications */ 00046 unsigned int dim_loc; //! number of internal nodes without any communication 00047 unsigned int dim_comm; //! number of internal nodes with communications 00048 00049 //DATA STRUCTURE 00050 //nodes 00051 unsigned int dim_node; //! number of nodes 00052 /*!< cumulative degrees for inside neighbors nodes and edges 00053 foreach node you can get the number of inside nodes and inside edges (same) neighbors */ 00054 unsigned int *degcum_in; 00055 /*!< cumulative degrees for outside neighbors nodes and edges 00056 foreach node you can get the number of outside nodes and inside edges (same) neighbors */ 00057 unsigned int *degcum_out; 00058 /*!< associated table to degcum_in 00059 This table is the list of input neighbors nodes indexes for each node of the local DDAG_impl */ 00060 unsigned int *neigh_in; 00061 /*!< associated table to degcum_out 00062 This table is the list of output neighbors nodes indexes for each node of the local DDAG_impl */ 00063 unsigned int *neigh_out; 00064 /*!< associated table to degcum_in 00065 This table is the list of input neighbors edges indexes for each node of the local DDAG_impl */ 00066 unsigned int *edges_out; 00067 /*!< associated table to degcum_out 00068 This table is the list of output neighbors edges indexes for each node of the local DDAG_impl */ 00069 unsigned int *edges_in; 00070 00071 //DATA STRUCTURE 00072 //edges 00073 unsigned int dim_edge; //! number of edges 00074 unsigned int *src_nodes; //! source node of each edge 00075 unsigned int *dst_nodes; //! destination node of each edge 00076 00077 //DATA STRUCTURE 00078 //indexation 00079 unsigned int dim_ind_ed,dim_ind_no; //! number of indexes for nodes and edges (with additionnal communication indexes) 00080 /*!< Associations between new local nodes indexes values and nodes indexes of the global DAG 00081 Order of the new nodes indexes are very important for a transparent iteration on local elements 00082 All local nodes tables use those new indexes (neighborhood etc) 00083 indexes are stored this way : 00084 ****************************************************************************************************************************************** 00085 || pure local elements | elements with communications | leafs | roots | comunicated elements from other processors IN then OUT || 00086 ****************************************************************************************************************************************** 00087 */ 00088 unsigned int *indexes_nodes; 00089 /*!< Associations between new local edges indexes values and edges indexes of the global DAG 00090 Edges are indexed following the nodes indexes 00091 output edges of Node 0 are indexed from 0 to degcum_out[0] 00092 output edges of Node k are indexed from degcum_out[k-1] to degcum_out[k] 00093 */ 00094 unsigned int *indexes_edges; 00095 00096 //DATA STRUCTURE 00097 //parallelization 00098 /*!< Number of elements to receive : outputs and inputs elements */ 00099 unsigned int dim_tor_out,dim_tor_in; 00100 /*!< Number of elements to send : outputs and inputs elements */ 00101 unsigned int dim_tos_out,dim_tos_in; 00102 /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output and input elements to send */ 00103 unsigned int *degcum_tos; 00104 /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of input elements to send 00105 for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types */ 00106 unsigned int * degcum_tos_in; 00107 /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output elements to send 00108 for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types */ 00109 unsigned int * degcum_tos_out; 00110 /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output and input elements to receive */ 00111 unsigned int *degcum_tor; 00112 /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of input elements to receive 00113 for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types*/ 00114 unsigned int *degcum_tor_in; 00115 /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output elements to receive 00116 for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types*/ 00117 unsigned int *degcum_tor_out; 00118 /*!< associated table to degcum_tos for edges 00119 This table is the list of edges local indexes to send to each other processor 00120 */ 00121 //unsigned int *edges_tos; 00122 /*!< associated table to degcum_tos_in for edges 00123 This table is the list of edges to send that goes in another processor, local indexes to send to each other processor */ 00124 unsigned int *edges_tos_in; 00125 /*!< associated table to degcum_tos_out for edges 00126 This table is the list of edges to send that goes out of another processor, local indexes to send to each other processor */ 00127 unsigned int *edges_tos_out; 00128 /*!< associated table to degcum_tos for nodes 00129 This table is the list of nodes local indexes to send to each other processor */ 00130 unsigned int *nodes_tos; 00131 /*!< associated table to degcum_tor for edges 00132 This table is the list of edges local indexes to receive to each other processor */ 00133 //unsigned int *edges_tor; 00134 /*!< associated table to degcum_tor_in for edges 00135 This table is the list of edges local indexes to receive in from each other processor */ 00136 unsigned int *edges_tor_in; 00137 /*!< associated table to degcum_tor_out for edges 00138 This table is the list of edges local indexes to receive out from each other processor */ 00139 unsigned int *edges_tor_out; 00140 /*!< associated table to degcum_tos for nodes 00141 This table is the list of nodes local indexes to receive to each other processor */ 00142 unsigned int *nodes_tor; 00143 00144 //------------------------------------------------------------------------------- 00145 //! find position tool 00146 /*! 00147 Find the position of element in table 00148 \param table is the pointer table in which the element has to be searched 00149 \param size is the size of the table 00150 \param element is the element value to search 00151 \param position is a reference to the position found 00152 \return true if the position has been found, false otherwise 00153 */ 00154 //------------------------------------------------------------------------------- 00155 bool find_position(unsigned int * table,unsigned int size,unsigned int element,unsigned int &position) 00156 //------------------------------------------------------------------------------- 00157 { 00158 for(unsigned int i=0;i<size;i++) 00159 { 00160 if(table[i]==element) 00161 { 00162 position=i; 00163 return true; 00164 } 00165 } 00166 return false; 00167 } 00168 //------------------------------------------------------------------------------- 00169 //! find position tool 00170 /*! 00171 Find the position of element in table but do not get the position value 00172 \param table is the pointer table in which the element has to be searched 00173 \param size is the size of the table 00174 \param element is the element value to search 00175 \return true if the position has been found, false otherwise 00176 */ 00177 //------------------------------------------------------------------------------- 00178 bool find_position(unsigned int * table,unsigned int size,unsigned int element) 00179 //------------------------------------------------------------------------------- 00180 { 00181 for(unsigned int i=0;i<size;i++) 00182 { 00183 if(table[i]==element) 00184 return true; 00185 } 00186 return false; 00187 } 00188 //------------------------------------------------------------------------------- 00189 //! find from tool 00190 /*! 00191 Search an element in a table with two positions between which to search 00192 \param table is the pointer table in which the element has to be searched 00193 \param position1 is the index value in the table where to start the search 00194 \param position2 is the index value in the table where to end the search (included) 00195 \param element is the element value to search in table 00196 \return true if the position has been found, false otherwise 00197 */ 00198 //------------------------------------------------------------------------------- 00199 bool find_from(unsigned int * table,unsigned int position1,unsigned int position2,unsigned int element) 00200 //------------------------------------------------------------------------------- 00201 { 00202 for(unsigned int i=position1;i<position2+1;i++) 00203 { 00204 if(table[i]==element) 00205 return true; 00206 } 00207 return false; 00208 } 00209 //------------------------------------------------------------------------------- 00210 //! get maximum value tool 00211 /*! 00212 search the minimum value between three values 00213 \param a is the first value 00214 \param b is the second value 00215 \param c is the third value 00216 \return the minimum value between a, b and c 00217 */ 00218 //------------------------------------------------------------------------------- 00219 unsigned int max(unsigned a,unsigned b,unsigned c) 00220 //------------------------------------------------------------------------------- 00221 { 00222 a=(a>b) ? a : b; 00223 return (a>c) ? a : c; 00224 } 00225 //------------------------------------------------------------------------------- 00226 //! recursively increment the number of time a subtree has been visited 00227 /*! 00228 Is used to count the number of total edges under a subtree 00229 \param index is the index of the root element of the subtree 00230 \param visited is the table to increment for the subtree 00231 \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks) 00232 \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks 00233 */ 00234 //------------------------------------------------------------------------------- 00235 void is_visited(unsigned int index, unsigned int * visited, unsigned int * degcum_block, unsigned int *linked_blocks) 00236 //------------------------------------------------------------------------------- 00237 { 00238 unsigned int nb = degcum_block[index+1]-degcum_block[index]; 00239 for(unsigned int i=0;i<nb;i++) 00240 is_visited(linked_blocks[degcum_block[index]+i],visited,degcum_block,linked_blocks); 00241 visited[index]+=1; 00242 } 00243 //------------------------------------------------------------------------------- 00244 //! recursively count the number of edges in a subtree 00245 /*! 00246 Is used to modify is_visited error 00247 \param index is the index of the root element of the subtree 00248 \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks) 00249 \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks 00250 \param edge_block is the cumulative degrees for the number of edges in each block of sister edges 00251 \return The number of edges in the subtree 00252 */ 00253 //------------------------------------------------------------------------------- 00254 unsigned int all_edges_under(unsigned int index, unsigned int * degcum_block, unsigned int *linked_blocks, unsigned int * edge_block) 00255 //------------------------------------------------------------------------------- 00256 { 00257 unsigned int nb = degcum_block[index+1]-degcum_block[index]; 00258 unsigned int res = edge_block[index+1] - edge_block[index]; 00259 for(unsigned int i=0;i<nb;i++) 00260 res+=all_edges_under(linked_blocks[degcum_block[index]+i],degcum_block,linked_blocks,edge_block); 00261 00262 return res; 00263 } 00264 //------------------------------------------------------------------------------- 00265 //! Take all the subtree for the same processor 00266 /*! 00267 Used in the distribution of the DDAG_impl, if the number of edges in the subtree < ideal take it entirely 00268 \param index is the index of the root element of the subtree 00269 \param edge_block is the cumulative degrees for the number of edges in each block of sister edges 00270 \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks) 00271 \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks 00272 \param taken is the table to note to which processor is assigned each block 00273 \param count is the reference to the count of edges for the current processor 00274 \param cur_proc is the current processor index 00275 */ 00276 //------------------------------------------------------------------------------- 00277 void takeall(unsigned int index,unsigned int *edge_block,unsigned int *degcum_block,unsigned int *linked_blocks,unsigned int *taken,unsigned int &count, unsigned int cur_proc) 00278 //------------------------------------------------------------------------------- 00279 { 00280 //std::cout<<"index="<<index<<std::endl; 00281 if(taken[index]==0) 00282 { 00283 count += edge_block[index+1]-edge_block[index]; 00284 taken[index] = cur_proc+1; 00285 } 00286 for(unsigned int i=0;i<degcum_block[index+1]-degcum_block[index];i++) 00287 takeall(linked_blocks[degcum_block[index]+i],edge_block,degcum_block,linked_blocks,taken,count,cur_proc); 00288 } 00289 //------------------------------------------------------------------------------- 00290 //! to verify that no isolated edges are stuck 00291 /*! 00292 When the ideal number of edges is reached, verify that no isolated edges are stuck in the subtree taken by the processor 00293 \param index is the index of the root element of the subtree 00294 \param edge_b_loc 00295 \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks) 00296 \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks 00297 \param taken is the table to note to which processor is assigned each block 00298 \param count is the reference to the count of edges for the current processor 00299 */ 00300 //------------------------------------------------------------------------------- 00301 void verif(unsigned int *index,unsigned int *edge_b_loc, unsigned int size, unsigned int * degcum_block, unsigned int *linked_blocks, 00302 unsigned int *taken, unsigned int &count) 00303 //------------------------------------------------------------------------------- 00304 { 00305 for(unsigned int i=0;i<size;i++) 00306 { 00307 if(taken[index[i]]==0 && degcum_block[index[i]+1]-degcum_block[index[i]]==1 && taken[linked_blocks[degcum_block[index[i]]]]>0) 00308 { 00309 count+=edge_b_loc[i]; 00310 taken[index[i]] = taken[linked_blocks[degcum_block[index[i]]]]; 00311 } 00312 } 00313 } 00314 //------------------------------------------------------------------------------- 00315 //! recursive function for distribution when a root has been chosen or when a leaf has been reached (so an additionnal root is chosen) 00316 /*! 00317 \param mean_edges is the mean of the number of edges in blocks, it is used for an error on the ideal number of edges 00318 \param edges_r 00319 \param index is the index where to start the recursive distribution 00320 \param edge_b_loc 00321 \param size 00322 \param ideal is the ideal number of edges per processor 00323 \param taken is the table to note which block is assigned to which processor 00324 \param edges_subtree 00325 \param count is the number of edges taken by the current processor 00326 \pram cur_proc is the current processor 00327 \return false if the ideal number of edges is reached 00328 */ 00329 //------------------------------------------------------------------------------- 00330 bool dist(unsigned int mean_edges, unsigned int & edges_r,unsigned int *index,unsigned int *edge_b_loc, unsigned int size, unsigned int ideal, 00331 unsigned int *edge_block, unsigned int * degcum_block, unsigned int *linked_blocks, 00332 unsigned int *taken, unsigned int * edges_subtree,unsigned int &count,int &cur_proc) 00333 //------------------------------------------------------------------------------- 00334 { 00335 /* 00336 1) try to take output blocks in edge_b_loc 00337 2) first search for subtrees (with roots in edge_b_loc) that can be get entirely without reaching ideal 00338 3) then enter the recrusive call of dist(...) itself for biger subtree 00339 This way isolated branches are avoided 00340 */ 00341 00342 if(size>0) 00343 { 00344 //first take the blocks that we can entirely take (<ideal) 00345 unsigned int bigger=0; 00346 for(unsigned int i=0;i<size;i++) 00347 { 00348 if(taken[index[i]]==0) 00349 { 00350 if(edges_subtree[index[i]]>edges_subtree[index[bigger]]) 00351 bigger = i; 00352 00353 if(count<ideal) 00354 { 00355 //if we can directly add the block and its subtree 00356 //if(count+edges_subtree[index[i]]<=ideal+mean_edges+floor(ideal*0.1)) 00357 if(count+edges_subtree[index[i]]<=ideal+mean_edges) 00358 takeall(index[i],edge_block,degcum_block,linked_blocks,taken,count,cur_proc); 00359 } 00360 else if(count>=ideal) 00361 { 00362 verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count); 00363 //free(index); 00364 //free(edge_b_loc); 00365 return false; 00366 } 00367 } 00368 } 00369 //bigger case 00370 if(taken[index[bigger]]==0 && count<ideal) 00371 { 00372 //if(count<ideal && count+edge_b_loc[bigger]<=ideal+mean_edges+floor(ideal*0.1)) 00373 if(count<ideal && count+edge_b_loc[bigger]<=ideal+mean_edges) 00374 { 00375 count+=edge_b_loc[bigger]; 00376 taken[index[bigger]] = cur_proc+1; 00377 //recursive call 00378 if(count<ideal) 00379 { 00380 unsigned int new_size=degcum_block[index[bigger]+1]-degcum_block[index[bigger]]; 00381 unsigned int *edge_block_loc = (unsigned int *)calloc(new_size,sizeof(unsigned int)); 00382 unsigned int *index_loc = (unsigned int *)calloc(new_size,sizeof(unsigned int)); 00383 if(new_size>0) 00384 { 00385 for(unsigned int j=0;j<degcum_block[index[bigger]+1]-degcum_block[index[bigger]];j++) 00386 { 00387 index_loc[j] = linked_blocks[degcum_block[index[bigger]]+j]; 00388 edge_block_loc[j] = edge_block[index_loc[j]+1]-edge_block[index_loc[j]]; 00389 } 00390 } 00391 00392 //appel récursif 00393 bool ret = dist(mean_edges,edges_r,index_loc,edge_block_loc,new_size,ideal, 00394 edge_block,degcum_block,linked_blocks,taken,edges_subtree,count,cur_proc); 00395 verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count); 00396 00397 free(index_loc); 00398 free(edge_block_loc); 00399 if(ret==false) 00400 return ret; 00401 } 00402 else if(count>=ideal) 00403 { 00404 verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count); 00405 //free(index); 00406 //free(edge_b_loc); 00407 return false; 00408 } 00409 } 00410 else if(count>=ideal) 00411 { 00412 verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count); 00413 //free(index); 00414 //free(edge_b_loc); 00415 return false; 00416 } 00417 } 00418 } 00419 } 00420 //------------------------------------------------------------------------------- 00421 //! Read the input DAG file .dot 00422 /*! 00423 \param file is the path to the file to read 00424 \param dim_node_g is the number of nodes in the global DDAG_impl 00425 \param dim_edge_g is the number of edges in the global DDAG_impl 00426 \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl 00427 \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl 00428 */ 00429 //------------------------------------------------------------------------------- 00430 void read(const char * file,unsigned int &dim_node_g,unsigned int &dim_edge_g,unsigned int *&src_nodes_g,unsigned int *&dst_nodes_g) 00431 //------------------------------------------------------------------------------- 00432 { 00433 FILE *dotfile=fopen(file,"r"); 00434 00435 int read = fscanf(dotfile,"%u -> %u ;", &src_nodes_g[dim_edge_g], &dst_nodes_g[dim_edge_g]); 00436 while(!feof(dotfile)) 00437 { 00438 dim_node_g=max(dim_node_g,src_nodes_g[dim_edge_g],dst_nodes_g[dim_edge_g]); 00439 dim_edge_g++; 00440 src_nodes_g=(unsigned int *)realloc(src_nodes_g,(dim_edge_g+1)*sizeof(unsigned int)); 00441 dst_nodes_g=(unsigned int *)realloc(dst_nodes_g,(dim_edge_g+1)*sizeof(unsigned int)); 00442 read = fscanf(dotfile,"%u -> %u ;", &src_nodes_g[dim_edge_g], &dst_nodes_g[dim_edge_g]); 00443 } 00444 00445 fclose(dotfile); 00446 } 00447 //------------------------------------------------------------------------------- 00448 //! Find roots and leafs of the global DDAG_impl 00449 /*! 00450 \param dim_node_g is the number of nodes in the global DDAG_impl 00451 \param dim_edge_g is the number of edges in the global DDAG_impl 00452 \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl 00453 \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl 00454 \param dim_roots_g is the reference to the global number of roots elements in the global DDAG_impl 00455 \param dim_leafs_g is the reference to the global number of leafs elements in the global DDAG_impl 00456 */ 00457 //------------------------------------------------------------------------------- 00458 void findRootsLeafs(unsigned int dim_node_g, unsigned int dim_edge_g, unsigned int * src_nodes_g, unsigned int * dst_nodes_g, 00459 unsigned int &dim_roots_g, unsigned int &dim_leafs_g, unsigned int *&roots_g, unsigned int *&leafs_g) 00460 //------------------------------------------------------------------------------- 00461 { 00462 for(unsigned int j=0;j<dim_node_g;j++) 00463 { 00464 int found_src=0; 00465 int found_dst=0; 00466 for(unsigned int i=0;i<dim_edge_g;i++) 00467 { 00468 if(src_nodes_g[i]==j) 00469 found_src++; 00470 if(dst_nodes_g[i]==j) 00471 found_dst++; 00472 } 00473 if(found_src>0 && found_dst==0) 00474 { 00475 dim_roots_g++; 00476 roots_g = (unsigned int *)realloc(roots_g,(dim_roots_g)*sizeof(unsigned int)); 00477 roots_g[dim_roots_g-1]=j; 00478 } 00479 if(found_src==0 && found_dst>0) 00480 { 00481 dim_leafs_g++; 00482 leafs_g = (unsigned int *)realloc(leafs_g,(dim_leafs_g)*sizeof(unsigned int)); 00483 leafs_g[dim_leafs_g-1]=j; 00484 } 00485 } 00486 } 00487 //------------------------------------------------------------------------------- 00488 //! Construction of the global DAG data structure 00489 /*! 00490 \param dim_edge_g is the number of edges in the global DDAG_impl 00491 \param dim_node_g is the number of nodes in the global DDAG_impl 00492 \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl 00493 \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl 00494 \param degcum_in_g equivalent of degcum_in for the global DAG_impl 00495 \param degcum_out_g equivalent of degcum_out for the global DAG_impl 00496 \param neigh_out_g equivalent of the neigh_out for the global DAG_impl 00497 \param neigh_in_g equivalent of the neigh_in for the global DAG_impl 00498 \param edges_g equivalent of edges_out and edges_in for the global DAG_impl (no distinction needed) 00499 \param edge_block cumulative degrees of the number of edges per block 00500 */ 00501 //------------------------------------------------------------------------------- 00502 void globalDS(unsigned int dim_edge_g,unsigned int dim_node_g,unsigned int *src_nodes_g,unsigned int *dst_nodes_g, 00503 unsigned int *°cum_in_g,unsigned int *°cum_out_g,unsigned int *&neigh_out_g,unsigned int *&neigh_in_g,unsigned int *&edges_g, unsigned int *&edge_block, 00504 unsigned int &mean_edges, unsigned int &max_edges, unsigned int &b) 00505 //------------------------------------------------------------------------------- 00506 { 00507 //-------------------------------------------------------------------------------- 00508 //construction of degcum_out_g and degcum_in_g : 00509 //represent the cumulative number of inputs and outputs nodes and edges of a node 00510 //construction of edge_block : 00511 //represent the number of edges in each group of sister edges 00512 //-------------------------------------------------------------------------------- 00513 unsigned int *deg_in=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int)); 00514 unsigned int *deg_out=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int)); 00515 for(unsigned int i=0;i<dim_edge_g;i++) 00516 { 00517 deg_out[src_nodes_g[i]]++; 00518 deg_in[dst_nodes_g[i]]++; 00519 } 00520 00521 degcum_in_g=(unsigned int *)calloc(dim_node_g+1,sizeof(unsigned int)); 00522 degcum_out_g=(unsigned int *)calloc(dim_node_g+1,sizeof(unsigned int)); 00523 edge_block=(unsigned int *)realloc(edge_block,1*sizeof(unsigned int)); 00524 edge_block[0] = degcum_out_g[0]; 00525 for (int i=1;i<dim_node_g+1;i++) 00526 { 00527 degcum_out_g[i]=degcum_out_g[i-1]+deg_out[i-1]; 00528 degcum_in_g[i]=degcum_in_g[i-1]+deg_in[i-1]; 00529 if(i<dim_node_g && degcum_out_g[i]>degcum_out_g[i-1]) 00530 { 00531 b++; 00532 edge_block=(unsigned int *)realloc(edge_block,(b+1)*sizeof(unsigned int)); 00533 edge_block[b] = degcum_out_g[i]; 00534 if(edge_block[b]-edge_block[b-1]>max_edges) 00535 max_edges = edge_block[b]-edge_block[b-1]; 00536 00537 mean_edges += edge_block[b]-edge_block[b-1]; 00538 } 00539 00540 } 00541 free(deg_in),free(deg_out); 00542 mean_edges = static_cast<unsigned int>(floor(mean_edges/b)); 00543 //-------------------------------------------------------------------------------- 00544 //construction of neigh_out_g, neigh_in_g and edges 00545 //represent the associated neighbour nodes and edges of a node with use of degcum tables 00546 //-------------------------------------------------------------------------------- 00547 unsigned int *t_in=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int)); 00548 unsigned int *t_out=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int)); 00549 unsigned int *t=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int)); 00550 00551 neigh_in_g=(unsigned int *)calloc(dim_edge_g,sizeof(unsigned int)); 00552 neigh_out_g=(unsigned int *)calloc(dim_edge_g,sizeof(unsigned int)); 00553 edges_g=(unsigned int *)calloc(dim_edge_g,sizeof(unsigned int)); 00554 00555 for (int i=0;i<dim_edge_g;i++) 00556 { 00557 neigh_out_g[ degcum_out_g[src_nodes_g[i]] + t_out[ src_nodes_g[i] ]++ ]=dst_nodes_g[i]; 00558 neigh_in_g[ degcum_in_g[dst_nodes_g[i]] + t_in[ dst_nodes_g[i] ]++ ]=src_nodes_g[i]; 00559 edges_g[ degcum_out_g[src_nodes_g[i]] + t[ src_nodes_g[i] ]++ ]=i; 00560 } 00561 free(t_out),free(t_in),free(t); 00562 } 00563 //------------------------------------------------------------------------------- 00564 //! Prepare data for distribution 00565 /*! 00566 \param b is the number of blocks in the global DAG 00567 \param edges_g equivalent of edges_out and edges_in for the global DAG (no distinction) 00568 \param edge_block cumulative degrees of the number of edges per block 00569 \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl 00570 \param degcum_out_g equivalent of degcum_out for the global DAG_impl 00571 \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks) 00572 \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks 00573 \param edges_subtree 00574 */ 00575 //------------------------------------------------------------------------------- 00576 void dataDistr(unsigned int b,unsigned int *edges_g,unsigned int *edge_block,unsigned int *dst_nodes_g,unsigned int *degcum_out_g, 00577 unsigned int *°cum_block,unsigned int *&linked_blocks,unsigned int *&edges_subtree) 00578 //------------------------------------------------------------------------------- 00579 { 00580 //-------------------------------------------------------------------------------- 00581 //construction of degcum_block and linked_block 00582 //represent the equivalent of degcum_out and neigh_out of nodes, but for blocks of sister edges 00583 //-------------------------------------------------------------------------------- 00584 for(unsigned int i=0;i<b;i++) 00585 { 00586 //initialization of degcum_block i+1 with the previous value 00587 degcum_block[i+1] = degcum_block[i]; 00588 00589 //with edge_block and edges we know which edges are in each block 00590 unsigned int end = edge_block[i+1] - edge_block[i]; 00591 unsigned int * cur_edges = (unsigned int *)calloc(end,sizeof(unsigned int)); 00592 for(unsigned int j=0;j<end;j++) 00593 cur_edges[j] = edges_g[edge_block[i]+j]; 00594 00595 for(unsigned int j=0;j<end;j++) 00596 { 00597 //with dst_nodes we know the destination node the edges is connected to 00598 unsigned int node_dst = dst_nodes_g[cur_edges[j]]; 00599 //with degcum_out and edges we know the out edges of the destination node 00600 unsigned int en = degcum_out_g[node_dst+1] - degcum_out_g[node_dst]; 00601 unsigned int *out_ed = (unsigned int *)calloc(en,sizeof(unsigned int)); 00602 for(unsigned int k=0;k<en;k++) 00603 out_ed[k] = edges_g[degcum_out_g[node_dst]+k]; 00604 00605 //now we identify which edges block has these output edges 00606 if(en>0) 00607 { 00608 for(unsigned int l=0;l<b;l++) 00609 { 00610 if(en >0 && edge_block[l+1]==out_ed[0]) 00611 { 00612 degcum_block[i+1]++; 00613 linked_blocks = (unsigned int *)realloc(linked_blocks,degcum_block[i+1]*sizeof(unsigned int)); 00614 linked_blocks[degcum_block[i+1]-1]=l+1; 00615 } 00616 } 00617 } 00618 free(out_ed); 00619 } 00620 free(cur_edges); 00621 } 00622 //-------------------------------------------------------------------------------- 00623 //construction of the last table edges_subtree 00624 //represent the total number of edges under a block if this block is the root of the subtree (we count its own edges too) 00625 //-------------------------------------------------------------------------------- 00626 for(unsigned int i=0;i<b;i++) 00627 { 00628 //naive calculation of edges_subtree 00629 edges_subtree[i] = all_edges_under(i,degcum_block,linked_blocks,edge_block); 00630 //error correction 00631 unsigned int * visited = (unsigned int *)calloc(b,sizeof(unsigned int)); 00632 is_visited(i,visited,degcum_block,linked_blocks); 00633 for(unsigned int j=0;j<b;j++) 00634 { 00635 if(visited[j]>1) 00636 edges_subtree[i] -= (visited[j]-1)*(edge_block[j+1]-edge_block[j]); 00637 } 00638 free(visited); 00639 } 00640 } 00641 //------------------------------------------------------------------------------- 00642 //! Fill src_nodes and dst_nodes and construct temporary pure local indexes 00643 /*! 00644 \param b is the number of blocks in the global DAG 00645 \param taken is the table to note which block is assigned to which processor 00646 \param edge_block is the cumulative degrees for the number of edges in each block of sister edges 00647 \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl 00648 \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl 00649 \param edges_g equivalent of edges_out and edges_in for the global DAG (no distinction) 00650 \param dim_roots_g is the number of roots in the global DAG_impl 00651 \param dim_leafs_g is the number of leafs in the global DAG_impl 00652 \param roots_g is the list of roots in the global DAG_impl 00653 \param leafs_g is the list of leafs in the global DAG_impl 00654 */ 00655 //------------------------------------------------------------------------------- 00656 void localSrcDstNodes(unsigned int b,unsigned int *taken,unsigned int *edge_block,unsigned int *src_nodes_g,unsigned int *dst_nodes_g,unsigned int *edges_g, 00657 unsigned int dim_roots_g,unsigned int dim_leafs_g,unsigned int *roots_g,unsigned int *leafs_g) 00658 //------------------------------------------------------------------------------- 00659 { 00660 /* 00661 src_nodes and dst_nodes are taken from globals src_nodes_g and dst_nodes_g and the table taken 00662 indexes of edges are also taken from this 00663 BUT indexation are modified three time during the construction of the data structure 00664 1) at the beginning (in this method) to take into acount local elements that are global roots and leafs 00665 (these elements do not need communications and in addition to this they have to be managed differently than other elements) 00666 2) later communications are calculated and indexation of new elements received from other processors are calculated 00667 3) finally in the same code different indexation are made between local elements that do not need any communication to be computed and elements that need communications 00668 Indexation for nodes is finally made this way : 00669 ****************************************************************************************************************************************** 00670 || pure local elements | elements with communications | leafs | roots | comunicated elements from other processors IN then OUT || 00671 ****************************************************************************************************************************************** 00672 00673 Indexation for edges depends on indexation of nodes and are modify too 00674 output edges of Node 0 are indexed from 0 to degcum_out[0] 00675 output edges of Node k are indexed from degcum_out[k-1] to degcum_out[k] 00676 */ 00677 00678 //get src_nodes, dst_nodes and basic indexes_edges from src_nodes_g dst_nodes_g and taken 00679 unsigned int ind=0; 00680 for(unsigned int i=0;i<b;i++) 00681 { 00682 if(taken[i]==Mpi_::mpi_rank+1) 00683 { 00684 for(unsigned int j=0;j<edge_block[i+1]-edge_block[i];j++) 00685 { 00686 src_nodes[ind+j] = src_nodes_g[edges_g[edge_block[i]+j]]; 00687 dst_nodes[ind+j] = dst_nodes_g[edges_g[edge_block[i]+j]]; 00688 indexes_edges[ind+j] = edges_g[edge_block[i]+j]; 00689 } 00690 ind += edge_block[i+1]-edge_block[i]; 00691 } 00692 } 00693 00694 //sort the node indexes (src and dst) without double values 00695 //it represents the new basic indexes 00696 unsigned int * temp = (unsigned int*)calloc(2*dim_edge,sizeof(unsigned int)); 00697 indexes_nodes = (unsigned int*)calloc(1,sizeof(unsigned int)); 00698 for(unsigned int i=0;i<dim_edge;i++) 00699 temp[i] = src_nodes[i]; 00700 for(unsigned int i=dim_edge;i<2*dim_edge;i++) 00701 temp[i] = dst_nodes[i-dim_edge]; 00702 //sort temp 00703 bool mod=true; 00704 while(mod) 00705 { 00706 mod=false; 00707 for(unsigned int i=1;i<2*dim_edge;i++) 00708 { 00709 if(temp[i]<temp[i-1]) 00710 { 00711 unsigned int t = temp[i]; 00712 temp[i] = temp[i-1]; 00713 temp[i-1] = t; 00714 mod=true; 00715 } 00716 } 00717 } 00718 //fill sort 00719 unsigned int * s_indexes_nodes = (unsigned int*)calloc(1,sizeof(unsigned int)); 00720 s_indexes_nodes[0] = temp[0]; 00721 dim_node=1; 00722 for(unsigned int i=1;i<2*dim_edge;i++) 00723 { 00724 //erase double values 00725 if(temp[i]!=temp[i-1]) 00726 { 00727 dim_node++; 00728 indexes_nodes = (unsigned int*)realloc(indexes_nodes,dim_node*sizeof(unsigned int)); 00729 s_indexes_nodes = (unsigned int*)realloc(s_indexes_nodes,dim_node*sizeof(unsigned int)); 00730 s_indexes_nodes[dim_node-1]=temp[i]; 00731 indexes_nodes[dim_node-1]=temp[i]; 00732 } 00733 } 00734 free(temp); 00735 00736 //change those new indexes, taking care of roots and leafs elements 00737 unsigned int rev = dim_node-1; 00738 unsigned int in=0; 00739 for(unsigned int i=0;i<dim_node;i++) 00740 { 00741 bool l=false; 00742 for(unsigned int j=0;j<dim_leafs_g;j++) 00743 { 00744 if(leafs_g[j]==s_indexes_nodes[i]) 00745 { 00746 dim_leafs++; 00747 indexes_nodes[rev]=s_indexes_nodes[i]; 00748 rev--; 00749 l=true; 00750 } 00751 } 00752 bool r = false; 00753 for(unsigned int j=0;j<dim_roots_g;j++) 00754 { 00755 if(roots_g[j]==s_indexes_nodes[i]) 00756 { 00757 dim_roots++; 00758 indexes_nodes[rev]=s_indexes_nodes[i]; 00759 rev--; 00760 r=true; 00761 } 00762 } 00763 if(!r && !l) 00764 { 00765 indexes_nodes[in] = s_indexes_nodes[i]; 00766 in++; 00767 } 00768 } 00769 free(s_indexes_nodes); 00770 00771 //modification of src_nodes and dst_nodes with local indexes 00772 for(unsigned int i=0;i<dim_edge;i++) 00773 { 00774 bool f_src=false; 00775 bool f_dst=false; 00776 for(unsigned int j=0;j<dim_node;j++) 00777 { 00778 if(!f_src && src_nodes[i]==indexes_nodes[j]) 00779 { 00780 src_nodes[i] = j; 00781 f_src=true; 00782 } 00783 if(!f_dst && dst_nodes[i]==indexes_nodes[j]) 00784 { 00785 dst_nodes[i] = j; 00786 f_dst=true; 00787 } 00788 } 00789 } 00790 //re-order src_nodes and dst_nodes to get growing src_nodes 00791 //usefull to get the local data structure with good output edges values 00792 unsigned int * old_src_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 00793 unsigned int * old_dst_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 00794 for(unsigned int i=0;i<dim_edge;i++) 00795 { 00796 old_src_nodes[i]=src_nodes[i]; 00797 old_dst_nodes[i]=dst_nodes[i]; 00798 } 00799 bool modif=true; 00800 while(modif) 00801 { 00802 modif=false; 00803 for(unsigned int i=1;i<dim_edge;i++) 00804 { 00805 if(src_nodes[i]<src_nodes[i-1]) 00806 { 00807 unsigned int s = src_nodes[i]; 00808 unsigned int d = dst_nodes[i]; 00809 src_nodes[i] = src_nodes[i-1]; 00810 src_nodes[i-1] = s; 00811 dst_nodes[i] = dst_nodes[i-1]; 00812 dst_nodes[i-1] = d; 00813 modif=true; 00814 } 00815 } 00816 } 00817 //change indexes_edges with this new order of src_nodes and dst_nodes 00818 unsigned int * new_indexes_edges = (unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 00819 for(unsigned int i=0;i<dim_edge;i++) 00820 { 00821 for(unsigned int j=0;j<dim_edge;j++) 00822 { 00823 if(src_nodes[i]==old_src_nodes[j] && dst_nodes[i]==old_dst_nodes[j]) 00824 { 00825 new_indexes_edges[i] = indexes_edges[j]; 00826 } 00827 } 00828 } 00829 00830 free(old_src_nodes);free(old_dst_nodes); 00831 free(indexes_edges); 00832 indexes_edges=new_indexes_edges; 00833 00834 } 00835 //------------------------------------------------------------------------------- 00836 //! Fill the local data structure DDAG_impl 00837 /*! 00838 \param b is the number of blocks in the global DAG_impl 00839 \param dim_edge_g number of edges in the global DAG_impl 00840 \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl 00841 \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl 00842 \param edge_block is the cumulative degrees for the number of edges in each block of sister edges 00843 \param taken is the table to note which block is assigned to which processor 00844 \param degcum_out_t is a temporary equivalent of degcum_out to keep the pure local version 00845 \param degcum_in_t is a temporary equivalent of degcum_in to keep the pure local version 00846 \param edges_t_out is a temporary equivalent of edges_out to keep the pure local version 00847 \param edges_t_in is a temporary equivalent of edges_in to keep the pure local version 00848 \param neigh_out_t is a temporary equivalent of neigh_out to keep the pure local version 00849 \param neigh_in_t is a temporary equivalent of neigh_in to keep the pure local version 00850 \param roots_g is the list of roots in the global DAG_impl 00851 \param leafs_g is the list of leafs in the global DAG_impl 00852 \param dim_roots_g is the number of roots in the global DAG_impl 00853 \param dim_leafs_g is the number of leafs in the global DAG_impl 00854 */ 00855 //------------------------------------------------------------------------------- 00856 void fillLocalDS(unsigned int b, unsigned int dim_edge_g,unsigned int *dst_nodes_g,unsigned int *src_nodes_g,unsigned int *edge_block,unsigned int *taken, 00857 unsigned int *degcum_out_t,unsigned int *degcum_in_t,unsigned int *edges_t_out,unsigned int *edges_t_in,unsigned int *neigh_out_t,unsigned int *neigh_in_t, 00858 unsigned int *roots_g,unsigned int *leafs_g,unsigned int dim_roots_g,unsigned int dim_leafs_g) 00859 //------------------------------------------------------------------------------- 00860 { 00861 /* 00862 for each node of the local data structure an analysis of communications needed is made 00863 00864 1) search in all the global edges that are not taken by the currant processor if the node is found. In this case it represents an edge and a node to receive from another processor. 00865 a) fill degcum_tor edges_tor and nodes_tor with in and out communications to receive 00866 b) remember those communications in tor_out and tor_in and stor_out stor_in to modify local data structures 00867 c) remember the processors connected to complete the point 2) 00868 2) search in the local edges if the node is found. In this case it represents an edge and a node to send to another processor. 00869 a) fill degcum_tos edges_tos and nodes_tos helping with 1-c 00870 b) distinguish communication nodes from pure local nodes 00871 3) get the good order of edges for input edges 00872 4) modify local data structure degcum_out,degcum_in,neigh_out,neigh_in,edges_out and edges_in with communications 00873 5) change indexation taking into acount communication and pure local nodes of 2-b 00874 00875 After that the new indexation can be applied to all local data structure 00876 */ 00877 00878 //indexes_nodes and indexes_edges has been filled for local elements 00879 //from dim_edge and dim_node to get new indexes for communicated elements 00880 dim_ind_ed=dim_edge; 00881 dim_ind_no=dim_node; 00882 //to note the nodes with comunication in order to change indexation after 00883 unsigned int * comm_nodes = (unsigned int *)calloc(dim_comm,sizeof(unsigned int)); 00884 unsigned int * loc_nodes = (unsigned int *)calloc(dim_loc,sizeof(unsigned int)); 00885 00886 //foreach node of the local structure 00887 for(unsigned int i=0;i<dim_node;i++) 00888 { 00889 //tables to receive out and in (edges) 00890 unsigned int stor_out=0; 00891 unsigned int * tor_out = (unsigned int *)calloc(stor_out,sizeof(unsigned int)); 00892 unsigned int stor_in=0; 00893 unsigned int * tor_in = (unsigned int *)calloc(stor_in,sizeof(unsigned int)); 00894 //tables to send out and in (edges) 00895 unsigned int stos_out=0; 00896 unsigned int stos_in=0; 00897 unsigned int nb_proc=0; 00898 //unsigned int nb_proc_out=0; 00899 unsigned int * procs = (unsigned int *)calloc(nb_proc,sizeof(unsigned int)); 00900 //unsigned int * procs_out = (unsigned int *)calloc(nb_proc_out,sizeof(unsigned int)); 00901 //look at all edges in the global structure 00902 for(unsigned int j=0;j<dim_edge_g;j++) 00903 { 00904 unsigned int block = 0; 00905 //if the node is found in an edges 00906 if(indexes_nodes[i]==dst_nodes_g[j] || indexes_nodes[i]==src_nodes_g[j]) 00907 { 00908 //which block is associated to this edge 00909 for(unsigned int k=1;k<b+1;k++) 00910 { 00911 if(j>=edge_block[k-1] && j<edge_block[k]) 00912 { 00913 block=k-1; 00914 k=b+1; 00915 } 00916 } 00917 //if the edge is not one of the current node then communications modifications are needed 00918 //to receive informations 00919 if(taken[block]-1!=Mpi_::mpi_rank) 00920 { 00921 //if the proc has not been noticed before in procs, add it 00922 unsigned int t; 00923 if(!find_position(procs,nb_proc,taken[block]-1,t)) 00924 { 00925 nb_proc++; 00926 procs = (unsigned int *)realloc(procs,nb_proc*sizeof(unsigned int)); 00927 procs[nb_proc-1]=taken[block]-1; 00928 } 00929 00930 //receive an element that goes out of this node 00931 if(indexes_nodes[i]==src_nodes_g[j]) 00932 { 00933 //to receive 00934 stor_out++; 00935 tor_out = (unsigned int *)realloc(tor_out,stor_out*sizeof(unsigned int)); 00936 tor_out[stor_out-1] = j; 00937 00938 //construction of degcum_tor,degcum_tos (simple modification of values) 00939 for(unsigned int k=taken[block];k<Mpi_::mpi_nb+1;k++) 00940 { 00941 degcum_tor[k]++; 00942 degcum_tor_out[k]++; 00943 } 00944 //construction of edges_tor,edges_tos,nodes_tor,nodes_tos (reallocation of new tables) 00945 //unsigned int *edges_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int)); 00946 unsigned int *edges_tor_out_new = (unsigned int *)calloc(degcum_tor_out[Mpi_::mpi_nb],sizeof(unsigned int)); 00947 unsigned int *nodes_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int)); 00948 //values 00949 //for processors before this one simply make a copy of values 00950 for(unsigned int k=0;k<taken[block]-1;k++) 00951 { 00952 for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++) 00953 nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l]; 00954 for(unsigned int l=0;l<degcum_tor_out[k+1]-degcum_tor_out[k];l++) 00955 edges_tor_out_new[degcum_tor_out[k]+l] = edges_tor_out[degcum_tor_out[k]+l]; 00956 } 00957 //for this processor add the new value 00958 for(unsigned int l=0;l<degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1;l++) 00959 nodes_tor_new[degcum_tor[taken[block]-1]+l] = nodes_tor[degcum_tor[taken[block]-1]+l]; 00960 for(unsigned int l=0;l<degcum_tor_out[taken[block]]-degcum_tor_out[taken[block]-1]-1;l++) 00961 edges_tor_out_new[degcum_tor_out[taken[block]-1]+l] = edges_tor_out[degcum_tor_out[taken[block]-1]+l]; 00962 //add the new value 00963 unsigned int last_tor = degcum_tor[taken[block]-1]+degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1; 00964 nodes_tor_new[last_tor] = dst_nodes_g[j]; 00965 last_tor = degcum_tor_out[taken[block]-1]+degcum_tor_out[taken[block]]-degcum_tor_out[taken[block]-1]-1; 00966 edges_tor_out_new[last_tor] = j; 00967 //for the next processors copy values at a position +1 00968 for(unsigned int k=taken[block];k<Mpi_::mpi_nb;k++) 00969 { 00970 for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++) 00971 { 00972 //edges_tor_new[degcum_tor[k]+l] = edges_tor[degcum_tor[k]+l-1]; 00973 nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l-1]; 00974 } 00975 for(unsigned int l=0;l<degcum_tor_out[k+1]-degcum_tor_out[k];l++) 00976 edges_tor_out_new[degcum_tor_out[k]+l] = edges_tor_out[degcum_tor_out[k]+l-1]; 00977 } 00978 00979 /*free(edges_tor);*/free(nodes_tor); 00980 /*edges_tor = edges_tor_new;*/ nodes_tor = nodes_tor_new; 00981 free(edges_tor_out); 00982 edges_tor_out = edges_tor_out_new; 00983 } 00984 //receive an element that goes in of this node 00985 if(indexes_nodes[i]==dst_nodes_g[j]) 00986 { 00987 //to receive 00988 stor_in++; 00989 tor_in = (unsigned int *)realloc(tor_in,stor_in*sizeof(unsigned int)); 00990 tor_in[stor_in-1] = j; 00991 00992 //construction of degcum_tor,degcum_tos (simple modification of values) 00993 for(unsigned int k=taken[block];k<Mpi_::mpi_nb+1;k++) 00994 { 00995 degcum_tor[k]++; 00996 degcum_tor_in[k]++; 00997 } 00998 //construction of edges_tor,edges_tos,nodes_tor,nodes_tos (reallocation of new tables) 00999 //unsigned int *edges_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int)); 01000 unsigned int *edges_tor_in_new = (unsigned int *)calloc(degcum_tor_in[Mpi_::mpi_nb],sizeof(unsigned int)); 01001 unsigned int *nodes_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int)); 01002 //values 01003 //for processors before this one simply make a copy of values 01004 for(unsigned int k=0;k<taken[block]-1;k++) 01005 { 01006 for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++) 01007 { 01008 //edges_tor_new[degcum_tor[k]+l] = edges_tor[degcum_tor[k]+l]; 01009 nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l]; 01010 } 01011 for(unsigned int l=0;l<degcum_tor_in[k+1]-degcum_tor_in[k];l++) 01012 edges_tor_in_new[degcum_tor_in[k]+l] = edges_tor_in[degcum_tor_in[k]+l]; 01013 } 01014 //for this processor add the new value 01015 for(unsigned int l=0;l<degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1;l++) 01016 { 01017 //edges_tor_new[degcum_tor[taken[block]-1]+l] = edges_tor[degcum_tor[taken[block]-1]+l]; 01018 nodes_tor_new[degcum_tor[taken[block]-1]+l] = nodes_tor[degcum_tor[taken[block]-1]+l]; 01019 } 01020 for(unsigned int l=0;l<degcum_tor_in[taken[block]]-degcum_tor_in[taken[block]-1]-1;l++) 01021 edges_tor_in_new[degcum_tor_in[taken[block]-1]+l] = edges_tor_in[degcum_tor_in[taken[block]-1]+l]; 01022 //add the new value 01023 unsigned int last_tor = degcum_tor[taken[block]-1]+degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1; 01024 nodes_tor_new[last_tor] = src_nodes_g[j]; 01025 last_tor = degcum_tor_in[taken[block]-1]+degcum_tor_in[taken[block]]-degcum_tor_in[taken[block]-1]-1; 01026 edges_tor_in_new[last_tor] = j; 01027 //for the next processors copy values at a position +1 01028 for(unsigned int k=taken[block];k<Mpi_::mpi_nb;k++) 01029 { 01030 for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++) 01031 { 01032 //edges_tor_new[degcum_tor[k]+l] = edges_tor[degcum_tor[k]+l-1]; 01033 nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l-1]; 01034 } 01035 for(unsigned int l=0;l<degcum_tor_in[k+1]-degcum_tor_in[k];l++) 01036 edges_tor_in_new[degcum_tor_in[k]+l] = edges_tor_in[degcum_tor_in[k]+l-1]; 01037 } 01038 01039 /*free(edges_tor);*/free(nodes_tor); 01040 /*edges_tor = edges_tor_new;*/ nodes_tor = nodes_tor_new; 01041 free(edges_tor_in); 01042 edges_tor_in = edges_tor_in_new; 01043 } 01044 } 01045 } 01046 } 01047 //sending informations 01048 if(nb_proc>0) 01049 { 01050 bool ro = find_position(roots_g,dim_roots_g,indexes_nodes[i]); 01051 bool le = find_position(leafs_g,dim_leafs_g,indexes_nodes[i]); 01052 if(!ro && !le) 01053 { 01054 //communication node 01055 dim_comm++; 01056 comm_nodes = (unsigned int *)realloc(comm_nodes,dim_comm*sizeof(unsigned int)); 01057 //current local indexation noted 01058 comm_nodes[dim_comm-1] = i; 01059 } 01060 01061 //sort procs 01062 bool mod=true; 01063 while(mod) 01064 { 01065 mod=false; 01066 for(unsigned int j=1;j<nb_proc;j++) 01067 { 01068 if(procs[j]<procs[j-1]) 01069 { 01070 unsigned int t = procs[j]; 01071 procs[j] = procs[j-1]; 01072 procs[j-1] = t; 01073 mod=true; 01074 } 01075 } 01076 } 01077 for(unsigned int j=0;j<dim_edge;j++) 01078 { 01079 //send an element that is out of another processor 01080 if(i==dst_nodes[j] || i==src_nodes[j]) 01081 { 01082 //Needed for communications in advanced DPMap with pointers 01083 if(i==dst_nodes[j]) 01084 stos_out+=nb_proc; 01085 else if(i==src_nodes[j]) 01086 stos_in+=nb_proc; 01087 01088 //construction of degcum_tor,degcum_tos (simple modification of values) 01089 for(unsigned int p=0;p<nb_proc;p++) 01090 { 01091 for(unsigned int k=procs[p]+1;k<Mpi_::mpi_nb+1;k++) 01092 { 01093 degcum_tos[k]++; 01094 if(i==dst_nodes[j]) 01095 degcum_tos_out[k]++; 01096 else if(i==src_nodes[j]) 01097 degcum_tos_in[k]++; 01098 } 01099 01100 //construction of edges_tor,edges_tos,nodes_tor,nodes_tos (reallocation of new tables) 01101 //unsigned int *edges_tos_new = (unsigned int *)calloc(degcum_tos[Mpi_::mpi_nb],sizeof(unsigned int)); 01102 unsigned int *edges_tos_in_new; unsigned int *edges_tos_out_new; 01103 if(i==src_nodes[j]) 01104 edges_tos_in_new = (unsigned int *)calloc(degcum_tos_in[Mpi_::mpi_nb],sizeof(unsigned int)); 01105 else if(i==dst_nodes[j]) 01106 edges_tos_out_new = (unsigned int *)calloc(degcum_tos_out[Mpi_::mpi_nb],sizeof(unsigned int)); 01107 unsigned int *nodes_tos_new = (unsigned int *)calloc(degcum_tos[Mpi_::mpi_nb],sizeof(unsigned int)); 01108 //values 01109 //for processors before this one simply make a copy of values 01110 for(unsigned int k=0;k<procs[p];k++) 01111 { 01112 for(unsigned int l=0;l<degcum_tos[k+1]-degcum_tos[k];l++) 01113 nodes_tos_new[degcum_tos[k]+l] = nodes_tos[degcum_tos[k]+l]; 01114 if(i==src_nodes[j]) 01115 { 01116 for(unsigned int l=0;l<degcum_tos_in[k+1]-degcum_tos_in[k];l++) 01117 edges_tos_in_new[degcum_tos_in[k]+l] = edges_tos_in[degcum_tos_in[k]+l]; 01118 } 01119 else if(i==dst_nodes[j]) 01120 { 01121 for(unsigned int l=0;l<degcum_tos_out[k+1]-degcum_tos_out[k];l++) 01122 edges_tos_out_new[degcum_tos_out[k]+l] = edges_tos_out[degcum_tos_out[k]+l]; 01123 } 01124 } 01125 //for this processor add the precedent values and the new value 01126 for(unsigned int l=0;l<degcum_tos[procs[p]+1]-degcum_tos[procs[p]]-1;l++) 01127 nodes_tos_new[degcum_tos[procs[p]]+l] = nodes_tos[degcum_tos[procs[p]]+l]; 01128 if(i==src_nodes[j]) 01129 { 01130 for(unsigned int l=0;l<degcum_tos_in[procs[p]+1]-degcum_tos_in[procs[p]]-1;l++) 01131 edges_tos_in_new[degcum_tos_in[procs[p]]+l] = edges_tos_in[degcum_tos_in[procs[p]]+l]; 01132 } 01133 else if(i==dst_nodes[j]) 01134 { 01135 for(unsigned int l=0;l<degcum_tos_out[procs[p]+1]-degcum_tos_out[procs[p]]-1;l++) 01136 edges_tos_out_new[degcum_tos_out[procs[p]]+l] = edges_tos_out[degcum_tos_out[procs[p]]+l]; 01137 } 01138 //add the new value 01139 unsigned int last_tos = degcum_tos[procs[p]+1]-1; 01140 if(i==dst_nodes[j]) 01141 nodes_tos_new[last_tos] = src_nodes[j]; 01142 else if(i==src_nodes[j]) 01143 nodes_tos_new[last_tos] = dst_nodes[j]; 01144 //edges_tos_new[last_tos] = j; 01145 if(i==src_nodes[j]) 01146 { 01147 last_tos = degcum_tos_in[procs[p]+1]-1; 01148 edges_tos_in_new[last_tos] = j; 01149 } 01150 else if(i==dst_nodes[j]) 01151 { 01152 last_tos = degcum_tos_out[procs[p]+1]-1; 01153 edges_tos_out_new[last_tos] = j; 01154 } 01155 01156 //for the next processors copy values at a position +1 01157 for(unsigned int k=procs[p]+1;k<Mpi_::mpi_nb;k++) 01158 { 01159 for(unsigned int l=0;l<degcum_tos[k+1]-degcum_tos[k];l++) 01160 { 01161 //edges_tos_new[degcum_tos[k]+l] = edges_tos[degcum_tos[k]+l-1]; 01162 nodes_tos_new[degcum_tos[k]+l] = nodes_tos[degcum_tos[k]+l-1]; 01163 } 01164 if(i==src_nodes[j]) 01165 { 01166 for(unsigned int l=0;l<degcum_tos_in[k+1]-degcum_tos_in[k];l++) 01167 edges_tos_in_new[degcum_tos_in[k]+l] = edges_tos_in[degcum_tos_in[k]+l-1]; 01168 } 01169 else if(i==dst_nodes[j]) 01170 { 01171 for(unsigned int l=0;l<degcum_tos_out[k+1]-degcum_tos_out[k];l++) 01172 edges_tos_out_new[degcum_tos_out[k]+l] = edges_tos_out[degcum_tos_out[k]+l-1]; 01173 } 01174 } 01175 01176 /*free(edges_tos);*/free(nodes_tos); 01177 /*edges_tos = edges_tos_new;*/ nodes_tos = nodes_tos_new; 01178 if(i==src_nodes[j]) 01179 { 01180 free(edges_tos_in); 01181 edges_tos_in = edges_tos_in_new; 01182 } 01183 else if(i==dst_nodes[j]) 01184 { 01185 free(edges_tos_out); 01186 edges_tos_out = edges_tos_out_new; 01187 } 01188 } 01189 } 01190 } 01191 } 01192 else 01193 { 01194 bool ro = find_position(roots_g,dim_roots_g,indexes_nodes[i]); 01195 bool le = find_position(leafs_g,dim_leafs_g,indexes_nodes[i]); 01196 if(!ro && !le) 01197 { 01198 dim_loc++; 01199 loc_nodes = (unsigned int *)realloc(loc_nodes,dim_loc*sizeof(unsigned int)); 01200 //current local indexation noted 01201 loc_nodes[dim_loc-1] = i; 01202 } 01203 } 01204 free(procs); 01205 01206 //edges_t_in 01207 //edges_t_out is from 0 to dim_edge but with new indexation edges_t_in can't be so simple and has to be changed 01208 //for each node find in all local edges the node as destination 01209 unsigned int pl=0; 01210 for(unsigned int j=0;j<dim_edge;j++) 01211 { 01212 if(i==dst_nodes[j]) 01213 { 01214 edges_t_in[degcum_in_t[i]+pl]=j; 01215 pl++; 01216 } 01217 } 01218 01219 //for this node modify degcum_out,degcum_in,neigh_out,neigh_in,edges_out and edges_in 01220 for(unsigned int j=i+1;j<dim_node+1;j++) 01221 { 01222 degcum_out[j]+=stor_out; 01223 degcum_in[j]+=stor_in; 01224 } 01225 01226 dim_tor_out+=stor_out; 01227 dim_tor_in+=stor_in; 01228 dim_tos_out+=stos_out; 01229 dim_tos_in+=stos_in; 01230 01231 //for the current node, modify neigh_out/neigh_in/edges_out/edges_in and indexes_nodes/indexes_edges 01232 neigh_out = (unsigned int *)realloc(neigh_out,degcum_out[i+1]*sizeof(unsigned int)); 01233 neigh_in = (unsigned int *)realloc(neigh_in,degcum_in[i+1]*sizeof(unsigned int)); 01234 edges_out = (unsigned int *)realloc(edges_out,degcum_out[i+1]*sizeof(unsigned int)); 01235 edges_in = (unsigned int *)realloc(edges_in,degcum_in[i+1]*sizeof(unsigned int)); 01236 01237 //these varaibles are used to not hav multiple times the same value in indexes tables and to count the number of elements to add in indexes 01238 unsigned int ind_ed=0; 01239 unsigned int ind_no=0; 01240 //add new elements first for the current node 01241 //in elements to receive 01242 for(unsigned int j=0;j<stor_in;j++) 01243 { 01244 //change the size of indexes tables 01245 indexes_nodes = (unsigned int *)realloc(indexes_nodes,(dim_ind_no+ind_no+1)*sizeof(unsigned int)); 01246 indexes_edges = (unsigned int *)realloc(indexes_edges,(dim_ind_ed+ind_ed+1)*sizeof(unsigned int)); 01247 01248 //for edges 01249 //if the index is not already stored add it to indexes when modifying neigh and edges 01250 unsigned int position; 01251 bool found = find_position(indexes_edges,dim_ind_ed+ind_ed,tor_in[j],position); 01252 if(!found) 01253 { 01254 //edges_in[degcum_in[i]+j]=dim_ind_ed+ind_ed; 01255 edges_in[degcum_in[i]+j]=dim_ind_ed+ind_ed; 01256 indexes_edges[dim_ind_ed+ind_ed]=tor_in[j]; 01257 ind_ed++; 01258 } 01259 //else use the existing position value 01260 else 01261 edges_in[degcum_in[i]+j]=position; 01262 //same for nodes 01263 found = find_position(indexes_nodes,dim_ind_no+ind_no,src_nodes_g[tor_in[j]],position); 01264 if(!found) 01265 { 01266 neigh_in[degcum_in[i]+j]=dim_ind_no+ind_no; 01267 indexes_nodes[dim_ind_no+ind_no]=src_nodes_g[tor_in[j]]; 01268 ind_no++; 01269 } 01270 else 01271 neigh_in[degcum_in[i]+j]=position; 01272 } 01273 //out elements to receive 01274 dim_ind_no+=ind_no; 01275 dim_ind_ed+=ind_ed; 01276 ind_no=0; 01277 ind_ed=0; 01278 for(unsigned int j=0;j<stor_out;j++) 01279 { 01280 //change the size of indexes tables 01281 indexes_nodes = (unsigned int *)realloc(indexes_nodes,(dim_ind_no+ind_no+1)*sizeof(unsigned int)); 01282 indexes_edges = (unsigned int *)realloc(indexes_edges,(dim_ind_ed+ind_ed+1)*sizeof(unsigned int)); 01283 01284 //for edges 01285 //if the index is not already stored add it to indexes when modifying neigh and edges 01286 unsigned int position; 01287 bool found = find_position(indexes_edges,dim_ind_ed+ind_ed,tor_out[j],position); 01288 if(!found) 01289 { 01290 edges_out[degcum_out[i]+j]=dim_ind_ed+ind_ed; 01291 indexes_edges[dim_ind_ed+ind_ed]=tor_out[j]; 01292 ind_ed++; 01293 } 01294 //else use existing position 01295 else 01296 edges_out[degcum_out[i]+j]=position; 01297 //for nodes 01298 found = find_position(indexes_nodes,dim_ind_no+ind_no,dst_nodes_g[tor_out[j]],position); 01299 if(!found) 01300 { 01301 neigh_out[degcum_out[i]+j]=dim_ind_no+ind_no; 01302 indexes_nodes[dim_ind_no+ind_no]=dst_nodes_g[tor_out[j]]; 01303 ind_no++; 01304 } 01305 else 01306 neigh_out[degcum_out[i]+j]=position; 01307 } 01308 dim_ind_no+=ind_no; 01309 dim_ind_ed+=ind_ed; 01310 //then add local elements for the current node in neigh and edges 01311 for(unsigned int j=0;j<degcum_out_t[i+1]-degcum_out_t[i];j++) 01312 { 01313 edges_out[degcum_out[i]+stor_out+j]=edges_t_out[degcum_out_t[i]+j]; 01314 neigh_out[degcum_out[i]+stor_out+j]=neigh_out_t[degcum_out_t[i]+j]; 01315 } 01316 for(unsigned int j=0;j<degcum_in_t[i+1]-degcum_in_t[i];j++) 01317 { 01318 edges_in[degcum_in[i]+stor_in+j]=edges_t_in[degcum_in_t[i]+j]; 01319 neigh_in[degcum_in[i]+stor_in+j]=neigh_in_t[degcum_in_t[i]+j]; 01320 } 01321 01322 free(tor_out);free(tor_in); 01323 } 01324 01325 //change indexation of nodes with communication and local nodes 01326 //this is very usefull for a communication/computation time overlap 01327 unsigned int * new_indexes_nodes = (unsigned int *)calloc(dim_ind_no,sizeof(unsigned int)); 01328 unsigned int * old_new = (unsigned int *)calloc(dim_ind_no,sizeof(unsigned int)); 01329 unsigned int * new_old = (unsigned int *)calloc(dim_ind_no,sizeof(unsigned int)); 01330 //foreach old indexation value 01331 unsigned int count = dim_ind_no-1; 01332 for(unsigned int i=0;i<dim_ind_no-dim_node;i++) 01333 { 01334 new_indexes_nodes[count]=indexes_nodes[count]; 01335 old_new[count]=count; 01336 new_old[count]=count; 01337 count--; 01338 } 01339 for(unsigned int i=0;i<dim_leafs;i++) 01340 { 01341 new_indexes_nodes[count]=indexes_nodes[count]; 01342 old_new[count]=count; 01343 new_old[count]=count; 01344 count--; 01345 } 01346 for(unsigned int i=0;i<dim_roots;i++) 01347 { 01348 new_indexes_nodes[count]=indexes_nodes[count]; 01349 old_new[count]=count; 01350 new_old[count]=count; 01351 count--; 01352 } 01353 unsigned int ind=dim_comm-1; 01354 for(unsigned int i=0;i<dim_comm;i++) 01355 { 01356 new_indexes_nodes[count]=indexes_nodes[comm_nodes[ind]]; 01357 old_new[comm_nodes[ind]]=count; 01358 new_old[count]=comm_nodes[ind]; 01359 ind--; 01360 count--; 01361 } 01362 ind = dim_loc-1; 01363 for(unsigned int i=0;i<dim_loc;i++) 01364 { 01365 new_indexes_nodes[count]=indexes_nodes[loc_nodes[ind]]; 01366 old_new[loc_nodes[ind]]=count; 01367 new_old[count]=loc_nodes[ind]; 01368 ind--; 01369 count--; 01370 } 01371 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" rcv = "<<dim_ind_no-dim_node<<std::endl; 01372 std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_leafs = "<<dim_leafs<<std::endl; 01373 std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_roots = "<<dim_roots<<std::endl; 01374 std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_comm = "<<dim_comm<<std::endl; 01375 std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_loc = "<<dim_loc<<std::endl;*/ 01376 01377 //delete old indexation 01378 free(indexes_nodes); 01379 indexes_nodes = new_indexes_nodes; 01380 01381 //change values in data structures using old_new (only nodes concerned to to send values) 01382 for (int i=0;i<dim_edge;i++) 01383 src_nodes[i]=old_new[src_nodes[i]]; 01384 for (int i=0;i<dim_edge;i++) 01385 dst_nodes[i]=old_new[dst_nodes[i]]; 01386 for (int i=0;i<dim_tos_out+dim_tos_in;i++) 01387 nodes_tos[i]=old_new[nodes_tos[i]]; 01388 //for degcum_out/degcum_in/neigh_out/neigh_in/edges_out/edges_in a little more dificult as it is cumulative 01389 unsigned int *new_degcum_out = (unsigned int *)calloc(dim_node+1,sizeof(unsigned int)); 01390 unsigned int *new_degcum_in = (unsigned int *)calloc(dim_node+1,sizeof(unsigned int)); 01391 unsigned int *new_neigh_out = (unsigned int *)calloc(dim_edge+dim_tor_out,sizeof(unsigned int)); 01392 unsigned int *new_neigh_in = (unsigned int *)calloc(dim_edge+dim_tor_in,sizeof(unsigned int)); 01393 unsigned int *new_edges_out = (unsigned int *)calloc(dim_edge+dim_tor_out,sizeof(unsigned int)); 01394 unsigned int *new_edges_in = (unsigned int *)calloc(dim_edge+dim_tor_in,sizeof(unsigned int)); 01395 for(unsigned int i=1;i<dim_node+1;i++) 01396 { 01397 new_degcum_out[i]=new_degcum_out[i-1]+(degcum_out[new_old[i-1]+1]-degcum_out[new_old[i-1]]); 01398 new_degcum_in[i]=new_degcum_in[i-1]+(degcum_in[new_old[i-1]+1]-degcum_in[new_old[i-1]]); 01399 01400 unsigned int new_st = new_degcum_out[i-1]; 01401 unsigned int st = degcum_out[new_old[i-1]]; 01402 for(unsigned int j=0;j<new_degcum_out[i]-new_degcum_out[i-1];j++) 01403 { 01404 new_neigh_out[new_st+j]=old_new[neigh_out[st+j]]; 01405 new_edges_out[new_st+j]=edges_out[st+j]; 01406 } 01407 new_st = new_degcum_in[i-1]; 01408 st = degcum_in[new_old[i-1]]; 01409 for(unsigned int j=0;j<new_degcum_in[i]-new_degcum_in[i-1];j++) 01410 { 01411 new_neigh_in[new_st+j]=old_new[neigh_in[st+j]]; 01412 new_edges_in[new_st+j]=edges_in[st+j]; 01413 } 01414 } 01415 01416 //put local indexes in nodes_tor and edges_tor (global values) 01417 for(unsigned int i=0;i<dim_tor_out;i++) 01418 { 01419 for(unsigned int j=0;j<dim_ind_no;j++) 01420 { 01421 if(indexes_nodes[j]==nodes_tor[i]) 01422 { 01423 nodes_tor[i] = j; 01424 break; 01425 } 01426 } 01427 for(unsigned int j=0;j<dim_ind_ed;j++) 01428 { 01429 if(indexes_edges[j]==edges_tor_out[i]) 01430 { 01431 edges_tor_out[i] = j; 01432 break; 01433 } 01434 } 01435 } 01436 for(unsigned int i=0;i<dim_tor_in;i++) 01437 { 01438 for(unsigned int j=0;j<dim_ind_no;j++) 01439 { 01440 if(indexes_nodes[j]==nodes_tor[dim_tor_out+i]) 01441 { 01442 nodes_tor[dim_tor_out+i] = j; 01443 break; 01444 } 01445 } 01446 for(unsigned int j=0;j<dim_ind_ed;j++) 01447 { 01448 if(indexes_edges[j]==edges_tor_in[i]) 01449 { 01450 edges_tor_in[i] = j; 01451 break; 01452 } 01453 } 01454 } 01455 01456 01457 01458 free(degcum_out);free(degcum_in);free(neigh_out);free(neigh_in);free(edges_out);free(edges_in); 01459 degcum_out=new_degcum_out; degcum_in = new_degcum_in; 01460 neigh_out = new_neigh_out; neigh_in=new_neigh_in; 01461 edges_out=new_edges_out; edges_in=new_edges_in; 01462 01463 free(old_new);free(new_old); 01464 free(loc_nodes);free(comm_nodes); 01465 } 01466 //------------------------------------------------------------------------------- 01467 //! Distribution 01468 /*! 01469 Read the input file, construct the global data structure, make the distribution and fill the local data structure 01470 \param file is the path to the .dot input file 01471 */ 01472 //------------------------------------------------------------------------------- 01473 void distribute(const char * file) 01474 //------------------------------------------------------------------------------- 01475 { 01476 unsigned int dim_node_g,dim_edge_g; 01477 unsigned int *src_nodes_g, *dst_nodes_g; 01478 unsigned int *degcum_out_g, *degcum_in_g; 01479 unsigned int *neigh_out_g, *neigh_in_g; 01480 unsigned int * edges_g; 01481 unsigned int b=0;//number of blocks 01482 unsigned int * edge_block, *degcum_block, *linked_blocks, *edges_subtree; 01483 01484 //-------------------------------------------------------------------------------- 01485 //construction of src_nodes, dst_nodes, dim_node, dim_edge from dot file 01486 //for each line of type "unsigned int -> unsigned int ;" it is an edge of the DAG. 01487 //incrementation of dim_edge and of dim_node 01488 //-------------------------------------------------------------------------------- 01489 dim_edge_g=0; 01490 dim_node_g=0; 01491 src_nodes_g=(unsigned int *)calloc(1,sizeof(unsigned int)); 01492 dst_nodes_g=(unsigned int *)calloc(1,sizeof(unsigned int)); 01493 read(file,dim_node_g,dim_edge_g,src_nodes_g,dst_nodes_g); 01494 dim_node_g++; 01495 //-------------------------------------------------------------------------------- 01496 //Identify roots and leafs of the DAG 01497 //-------------------------------------------------------------------------------- 01498 unsigned int * roots_g = (unsigned int *)calloc(0,sizeof(unsigned int)); 01499 unsigned int * leafs_g = (unsigned int *)calloc(0,sizeof(unsigned int)); 01500 unsigned int dim_roots_g=0; 01501 unsigned int dim_leafs_g=0; 01502 findRootsLeafs(dim_node_g, dim_edge_g, src_nodes_g, dst_nodes_g, dim_roots_g, dim_leafs_g, roots_g, leafs_g); 01503 //-------------------------------------------------------------------------------- 01504 //Global data structure creation + edge_block 01505 //-------------------------------------------------------------------------------- 01506 unsigned int mean_edges = 0; 01507 unsigned int max_edges = 0; 01508 edge_block = (unsigned int *)calloc(0,sizeof(unsigned int)); 01509 globalDS(dim_edge_g,dim_node_g,src_nodes_g,dst_nodes_g,degcum_in_g,degcum_out_g,neigh_out_g,neigh_in_g,edges_g,edge_block,mean_edges,max_edges,b); 01510 //-------------------------------------------------------------------------------- 01511 //Prepare data for distribution : degcum_block and linked_blocks and edges_subtree 01512 //-------------------------------------------------------------------------------- 01513 degcum_block = (unsigned int *)calloc(b+1,sizeof(unsigned int)); 01514 linked_blocks = (unsigned int *)calloc(1,sizeof(unsigned int)); 01515 edges_subtree = (unsigned int *)calloc(b,sizeof(unsigned int)); 01516 dataDistr(b,edges_g,edge_block,dst_nodes_g,degcum_out_g,degcum_block,linked_blocks,edges_subtree); 01517 //-------------------------------------------------------------------------------- 01518 //DISTRIBUTION 01519 //-------------------------------------------------------------------------------- 01520 /* 01521 The algorithm works this way : 01522 =TODO= ideal is the ideal number of edges needed per each processor for a perfect distribution 01523 =TODO= edges of the DAG can be ponderate by a weight, the ideal number take into acount this weight 01524 Edges are not managed independently. All sister edges are together in a block, and each is gonna be distribute amoung processors (table taken) 01525 All edges of a block are taken by a same processor 01526 1) foreach block (this is a sort of queue of blocks to deal with) - each time we reach this point the end of a subtree has been reached or we make the distribution for another processor 01527 2) try to get the new block 01528 3) if the new block is the first one, check if a brother block is not isolated or take it 01529 4) construct the list of outpt blocks and enter the recursive distribution call dist(...) 01530 5) When you get out of this recursive call it is because the ideal number has been reached for the processor or because the end of the subtree has been reached for this block 01531 */ 01532 //table to know if a block is taken by a processor 01533 unsigned int *taken = (unsigned int *)calloc(b,sizeof(unsigned int)); 01534 //to count the current number of edges taken 01535 unsigned int count=0; 01536 //the ideal number of edges to take 01537 unsigned int ideal = static_cast<unsigned int>(floor(dim_edge_g/Mpi_::mpi_nb)) +1; 01538 //std::cout<<"\nideal = "<<ideal<<"\n"; 01539 //total number of edges that are not taken 01540 unsigned int edges_r = dim_edge_g; 01541 //current processor 01542 int cur_proc=0; 01543 01544 for(unsigned int i=0;i<b;i++) 01545 { 01546 if(count<ideal) 01547 { 01548 if(taken[i]==0) 01549 { 01550 //new ideal value si calculated at each knew processor to manage 01551 if(count==0) 01552 ideal = static_cast<unsigned int>(floor(edges_r/(Mpi_::mpi_nb-cur_proc))); 01553 01554 if(count+edge_block[i+1]-edge_block[i]<=ideal) 01555 { 01556 count+=edge_block[i+1]-edge_block[i]; 01557 taken[i] = cur_proc+1; 01558 01559 if(count-(edge_block[i+1]-edge_block[i])==0) 01560 { 01561 //particular case only if count==0 before this node 01562 if(count<ideal && count+edge_block[i+2]-edge_block[i+1]<=ideal+mean_edges) 01563 { 01564 //we verify if the next block is not getting out of the current one 01565 bool found=false; 01566 for(unsigned int j=0;j<degcum_block[i+1]-degcum_block[i];j++) 01567 { 01568 if(linked_blocks[degcum_block[i]+j]==1) 01569 {found=true;break;} 01570 } 01571 //if the next block is not already taken and that it does not have any output block, we take it to not isolate it 01572 if(taken[i+1]==0 && found==false && degcum_block[i+2]==degcum_block[i+1]) 01573 { 01574 count+=edge_block[i+2]-edge_block[i+1]; 01575 taken[i+1]=cur_proc+1; 01576 } 01577 //if the next block is not already taken and that it does have a single output block 01578 else if(taken[i+1]==0 && found==false && degcum_block[i+2]==degcum_block[i+1]+1 && edges_subtree[linked_blocks[i+2]]==edge_block[i+2]-edge_block[i+1]) 01579 { 01580 count+=edge_block[i+2]-edge_block[i+1]; 01581 taken[i+1]=cur_proc+1; 01582 } 01583 } 01584 } 01585 if(count<ideal) 01586 { 01587 unsigned int size = degcum_block[i+1]-degcum_block[i]; 01588 unsigned int *edge_b_loc = (unsigned int *)calloc(size,sizeof(unsigned int)); 01589 unsigned int *index = (unsigned int *)calloc(size,sizeof(unsigned int)); 01590 01591 for(unsigned int j=0;j<size;j++) 01592 { 01593 index[j] = linked_blocks[degcum_block[i]+j]; 01594 edge_b_loc[j] = edge_block[index[j]+1]-edge_block[index[j]]; 01595 } 01596 //recursive call 01597 dist(mean_edges, edges_r,index,edge_b_loc,size,ideal,edge_block,degcum_block,linked_blocks,taken,edges_subtree,count,cur_proc); 01598 verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count); 01599 free(index); 01600 free(edge_b_loc); 01601 if(count>=ideal) 01602 { 01603 //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n"; 01604 if(cur_proc==Mpi_::mpi_rank) 01605 dim_edge = count; 01606 edges_r -= count; 01607 count = 0; 01608 cur_proc++; 01609 } 01610 } 01611 else 01612 { 01613 //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n"; 01614 if(cur_proc==Mpi_::mpi_rank) 01615 dim_edge = count; 01616 edges_r -= count; 01617 count = 0; 01618 cur_proc++; 01619 } 01620 } 01621 else 01622 { 01623 //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n"; 01624 if(cur_proc==Mpi_::mpi_rank) 01625 dim_edge = count; 01626 edges_r -= count; 01627 count = 0; 01628 cur_proc++; 01629 i=i-1; 01630 } 01631 } 01632 } 01633 else 01634 { 01635 //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n"; 01636 if(cur_proc==Mpi_::mpi_rank) 01637 dim_edge = count; 01638 edges_r -= count; 01639 count = 0; 01640 cur_proc++; 01641 } 01642 } 01643 /*std::cout<<std::endl; 01644 std::cout<<"Proc "<<Mpi_::mpi_rank<<" taken = "; 01645 for (int i=0;i<b;i++) 01646 std::cout<<taken[i]<<" "; 01647 std::cout<<std::endl;*/ 01648 01649 //-------------------------------------------------------------------------------- 01650 //FILL Parallel data structure 01651 //-------------------------------------------------------------------------------- 01652 //with taken, edge_block & edges_g we can construct the local data structure has done before for the global one 01653 //with degcum_block & linked_blocks we can get where communications are needed in the local data structure 01654 //-------------------------------------------------------------------------------- 01655 //local src_nodes & dst_nodes 01656 //-------------------------------------------------------------------------------- 01657 src_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01658 dst_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01659 indexes_edges = (unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01660 unsigned int * edges_t_out=(unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01661 unsigned int * edges_t_in=(unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01662 localSrcDstNodes(b,taken,edge_block,src_nodes_g,dst_nodes_g,edges_g,dim_roots_g,dim_leafs_g,roots_g,leafs_g/*,src_nodes,dst_nodes,indexes_edges,indexes_nodes,dim_edge,dim_node*/); 01663 //std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_node="<<dim_node<<std::endl; 01664 //-------------------------------------------------------------------------------- 01665 //free global and distribution tables 01666 //-------------------------------------------------------------------------------- 01667 free(degcum_out_g);free(degcum_in_g); 01668 free(neigh_out_g);free(neigh_in_g); 01669 free(edges_g); 01670 free(degcum_block);free(linked_blocks);free(edges_subtree); 01671 //-------------------------------------------------------------------------------- 01672 //construction of local degcum_out and degcum_in : 01673 //represents the cumulative number of inputs and outputs nodes and edges of a node 01674 //-------------------------------------------------------------------------------- 01675 unsigned int *deg_in2=(unsigned int *)calloc(dim_node,sizeof(unsigned int)); 01676 unsigned int *deg_out2=(unsigned int *)calloc(dim_node,sizeof(unsigned int)); 01677 for(unsigned int i=0;i<dim_edge;i++) 01678 { 01679 deg_out2[src_nodes[i]]++; 01680 deg_in2[dst_nodes[i]]++; 01681 } 01682 degcum_in=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int)); 01683 degcum_out=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int)); 01684 for(unsigned int i=1;i<dim_node+1;i++) 01685 { 01686 degcum_out[i]=degcum_out[i-1]+deg_out2[i-1]; 01687 degcum_in[i]=degcum_in[i-1]+deg_in2[i-1]; 01688 } 01689 free(deg_in2),free(deg_out2); 01690 //-------------------------------------------------------------------------------- 01691 //-------------------------------------------------------------------------------- 01692 //TEMPORARY DATA 01693 //-------------------------------------------------------------------------------- 01694 //degcum_in_t and degcum_out_t = degcum_in and degcum_out to keep the pure local values (without communications problems) 01695 //-------------------------------------------------------------------------------- 01696 unsigned int *degcum_in_t=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int)); 01697 unsigned int *degcum_out_t=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int)); 01698 for(unsigned int i=0;i<dim_node+1;i++) 01699 { 01700 degcum_in_t[i] = degcum_in[i]; 01701 degcum_out_t[i] = degcum_out[i]; 01702 } 01703 01704 //-------------------------------------------------------------------------------- 01705 //neigh_out_t and neigh_in_t and edges_t to keep the pure local values (without communications problems) 01706 //-------------------------------------------------------------------------------- 01707 unsigned int * t_in=(unsigned int *)calloc(dim_node,sizeof(unsigned int)); 01708 unsigned int * t_out=(unsigned int *)calloc(dim_node,sizeof(unsigned int)); 01709 01710 unsigned int * neigh_in_t=(unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01711 unsigned int * neigh_out_t=(unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01712 //unsigned int * edges_t_out=(unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01713 //unsigned int * edges_t_in=(unsigned int *)calloc(dim_edge,sizeof(unsigned int)); 01714 01715 for (int i=0;i<dim_edge;i++) 01716 { 01717 neigh_out_t[ degcum_out[src_nodes[i]] + t_out[ src_nodes[i] ]++ ]=dst_nodes[i]; 01718 neigh_in_t[ degcum_in[dst_nodes[i]] + t_in[ dst_nodes[i] ]++ ]=src_nodes[i]; 01719 edges_t_out[i]=i; 01720 //edges_t_in[i]=; 01721 } 01722 free(t_out),free(t_in); 01723 //-------------------------------------------------------------------------------- 01724 //-------------------------------------------------------------------------------- 01725 01726 //-------------------------------------------------------------------------------- 01727 //we have to add edges and nodes for parallelization and communications 01728 //to do that search root and leaf nodes of the local structure 01729 //found their direct (distance 1) neighbors in the global data structure 01730 //construct degcum_tos and degcum_tor and associated edges_tos, edges_tor, nodes_tos, nodes_tor 01731 //indexes of new elements have to be higher than local elements (at the end of every local data structure) 01732 //-------------------------------------------------------------------------------- 01733 neigh_out = (unsigned int *)calloc(0,sizeof(unsigned int)); 01734 neigh_in = (unsigned int *)calloc(0,sizeof(unsigned int)); 01735 edges_out = (unsigned int *)calloc(0,sizeof(unsigned int)); 01736 edges_in = (unsigned int *)calloc(0,sizeof(unsigned int)); 01737 //edges_tor = (unsigned int *)calloc(0,sizeof(unsigned int)); 01738 edges_tor_in = (unsigned int *)calloc(0,sizeof(unsigned int)); 01739 edges_tor_out = (unsigned int *)calloc(0,sizeof(unsigned int)); 01740 //edges_tos = (unsigned int *)calloc(0,sizeof(unsigned int)); 01741 edges_tos_in = (unsigned int *)calloc(0,sizeof(unsigned int)); 01742 edges_tos_out = (unsigned int *)calloc(0,sizeof(unsigned int)); 01743 nodes_tor = (unsigned int *)calloc(0,sizeof(unsigned int)); 01744 nodes_tos = (unsigned int *)calloc(0,sizeof(unsigned int)); 01745 fillLocalDS(b,dim_edge_g,dst_nodes_g,src_nodes_g,edge_block,taken,degcum_out_t,degcum_in_t,edges_t_out,edges_t_in,neigh_out_t,neigh_in_t,roots_g,leafs_g,dim_roots_g,dim_leafs_g); 01746 free(degcum_in_t);free(degcum_out_t); 01747 free(neigh_out_t);free(neigh_in_t);free(edges_t_out);free(edges_t_in); 01748 free(roots_g);free(leafs_g); 01749 free(edge_block); 01750 free(taken); 01751 free(src_nodes_g);free(dst_nodes_g); 01752 //--------------------------------------------------------- 01753 //PRINTINGS 01754 //--------------------------------------------------------- 01755 /*std::cout<<std::endl; 01756 std::cout<<"Proc "<<Mpi_::mpi_rank<<" src_nodes = "; 01757 for (int i=0;i<dim_edge;i++) 01758 std::cout<<src_nodes[i]<<" "; 01759 std::cout<<std::endl; 01760 std::cout<<"Proc "<<Mpi_::mpi_rank<<" dst_nodes = "; 01761 for (int i=0;i<dim_edge;i++) 01762 std::cout<<dst_nodes[i]<<" "; 01763 std::cout<<std::endl; 01764 */ 01765 /*std::cout<<std::endl; 01766 std::cout<<"Proc "<<Mpi_::mpi_rank<<" indexes_nodes = "; 01767 for (int i=0;i<dim_ind_no;i++) 01768 std::cout<<indexes_nodes[i]<<" "; 01769 std::cout<<std::endl;*/ 01770 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" indexes_edges = "; 01771 for (int i=0;i<dim_ind_ed;i++) 01772 std::cout<<indexes_edges[i]<<" "; 01773 std::cout<<std::endl;*/ 01774 /* 01775 std::cout<<std::endl; 01776 std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_out = "; 01777 for (int i=1;i<dim_node+1;i++) 01778 std::cout<<degcum_out[i]<<" "; 01779 std::cout<<std::endl;*/ 01780 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_in = "; 01781 for (int i=1;i<dim_node+1;i++) 01782 std::cout<<degcum_in[i]<<" "; 01783 std::cout<<std::endl;*/ 01784 01785 /*std::cout<<std::endl; 01786 std::cout<<"Proc "<<Mpi_::mpi_rank<<" neigh_out = "; 01787 for (int i=0;i<dim_edge+dim_tor_out;i++) 01788 std::cout<<neigh_out[i]<<" "; 01789 std::cout<<std::endl; 01790 std::cout<<"Proc "<<Mpi_::mpi_rank<<" neigh_in = "; 01791 for (int i=0;i<dim_edge+dim_tor_in;i++) 01792 std::cout<<neigh_in[i]<<" "; 01793 std::cout<<std::endl; 01794 */ 01795 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_out = "; 01796 for (int i=0;i<dim_edge+dim_tor_out;i++) 01797 std::cout<<edges_out[i]<<" "; 01798 std::cout<<std::endl;*/ 01799 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_in = "; 01800 for (int i=0;i<dim_edge+dim_tor_in;i++) 01801 std::cout<<edges_in[i]<<" "; 01802 std::cout<<std::endl;*/ 01803 01804 //std::cout<<std::endl; 01805 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tor = "; 01806 for (int i=1;i<Mpi_::mpi_nb+1;i++) 01807 std::cout<<degcum_tor[i]<<" "; 01808 std::cout<<std::endl;*/ 01809 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tos = "; 01810 for (int i=0;i<Mpi_::mpi_nb+1;i++) 01811 std::cout<<degcum_tos[i]<<" "; 01812 std::cout<<std::endl;*/ 01813 01814 //std::cout<<std::endl; 01815 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tor_in = "; 01816 for (int i=1;i<Mpi_::mpi_nb+1;i++) 01817 std::cout<<degcum_tor_in[i]<<" "; 01818 std::cout<<std::endl; 01819 std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tos_in = "; 01820 for (int i=0;i<Mpi_::mpi_nb+1;i++) 01821 std::cout<<degcum_tos_in[i]<<" "; 01822 std::cout<<std::endl; 01823 01824 //std::cout<<std::endl; 01825 std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tor_out = "; 01826 for (int i=1;i<Mpi_::mpi_nb+1;i++) 01827 std::cout<<degcum_tor_out[i]<<" "; 01828 std::cout<<std::endl; 01829 std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tos_out = "; 01830 for (int i=0;i<Mpi_::mpi_nb+1;i++) 01831 std::cout<<degcum_tos_out[i]<<" "; 01832 std::cout<<std::endl;*/ 01833 01834 //std::cout<<std::endl; 01835 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tor = "; 01836 for (int i=0;i<dim_tor_out+dim_tor_in;i++) 01837 std::cout<<edges_tor[i]<<" "; 01838 std::cout<<std::endl;*/ 01839 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tos = "; 01840 for (int i=0;i<dim_tos_out+dim_tos_in;i++) 01841 std::cout<<edges_tos[i]<<" "; 01842 std::cout<<std::endl;*/ 01843 01844 //std::cout<<std::endl; 01845 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tor_in = "; 01846 for (int i=0;i<dim_tor_in;i++) 01847 std::cout<<edges_tor_in[i]<<" "; 01848 std::cout<<std::endl;*/ 01849 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tos_in = "; 01850 for (int i=0;i<dim_tos_in;i++) 01851 std::cout<<edges_tos_in[i]<<" "; 01852 std::cout<<std::endl;*/ 01853 01854 //std::cout<<std::endl; 01855 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tor_out = "; 01856 for (int i=0;i<dim_tor_out;i++) 01857 std::cout<<edges_tor_out[i]<<" "; 01858 std::cout<<std::endl;*/ 01859 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tos_out = "; 01860 for (int i=0;i<dim_tos_out;i++) 01861 std::cout<<edges_tos_out[i]<<" "; 01862 std::cout<<std::endl;*/ 01863 01864 /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" nodes_tor = "; 01865 for (int i=0;i<dim_tor_out+dim_tor_in;i++) 01866 std::cout<<nodes_tor[i]<<" "; 01867 std::cout<<std::endl; 01868 std::cout<<"Proc "<<Mpi_::mpi_rank<<" nodes_tos = "; 01869 for (int i=0;i<dim_tos_out+dim_tos_in;i++) 01870 std::cout<<nodes_tos[i]<<" "; 01871 std::cout<<std::endl;*/ 01872 } 01873 //------------------------------------------------------------------------------- 01874 //! Initialization of the DDAG_impl 01875 /*! 01876 \param file is the path to the .dot input file 01877 */ 01878 //------------------------------------------------------------------------------- 01879 void init(const char * file) 01880 //------------------------------------------------------------------------------- 01881 { 01882 degcum_in = NULL;degcum_out = NULL;neigh_in = NULL;neigh_out = NULL;edges_out = NULL;edges_in=NULL;src_nodes = NULL;dst_nodes = NULL;indexes_nodes=NULL;indexes_edges=NULL; 01883 degcum_tos = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int)); 01884 degcum_tos_in = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int)); 01885 degcum_tos_out = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int)); 01886 degcum_tor = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int)); 01887 degcum_tor_in = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int)); 01888 degcum_tor_out = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int)); 01889 /*edges_tor=NULL;*/edges_tor_in=NULL;edges_tor_out=NULL;/*edges_tos=NULL;*/edges_tos_in=NULL;edges_tos_out=NULL;nodes_tor=NULL;nodes_tos=NULL; 01890 dim_node=0;dim_edge=0;dim_roots=0;dim_leafs=0;dim_comm=0;dim_loc=0; 01891 dim_tor_out=0;dim_tor_in=0;dim_tos_out=0;dim_tos_in=0; 01892 //lecture du .dot, construction d'une structure séquentielle temporaire 01893 //algo distribution 01894 //remplissage structure locale 01895 distribute(file); 01896 } 01897 //------------------------------------------------------------------------------- 01898 01899 public: 01900 01901 //------------------------------------------------------------------------------- 01902 //! Constructor of the DDAG_impl 01903 /*! 01904 \param path to the input .dot file 01905 */ 01906 //------------------------------------------------------------------------------- 01907 DDAG_impl(const char * file) 01908 //------------------------------------------------------------------------------- 01909 { 01910 //read file 01911 //distribution algorithm 01912 //data structure construction 01913 init(file); 01914 } 01915 //------------------------------------------------------------------------------- 01916 //! Destructor of the DDAG_impl 01917 /*! 01918 */ 01919 //------------------------------------------------------------------------------- 01920 ~DDAG_impl() 01921 //------------------------------------------------------------------------------- 01922 { 01923 if(NULL!=degcum_in) 01924 free(degcum_in); 01925 if(NULL!=degcum_out) 01926 free(degcum_out); 01927 if(NULL!=neigh_in) 01928 free(neigh_in); 01929 if(NULL!=neigh_out) 01930 free(neigh_out); 01931 if(NULL!=edges_out) 01932 free(edges_out); 01933 if(NULL!=edges_in) 01934 free(edges_in); 01935 if(NULL!=src_nodes) 01936 free(src_nodes); 01937 if(NULL!=dst_nodes) 01938 free(dst_nodes); 01939 if(NULL!=indexes_nodes) 01940 free(indexes_nodes); 01941 if(NULL!=indexes_edges) 01942 free(indexes_edges); 01943 if(NULL!=degcum_tos) 01944 free(degcum_tos); 01945 if(NULL!=degcum_tos_in) 01946 free(degcum_tos_in); 01947 if(NULL!=degcum_tos_out) 01948 free(degcum_tos_out); 01949 if(NULL!=degcum_tor) 01950 free(degcum_tor); 01951 if(NULL!=degcum_tor_in) 01952 free(degcum_tor_in); 01953 if(NULL!=degcum_tor_out) 01954 free(degcum_tor_out); 01955 /*if(NULL!=edges_tor) 01956 free(edges_tor);*/ 01957 /*if(NULL!=edges_tos) 01958 free(edges_tos);*/ 01959 if(NULL!=edges_tor_in) 01960 free(edges_tor_in); 01961 if(NULL!=edges_tos_in) 01962 free(edges_tos_in); 01963 if(NULL!=edges_tor_out) 01964 free(edges_tor_out); 01965 if(NULL!=edges_tos_out) 01966 free(edges_tos_out); 01967 if(NULL!=nodes_tor) 01968 free(nodes_tor); 01969 if(NULL!=nodes_tos) 01970 free(nodes_tos); 01971 } 01972 //------------------------------------------------------------------------------- 01973 //! get the number of nodes 01974 /*! 01975 \return dim_node the number of nodes in the local data structure 01976 */ 01977 //------------------------------------------------------------------------------- 01978 inline unsigned int getDimNode(){return dim_node;} 01979 //------------------------------------------------------------------------------- 01980 //! get the number of edges 01981 /*! 01982 \return dim_edge the number of edges in the local data structure 01983 */ 01984 //------------------------------------------------------------------------------- 01985 inline unsigned int getDimEdge(){return dim_edge;} 01986 //------------------------------------------------------------------------------- 01987 //! get the number of pure local nodes 01988 /*! 01989 \return dim_node the number of pure local nodes 01990 */ 01991 //------------------------------------------------------------------------------- 01992 inline unsigned int getDimLoc(){return dim_loc;} 01993 //------------------------------------------------------------------------------- 01994 //! get the number of communication nodes 01995 /*! 01996 \return dim_node the number of communication nodes 01997 */ 01998 //------------------------------------------------------------------------------- 01999 inline unsigned int getDimComm(){return dim_comm;} 02000 //------------------------------------------------------------------------------- 02001 //! get the number of roots nodes 02002 /*! 02003 \return dim_node the number of roots nodes 02004 */ 02005 //------------------------------------------------------------------------------- 02006 inline unsigned int getDimRoots(){return dim_roots;} 02007 //------------------------------------------------------------------------------- 02008 //! get the number of leafs nodes 02009 /*! 02010 \return dim_node the number of leafs nodes 02011 */ 02012 //------------------------------------------------------------------------------- 02013 inline unsigned int getDimLeafs(){return dim_leafs;} 02014 //------------------------------------------------------------------------------- 02015 //! get the number of elements to receive in 02016 /*! 02017 \return the number of elements 02018 */ 02019 //------------------------------------------------------------------------------- 02020 inline unsigned int getDimTorIn(){return dim_tor_in;} 02021 //------------------------------------------------------------------------------- 02022 //! get the number of elements to receive out 02023 /*! 02024 \return the number of elements 02025 */ 02026 //------------------------------------------------------------------------------- 02027 inline unsigned int getDimTorOut(){return dim_tor_out;} 02028 //------------------------------------------------------------------------------- 02029 //! get the global index of a local node 02030 /*! 02031 \return the global index of a local node 02032 */ 02033 //------------------------------------------------------------------------------- 02034 inline unsigned int getIndexNode(unsigned int ind){return indexes_nodes[ind];} 02035 //------------------------------------------------------------------------------- 02036 //! get the global index of a local edge 02037 /*! 02038 \return the global index of a local edge 02039 */ 02040 //------------------------------------------------------------------------------- 02041 inline unsigned int getIndexEdge(unsigned int ind){return indexes_edges[ind];} 02042 //------------------------------------------------------------------------------- 02043 //! to get the iterator rank on the source node of the index edge 02044 /*! 02045 \return the iterator rank on the source node 02046 */ 02047 //------------------------------------------------------------------------------- 02048 inline unsigned int getSrcNode(unsigned int r){return src_nodes[r];} 02049 //------------------------------------------------------------------------------- 02050 //! to get the iterator rank on the destination node of the index edge 02051 /*! 02052 \return the iterator rank on the destination node 02053 */ 02054 //------------------------------------------------------------------------------- 02055 inline unsigned int getDstNode(unsigned int r){return dst_nodes[r];} 02056 //------------------------------------------------------------------------------- 02057 //! to get a vector of iterator on input edges for the node at rank r 02058 /*! 02059 \param r is the rank of the node to get in edges 02060 \return a vector of iterator 02061 */ 02062 //------------------------------------------------------------------------------- 02063 std::vector<iterator_dag> getInEdges(unsigned int r) 02064 { 02065 std::vector<iterator_dag> v; 02066 for(int i=degcum_in[r];i<degcum_in[r+1];i++) 02067 v.push_back(iterator_dag(edges_in[i])); 02068 return v; 02069 } 02070 //------------------------------------------------------------------------------- 02071 //! to get a vector of iterator on output edges for the node at rank r 02072 /*! 02073 \param r is the rank of the node to get out edges 02074 \return a vector of iterator 02075 */ 02076 //------------------------------------------------------------------------------- 02077 std::vector<iterator_dag> getOutEdges(unsigned int r) 02078 { 02079 std::vector<iterator_dag> v; 02080 for(int i=degcum_out[r];i<degcum_out[r+1];i++) 02081 v.push_back(iterator_dag(edges_out[i])); 02082 return v; 02083 } 02084 //------------------------------------------------------------------------------- 02085 //! to get a vector of iterator on input nodes for the node at rank r 02086 /*! 02087 \param r is the rank of the node to get in nodes 02088 \return a vector of iterator 02089 */ 02090 //------------------------------------------------------------------------------- 02091 std::vector<iterator_dag> getInNodes(unsigned int r) 02092 { 02093 std::vector<iterator_dag> v; 02094 for(int i=degcum_in[r];i<degcum_in[r+1];i++) 02095 v.push_back(iterator_dag(neigh_in[i])); 02096 return v; 02097 } 02098 //------------------------------------------------------------------------------- 02099 //! to get a vector of iterator on output nodes for the node at rank r 02100 /*! 02101 \param r is the rank of the node to get out nodes 02102 \return a vector of iterator 02103 */ 02104 //------------------------------------------------------------------------------- 02105 std::vector<iterator_dag> getOutNodes(unsigned int r) 02106 { 02107 std::vector<iterator_dag> v; 02108 for(int i=degcum_out[r];i<degcum_out[r+1];i++) 02109 v.push_back(iterator_dag(neigh_out[i])); 02110 return v; 02111 } 02112 //------------------------------------------------------------------------------- 02113 //! to get the number of elements to send to a precised processor rank 02114 /*! 02115 \param rank is the rank of the processor to send elements to 02116 \return the number of elements to send to this processor 02117 */ 02118 //------------------------------------------------------------------------------- 02119 inline unsigned int getNbNodesToSend(unsigned int rank){return degcum_tos[rank+1]-degcum_tos[rank];} 02120 //------------------------------------------------------------------------------- 02121 //! to fill a table with indexes to send to other processors 02122 /*! 02123 \param rank is the rank of the processor to send data to 02124 \return a table with indexes to send 02125 */ 02126 //------------------------------------------------------------------------------- 02127 unsigned int * getNodesToSend(unsigned int rank) 02128 //------------------------------------------------------------------------------- 02129 { 02130 unsigned int * ret = (unsigned int *)calloc(degcum_tos[rank+1]-degcum_tos[rank],sizeof(unsigned int)); 02131 for(unsigned int i=0;i<degcum_tos[rank+1]-degcum_tos[rank];i++) 02132 ret[i] = nodes_tos[degcum_tos[rank]+i]; 02133 02134 return ret; 02135 } 02136 //------------------------------------------------------------------------------- 02137 //! to get the number of edges to send to a precised processor rank 02138 /*! 02139 \param rank is the rank of the processor to send edges to 02140 \return the number of edges to send to this processor 02141 */ 02142 //------------------------------------------------------------------------------- 02143 inline unsigned int getNbEdgesToSend(unsigned int rank){return (degcum_tos_in[rank+1]+degcum_tos_out[rank+1])-(degcum_tos_in[rank]+degcum_tos_out[rank]);} 02144 //------------------------------------------------------------------------------- 02145 //! to get the number of edges to send in to a precised processor rank 02146 /*! 02147 \param rank is the rank of the processor to send edges to 02148 \return the number of edges to send in to this processor 02149 */ 02150 //------------------------------------------------------------------------------- 02151 inline unsigned int getNbEdgesToSendIn(unsigned int rank){return degcum_tos_in[rank+1]-degcum_tos_in[rank];} 02152 //------------------------------------------------------------------------------- 02153 //! to get the number of edges to send out to a precised processor rank, those edges go inside the processor rank 02154 /*! 02155 \param rank is the rank of the processor to send edges to 02156 \return the number of edges to send out to this processor 02157 */ 02158 //------------------------------------------------------------------------------- 02159 inline unsigned int getNbEdgesToSendOut(unsigned int rank){return degcum_tos_out[rank+1]-degcum_tos_out[rank];} 02160 //------------------------------------------------------------------------------- 02161 //! to fill a table with indexes to send to other processors, those edges go outside the processor rank 02162 /*! 02163 \param rank is the rank of the processor to send data to 02164 \return a table with indexes to send 02165 */ 02166 //------------------------------------------------------------------------------- 02167 unsigned int * getEdgesToSend(unsigned int rank) 02168 //------------------------------------------------------------------------------- 02169 { 02170 unsigned int * ret = (unsigned int *)calloc((degcum_tos_in[rank+1]+degcum_tos_out[rank+1])-(degcum_tos_in[rank]+degcum_tos_out[rank]),sizeof(unsigned int)); 02171 for(unsigned int i=0;i<degcum_tos_in[rank+1]-degcum_tos_in[rank];i++) 02172 ret[i] = edges_tos_in[degcum_tos_in[rank]+i]; 02173 for(unsigned int i=0;i<degcum_tos_out[rank+1]-degcum_tos_out[rank];i++) 02174 ret[degcum_tos_in[rank+1]-degcum_tos_in[rank]+i] = edges_tos_out[degcum_tos_out[rank]+i]; 02175 02176 return ret; 02177 } 02178 //------------------------------------------------------------------------------- 02179 //! to fill a table with indexes to send in to other processors 02180 /*! 02181 \param rank is the rank of the processor to send in data to 02182 \return a table with indexes to send in 02183 */ 02184 //------------------------------------------------------------------------------- 02185 unsigned int * getEdgesToSendIn(unsigned int rank) 02186 //------------------------------------------------------------------------------- 02187 { 02188 unsigned int * ret = (unsigned int *)calloc(degcum_tos_in[rank+1]-degcum_tos_in[rank],sizeof(unsigned int)); 02189 for(unsigned int i=0;i<degcum_tos_in[rank+1]-degcum_tos_in[rank];i++) 02190 ret[i] = edges_tos_in[degcum_tos_in[rank]+i]; 02191 02192 return ret; 02193 } 02194 //------------------------------------------------------------------------------- 02195 //! to fill a table with indexes to send out to other processors 02196 /*! 02197 \param rank is the rank of the processor to send out data to 02198 \return a table with indexes to send out 02199 */ 02200 //------------------------------------------------------------------------------- 02201 unsigned int * getEdgesToSendOut(unsigned int rank) 02202 //------------------------------------------------------------------------------- 02203 { 02204 unsigned int * ret = (unsigned int *)calloc(degcum_tos_out[rank+1]-degcum_tos_out[rank],sizeof(unsigned int)); 02205 for(unsigned int i=0;i<degcum_tos_out[rank+1]-degcum_tos_out[rank];i++) 02206 ret[degcum_tos_in[rank+1]-degcum_tos_in[rank]+i] = edges_tos_out[degcum_tos_out[rank]+i]; 02207 02208 return ret; 02209 } 02210 //------------------------------------------------------------------------------- 02211 //! to get the number of elements to receive to a precised processor rank 02212 /*! 02213 \param rank is the rank of the processor to receive elements to 02214 \return the number of elements to receive to this processor 02215 */ 02216 //------------------------------------------------------------------------------- 02217 inline unsigned int getNbNodesToRecv(unsigned int rank){return degcum_tor[rank+1]-degcum_tor[rank];} 02218 //------------------------------------------------------------------------------- 02219 //! to fill a table with indexes to receive to other processors 02220 /*! 02221 \param rank is the rank of the processor to receive data to 02222 \return a table with indexes to receive 02223 */ 02224 //------------------------------------------------------------------------------- 02225 unsigned int * getNodesToRecv(unsigned int rank) 02226 //------------------------------------------------------------------------------- 02227 { 02228 unsigned int * ret = (unsigned int *)calloc(degcum_tor[rank+1]-degcum_tor[rank],sizeof(unsigned int)); 02229 for(unsigned int i=0;i<degcum_tor[rank+1]-degcum_tor[rank];i++) 02230 ret[i] = nodes_tor[degcum_tor[rank]+i];; 02231 02232 return ret; 02233 } 02234 //------------------------------------------------------------------------------- 02235 //! to get the number of edges to receive to a precised processor rank 02236 /*! 02237 \param rank is the rank of the processor to receive edges to 02238 \return the number of edges to receive to this processor 02239 */ 02240 //------------------------------------------------------------------------------- 02241 inline unsigned int getNbEdgesToRecv(unsigned int rank){return (degcum_tor_in[rank+1]+degcum_tor_out[rank+1])-(degcum_tor_in[rank]+degcum_tor_out[rank]);} 02242 //------------------------------------------------------------------------------- 02243 //! to get the number of edges to receive in to a precised processor rank 02244 /*! 02245 \param rank is the rank of the processor to receive edges to 02246 \return the number of edges to receive in to this processor 02247 */ 02248 //------------------------------------------------------------------------------- 02249 inline unsigned int getNbEdgesToRecvIn(unsigned int rank){return degcum_tor_in[rank+1]-degcum_tor_in[rank];} 02250 //------------------------------------------------------------------------------- 02251 //! to get the number of edges to receive out to a precised processor rank 02252 /*! 02253 \param rank is the rank of the processor to receive edges to 02254 \return the number of edges to receive out to this processor 02255 */ 02256 //------------------------------------------------------------------------------- 02257 inline unsigned int getNbEdgesToRecvOut(unsigned int rank){return degcum_tor_out[rank+1]-degcum_tor_out[rank];} 02258 //------------------------------------------------------------------------------- 02259 //! to fill a table with indexes to receive to other processors 02260 /*! 02261 \param rank is the rank of the processor to receive data to 02262 \return a table with indexes to receive 02263 */ 02264 //------------------------------------------------------------------------------- 02265 unsigned int * getEdgesToRecv(unsigned int rank) 02266 //------------------------------------------------------------------------------- 02267 { 02268 unsigned int * ret = (unsigned int *)calloc((degcum_tor_in[rank+1]+degcum_tor_out[rank+1])-(degcum_tor_in[rank]+degcum_tor_out[rank]),sizeof(unsigned int)); 02269 for(unsigned int i=0;i<degcum_tor_in[rank+1]-degcum_tor_in[rank];i++) 02270 ret[i] = edges_tor_in[degcum_tor_in[rank]+i]; 02271 for(unsigned int i=0;i<degcum_tor_out[rank+1]-degcum_tor_out[rank];i++) 02272 ret[degcum_tor_in[rank+1]-degcum_tor_in[rank]+i] = edges_tor_out[degcum_tor_out[rank]+i]; 02273 02274 return ret; 02275 } 02276 //------------------------------------------------------------------------------- 02277 //! to fill a table with indexes to receive in to other processors 02278 /*! 02279 \param rank is the rank of the processor to receive in data to 02280 \return a table with indexes to receive in 02281 */ 02282 //------------------------------------------------------------------------------- 02283 unsigned int * getEdgesToRecvIn(unsigned int rank) 02284 //------------------------------------------------------------------------------- 02285 { 02286 unsigned int * ret = (unsigned int *)calloc(degcum_tor_in[rank+1]-degcum_tor_in[rank],sizeof(unsigned int)); 02287 for(unsigned int i=0;i<degcum_tor_in[rank+1]-degcum_tor_in[rank];i++) 02288 ret[i] = edges_tor_in[degcum_tor_in[rank]+i]; 02289 02290 return ret; 02291 } 02292 //------------------------------------------------------------------------------- 02293 //! to fill a table with indexes to receive out to other processors 02294 /*! 02295 \param rank is the rank of the processor to receive out data to 02296 \return a table with indexes to receive out 02297 */ 02298 //------------------------------------------------------------------------------- 02299 unsigned int * getEdgesToRecvOut(unsigned int rank) 02300 //------------------------------------------------------------------------------- 02301 { 02302 unsigned int * ret = (unsigned int *)calloc(degcum_tor_out[rank+1]-degcum_tor_out[rank],sizeof(unsigned int)); 02303 for(unsigned int i=0;i<degcum_tor_out[rank+1]-degcum_tor_out[rank];i++) 02304 ret[degcum_tor_in[rank+1]-degcum_tor_in[rank]+i] = edges_tor_out[degcum_tor_out[rank]+i]; 02305 02306 return ret; 02307 } 02308 //------------------------------------------------------------------------------- 02309 02310 }; 02311 02312 //------------------------------------------------------------------------------- 02313 //! Second specialization of the DDAG_impl class 02314 /*! 02315 Computations on edges only 02316 */ 02317 //------------------------------------------------------------------------------- 02318 template<> struct DDAG_impl<false,true> 02319 //------------------------------------------------------------------------------- 02320 { 02321 protected: 02322 02323 public: 02324 DDAG_impl(const char * binFile) 02325 { 02326 } 02327 ~DDAG_impl() 02328 { 02329 } 02330 02331 }; 02332 02333 //------------------------------------------------------------------------------- 02334 //! Third specialization of the DDAG_impl class 02335 /*! 02336 Computations on nodes only 02337 */ 02338 //------------------------------------------------------------------------------- 02339 template<> struct DDAG_impl<true,false> 02340 //------------------------------------------------------------------------------- 02341 { 02342 protected: 02343 02344 public: 02345 DDAG_impl(const char * binFile) 02346 { 02347 } 02348 ~DDAG_impl() 02349 { 02350 } 02351 02352 }; 02353 02354 } 02355 02356 #endif