1 /* Copyright 2004,2007,2008,2010-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 : gotst.c **/
35 /** **/
36 /** AUTHORS : Francois PELLEGRINI **/
37 /** Bruno MARCUSSEAU (v3.1) **/
38 /** **/
39 /** FUNCTION : Graph symbolic factorizer. **/
40 /** This module contains the main function. **/
41 /** **/
42 /** DATES : # Version 4.0 : from : 27 jan 2004 **/
43 /** to : 28 nov 2005 **/
44 /** # Version 5.0 : from : 25 jun 2007 **/
45 /** to : 16 mar 2008 **/
46 /** # Version 5.1 : from : 20 apr 2010 **/
47 /** to : 14 feb 2011 **/
48 /** # Version 6.0 : from : 01 jan 2012 **/
49 /** to : 12 nov 2014 **/
50 /** **/
51 /** NOTES : # The cost analysis routine leaves the **/
52 /** memory management to malloc and free **/
53 /** because it is assumed to be the most **/
54 /** efficient to merge free blocks and **/
55 /** reallocate them. **/
56 /** **/
57 /************************************************************/
58
59 /*
60 ** The defines and includes.
61 */
62
63 #define GOTST
64
65 #include "module.h"
66 #include "common.h"
67 #include "scotch.h"
68 #include "gotst.h"
69
70 /*
71 ** The static and global variables.
72 */
73
74 static int C_fileNum = 0; /* Number of file in arg list */
75 static File C_fileTab[3] = { /* File array */
76 { "r" },
77 { "r" },
78 { "w" } };
79
80 static const char * C_usageList[] = {
81 "gotst [<input graph file> [<input ordering file> [<output data file>]]] <options>",
82 " -h : Display this help",
83 " -V : Print program version and copyright",
84 NULL };
85
86 /*****************************/
87 /* */
88 /* This is the main function */
89 /* */
90 /*****************************/
91
92 int
main(int argc,char * argv[])93 main (
94 int argc,
95 char * argv[])
96 {
97 SCOTCH_Graph grafdat;
98 SCOTCH_Num vertnbr;
99 SCOTCH_Num * verttab;
100 SCOTCH_Num * vendtab;
101 SCOTCH_Num edgenbr;
102 SCOTCH_Num * edgetab;
103 SCOTCH_Num baseval;
104 SCOTCH_Ordering ordedat;
105 SCOTCH_Num * permtab;
106 SCOTCH_Num * peritab;
107 int i;
108
109 errorProg ("gotst");
110
111 if ((argc >= 2) && (argv[1][0] == '?')) { /* If need for help */
112 usagePrint (stdout, C_usageList);
113 return (0);
114 }
115
116 fileBlockInit (C_fileTab, C_FILENBR); /* Set default stream pointers */
117
118 for (i = 1; i < argc; i ++) { /* Loop for all option codes */
119 if ((argv[i][0] != '-') || (argv[i][1] == '\0') || (argv[i][1] == '.')) { /* If found a file name */
120 if (C_fileNum < C_FILEARGNBR) /* File name has been given */
121 fileBlockName (C_fileTab, C_fileNum ++) = argv[i];
122 else {
123 errorPrint ("main: too many file names given");
124 return (1);
125 }
126 }
127 else { /* If found an option name */
128 switch (argv[i][1]) {
129 case 'H' : /* Give help */
130 case 'h' :
131 usagePrint (stdout, C_usageList);
132 return (0);
133 case 'V' :
134 fprintf (stderr, "gotst, version " SCOTCH_VERSION_STRING "\n");
135 fprintf (stderr, "Copyright 2004,2007,2008,2010-2012,2014 IPB, Universite de Bordeaux, INRIA & CNRS, France\n");
136 fprintf (stderr, "This software is libre/free software under CeCILL-C -- see the user's manual for more information\n");
137 return (0);
138 default :
139 errorPrint ("main: unprocessed option '%s'", argv[i]);
140 return (1);
141 }
142 }
143 }
144
145 fileBlockOpen (C_fileTab, C_FILENBR); /* Open all files */
146
147 SCOTCH_graphInit (&grafdat);
148 SCOTCH_graphLoad (&grafdat, C_filepntrgrfinp, -1, 3);
149 SCOTCH_graphData (&grafdat, &baseval, &vertnbr, &verttab, &vendtab, NULL, NULL, &edgenbr, &edgetab, NULL);
150 #ifdef SCOTCH_DEBUG_ALL
151 if (vendtab != (verttab + 1)) {
152 errorPrint ("main: graph should be compact");
153 return (1);
154 }
155 #endif /* SCOTCH_DEBUG_ALL */
156 if (memAllocGroup ((void **) (void *)
157 &peritab, (size_t) (vertnbr * sizeof (SCOTCH_Num)),
158 &permtab, (size_t) (vertnbr * sizeof (SCOTCH_Num)), NULL) == NULL) {
159 errorPrint ("main: out of memory");
160 return (1);
161 }
162 SCOTCH_graphOrderInit (&grafdat, &ordedat, permtab, peritab, NULL, NULL, NULL);
163 SCOTCH_graphOrderLoad (&grafdat, &ordedat, C_filepntrordinp);
164 if (SCOTCH_graphOrderCheck (&grafdat, &ordedat) != 0) {
165 errorPrint ("main: invalid ordering");
166 return (1);
167 }
168
169 factorView (baseval, vertnbr, verttab, edgenbr, edgetab, permtab, peritab, C_filepntrdatout);
170
171 fileBlockClose (C_fileTab, C_FILENBR); /* Always close explicitely to end eventual (un)compression tasks */
172
173 memFree (peritab);
174 SCOTCH_graphOrderExit (&grafdat, &ordedat);
175 SCOTCH_graphExit (&grafdat);
176
177 #ifdef COMMON_PTHREAD
178 pthread_exit ((void *) 0); /* Allow potential (un)compression tasks to complete */
179 #endif /* COMMON_PTHREAD */
180 return (0);
181 }
182
183 /*************************************/
184 /* */
185 /* These routines compute statistics */
186 /* on orderings. */
187 /* */
188 /*************************************/
189
190 static
191 int
factorView(const SCOTCH_Num baseval,const SCOTCH_Num vertnbr,const SCOTCH_Num * const verttab,const SCOTCH_Num edgenbr,const SCOTCH_Num * const edgetab,const SCOTCH_Num * const permtab,const SCOTCH_Num * const peritab,FILE * restrict const stream)192 factorView (
193 const SCOTCH_Num baseval,
194 const SCOTCH_Num vertnbr,
195 const SCOTCH_Num * const verttab,
196 const SCOTCH_Num edgenbr,
197 const SCOTCH_Num * const edgetab,
198 const SCOTCH_Num * const permtab,
199 const SCOTCH_Num * const peritab,
200 FILE * restrict const stream)
201 {
202 SCOTCH_Num * restrict ldadtab;
203 SCOTCH_Num * restrict lsontab;
204 SCOTCH_Num * restrict lbrotab;
205 SCOTCH_Num * restrict fnnztab;
206 double fopcsum;
207 double heigsum;
208 FactorStat statdat;
209 SCOTCH_Num vertnum;
210 int o;
211
212 if (memAllocGroup ((void **) (void *)
213 &ldadtab, (size_t) (vertnbr * sizeof (SCOTCH_Num)),
214 &lsontab, (size_t) (vertnbr * sizeof (SCOTCH_Num)),
215 &lbrotab, (size_t) (vertnbr * sizeof (SCOTCH_Num)),
216 &fnnztab, (size_t) (vertnbr * sizeof (SCOTCH_Num)), NULL) == NULL) {
217 errorPrint ("factorView: out of memory");
218 return (1);
219 }
220 statdat.ldadtax = ldadtab - baseval;
221 statdat.lsontax = lsontab - baseval;
222 statdat.lbrotax = lbrotab - baseval;
223 statdat.fnnztax = fnnztab - baseval;
224
225 if (factorView2 (baseval, vertnbr, verttab - baseval, edgetab - baseval, permtab - baseval, peritab - baseval,
226 ldadtab - baseval, lsontab - baseval, lbrotab - baseval, fnnztab - baseval) != 0) {
227 errorPrint ("factorView: factored matrix too large");
228 memFree (ldadtab); /* Free group leader */
229 return (1);
230 }
231
232 statdat.heigmin = SCOTCH_NUMMAX;
233 statdat.heigmax =
234 statdat.heignbr = 0;
235 heigsum = 0.0L;
236 for (vertnum = 0; vertnum < vertnbr; vertnum ++) { /* Get height sum */
237 if (ldadtab[vertnum] == -1) /* If column is a root */
238 factorView3 (&statdat, 1, vertnum + baseval, &heigsum); /* Scan subtree */
239 }
240 statdat.heigavg = heigsum / (double) statdat.heignbr;
241 statdat.heigdlt = 0.0L;
242 statdat.fnnzsum = 0.0L;
243 fopcsum = 0.0L;
244 for (vertnum = 0; vertnum < vertnbr; vertnum ++) { /* Get delta */
245 if (ldadtab[vertnum] == -1) /* If column is a root */
246 factorView4 (&statdat, 1, vertnum + baseval, &fopcsum);
247 }
248 statdat.heigdlt /= (double) statdat.heignbr;
249
250 o = (fprintf (stream, "O\tLeaf=" SCOTCH_NUMSTRING "\nO\tHeight min=" SCOTCH_NUMSTRING "\tmax=" SCOTCH_NUMSTRING "\tavg=%f\tdlt=%f (%5.2f)\n", /* Write tree height statistics */
251 (SCOTCH_Num) statdat.heignbr, (SCOTCH_Num) statdat.heigmin, (SCOTCH_Num) statdat.heigmax,
252 statdat.heigavg, statdat.heigdlt, ((statdat.heigdlt / statdat.heigavg) * (double) 100.0L)) == EOF);
253
254 o |= (fprintf (stream, "O\tNNZ=%e\nO\tOPC=%e\n",
255 statdat.fnnzsum,
256 fopcsum) == EOF);
257
258 if (o != 0)
259 errorPrint ("factorView: bad output");
260
261 memFree (ldadtab); /* Free group leader */
262
263 return (o);
264 }
265
266 static
267 int
factorView2(const SCOTCH_Num baseval,const SCOTCH_Num vertnbr,const SCOTCH_Num * const verttax,const SCOTCH_Num * const edgetax,const SCOTCH_Num * const permtax,const SCOTCH_Num * const peritax,SCOTCH_Num * restrict ldadtax,SCOTCH_Num * restrict lsontax,SCOTCH_Num * restrict lbrotax,SCOTCH_Num * restrict fnnztax)268 factorView2 (
269 const SCOTCH_Num baseval,
270 const SCOTCH_Num vertnbr,
271 const SCOTCH_Num * const verttax,
272 const SCOTCH_Num * const edgetax,
273 const SCOTCH_Num * const permtax,
274 const SCOTCH_Num * const peritax,
275 SCOTCH_Num * restrict ldadtax,
276 SCOTCH_Num * restrict lsontax,
277 SCOTCH_Num * restrict lbrotax,
278 SCOTCH_Num * restrict fnnztax)
279 {
280 SCOTCH_Num * restrict frowtab;
281 SCOTCH_Num * restrict fnxttab;
282 SCOTCH_Num ** restrict facttax;
283 SCOTCH_Num vertnnd;
284 SCOTCH_Num pcolnum;
285
286 memSet (lsontax + baseval, ~0, vertnbr * sizeof (SCOTCH_Num)); /* Assume columns have no sons at all */
287
288 if (memAllocGroup ((void **) (void *)
289 &frowtab, (size_t) ((vertnbr + 1) * sizeof (SCOTCH_Num)),
290 &fnxttab, (size_t) ((vertnbr + 1) * sizeof (SCOTCH_Num)),
291 &facttax, (size_t) (vertnbr * sizeof (SCOTCH_Num *)), NULL) == NULL) {
292 errorPrint ("factorView2: out of memory (1)");
293 return (1);
294 }
295 memSet (facttax, 0, vertnbr * sizeof (SCOTCH_Num *)); /* Set all factored column pointers to NULL */
296 facttax -= baseval;
297
298 vertnnd = vertnbr + baseval;
299 for (pcolnum = baseval; pcolnum < vertnnd; pcolnum ++) { /* For all columns of the permuted matrix */
300 SCOTCH_Num * fcoltab;
301 SCOTCH_Num * restrict fcolptr;
302 SCOTCH_Num frownbr;
303 SCOTCH_Num frowidx;
304 SCOTCH_Num frowidd;
305 SCOTCH_Num scolnum;
306 SCOTCH_Num icolnum;
307 SCOTCH_Num irownum;
308 SCOTCH_Num dcolnum;
309
310 icolnum = peritax[pcolnum]; /* Get the original number of the column */
311
312 frownbr = 1; /* Start array of factored terms for column */
313 frowtab[0] = pcolnum; /* Add diagonal element as unmoveable starter */
314 for (irownum = verttax[icolnum]; irownum < verttax[icolnum + 1]; irownum ++) {
315 SCOTCH_Num prownum;
316
317 prownum = permtax[edgetax[irownum]]; /* Get permuted row */
318
319 if (prownum >= pcolnum)
320 frowtab[frownbr ++] = prownum;
321 }
322 intSort1asc1 (frowtab + 1, frownbr - 1); /* Sort rows in ascending order */
323
324 frowtab[frownbr ++] = vertnnd; /* Add trailer */
325 for (frowidx = 0; frowidx < (frownbr - 1); frowidx ++) /* Create initial links */
326 fnxttab[frowidx] = frowidx + 1;
327 frowidd = frowidx; /* Save index of trailer */
328
329 for (scolnum = lsontax[pcolnum]; scolnum != -1; scolnum = lbrotax[scolnum]) { /* For all son columns in elimination tree */
330 const SCOTCH_Num * restrict srowtab;
331 SCOTCH_Num srownbr;
332 SCOTCH_Num srowidx;
333 SCOTCH_Num frowidx;
334 SCOTCH_Num foldidx;
335 SCOTCH_Num frownum;
336
337 srowtab = facttax[scolnum]; /* Point to array of factors for son column */
338 srownbr = fnnztax[scolnum]; /* Get size of array */
339 for (srowidx = 1, frowidx = 0, foldidx = -1, frownum = frowtab[frowidx];
340 srowidx < srownbr; srowidx ++) {
341 SCOTCH_Num srownum;
342
343 srownum = srowtab[srowidx];
344
345 while (frownum < srownum) { /* While factor to add not in place */
346 foldidx = frowidx; /* Skip to next position */
347 frowidx = fnxttab[frowidx];
348 frownum = frowtab[frowidx];
349 }
350 if (srownum == frownum) /* If factor already in column */
351 continue;
352
353 frowtab[frownbr] = srownum; /* Add new slot */
354 fnxttab[frownbr] = frowidx; /* Link new slot */
355 fnxttab[foldidx] = frownbr;
356 foldidx = frownbr ++;
357 }
358
359 memFree ((void *) srowtab); /* Free now useless factored column */
360 #ifdef SCOTCH_DEBUG_ALL
361 facttax[scolnum] = NULL;
362 #endif /* SCOTCH_DEBUG_ALL */
363 }
364
365 frownbr -= 2; /* Remove markers from number of extra-diagonals */
366 fnnztax[pcolnum] = frownbr; /* Save number of extra-diagonals */
367
368 if (frownbr <= 0) { /* If factored column has no extra-diagonals */
369 ldadtax[pcolnum] = -1; /* Column has no father */
370 #ifdef SCOTCH_DEBUG_ALL
371 lbrotax[pcolnum] = -1;
372 #endif /* SCOTCH_DEBUG_ALL */
373 continue; /* Skip to next column without allocating or linking */
374 }
375
376 if ((fcoltab = memAlloc (frownbr * sizeof (SCOTCH_Num))) == NULL) { /* Allocate array for factored column */
377 errorPrint ("factorView2: out of memory (2)");
378 return (1);
379 }
380 for (frowidx = fnxttab[0], fcolptr = fcoltab; frowidx != frowidd; frowidx = fnxttab[frowidx]) /* Fill factored array for column */
381 *fcolptr ++ = frowtab[frowidx];
382
383 dcolnum = fcoltab[0]; /* Get number of father, that it, first extra-diagonal */
384 ldadtax[pcolnum] = dcolnum; /* Link factored column to the separation tree */
385 lbrotax[pcolnum] = lsontax[dcolnum];
386 lsontax[dcolnum] = pcolnum;
387
388 facttax[pcolnum] = fcoltab; /* Save factored array */
389 }
390
391 memFree (frowtab); /* Free group leader */
392
393 return (0);
394 }
395
396 static
397 void
factorView3(FactorStat * restrict const statptr,SCOTCH_Num levlnum,SCOTCH_Num vertnum,double * restrict const hsumptr)398 factorView3 (
399 FactorStat * restrict const statptr,
400 SCOTCH_Num levlnum,
401 SCOTCH_Num vertnum,
402 double * restrict const hsumptr)
403 {
404 double hsumtmp;
405
406 hsumtmp = 0.0;
407 if (statptr->lsontax[vertnum] != -1) { /* If node has descendants */
408 SCOTCH_Num csonnum;
409
410 for (csonnum = statptr->lsontax[vertnum]; csonnum != -1; csonnum = statptr->lbrotax[csonnum])
411 factorView3 (statptr, levlnum + 1, csonnum, &hsumtmp);
412 }
413 else {
414 hsumtmp = (double) levlnum;
415
416 statptr->heignbr ++;
417 if (levlnum < statptr->heigmin)
418 statptr->heigmin = levlnum;
419 if (levlnum > statptr->heigmax)
420 statptr->heigmax = levlnum;
421 }
422
423 *hsumptr += hsumtmp;
424 }
425
426 static
427 void
factorView4(FactorStat * restrict const statptr,SCOTCH_Num levlnum,SCOTCH_Num vertnum,double * restrict const fopcptr)428 factorView4 (
429 FactorStat * restrict const statptr,
430 SCOTCH_Num levlnum,
431 SCOTCH_Num vertnum,
432 double * restrict const fopcptr)
433 {
434 SCOTCH_Num fnnztmp;
435 double fopctmp;
436
437 fnnztmp = statptr->fnnztax[vertnum] + 1; /* Get extra-diagonals, plus diagonal */
438 fopctmp = (double) fnnztmp;
439 statptr->fnnzsum += fopctmp;
440 fopctmp *= fopctmp;
441
442 if (statptr->lsontax[vertnum] != -1) { /* If node has descendants */
443 SCOTCH_Num csonnum;
444
445 for (csonnum = statptr->lsontax[vertnum]; csonnum != -1; csonnum = statptr->lbrotax[csonnum])
446 factorView4 (statptr, levlnum + 1, csonnum, &fopctmp); /* Accumulate OPC on local sum */
447 }
448 else
449 statptr->heigdlt += fabs ((double) levlnum - statptr->heigavg);
450
451 *fopcptr += fopctmp; /* Aggregate local sum at higher level */
452 }
453