1 /* Copyright 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 : dgord.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** Cedric CHEVALIER (v5.0) **/
38 /** **/
39 /** FUNCTION : Part of a parallel sparse matrix **/
40 /** ordering software. **/
41 /** This module contains the main function. **/
42 /** **/
43 /** DATES : # Version 5.0 : from : 30 apr 2006 **/
44 /** to : 16 jun 2008 **/
45 /** # Version 5.1 : from : 26 oct 2008 **/
46 /** to : 14 feb 2011 **/
47 /** # Version 6.0 : from : 01 jan 2012 **/
48 /** to : 12 nov 2014 **/
49 /** **/
50 /************************************************************/
51
52 /*
53 ** The defines and includes.
54 */
55
56 #define DGORD
57 #define SCOTCH_PTSCOTCH
58
59 #include <sys/time.h>
60
61 #include "module.h"
62 #include "common.h"
63 #include "ptscotch.h"
64 #include "dgord.h"
65
66 /*
67 ** The static and global definitions.
68 */
69
70 static int C_fileNum = 0; /* Number of file in arg list */
71 static File C_fileTab[C_FILENBR] = { /* File array */
72 { "r" },
73 { "w" },
74 { "w" },
75 { "w" },
76 { "w" } };
77
78 static const char * C_usageList[] = {
79 "dgord [<input source file> [<output ordering file> [<output log file>]]] <options>",
80 " -b : Output block ordering data instead of plain ordering data",
81 " -c<opt> : Choose default ordering strategy according to one or several of <opt>:",
82 " b : enforce load balance as much as possible",
83 " q : privilege quality over speed (default)",
84 " s : privilege speed over quality",
85 " t : enforce safety",
86 " x : enforce scalability",
87 " -h : Display this help",
88 " -m<file> : Save column block mapping data to <file>",
89 " -o<strat> : Set parallel ordering strategy (see user's manual)",
90 " -r<num> : Set root process for centralized files (default is 0)",
91 " -t<file> : Save partitioning tree data to <file>",
92 " -V : Print program version and copyright",
93 " -v<verb> : Set verbose mode to <verb> :",
94 " a : memory allocation information",
95 " s : strategy information",
96 " t : timing information",
97 "",
98 "See default strategy with option '-vs'",
99 NULL };
100
101 /*********************/
102 /* */
103 /* The main routine. */
104 /* */
105 /*********************/
106
107 int
main(int argc,char * argv[])108 main (
109 int argc,
110 char * argv[])
111 {
112 SCOTCH_Dgraph grafdat;
113 SCOTCH_Dordering ordedat;
114 SCOTCH_Strat stradat;
115 SCOTCH_Num straval;
116 char * straptr;
117 int flagval;
118 int procglbnbr;
119 int proclocnum;
120 int protglbnum; /* Root process */
121 Clock runtime[2]; /* Timing variables */
122 double reduloctab[12]; /* 3 * (min, max, sum) */
123 double reduglbtab[12];
124 MPI_Datatype redutype;
125 MPI_Op reduop;
126 int i, j;
127 #ifdef SCOTCH_PTHREAD
128 int thrdlvlreqval;
129 int thrdlvlproval;
130 #endif /* SCOTCH_PTHREAD */
131
132 errorProg ("dgord");
133
134 #ifdef SCOTCH_PTHREAD
135 thrdlvlreqval = MPI_THREAD_MULTIPLE;
136 if (MPI_Init_thread (&argc, &argv, thrdlvlreqval, &thrdlvlproval) != MPI_SUCCESS)
137 errorPrint ("main: Cannot initialize (1)");
138 if (thrdlvlreqval > thrdlvlproval)
139 errorPrint ("main: MPI implementation is not thread-safe: recompile without SCOTCH_PTHREAD");
140 #else /* SCOTCH_PTHREAD */
141 if (MPI_Init (&argc, &argv) != MPI_SUCCESS)
142 errorPrint ("main: Cannot initialize (2)");
143 #endif /* SCOTCH_PTHREAD */
144
145 MPI_Comm_size (MPI_COMM_WORLD, &procglbnbr); /* Get communicator data */
146 MPI_Comm_rank (MPI_COMM_WORLD, &proclocnum);
147 protglbnum = 0; /* Assume root process is process 0 */
148
149 if ((argc >= 2) && (argv[1][0] == '?')) { /* If need for help */
150 usagePrint (stdout, C_usageList);
151 return (0);
152 }
153
154 SCOTCH_randomProc (proclocnum); /* Record process number to initialize pseudo-random seed */
155
156 flagval = C_FLAGNONE; /* Default behavior */
157 straval = 0; /* No strategy flags */
158 straptr = NULL;
159 SCOTCH_stratInit (&stradat);
160
161 fileBlockInit (C_fileTab, C_FILENBR); /* Set default stream pointers */
162
163 for (i = 1; i < argc; i ++) { /* Loop for all option codes */
164 if ((argv[i][0] != '-') || (argv[i][1] == '\0') || (argv[i][1] == '.')) { /* If found a file name */
165 if (C_fileNum < C_FILEARGNBR) /* File name has been given */
166 fileBlockName (C_fileTab, C_fileNum ++) = argv[i];
167 else
168 errorPrint ("main: too many file names given");
169 }
170 else { /* If found an option name */
171 switch (argv[i][1]) {
172 case 'B' :
173 case 'b' :
174 flagval |= C_FLAGBLOCK;
175 break;
176 case 'C' :
177 case 'c' : /* Strategy selection parameters */
178 for (j = 2; argv[i][j] != '\0'; j ++) {
179 switch (argv[i][j]) {
180 case 'B' :
181 case 'b' :
182 straval |= SCOTCH_STRATBALANCE;
183 break;
184 case 'Q' :
185 case 'q' :
186 straval |= SCOTCH_STRATQUALITY;
187 break;
188 case 'S' :
189 case 's' :
190 straval |= SCOTCH_STRATSPEED;
191 break;
192 case 'T' :
193 case 't' :
194 straval |= SCOTCH_STRATSAFETY;
195 break;
196 case 'X' :
197 case 'x' :
198 straval |= SCOTCH_STRATSCALABILITY;
199 break;
200 default :
201 errorPrint ("main: invalid strategy selection option '%c'", argv[i][j]);
202 }
203 }
204 break;
205 #ifdef SCOTCH_DEBUG_ALL
206 case 'D' :
207 case 'd' :
208 flagval |= C_FLAGDEBUG;
209 break;
210 #endif /* SCOTCH_DEBUG_ALL */
211 case 'H' : /* Give the usage message */
212 case 'h' :
213 usagePrint (stdout, C_usageList);
214 return (0);
215 case 'M' : /* Output separator mapping */
216 case 'm' :
217 flagval |= C_FLAGMAPOUT;
218 if (argv[i][2] != '\0')
219 C_filenamemapout = &argv[i][2];
220 break;
221 case 'O' : /* Ordering strategy */
222 case 'o' :
223 straptr = &argv[i][2];
224 SCOTCH_stratExit (&stradat);
225 SCOTCH_stratInit (&stradat);
226 SCOTCH_stratDgraphOrder (&stradat, straptr);
227 break;
228 case 'R' : /* Root process (if necessary) */
229 case 'r' :
230 protglbnum = atoi (&argv[i][2]);
231 if ((protglbnum < 0) ||
232 (protglbnum >= procglbnbr) ||
233 ((protglbnum == 0) && (argv[i][2] != '0')))
234 errorPrint ("main: invalid root process number");
235 break;
236 case 'T' : /* Output separator tree */
237 case 't' :
238 flagval |= C_FLAGTREOUT;
239 if (argv[i][2] != '\0')
240 C_filenametreout = &argv[i][2];
241 break;
242 case 'V' :
243 fprintf (stderr, "dgord, version " SCOTCH_VERSION_STRING "\n");
244 fprintf (stderr, "Copyright 2007-2012,2014 IPB, Universite de Bordeaux, INRIA & CNRS, France\n");
245 fprintf (stderr, "This software is libre/free software under CeCILL-C -- see the user's manual for more information\n");
246 return (0);
247 case 'v' : /* Output control info */
248 for (j = 2; argv[i][j] != '\0'; j ++) {
249 switch (argv[i][j]) {
250 case 'A' :
251 case 'a' :
252 #ifdef COMMON_MEMORY_TRACE
253 flagval |= C_FLAGVERBMEM;
254 #else /* COMMON_MEMORY_TRACE */
255 errorPrint ("main: not compiled with COMMON_MEMORY_TRACE");
256 #endif /* COMMON_MEMORY_TRACE */
257 break;
258 case 'S' :
259 case 's' :
260 flagval |= C_FLAGVERBSTR;
261 break;
262 case 'T' :
263 case 't' :
264 flagval |= C_FLAGVERBTIM;
265 break;
266 default :
267 errorPrint ("main: unprocessed parameter '%c' in '%s'", argv[i][j], argv[i]);
268 }
269 }
270 break;
271 default :
272 errorPrint ("main: unprocessed option '%s'", argv[i]);
273 }
274 }
275 }
276
277 #ifdef SCOTCH_DEBUG_ALL
278 if ((flagval & C_FLAGDEBUG) != 0) {
279 fprintf (stderr, "Proc %4d of %d, pid %d\n", proclocnum, procglbnbr, getpid ());
280 if (proclocnum == protglbnum) { /* Synchronize on keybord input */
281 char c;
282
283 printf ("Waiting for key press...\n");
284 scanf ("%c", &c);
285 }
286 MPI_Barrier (MPI_COMM_WORLD);
287 }
288 #endif /* SCOTCH_DEBUG_ALL */
289
290 fileBlockOpenDist (C_fileTab, C_FILENBR, procglbnbr, proclocnum, protglbnum); /* Open all files */
291
292 clockInit (&runtime[0]);
293 clockStart (&runtime[0]);
294
295 SCOTCH_dgraphInit (&grafdat, MPI_COMM_WORLD);
296 SCOTCH_dgraphLoad (&grafdat, C_filepntrsrcinp, -1, 0);
297
298 if (straval != 0) {
299 if (straptr != NULL)
300 errorPrint ("main: options '-c' and '-o' are exclusive");
301
302 SCOTCH_stratDgraphOrderBuild (&stradat, straval, (SCOTCH_Num) procglbnbr, 0, 0.2);
303 }
304
305 clockStop (&runtime[0]); /* Get input time */
306 clockInit (&runtime[1]);
307
308 #ifdef SCOTCH_DEBUG_ALL
309 if ((flagval & C_FLAGDEBUG) != 0)
310 MPI_Barrier (MPI_COMM_WORLD);
311 #endif /* SCOTCH_DEBUG_ALL */
312
313 clockStart (&runtime[1]);
314
315 SCOTCH_dgraphGhst (&grafdat); /* Compute it once for good */
316
317 SCOTCH_dgraphOrderInit (&grafdat, &ordedat);
318 SCOTCH_dgraphOrderCompute (&grafdat, &ordedat, &stradat);
319
320 clockStop (&runtime[1]); /* Get ordering time */
321
322 #ifdef SCOTCH_DEBUG_ALL
323 if ((flagval & C_FLAGDEBUG) != 0)
324 MPI_Barrier (MPI_COMM_WORLD);
325 #endif /* SCOTCH_DEBUG_ALL */
326
327 clockStart (&runtime[0]);
328
329 if (proclocnum == protglbnum) {
330 if ((flagval & C_FLAGBLOCK) == 0)
331 SCOTCH_dgraphOrderSave (&grafdat, &ordedat, C_filepntrordout);
332 else
333 SCOTCH_dgraphOrderSaveBlock (&grafdat, &ordedat, C_filepntrordout);
334 if ((flagval & C_FLAGMAPOUT) != 0) /* If mapping wanted */
335 SCOTCH_dgraphOrderSaveMap (&grafdat, &ordedat, C_filepntrmapout); /* Write mapping */
336 if ((flagval & C_FLAGTREOUT) != 0) /* If separator tree wanted */
337 SCOTCH_dgraphOrderSaveTree (&grafdat, &ordedat, C_filepntrtreout); /* Write tree */
338 }
339 else {
340 if ((flagval & C_FLAGBLOCK) == 0)
341 SCOTCH_dgraphOrderSave (&grafdat, &ordedat, NULL);
342 else
343 SCOTCH_dgraphOrderSaveBlock (&grafdat, &ordedat, NULL);
344 if ((flagval & C_FLAGMAPOUT) != 0)
345 SCOTCH_dgraphOrderSaveMap (&grafdat, &ordedat, NULL);
346 if ((flagval & C_FLAGTREOUT) != 0)
347 SCOTCH_dgraphOrderSaveTree (&grafdat, &ordedat, NULL);
348 }
349
350 clockStop (&runtime[0]);
351
352 #ifdef SCOTCH_DEBUG_ALL
353 if ((flagval & C_FLAGDEBUG) != 0)
354 MPI_Barrier (MPI_COMM_WORLD);
355 #endif /* SCOTCH_DEBUG_ALL */
356
357 MPI_Type_contiguous (3, MPI_DOUBLE, &redutype);
358 MPI_Type_commit (&redutype);
359 MPI_Op_create ((MPI_User_function *) dgordStatReduceOp, 1, &reduop);
360
361 if ((flagval & C_FLAGVERBTIM) != 0) {
362 reduloctab[0] =
363 reduloctab[1] =
364 reduloctab[2] = (double) clockVal (&runtime[1]);
365 reduloctab[3] =
366 reduloctab[4] =
367 reduloctab[5] = (double) clockVal (&runtime[0]);
368 reduloctab[6] =
369 reduloctab[7] =
370 reduloctab[8] = reduloctab[0] + reduloctab[3];
371 MPI_Allreduce (&reduloctab[0], &reduglbtab[0], 3, redutype, reduop, MPI_COMM_WORLD);
372 }
373 #ifdef COMMON_MEMORY_TRACE
374 if ((flagval & C_FLAGVERBMEM) != 0) {
375 reduloctab[9] =
376 reduloctab[10] =
377 reduloctab[11] = (double) memMax ();
378 MPI_Allreduce (&reduloctab[9], &reduglbtab[9], 1, redutype, reduop, MPI_COMM_WORLD);
379 }
380 #endif /* COMMON_MEMORY_TRACE */
381
382 MPI_Op_free (&reduop);
383 MPI_Type_free (&redutype);
384
385 if (C_filepntrlogout != NULL) {
386 if ((flagval & C_FLAGVERBSTR) != 0) {
387 fprintf (C_filepntrlogout, "S\tStrat=");
388 SCOTCH_stratSave (&stradat, C_filepntrlogout);
389 putc ('\n', C_filepntrlogout);
390 }
391 if ((flagval & C_FLAGVERBTIM) != 0) {
392 fprintf (C_filepntrlogout, "T\tOrder\tmin=%g\tmax=%g\tavg=%g\nT\tI/O\tmin=%g\tmax=%g\tavg=%g\nT\tTotal\tmin=%g\tmax=%g\tavg=%g\n",
393 reduglbtab[0], reduglbtab[1], reduglbtab[2] / (double) procglbnbr,
394 reduglbtab[3], reduglbtab[4], reduglbtab[5] / (double) procglbnbr,
395 reduglbtab[6], reduglbtab[7], reduglbtab[8] / (double) procglbnbr);
396 }
397 #ifdef COMMON_MEMORY_TRACE
398 if ((flagval & C_FLAGVERBMEM) != 0)
399 fprintf (C_filepntrlogout, "A\tMemory\tmin=%g\tmax=%g\tavg=%g\n",
400 reduglbtab[9], reduglbtab[10], reduglbtab[11] / (double) procglbnbr);
401 #endif /* COMMON_MEMORY_TRACE */
402 }
403
404 fileBlockClose (C_fileTab, C_FILENBR); /* Always close explicitely to end eventual (un)compression tasks */
405
406 SCOTCH_dgraphOrderExit (&grafdat, &ordedat);
407 SCOTCH_dgraphExit (&grafdat);
408 SCOTCH_stratExit (&stradat);
409
410 MPI_Finalize ();
411 #ifdef COMMON_PTHREAD
412 pthread_exit ((void *) 0); /* Allow potential (un)compression tasks to complete */
413 #endif /* COMMON_PTHREAD */
414 return (0);
415 }
416
417 /* Reduction routine for statistics output.
418 */
419
420 void
dgordStatReduceOp(double * in,double * inout,int * len,MPI_Datatype * datatype)421 dgordStatReduceOp (
422 double * in,
423 double * inout,
424 int * len,
425 MPI_Datatype * datatype)
426 {
427 int i;
428
429 for (i = 0; i < *len; i ++) {
430 inout[3 * i] = MIN (in[3 * i], inout[3 * i]);
431 inout[3 * i + 1] = MAX (in[3 * i + 1], inout[3 * i + 1]);
432 inout[3 * i + 2] = in[3 * i + 2] + inout[3 * i + 2];
433 }
434 }
435