Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
hit_layoutMetis.c
Go to the documentation of this file.
1 
13 /*
14  * <license>
15  *
16  * Hitmap v1.2
17  *
18  * This software is provided to enhance knowledge and encourage progress in the scientific
19  * community. It should be used only for research and educational purposes. Any reproduction
20  * or use for commercial purpose, public redistribution, in source or binary forms, with or
21  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
22  * holder. The origin of this software must not be misrepresented; you must not claim that you
23  * wrote the original software. If you use this software for any purpose (e.g. publication),
24  * a reference to the software package and the authors must be included.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
27  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
28  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
29  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
33  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
34  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  *
36  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
37  * All rights reserved.
38  *
39  * More information on http://trasgo.infor.uva.es/
40  *
41  * </license>
42 */
43 
44 #include <stdio.h>
45 #include <math.h>
46 
47 #include <hit_layout.h>
48 #include <hit_layoutP.h>
49 #include <hit_funcop.h>
50 #include <hit_allocP.h>
51 #include <hit_com.h>
52 
53 #include <hit_cshape.h>
54 #include <hit_bshape.h>
55 
56 
57 
58 
63 
64  int ok;
65  int sizes[2];
66  // @arturo Mar 2013
67  //MPI_Comm comm = *((MPI_Comm *)topo.pTopology.lowLevel);
68  MPI_Comm comm = topo.pTopology->comm;
69 
70  if(topo.pTopology->selfRank == 0){
71 
72  int n = hit_cShapeNvertices(*shape);
73  int m2 = hit_cShapeNedges(*shape);
74 
75  sizes[0] = n;
76  sizes[1] = m2;
77 
78  ok = MPI_Bcast(sizes, 2, MPI_INT, 0, comm);
79  hit_mpiTestError(ok,"Error in sparseShapeBcast");
80 
81  ok = MPI_Bcast(&(hit_cShapeNameList(*shape,0).flagNames),1,MPI_INT,0,comm);
82  hit_mpiTestError(ok,"Error in sparseShapeBcast");
83  ok = MPI_Bcast(hit_cShapeXadj(*shape), n+1, MPI_INT, 0, comm);
84  hit_mpiTestError(ok,"Error in sparseShapeBcast");
85  ok = MPI_Bcast(hit_cShapeAdjncy(*shape), m2, MPI_INT, 0, comm);
86  hit_mpiTestError(ok,"Error in sparseShapeBcast");
87  ok = MPI_Bcast(hit_cShapeNameList(*shape,0).names, n, MPI_INT, 0, comm);
88  hit_mpiTestError(ok,"Error in sparseShapeBcast");
89 
90  } else {
91 
92  ok = MPI_Bcast(sizes, 2, MPI_INT, 0, comm);
93  hit_mpiTestError(ok,"Error in sparseShapeBcast");
94  int n = sizes[0];
95  int m2 = sizes[1];
96 
97  HitShape newShp = hit_csrShape(n,m2);
98 
99  ok = MPI_Bcast(&(hit_cShapeNameList(newShp,0).flagNames),1,MPI_INT,0,comm);
100  hit_mpiTestError(ok,"Error in sparseShapeBcast");
101  if(hit_cShapeNameList(newShp,0).flagNames == HIT_SHAPE_NAMES_ARRAY)
102  hit_cShapeNameList(newShp,0).flagNames = HIT_SHAPE_NAMES_NOARRAY;
103 
104  ok = MPI_Bcast(hit_cShapeXadj(newShp), n+1, MPI_INT, 0, comm);
105  hit_mpiTestError(ok,"Error in sparseShapeBcast");
106  ok = MPI_Bcast(hit_cShapeAdjncy(newShp), m2, MPI_INT, 0, comm);
107  hit_mpiTestError(ok,"Error in sparseShapeBcast");
108  ok = MPI_Bcast(hit_cShapeNameList(newShp,0).names, n, MPI_INT, 0, comm);
109  hit_mpiTestError(ok,"Error in sparseShapeBcast");
110 
111  hit_cShapeNameList(newShp,0).nNames = n;
112  hit_cShapeNameList(newShp,1) = hit_cShapeNameList(newShp,0);
113 
114  *shape = newShp;
115  }
116 
117 }
118 
119 //#define DEBUG_LAY_METIS
120 
121 #ifdef DEBUG_LAY_METIS
122 #define debug(...) { if( hit_Rank == 0 ) { printf(__VA_ARGS__); fflush(stdout); }}
123 #define debugall(...) { printf(__VA_ARGS__);}
124 #endif
125 
126 
127 
128 // @javfres 2015-10-05 I have been refactoring this function dropping out part
129 // of the group support so it could work when there are more processes than
130 // nodes. Now some processes will be inactive.
132 
133  int i;
134 
135  // 0. Broadcast the sparse shape
136  hit_sparseShapeBcastInternal(shapeP,topo);
137 
138  // Shape pointer to struct
139  HitShape shape = *shapeP;
140 
141  // 1. Obtain the number of vertices and processes
142  int numVertices = hit_cShapeNvertices(shape);
143  int numProcessors = hit_topCard(topo);
144 
145  // 2. Create the layout
148  lay.topo = topo;
149  lay.origShape = shape;
150  int numParts = hit_min(numVertices,numProcessors);
151  lay.numActives[0] = numParts;
152  lay.type = HIT_LAYOUT_METIS;
154 
155  // Metis doesn't work if there is more processes than nodes,
156  // we must split the communicator and set non active processros.
157  if(numProcessors <= numVertices){
158  lay.active = 1;
159  lay.pTopology[0] = hit_ptopDup(topo.pTopology);
160  } else {
161  int linearRank = hit_topRankInternal(topo,hit_topRanks(topo));
162 
163  if(linearRank < numVertices){
164  lay.active = 1;
165  } else {
166  lay.active = 0;
167  }
168 
169  // Split the communicator
170  lay.pTopology[0] = hit_ptopSplit(topo.pTopology, lay.active);
171  }
172 
173  // Exit if the layout is not active
174  if(lay.active == 0) return lay;
175 
176  // Create the groups
177  for(i=0;i<numParts;i++){
178  // @javier 2015-10-05 Only one process per group so the rest are disabled
179  // hit_layout_list_addGroup(&lay,-1,numProcessors / numParts + ((numProcessors % numParts > i) ? 1 : 0 ));
180  hit_layout_list_addGroup(&lay,-1,1);
181 
182  }
183 
184  // @arturo 2015/01/22
185  //int group = hit_lay_procGroup(lay,topo.linearRank);
186  int group = hit_lay_procGroup(lay, hit_topSelfRankInternal( topo ) );
187  lay.group = group;
188 
189  // 3. Call the partition function
190  int wgtflag = 0;
191  int numflag = 0;
192  int options[5] = {0,0,0,0,0};
193  int edgecut;
194 
195  // We can use the assignedGroups generated in hit_layout_list_initGroups as the part array.
196  int * part = lay.info.layoutList.assignedGroups;
197 
198  if(numProcessors > 1){
199 
200  // Call METIS function.
202  hit_cShapeAdjncy(shape), NULL, NULL,
203  &wgtflag, &numflag, &numParts, options, &edgecut, part);
204 
205  } else {
206 
207  bzero(part, (size_t) numVertices * sizeof(int));
208  }
209 
210 
211 #ifdef DEBUG_LAY_METIS
212  {int i; sleep(2*hit_Rank);
213  debug("part: ");
214  for(i=0;i<hit_cShapeNvertices(shape);i++){
215  debug("%d",part[i]);
216  }
217  debug("\n");}
218 #endif
219 
220  // 4.a Get the number of vertices (n) from the partition.
221  int n = 0;
222 
223  for(i=0;i<hit_cShapeNvertices(shape);i++){
224  if(part[i] == group){
225  n++;
226  }
227  }
228 
229  // 4.b Get the number of edges (m).
230  int vertex;
231  int m=0;
232 
233  for(vertex=0; vertex<hit_cShapeNvertices(shape); vertex++){
234 
235  // Get first and last links.
236  int first = hit_cShapeXadj(shape)[vertex];
237  int last = hit_cShapeXadj(shape)[vertex+1];
238  int link;
239 
240  for(link=first; link<last; link++){
241 
242  //Get the neighbor.
243  int neighbor = hit_cShapeAdjncy(shape)[link];
244  if((part[vertex] == group && part[neighbor] == group) ){
245  m++;
246  }
247  }
248  }
249 
250 
251 #ifdef DEBUG_LAY_METIS
252  {int i;
253  debugall("p(%d): ",group);
254  debugall(" n=%d, m=%d \n",n,m);}
255 #endif
256 
257 
258  // 5. Create the local shape.
260 
261  // 5.1 Calculate the global-local name translation.
262  int current = 0;
263  for(i=0; i<hit_cShapeNvertices(shape); i++){
264  if( part[i] == group ){
265  hit_cShapeNameList(lshape,0).names[current++] = hit_cShapeNameList(shape,0).names[i];
266  }
267  }
268 
269  // Create the inverse translation list to speedup the algorithm.
270  hit_cShapeCreateInvNames(&lshape);
271 
272 #ifdef DEBUG_LAY_METIS
273  {int i;
274  debugall("globalName(%d): ",group);
275  for(i=0;i<hit_cShapeNvertices(lshape);i++){
276  debugall("%d",hit_cShapeNameList(lshape,0).names[i]);
277  }
278  debugall("\n");}
279 #endif
280 
281  // 5.2 Init xadj and adjncy
282  hit_cShapeXadj(lshape)[0] = 0;
283  int lvertex;
284 
285 
286  // Create the local graph.
287  for(lvertex=0; lvertex<hit_cShapeNvertices(lshape); lvertex++){
288 
289  hit_cShapeXadj(lshape)[lvertex+1] = hit_cShapeXadj(lshape)[lvertex];
290  int gvertex = hit_cShapeNameList(lshape,0).names[lvertex];
291 
292  // Locate the vertex in the global shape.
293  int g;
294  for(g=0;g<hit_cShapeNvertices(shape); g++){
295  if( gvertex == hit_cShapeNameList(shape,0).names[g] ){
296  vertex = g;
297  break;
298  }
299  }
300 
301  // Get first and last links.
302  int first = hit_cShapeXadj(shape)[vertex];
303  int last = hit_cShapeXadj(shape)[vertex+1];
304  int link;
305 
306  for(link=first; link<last; link++){
307 
308  //Get the neighbor.
309  int neighbor = hit_cShapeAdjncy(shape)[link];
310  int gneighbor = hit_cShapeNameList(shape,0).names[neighbor];
311  int lneighbor = hit_cShapeVertexToLocal(lshape,gneighbor);
312 
313  if(lneighbor != -1){
314 
315  hit_cShapeAdjncy(lshape)[hit_cShapeXadj(lshape)[lvertex+1]] = lneighbor;
316  hit_cShapeXadj(lshape)[lvertex+1] ++;
317  }
318  }
319  }
320 
321 #ifdef DEBUG_LAY_METIS
322  {int i;
323  debugall("xadj(%d): ",group);
324  for(i=0;i<hit_cShapeNvertices(lshape)+1;i++){
325  debugall("%d",hit_cShapeXadj(lshape)[i]);
326  }
327  debugall("\n");}
328 
329 
330  {int i;
331  debugall("adjncy(%d): ",group);
332  for(i=0;i<m;i++){
333  debugall("%d",hit_cShapeAdjncy(lshape)[i]);
334  }
335  debugall("\n");}
336 #endif
337 
338  // The namelist is the same for both dimensions
339  hit_cShapeNameList(lshape,1) = hit_cShapeNameList(lshape,0);
340 
341  // 7. Fill the layout structure.
342  hit_layShape(lay) = lshape;
343 
344  // 8. Create the assignedGroups array
346 
347  // 10. Return the layout
348  return lay;
349 }
350 
351 
352 
353 
354 
355 
356 
#define hit_cShapeAdjncy(shape)
Vector g(int i, int j)
int * sizes
Definition: refMPIluBack.c:104
HitLayout HIT_LAYOUT_NULL
Definition: hit_layout.c:71
#define hit_layShape(lay)
Definition: hit_layout.h:650
#define hit_cShapeNedges(shape)
HitPTopology * hit_ptopSplit(HitPTopology *in, int group)
Definition: hit_topology.c:80
#define hit_Rank
Definition: hit_com.h:140
int hit_topRankInternal(HitTopology topo, HitRanks ranks)
Definition: hit_topology.c:415
HitTopology topo
Definition: hit_layout.h:255
HitPTopology * pTopology
Definition: hit_topology.h:253
int numElementsTotal
Definition: hit_layout.h:226
#define hit_topRanks(topo)
Definition: hit_topology.h:425
void hit_cShapeCreateInvNames(HitShape *shape)
Definition: hit_cshape.c:318
HitShape hit_csrShape(int nvertices, int nedges)
Definition: hit_cshape.c:47
void hit_layout_list_addGroup(HitLayout *lay, int leader, int np)
Definition: hit_layout.c:2423
HitPTopology * hit_ptopDup(HitPTopology *in)
Definition: hit_topology.c:74
HitPTopology * pTopology[HIT_MAXDIMS+1]
Definition: hit_layout.h:278
MPI_Comm comm
Definition: SWpar_ref.c:193
#define hit_cShapeXadj(shape)
#define hit_mpiTestError(ok, cad)
Definition: hit_com.h:62
#define hit_cShapeNvertices(shape)
int * assignedGroups
Definition: hit_layout.h:227
#define hit_cShapeVertexToLocal(s, vertex)
Definition: hit_cshape.h:243
Hitmap functions to allocate memory.
#define hit_cShapeNameList(shape, dim)
Definition: hit_cshape.h:162
void hit_sparseShapeBcastInternal(HitShape *shape, HitTopology topo)
void METIS_PartGraphKway(int *nvtxs, idxtype *xadj, idxtype *adjncy, idxtype *vwgt, idxtype *adjwgt, int *wgtflag, int *numflag, int *nparts, int *options, int *edgecut, idxtype *part)
Definition: kmetis.c:22
HitShape shape
HitLayoutList layoutList
Definition: hit_layout.h:285
HitShape lshape
Definition: SWpar.c:273
HitLayout hit_layout_plug_layMetis(HitTopology topo, HitShape *shape)
int hit_topCard(HitTopology topo)
Definition: hit_topology.c:361
HitShape HIT_CSR_SHAPE_NULL
Definition: hit_shape.c:70
#define HIT_LAYOUT_METIS
Definition: hit_layout.h:391
#define m(a, b, c)
union HitLayout::@0 info
HitShape origShape
Definition: hit_layout.h:274
int active
Definition: hit_layout.h:263
#define hit_topSelfRankInternal(topo)
Definition: hit_topology.h:439
int numActives[HIT_MAXDIMS]
Definition: hit_layout.h:257
HitLayout lay
Definition: heat.c:107
#define hit_min(a, b)
Definition: hit_funcop.h:65
int hit_lay_procGroup(HitLayout layout, int processor)
Definition: hit_layout.c:2477
void hit_layout_list_initGroups(HitLayout *lay, int numElementsTotal)
Definition: hit_layout.c:2401