1 /* Copyright 2008-2012 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_dgraph_map.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module is the API for the distri- **/
39 /** buted graph mapping routines of the **/
40 /** libSCOTCH library. **/
41 /** **/
42 /** DATES : # Version 5.1 : from : 12 jun 2008 **/
43 /** to 31 aug 2011 **/
44 /** # Version 6.0 : from : 14 nov 2012 **/
45 /** to 29 nov 2012 **/
46 /** **/
47 /************************************************************/
48
49 /*
50 ** The defines and includes.
51 */
52
53 #define LIBRARY
54
55 #include "module.h"
56 #include "common.h"
57 #include "parser.h"
58 #include "dgraph.h"
59 #include "arch.h"
60 #include "dmapping.h"
61 #include "kdgraph.h"
62 #include "kdgraph_map_st.h"
63 #include "library_dmapping.h"
64 #include "ptscotch.h"
65
66 /************************************/
67 /* */
68 /* These routines are the C API for */
69 /* the parallel mapping routines. */
70 /* */
71 /************************************/
72
73 /*+ This routine initializes an API opaque
74 *** mapping with respect to the given source
75 *** graph and the locations of output parameters.
76 *** It returns:
77 *** - 0 : on success.
78 *** - !0 : on error.
79 +*/
80
81 int
SCOTCH_dgraphMapInit(const SCOTCH_Dgraph * const grafptr,SCOTCH_Dmapping * const mappptr,const SCOTCH_Arch * const archptr,SCOTCH_Num * const termloctab)82 SCOTCH_dgraphMapInit (
83 const SCOTCH_Dgraph * const grafptr, /*+ Graph to map +*/
84 SCOTCH_Dmapping * const mappptr, /*+ Mapping structure to initialize +*/
85 const SCOTCH_Arch * const archptr, /*+ Target architecture used to map +*/
86 SCOTCH_Num * const termloctab) /*+ Mapping array +*/
87 {
88 LibDmapping * restrict srcmappptr;
89
90 #ifdef SCOTCH_DEBUG_LIBRARY1
91 if (sizeof (SCOTCH_Dmapping) < sizeof (LibDmapping)) {
92 errorPrint ("SCOTCH_dgraphMapInit: internal error");
93 return (1);
94 }
95 #endif /* SCOTCH_DEBUG_LIBRARY1 */
96
97 srcmappptr = (LibDmapping *) mappptr;
98 srcmappptr->termloctab = ((termloctab == NULL) || ((void *) termloctab == (void *) grafptr)) ? NULL : termloctab;
99 return (dmapInit (&srcmappptr->m, (Arch *) archptr));
100 }
101
102 /*+ This routine frees an API mapping.
103 *** It returns:
104 *** - VOID : in all cases.
105 +*/
106
107 void
SCOTCH_dgraphMapExit(const SCOTCH_Dgraph * const grafptr,SCOTCH_Dmapping * const mappptr)108 SCOTCH_dgraphMapExit (
109 const SCOTCH_Dgraph * const grafptr,
110 SCOTCH_Dmapping * const mappptr)
111 {
112 dmapExit (&((LibDmapping *) mappptr)->m);
113 }
114
115 /*+ This routine saves the contents of
116 *** the given mapping to the given stream.
117 *** It returns:
118 *** - 0 : on success.
119 *** - !0 : on error.
120 +*/
121
122 int
SCOTCH_dgraphMapSave(const SCOTCH_Dgraph * const grafptr,const SCOTCH_Dmapping * const mappptr,FILE * const stream)123 SCOTCH_dgraphMapSave (
124 const SCOTCH_Dgraph * const grafptr, /*+ Graph to map +*/
125 const SCOTCH_Dmapping * const mappptr, /*+ Mapping to save +*/
126 FILE * const stream) /*+ Output stream +*/
127 {
128 return (dmapSave (&((LibDmapping *) mappptr)->m, (Dgraph *) grafptr, stream));
129 }
130
131 /*+ This routine computes a mapping
132 *** of the API mapping structure with
133 *** respect to the given strategy.
134 *** It returns:
135 *** - 0 : on success.
136 *** - !0 : on error.
137 +*/
138
139 int
SCOTCH_dgraphMapCompute(SCOTCH_Dgraph * const grafptr,SCOTCH_Dmapping * const mappptr,SCOTCH_Strat * const stratptr)140 SCOTCH_dgraphMapCompute (
141 SCOTCH_Dgraph * const grafptr, /*+ Graph to map +*/
142 SCOTCH_Dmapping * const mappptr, /*+ Mapping to compute +*/
143 SCOTCH_Strat * const stratptr) /*+ Mapping strategy +*/
144 {
145 Kdgraph mapgrafdat; /* Effective mapping graph */
146 Kdmapping mapmappdat; /* Initial mapping domain */
147 const Strat * mapstratptr; /* Pointer to mapping strategy */
148 LibDmapping * restrict srcmappptr;
149 Dgraph * srcgrafptr;
150 int o;
151
152 srcgrafptr = (Dgraph *) grafptr;
153 srcmappptr = (LibDmapping *) mappptr;
154
155 #ifdef SCOTCH_DEBUG_DGRAPH2
156 if (dgraphCheck (srcgrafptr) != 0) {
157 errorPrint ("SCOTCH_dgraphMapCompute: invalid input graph");
158 return (1);
159 }
160 #endif /* SCOTCH_DEBUG_DGRAPH2 */
161
162 if (*((Strat **) stratptr) == NULL) { /* Set default mapping strategy if necessary */
163 ArchDom archdomnorg;
164
165 archDomFrst (&srcmappptr->m.archdat, &archdomnorg);
166 if (archVar (&srcmappptr->m.archdat))
167 SCOTCH_stratDgraphClusterBuild (stratptr, 0, srcgrafptr->procglbnbr, 1, 1.0, 0.05);
168 else
169 SCOTCH_stratDgraphMapBuild (stratptr, 0, srcgrafptr->procglbnbr, archDomSize (&srcmappptr->m.archdat, &archdomnorg), 0.05);
170 }
171 mapstratptr = *((Strat **) stratptr);
172 if (mapstratptr->tabl != &kdgraphmapststratab) {
173 errorPrint ("SCOTCH_dgraphMapCompute: not a parallel graph mapping strategy");
174 return (1);
175 }
176
177 intRandInit (); /* Check that random number generator is initialized */
178
179 if (kdgraphInit (&mapgrafdat, srcgrafptr, &srcmappptr->m) != 0)
180 return (1);
181 mapmappdat.mappptr = &srcmappptr->m;
182
183 if (((o = kdgraphMapSt (&mapgrafdat, &mapmappdat, mapstratptr)) == 0) && /* Perform mapping */
184 (srcmappptr->termloctab != NULL))
185 o = dmapTerm (&srcmappptr->m, &mapgrafdat.s, srcmappptr->termloctab); /* Use "&mapgrafdat.s" to take advantage of ghost arrays */
186 kdgraphExit (&mapgrafdat);
187
188 return (o);
189 }
190
191 /*+ This routine computes a mapping of the
192 *** given graph structure onto the given
193 *** target architecture with respect to the
194 *** given strategy.
195 *** It returns:
196 *** - 0 : on success.
197 *** - !0 : on error.
198 +*/
199
200 int
SCOTCH_dgraphMap(SCOTCH_Dgraph * const grafptr,const SCOTCH_Arch * const archptr,SCOTCH_Strat * const stratptr,SCOTCH_Num * const termloctab)201 SCOTCH_dgraphMap (
202 SCOTCH_Dgraph * const grafptr, /*+ Graph to map +*/
203 const SCOTCH_Arch * const archptr, /*+ Target architecture +*/
204 SCOTCH_Strat * const stratptr, /*+ Mapping strategy +*/
205 SCOTCH_Num * const termloctab) /*+ Mapping array +*/
206 {
207 SCOTCH_Dmapping mappdat;
208 int o;
209
210 SCOTCH_dgraphMapInit (grafptr, &mappdat, archptr, termloctab);
211 o = SCOTCH_dgraphMapCompute (grafptr, &mappdat, stratptr);
212 SCOTCH_dgraphMapExit (grafptr, &mappdat);
213
214 return (o);
215 }
216
217 /*+ This routine computes a partition of
218 *** the given graph structure with respect
219 *** to the given strategy.
220 *** It returns:
221 *** - 0 : on success.
222 *** - !0 : on error.
223 +*/
224
225 int
SCOTCH_dgraphPart(SCOTCH_Dgraph * const grafptr,const SCOTCH_Num partnbr,SCOTCH_Strat * const stratptr,SCOTCH_Num * const termloctab)226 SCOTCH_dgraphPart (
227 SCOTCH_Dgraph * const grafptr, /*+ Graph to map +*/
228 const SCOTCH_Num partnbr, /*+ Number of parts +*/
229 SCOTCH_Strat * const stratptr, /*+ Mapping strategy +*/
230 SCOTCH_Num * const termloctab) /*+ Mapping array +*/
231 {
232 SCOTCH_Arch archdat;
233 int o;
234
235 SCOTCH_archInit (&archdat);
236 SCOTCH_archCmplt (&archdat, partnbr);
237 o = SCOTCH_dgraphMap (grafptr, &archdat, stratptr, termloctab);
238 SCOTCH_archExit (&archdat);
239
240 return (o);
241 }
242
243 /*+ This routine parses the given
244 *** mapping strategy.
245 *** It returns:
246 *** - 0 : if string successfully scanned.
247 *** - !0 : on error.
248 +*/
249
250 int
SCOTCH_stratDgraphMap(SCOTCH_Strat * const stratptr,const char * const string)251 SCOTCH_stratDgraphMap (
252 SCOTCH_Strat * const stratptr,
253 const char * const string)
254 {
255 if (*((Strat **) stratptr) != NULL)
256 stratExit (*((Strat **) stratptr));
257
258 if ((*((Strat **) stratptr) = stratInit (&kdgraphmapststratab, string)) == NULL) {
259 errorPrint ("SCOTCH_stratDgraphMap: error in parallel mapping strategy");
260 return (1);
261 }
262
263 return (0);
264 }
265
266 /*+ This routine provides predefined
267 *** mapping strategies.
268 *** It returns:
269 *** - 0 : if string successfully initialized.
270 *** - !0 : on error.
271 +*/
272
273 int
SCOTCH_stratDgraphMapBuild(SCOTCH_Strat * const stratptr,const SCOTCH_Num flagval,const SCOTCH_Num procnbr,const SCOTCH_Num partnbr,const double kbalval)274 SCOTCH_stratDgraphMapBuild (
275 SCOTCH_Strat * const stratptr, /*+ Strategy to create +*/
276 const SCOTCH_Num flagval, /*+ Desired characteristics +*/
277 const SCOTCH_Num procnbr, /*+ Number of processes for running +*/
278 const SCOTCH_Num partnbr, /*+ Number of expected parts +*/
279 const double kbalval) /*+ Desired imbalance ratio +*/
280 {
281 char bufftab[8192]; /* Should be enough */
282 char bbaltab[32];
283 char kbaltab[32];
284 char verttab[32];
285 Gnum vertnbr;
286 char * difpptr;
287 char * difsptr;
288 char * exapptr;
289 char * exasptr;
290 char * muceptr;
291
292 sprintf (kbaltab, "%lf", kbalval);
293 sprintf (bbaltab, "%lf", kbalval);
294
295 vertnbr = MAX (2000 * procnbr, 10000);
296 vertnbr = MIN (vertnbr, 100000);
297 sprintf (verttab, GNUMSTRING, vertnbr);
298
299 strcpy (bufftab, "r{bal=<KBAL>,sep=m{vert=<VERT>,asc=b{bnd=<DIFP><MUCE><EXAP>,org=<MUCE><EXAP>},low=q{strat=(<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>},seq=q{strat=(<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>}},seq=r{bal=<KBAL>,poli=S,sep=(<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>}}");
300 stringSubst (bufftab, "<BIPA>", ((flagval & SCOTCH_STRATSPEED) != 0) ? ""
301 : "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}}}|");
302
303 if ((flagval & SCOTCH_STRATSCALABILITY) != 0)
304 muceptr = "/(edge<10000000)?q{strat=f};"; /* Multi-centralization */
305 else
306 muceptr = "q{strat=f}";
307
308 if ((flagval & SCOTCH_STRATBALANCE) != 0) {
309 exapptr = "x{bal=0}";
310 exasptr = "f{bal=0}";
311 }
312 else {
313 exapptr = "x{bal=<KBAL>}"; /* Parallel exactifier */
314 exasptr = "";
315 }
316
317 if ((flagval & SCOTCH_STRATSAFETY) != 0) {
318 difpptr = "";
319 difsptr = "";
320 }
321 else {
322 difpptr = "(d{pass=40}|)";
323 difsptr = "(d{pass=40}|)";
324 }
325
326 stringSubst (bufftab, "<MUCE>", muceptr);
327 stringSubst (bufftab, "<EXAP>", exapptr);
328 stringSubst (bufftab, "<EXAS>", exasptr);
329 stringSubst (bufftab, "<DIFP>", difpptr);
330 stringSubst (bufftab, "<DIFS>", difsptr);
331 stringSubst (bufftab, "<BBAL>", bbaltab);
332 stringSubst (bufftab, "<KBAL>", kbaltab);
333 stringSubst (bufftab, "<VERT>", verttab);
334
335 if (SCOTCH_stratDgraphMap (stratptr, bufftab) != 0) {
336 errorPrint ("SCOTCH_stratDgraphMapBuild: error in parallel mapping strategy");
337 return (1);
338 }
339
340 return (0);
341 }
342
343 /*+ This routine provides predefined
344 *** clustering strategies.
345 *** It returns:
346 *** - 0 : if string successfully initialized.
347 *** - !0 : on error.
348 +*/
349
350 int
SCOTCH_stratDgraphClusterBuild(SCOTCH_Strat * const stratptr,const SCOTCH_Num flagval,const SCOTCH_Num procnbr,const SCOTCH_Num pwgtval,const double densval,const double bbalval)351 SCOTCH_stratDgraphClusterBuild (
352 SCOTCH_Strat * const stratptr, /*+ Strategy to create +*/
353 const SCOTCH_Num flagval, /*+ Desired characteristics +*/
354 const SCOTCH_Num procnbr, /*+ Number of processes for running +*/
355 const SCOTCH_Num pwgtval, /*+ Threshold part load +*/
356 const double densval, /*+ Threshold density value +*/
357 const double bbalval) /*+ Maximum imbalance ratio +*/
358 {
359 char bufftab[8192]; /* Should be enough */
360 char bbaltab[32];
361 char denstab[32];
362 char pwgttab[32];
363 char verttab[32];
364 Gnum vertnbr;
365 char * difpptr;
366 char * difsptr;
367 char * exapptr;
368 char * exasptr;
369 char * muceptr;
370
371 sprintf (bbaltab, "%lf", bbalval);
372 sprintf (denstab, "%lf", densval);
373 sprintf (pwgttab, GNUMSTRING, pwgtval);
374
375 vertnbr = MAX (2000 * procnbr, 10000);
376 vertnbr = MIN (vertnbr, 100000);
377 sprintf (verttab, GNUMSTRING, vertnbr);
378
379 strcpy (bufftab, "r{sep=/((load><PWGT>)&!(edge>vert*<DENS>*(vert-1)))?m{vert=<VERT>,asc=b{bnd=<DIFP><MUCE><EXAP>,org=<MUCE><EXAP>},low=q{strat=(<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>},seq=q{strat=/((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>;}};,seq=r{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>;}}");
380 stringSubst (bufftab, "<BIPA>", ((flagval & SCOTCH_STRATSPEED) != 0) ? ""
381 : "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}}}|");
382
383 if ((flagval & SCOTCH_STRATSCALABILITY) != 0)
384 muceptr = "/(edge<10000000)?q{strat=f};"; /* Multi-centralization */
385 else
386 muceptr = "q{strat=f}";
387
388 if ((flagval & SCOTCH_STRATBALANCE) != 0) {
389 exapptr = "x{bal=0}";
390 exasptr = "f{bal=0}";
391 }
392 else {
393 exapptr = "x{bal=<BBAL>}"; /* Parallel exactifier */
394 exasptr = "";
395 }
396
397 if ((flagval & SCOTCH_STRATSAFETY) != 0) {
398 difpptr = "";
399 difsptr = "";
400 }
401 else {
402 difpptr = "(d{pass=40}|)";
403 difsptr = "(d{pass=40}|)";
404 }
405
406 stringSubst (bufftab, "<MUCE>", muceptr);
407 stringSubst (bufftab, "<EXAP>", exapptr);
408 stringSubst (bufftab, "<EXAS>", exasptr);
409 stringSubst (bufftab, "<DIFP>", difpptr);
410 stringSubst (bufftab, "<DIFS>", difsptr);
411 stringSubst (bufftab, "<BBAL>", bbaltab);
412 stringSubst (bufftab, "<DENS>", denstab);
413 stringSubst (bufftab, "<PWGT>", pwgttab);
414 stringSubst (bufftab, "<VERT>", verttab);
415
416 if (SCOTCH_stratDgraphMap (stratptr, bufftab) != 0) {
417 errorPrint ("SCOTCH_stratDgraphClusterBuild: error in parallel mapping strategy");
418 return (1);
419 }
420
421 return (0);
422 }
423