1 /* Copyright 2004,2007-2012,2014 IPB, Universite de Bordeaux, INRIA & CNRS
2 **
3 ** This file is part of the Scotch software package for static mapping,
4 ** graph partitioning and sparse matrix ordering.
5 **
6 ** This software is governed by the CeCILL-C license under French law
7 ** and abiding by the rules of distribution of free software. You can
8 ** use, modify and/or redistribute the software under the terms of the
9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10 ** URL: "http://www.cecill.info".
11 **
12 ** As a counterpart to the access to the source code and rights to copy,
13 ** modify and redistribute granted by the license, users are provided
14 ** only with a limited warranty and the software's author, the holder of
15 ** the economic rights, and the successive licensors have only limited
16 ** liability.
17 **
18 ** In this respect, the user's attention is drawn to the risks associated
19 ** with loading, using, modifying and/or developing or reproducing the
20 ** software by the user in light of its specific status of free software,
21 ** that may mean that it is complicated to manipulate, and that also
22 ** therefore means that it is reserved for developers and experienced
23 ** professionals having in-depth computer knowledge. Users are therefore
24 ** encouraged to load and test the software's suitability as regards
25 ** their requirements in conditions enabling the security of their
26 ** systems and/or data to be ensured and, more generally, to use and
27 ** operate it in the same conditions as regards security.
28 **
29 ** The fact that you are presently reading this means that you have had
30 ** knowledge of the CeCILL-C license and that you accept its terms.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : library_graph_map.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** Sebastien FOURESTIER (v6.0) **/
38 /** **/
39 /** FUNCTION : This module is the API for the mapping **/
40 /** routines of the libSCOTCH library. **/
41 /** **/
42 /** DATES : # Version 3.2 : from : 19 aug 1998 **/
43 /** to 20 aug 1998 **/
44 /** # Version 3.3 : from : 19 oct 1998 **/
45 /** to 30 mar 1999 **/
46 /** # Version 3.4 : from : 01 nov 2001 **/
47 /** to 01 nov 2001 **/
48 /** # Version 4.0 : from : 13 jan 2004 **/
49 /** to 13 nov 2005 **/
50 /** # Version 5.1 : from : 29 oct 2007 **/
51 /** to 24 jul 2011 **/
52 /** # Version 6.0 : from : 03 mar 2011 **/
53 /** to 29 oct 2014 **/
54 /** **/
55 /************************************************************/
56
57 /*
58 ** The defines and includes.
59 */
60
61 #define LIBRARY
62
63 #include "module.h"
64 #include "common.h"
65 #include "parser.h"
66 #include "graph.h"
67 #include "arch.h"
68 #include "arch_dist.h"
69 #include "mapping.h"
70 #include "kgraph.h"
71 #include "kgraph_map_st.h"
72 #include "library_mapping.h"
73 #include "scotch.h"
74
75 /************************************/
76 /* */
77 /* These routines are the C API for */
78 /* the mapping routines. */
79 /* */
80 /************************************/
81
82 /*+ This routine initializes an API opaque
83 *** mapping with respect to the given source
84 *** graph and the locations of output parameters.
85 *** It returns:
86 *** - 0 : on success.
87 *** - !0 : on error.
88 +*/
89
90 int
SCOTCH_graphMapInit(const SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr,const SCOTCH_Arch * const archptr,SCOTCH_Num * const parttab)91 SCOTCH_graphMapInit (
92 const SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
93 SCOTCH_Mapping * const mappptr, /*+ Mapping structure to initialize +*/
94 const SCOTCH_Arch * const archptr, /*+ Target architecture used to map +*/
95 SCOTCH_Num * const parttab) /*+ Mapping array +*/
96 {
97 LibMapping * restrict lmapptr;
98
99 lmapptr = (LibMapping *) mappptr;
100
101 lmapptr->flagval = LIBMAPPINGNONE; /* No options set */
102 lmapptr->grafptr = (Graph *) grafptr;
103 lmapptr->archptr = (Arch *) archptr;
104 if (parttab == NULL) {
105 if ((lmapptr->parttab = (Gnum *) memAlloc (lmapptr->grafptr->vertnbr * sizeof (Gnum))) == NULL) {
106 errorPrint ("SCOTCH_graphMapInit: out of memory");
107 return (1);
108 }
109 memSet (lmapptr->parttab, 0, lmapptr->grafptr->vertnbr * sizeof (Anum)); /* All vertices mapped to first domain */
110 lmapptr->flagval |= LIBMAPPINGFREEPART; /* The user did not provided the partition array, so we will free it */
111 }
112 else
113 lmapptr->parttab = (Gnum *) parttab;
114
115 return (0);
116 }
117
118 /*+ This routine frees an API mapping.
119 *** It returns:
120 *** - VOID : in all cases.
121 +*/
122
123 void
SCOTCH_graphMapExit(const SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr)124 SCOTCH_graphMapExit (
125 const SCOTCH_Graph * const grafptr,
126 SCOTCH_Mapping * const mappptr)
127 {
128 LibMapping * restrict lmapptr;
129
130 lmapptr = (LibMapping *) mappptr;
131
132 if (((lmapptr->flagval & LIBMAPPINGFREEPART) != 0) && /* If parttab must be freed */
133 (lmapptr->parttab != NULL)) /* And if exists */
134 memFree (lmapptr->parttab); /* Free it */
135
136 memSet (lmapptr, 0, sizeof (LibMapping));
137 }
138
139 /*+ This routine computes a mapping or a
140 *** remapping, with or without fixed
141 *** vertices, of the API mapping
142 *** structures given in input, with
143 *** respect to the given strategy.
144 *** It returns:
145 *** - 0 : on success.
146 *** - !0 : on error.
147 +*/
148
149 static
150 int
graphMapCompute2(SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr,SCOTCH_Mapping * const mapoptr,const double emraval,const SCOTCH_Num * vmlotab,const Gnum vfixnbr,SCOTCH_Strat * const straptr)151 graphMapCompute2 (
152 SCOTCH_Graph * const grafptr, /*+ Graph to order +*/
153 SCOTCH_Mapping * const mappptr, /*+ Mapping to compute +*/
154 SCOTCH_Mapping * const mapoptr, /*+ Old mapping +*/
155 const double emraval, /*+ Edge migration ratio +*/
156 const SCOTCH_Num * vmlotab, /*+ Vertex migration cost array +*/
157 const Gnum vfixnbr, /*+ Number of fixed vertices in part array +*/
158 SCOTCH_Strat * const straptr) /*+ Mapping strategy +*/
159 {
160 Kgraph mapgrafdat; /* Effective mapping graph */
161 const Strat * mapstraptr; /* Pointer to mapping strategy */
162 LibMapping * restrict lmapptr;
163 Anum * pfixtax;
164 Gnum baseval;
165 Anum * parttax; /* Partition array */
166 Anum * parotax; /* Old partition array */
167 Gnum crloval; /* Coefficient load for regular edges */
168 Gnum cmloval; /* Coefficient load for migration edges */
169 const Gnum * vmlotax; /* Vertex migration cost array */
170 Gnum vertnum;
171 Gnum vertnnd;
172 Gnum vertnbr;
173 int o;
174
175 lmapptr = (LibMapping *) mappptr;
176 #ifdef SCOTCH_DEBUG_LIBRARY1
177 if ((Graph *) grafptr != lmapptr->grafptr) {
178 errorPrint ("graphMapCompute2: output mapping does not correspond to input graph");
179 return (1);
180 }
181 #endif /* SCOTCH_DEBUG_LIBRARY1 */
182 #ifdef SCOTCH_DEBUG_LIBRARY2
183 if (graphCheck ((Graph *) grafptr) != 0) { /* Vertex loads can be 0 if we have fixed vertices */
184 errorPrint ("graphMapCompute2: invalid input graph");
185 return (1);
186 }
187 #endif /* SCOTCH_DEBUG_LIBRARY2 */
188
189 if (*((Strat **) straptr) == NULL) { /* Set default mapping strategy if necessary */
190 ArchDom domnorg;
191
192 archDomFrst (lmapptr->archptr, &domnorg);
193 SCOTCH_stratGraphMapBuild (straptr, SCOTCH_STRATDEFAULT, archDomSize (lmapptr->archptr, &domnorg), 0.01);
194 }
195
196 mapstraptr = *((Strat **) straptr);
197 #ifdef SCOTCH_DEBUG_LIBRARY1
198 if (mapstraptr->tabl != &kgraphmapststratab) {
199 errorPrint ("graphMapCompute2: not a graph mapping strategy");
200 return (1);
201 }
202 #endif /* SCOTCH_DEBUG_LIBRARY1 */
203
204 baseval = lmapptr->grafptr->baseval;
205 vertnbr = lmapptr->grafptr->vertnbr;
206
207 if (vfixnbr != 0) { /* We have fixed vertices */
208 #ifdef SCOTCH_DEBUG_LIBRARY1
209 ArchDom domndat;
210 Gnum vertnum;
211
212 if (lmapptr->parttab == NULL) { /* We must have fixed vertex information */
213 errorPrint ("graphMapCompute2: missing output mapping part array");
214 return (1);
215 }
216 for (vertnum = 0; vertnum < vertnbr; vertnum ++) {
217 if ((lmapptr->parttab[vertnum] >= 0) &&
218 (archDomTerm (lmapptr->archptr, &domndat, lmapptr->parttab[vertnum]) != 0)) {
219 errorPrint ("graphMapCompute2: invalid fixed partition");
220 return (1);
221 }
222 }
223 #endif /* SCOTCH_DEBUG_LIBRARY1 */
224 pfixtax = lmapptr->parttab - baseval;
225 }
226 else
227 pfixtax = NULL;
228
229 if (mapoptr != NULL) { /* We are doing a repartitioning */
230 const LibMapping * restrict lmaoptr;
231 Gnum numeval;
232 Gnum denoval;
233 #ifdef SCOTCH_DEBUG_LIBRARY1
234 ArchDom domndat;
235 Gnum vertnum;
236 #endif /* SCOTCH_DEBUG_LIBRARY1 */
237
238 lmaoptr = (LibMapping *) mapoptr;
239 #ifdef SCOTCH_DEBUG_LIBRARY1
240 if (lmapptr->grafptr != lmaoptr->grafptr) {
241 errorPrint ("graphMapCompute2: output and old mappings must correspond to same graph");
242 return (1);
243 }
244 if (lmapptr->archptr != lmaoptr->archptr) {
245 errorPrint ("graphMapCompute2: output and old mappings must correspond to same architecture");
246 return (1);
247 }
248 for (vertnum = 0; vertnum < vertnbr; vertnum ++) {
249 if ((lmaoptr->parttab[vertnum] >= 0) &&
250 (archDomTerm (lmapptr->archptr, &domndat, lmaoptr->parttab[vertnum]) != 0)) {
251 errorPrint ("graphMapCompute2: invalid old partition");
252 return (1);
253 }
254 }
255 #endif /* SCOTCH_DEBUG_LIBRARY1 */
256 parotax = lmaoptr->parttab - baseval;
257 vmlotax = (vmlotab != NULL) ? vmlotab - baseval : NULL;
258 numeval = (INT) ((emraval * 100.0) + 0.5);
259 denoval = intGcd (numeval, 100);
260 cmloval = numeval / denoval;
261 crloval = 100 / denoval;
262 }
263 else {
264 parotax = NULL;
265 vmlotax = NULL;
266 cmloval =
267 crloval = 1;
268 }
269
270 intRandInit (); /* Check that random number generator is initialized */
271
272 if (kgraphInit (&mapgrafdat, (Graph *) grafptr, lmapptr->archptr, NULL, vfixnbr, pfixtax, parotax, crloval, cmloval, vmlotax) != 0)
273 return (1);
274
275 o = 0;
276 if (mapgrafdat.vfixnbr < mapgrafdat.s.vertnbr) { /* Perform mapping if not all fixed vertices */
277 o = kgraphMapSt (&mapgrafdat, mapstraptr);
278 mapTerm (&mapgrafdat.m, lmapptr->parttab - baseval); /* Propagate mapping result to part array */
279 }
280
281 kgraphExit (&mapgrafdat);
282
283 return (o);
284 }
285
286 /*+ This routine computes a mapping
287 *** of the API mapping structure with
288 *** respect to the given strategy.
289 *** It returns:
290 *** - 0 : on success.
291 *** - !0 : on error.
292 +*/
293
294 int
SCOTCH_graphMapCompute(SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr,SCOTCH_Strat * const straptr)295 SCOTCH_graphMapCompute (
296 SCOTCH_Graph * const grafptr, /*+ Graph to order +*/
297 SCOTCH_Mapping * const mappptr, /*+ Mapping to compute +*/
298 SCOTCH_Strat * const straptr) /*+ Mapping strategy +*/
299 {
300 return (graphMapCompute2 (grafptr, mappptr, NULL, 1, NULL, 0, straptr));
301 }
302
303 /*+ This routine computes a mapping
304 *** with fixed vertices of the API
305 *** mapping structure with respect
306 *** to the given strategy.
307 *** It returns:
308 *** - 0 : on success.
309 *** - !0 : on error.
310 +*/
311
312 int
SCOTCH_graphMapFixedCompute(SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr,SCOTCH_Strat * const straptr)313 SCOTCH_graphMapFixedCompute (
314 SCOTCH_Graph * const grafptr, /*+ Graph to order +*/
315 SCOTCH_Mapping * const mappptr, /*+ Mapping to compute +*/
316 SCOTCH_Strat * const straptr) /*+ Mapping strategy +*/
317 {
318 return (SCOTCH_graphRemapFixedCompute (grafptr, mappptr, NULL, 1, NULL, straptr));
319 }
320
321 /*+ This routine computes a remapping
322 *** of the API mapping structure with
323 *** respect to the given strategy.
324 *** It returns:
325 *** - 0 : on success.
326 *** - !0 : on error.
327 +*/
328
329 int
SCOTCH_graphRemapCompute(SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr,SCOTCH_Mapping * const mapoptr,const double emraval,const SCOTCH_Num * vmlotab,SCOTCH_Strat * const straptr)330 SCOTCH_graphRemapCompute (
331 SCOTCH_Graph * const grafptr, /*+ Graph to order +*/
332 SCOTCH_Mapping * const mappptr, /*+ Mapping to compute +*/
333 SCOTCH_Mapping * const mapoptr, /*+ Old mapping +*/
334 const double emraval, /*+ Edge migration ratio +*/
335 const SCOTCH_Num * vmlotab, /*+ Vertex migration cost array +*/
336 SCOTCH_Strat * const straptr) /*+ Mapping strategy +*/
337 {
338 return (graphMapCompute2 (grafptr, mappptr, mapoptr, emraval, vmlotab, 0, straptr));
339 }
340
341 /*+ This routine computes a remapping
342 *** with fixed vertices of the API
343 *** mapping structure with respect
344 *** to the given strategy.
345 *** It returns:
346 *** - 0 : on success.
347 *** - !0 : on error.
348 +*/
349
350 int
SCOTCH_graphRemapFixedCompute(SCOTCH_Graph * const grafptr,SCOTCH_Mapping * const mappptr,SCOTCH_Mapping * const mapoptr,const double emraval,const SCOTCH_Num * vmlotab,SCOTCH_Strat * const straptr)351 SCOTCH_graphRemapFixedCompute (
352 SCOTCH_Graph * const grafptr, /*+ Graph to order +*/
353 SCOTCH_Mapping * const mappptr, /*+ Mapping to compute +*/
354 SCOTCH_Mapping * const mapoptr, /*+ Old mapping +*/
355 const double emraval, /*+ Edge migration ratio +*/
356 const SCOTCH_Num * vmlotab, /*+ Vertex migration cost array +*/
357 SCOTCH_Strat * const straptr) /*+ Mapping strategy +*/
358 {
359 Gnum vfixnbr;
360 Gnum vertnbr;
361 Gnum vertnum;
362
363 const Anum * restrict const pfixtab = ((LibMapping *) mappptr)->parttab;
364
365 for (vertnum = 0, vertnbr = ((Graph *) grafptr)->vertnbr, vfixnbr = 0; /* Compute number of fixed vertices */
366 vertnum < vertnbr; vertnum ++) {
367 if (pfixtab[vertnum] != ~0)
368 vfixnbr ++;
369 }
370
371 return (graphMapCompute2 (grafptr, mappptr, mapoptr, emraval, vmlotab, vfixnbr, straptr));
372 }
373
374 /*+ This routine computes a mapping of the
375 *** given graph structure onto the given
376 *** target architecture with respect to the
377 *** given strategy.
378 *** It returns:
379 *** - 0 : on success.
380 *** - !0 : on error.
381 +*/
382
383 int
SCOTCH_graphMap(SCOTCH_Graph * const grafptr,const SCOTCH_Arch * const archptr,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)384 SCOTCH_graphMap (
385 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
386 const SCOTCH_Arch * const archptr, /*+ Target architecture +*/
387 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
388 SCOTCH_Num * const parttab) /*+ Partition array +*/
389 {
390 SCOTCH_Mapping mappdat;
391 int o;
392
393 SCOTCH_graphMapInit (grafptr, &mappdat, archptr, parttab);
394 o = SCOTCH_graphMapCompute (grafptr, &mappdat, straptr);
395 SCOTCH_graphMapExit (grafptr, &mappdat);
396
397 return (o);
398 }
399
400 /*+ This routine computes a mapping of the
401 *** given graph structure onto the given
402 *** target architecture with respect to the
403 *** given strategy and the fixed vertices in
404 *** maptab.
405 *** It returns:
406 *** - 0 : on success.
407 *** - !0 : on error.
408 +*/
409
410 int
SCOTCH_graphMapFixed(SCOTCH_Graph * const grafptr,const SCOTCH_Arch * const archptr,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)411 SCOTCH_graphMapFixed (
412 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
413 const SCOTCH_Arch * const archptr, /*+ Target architecture +*/
414 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
415 SCOTCH_Num * const parttab) /*+ Partition array +*/
416 {
417 SCOTCH_Mapping mappdat;
418 int o;
419
420 SCOTCH_graphMapInit (grafptr, &mappdat, archptr, parttab);
421 o = SCOTCH_graphMapFixedCompute (grafptr, &mappdat, straptr);
422 SCOTCH_graphMapExit (grafptr, &mappdat);
423
424 return (o);
425 }
426
427 /*+ This routine computes a remapping of the
428 *** given graph structure onto the given
429 *** target architecture with respect to the
430 *** given strategy.
431 *** It returns:
432 *** - 0 : on success.
433 *** - !0 : on error.
434 +*/
435
436 int
SCOTCH_graphRemap(SCOTCH_Graph * const grafptr,const SCOTCH_Arch * const archptr,SCOTCH_Num * const parotab,const double emraval,const SCOTCH_Num * vmlotab,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)437 SCOTCH_graphRemap (
438 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
439 const SCOTCH_Arch * const archptr, /*+ Target architecture +*/
440 SCOTCH_Num * const parotab, /*+ Old partition array +*/
441 const double emraval, /*+ Edge migration ratio +*/
442 const SCOTCH_Num * vmlotab, /*+ Vertex migration cost array +*/
443 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
444 SCOTCH_Num * const parttab) /*+ Partition array +*/
445 {
446 SCOTCH_Mapping mappdat;
447 SCOTCH_Mapping mapodat;
448 int o;
449
450 SCOTCH_graphMapInit (grafptr, &mappdat, archptr, parttab);
451 SCOTCH_graphMapInit (grafptr, &mapodat, archptr, parotab);
452 o = SCOTCH_graphRemapCompute (grafptr, &mappdat, &mapodat, emraval, vmlotab, straptr);
453 SCOTCH_graphMapExit (grafptr, &mapodat);
454 SCOTCH_graphMapExit (grafptr, &mappdat);
455
456 return (o);
457 }
458
459 /*+ This routine computes a remapping of the
460 *** given graph structure onto the given
461 *** target architecture with respect to the
462 *** given strategy and the fixed vertices in
463 *** maptab.
464 *** It returns:
465 *** - 0 : on success.
466 *** - !0 : on error.
467 +*/
468
469 int
SCOTCH_graphRemapFixed(SCOTCH_Graph * const grafptr,const SCOTCH_Arch * const archptr,SCOTCH_Num * const parotab,const double emraval,const SCOTCH_Num * vmlotab,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)470 SCOTCH_graphRemapFixed (
471 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
472 const SCOTCH_Arch * const archptr, /*+ Target architecture +*/
473 SCOTCH_Num * const parotab, /*+ Old partition array +*/
474 const double emraval, /*+ Edge migration ratio +*/
475 const SCOTCH_Num * vmlotab, /*+ Vertex migration cost array +*/
476 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
477 SCOTCH_Num * const parttab) /*+ Partition array +*/
478 {
479 SCOTCH_Mapping mappdat;
480 SCOTCH_Mapping mapodat;
481 int o;
482
483 SCOTCH_graphMapInit (grafptr, &mappdat, archptr, parttab);
484 SCOTCH_graphMapInit (grafptr, &mapodat, archptr, parotab);
485 o = SCOTCH_graphRemapFixedCompute (grafptr, &mappdat, &mapodat, emraval, vmlotab, straptr);
486 SCOTCH_graphMapExit (grafptr, &mapodat);
487 SCOTCH_graphMapExit (grafptr, &mappdat);
488
489 return (o);
490 }
491
492 /*+ This routine computes a partition of
493 *** the given graph structure with respect
494 *** to the given strategy.
495 *** It returns:
496 *** - 0 : on success.
497 *** - !0 : on error.
498 +*/
499
500 int
SCOTCH_graphPart(SCOTCH_Graph * const grafptr,const SCOTCH_Num partnbr,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)501 SCOTCH_graphPart (
502 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
503 const SCOTCH_Num partnbr, /*+ Number of parts +*/
504 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
505 SCOTCH_Num * const parttab) /*+ Partition array +*/
506 {
507 SCOTCH_Arch archdat;
508 int o;
509
510 SCOTCH_archInit (&archdat);
511 SCOTCH_archCmplt (&archdat, partnbr);
512 o = SCOTCH_graphMap (grafptr, &archdat, straptr, parttab);
513 SCOTCH_archExit (&archdat);
514
515 return (o);
516 }
517
518 /*+ This routine computes a partition of
519 *** the given graph structure with respect
520 *** to the given strategy and the fixed
521 *** vertices in maptab.
522 *** It returns:
523 *** - 0 : on success.
524 *** - !0 : on error.
525 +*/
526
527 int
SCOTCH_graphPartFixed(SCOTCH_Graph * const grafptr,const SCOTCH_Num partnbr,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)528 SCOTCH_graphPartFixed (
529 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
530 const SCOTCH_Num partnbr, /*+ Number of parts +*/
531 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
532 SCOTCH_Num * const parttab) /*+ Partition array +*/
533 {
534 SCOTCH_Arch archdat;
535 int o;
536
537 SCOTCH_archInit (&archdat);
538 SCOTCH_archCmplt (&archdat, partnbr);
539 o = SCOTCH_graphMapFixed (grafptr, &archdat, straptr, parttab);
540 SCOTCH_archExit (&archdat);
541
542 return (o);
543 }
544
545 /*+ This routine computes a repartitionning
546 *** of the given graph structure with
547 *** respect to the given strategy.
548 *** It returns:
549 *** - 0 : on success.
550 *** - !0 : on error.
551 +*/
552
553 int
SCOTCH_graphRepart(SCOTCH_Graph * const grafptr,const SCOTCH_Num partnbr,SCOTCH_Num * const parotab,const double emraval,const SCOTCH_Num * const vmlotab,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)554 SCOTCH_graphRepart (
555 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
556 const SCOTCH_Num partnbr, /*+ Number of parts +*/
557 SCOTCH_Num * const parotab, /*+ Old partition array +*/
558 const double emraval, /*+ Edge migration ratio +*/
559 const SCOTCH_Num * const vmlotab, /*+ Vertex migration cost array +*/
560 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
561 SCOTCH_Num * const parttab) /*+ Partition array +*/
562 {
563 SCOTCH_Arch archdat;
564 int o;
565
566 SCOTCH_archInit (&archdat);
567 SCOTCH_archCmplt (&archdat, partnbr);
568 o = SCOTCH_graphRemap (grafptr, &archdat, parotab, emraval, vmlotab, straptr, parttab);
569 SCOTCH_archExit (&archdat);
570
571 return (o);
572 }
573
574 /*+ This routine computes a repartitionning
575 *** of the given graph structure with
576 *** respect to the given strategy and the
577 *** fixed vertices in maptab.
578 *** It returns:
579 *** - 0 : on success.
580 *** - !0 : on error.
581 +*/
582
583 int
SCOTCH_graphRepartFixed(SCOTCH_Graph * const grafptr,const SCOTCH_Num partnbr,SCOTCH_Num * const parotab,const double emraval,const SCOTCH_Num * vmlotab,SCOTCH_Strat * const straptr,SCOTCH_Num * const parttab)584 SCOTCH_graphRepartFixed (
585 SCOTCH_Graph * const grafptr, /*+ Graph to map +*/
586 const SCOTCH_Num partnbr, /*+ Number of parts +*/
587 SCOTCH_Num * const parotab, /*+ Old partition array +*/
588 const double emraval, /*+ Edge migration ratio +*/
589 const SCOTCH_Num * vmlotab, /*+ Vertex migration cost array +*/
590 SCOTCH_Strat * const straptr, /*+ Mapping strategy +*/
591 SCOTCH_Num * const parttab) /*+ Partition array +*/
592 {
593 SCOTCH_Arch archdat;
594 int o;
595
596 SCOTCH_archInit (&archdat);
597 SCOTCH_archCmplt (&archdat, partnbr);
598 o = SCOTCH_graphRemapFixed (grafptr, &archdat, parotab, emraval, vmlotab, straptr, parttab);
599 SCOTCH_archExit (&archdat);
600
601 return (o);
602 }
603
604 /*+ This routine parses the given
605 *** mapping strategy.
606 *** It returns:
607 *** - 0 : if string successfully scanned.
608 *** - !0 : on error.
609 +*/
610
611 int
SCOTCH_stratGraphMap(SCOTCH_Strat * const straptr,const char * const string)612 SCOTCH_stratGraphMap (
613 SCOTCH_Strat * const straptr,
614 const char * const string)
615 {
616 if (*((Strat **) straptr) != NULL)
617 stratExit (*((Strat **) straptr));
618
619 if ((*((Strat **) straptr) = stratInit (&kgraphmapststratab, string)) == NULL) {
620 errorPrint ("SCOTCH_stratGraphMap: error in mapping strategy");
621 return (1);
622 }
623
624 return (0);
625 }
626
627 /*+ This routine provides predefined
628 *** mapping strategies.
629 *** It returns:
630 *** - 0 : if string successfully initialized.
631 *** - !0 : on error.
632 +*/
633
634 int
SCOTCH_stratGraphMapBuild(SCOTCH_Strat * const straptr,const SCOTCH_Num flagval,const SCOTCH_Num partnbr,const double kbalval)635 SCOTCH_stratGraphMapBuild (
636 SCOTCH_Strat * const straptr, /*+ Strategy to create +*/
637 const SCOTCH_Num flagval, /*+ Desired characteristics +*/
638 const SCOTCH_Num partnbr, /*+ Number of expected parts/size +*/
639 const double kbalval) /*+ Desired imbalance ratio +*/
640 {
641 char bufftab[8192]; /* Should be enough */
642 char bbaltab[64];
643 char kbaltab[64];
644 char kmovtab[64];
645 char mvrttab[64];
646 Gunum parttmp; /* "Unsigned" so that ">>" will always insert "0"s */
647 const char * difkptr;
648 const char * difsptr;
649 const char * exasptr;
650 const char * exaxptr;
651
652 sprintf (bbaltab, "%lf", kbalval);
653 sprintf (kbaltab, "%lf", kbalval);
654 sprintf (kmovtab, GNUMSTRING, (Gnum) (((flagval & SCOTCH_STRATQUALITY) != 0) ? 200 : 80));
655 sprintf (mvrttab, GNUMSTRING, (Gnum) (MAX ((20 * partnbr), 10000)));
656
657 strcpy (bufftab, ((flagval & SCOTCH_STRATRECURSIVE) != 0)
658 ? "<RECU>" /* Use only the recursive bipartitioning framework */
659 : "m{vert=<MVRT>,low=<RECU>,asc=b{bnd=<DIFK>f{bal=<KBAL>,move=<KMOV>},org=f{bal=<KBAL>,move=<KMOV>}}}<EXAX>");
660 stringSubst (bufftab, "<RECU>", "r{job=t,map=t,poli=S,bal=<KBAL>,sep=<BSEP><EXAS>}");
661 stringSubst (bufftab, "<BSEP>", ((flagval & SCOTCH_STRATQUALITY) != 0) ? "<BSEQ>|<BSEQ>|<BSEQ>" : "<BSEQ>|<BSEQ>");
662 stringSubst (bufftab, "<BSEQ>", "m{vert=120,low=h{pass=10}f{bal=<BBAL>,move=120},asc=b{bnd=f{bal=<BBAL>,move=120},org=f{bal=<BBAL>,move=120}}}");
663
664 if ((flagval & SCOTCH_STRATSAFETY) != 0)
665 difsptr = "";
666 else
667 difsptr = "d{pass=40}";
668 difkptr = "d{pass=40}";
669
670 if ((flagval & SCOTCH_STRATBALANCE) != 0) {
671 exasptr = "f{bal=<KBAL>}";
672 exaxptr = "x{bal=<KBAL>}f{bal=<KBAL>,move=<KMOV>}";
673 }
674 else {
675 exasptr = "";
676 exaxptr = "";
677 }
678
679 stringSubst (bufftab, "<MVRT>", mvrttab);
680 stringSubst (bufftab, "<EXAX>", exaxptr);
681 stringSubst (bufftab, "<EXAS>", exasptr);
682 stringSubst (bufftab, "<DIFS>", difsptr);
683 stringSubst (bufftab, "<DIFK>", difkptr);
684 stringSubst (bufftab, "<KMOV>", kmovtab);
685 stringSubst (bufftab, "<KBAL>", kbaltab);
686 stringSubst (bufftab, "<BBAL>", bbaltab);
687
688 if (SCOTCH_stratGraphMap (straptr, bufftab) != 0) {
689 errorPrint ("SCOTCH_stratGraphMapBuild: error in sequential mapping strategy");
690 return (1);
691 }
692
693 return (0);
694 }
695
696 /*+ This routine provides predefined
697 *** clustering strategies.
698 *** It returns:
699 *** - 0 : if string successfully initialized.
700 *** - !0 : on error.
701 +*/
702
703 int
SCOTCH_stratGraphClusterBuild(SCOTCH_Strat * const straptr,const SCOTCH_Num flagval,const SCOTCH_Num pwgtval,const double densval,const double bbalval)704 SCOTCH_stratGraphClusterBuild (
705 SCOTCH_Strat * const straptr, /*+ Strategy to create +*/
706 const SCOTCH_Num flagval, /*+ Desired characteristics +*/
707 const SCOTCH_Num pwgtval, /*+ Threshold part weight +*/
708 const double densval, /*+ Threshold density value +*/
709 const double bbalval) /*+ Maximum imbalance ratio +*/
710 {
711 char bufftab[8192]; /* Should be enough */
712 char bbaltab[32];
713 char pwgttab[32];
714 char denstab[32];
715 char * difsptr;
716 char * exasptr;
717
718 sprintf (bbaltab, "%lf", bbalval);
719 sprintf (denstab, "%lf", densval);
720 sprintf (pwgttab, GNUMSTRING, pwgtval);
721
722 strcpy (bufftab, "r{job=u,map=t,poli=L,sep=/((load><PWGT>)&!(edge>vert*<DENS>*(vert-1)))?(<BIPA>m{vert=80,low=h{pass=10}f{bal=<BBAL>,move=80},asc=b{bnd=<DIFS>f{bal=<BBAL>,move=80},org=f{bal=<BBAL>,move=80}}})<EXAS>;}");
723 stringSubst (bufftab, "<BIPA>", ((flagval & SCOTCH_STRATSPEED) != 0) ? ""
724 : "m{vert=80,low=h{pass=10}f{bal=<BBAL>,move=80},asc=b{bnd=<DIFS>f{bal=<BBAL>,move=80},org=f{bal=<BBAL>,move=80}}}|");
725
726 if ((flagval & SCOTCH_STRATBALANCE) != 0)
727 exasptr = "f{bal=0}";
728 else
729 exasptr = "";
730
731 if ((flagval & SCOTCH_STRATSAFETY) != 0)
732 difsptr = "";
733 else
734 difsptr = "(d{pass=40}|)";
735
736 stringSubst (bufftab, "<EXAS>", exasptr);
737 stringSubst (bufftab, "<DIFS>", difsptr);
738 stringSubst (bufftab, "<BBAL>", bbaltab);
739 stringSubst (bufftab, "<DENS>", denstab);
740 stringSubst (bufftab, "<PWGT>", pwgttab);
741
742 if (SCOTCH_stratGraphMap (straptr, bufftab) != 0) {
743 errorPrint ("SCOTCH_stratGraphClusterBuild: error in sequential mapping strategy");
744 return (1);
745 }
746
747 return (0);
748 }
749