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 : amk_ccc.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : Creates the distance map for CCC **/
39 /** graphs, to be used to build the archi- **/
40 /** tecture description files for these **/
41 /** graphs. **/
42 /** **/
43 /** DATES : # Version 1.3 : from : 24 apr 1994 **/
44 /** to : 24 apr 1994 **/
45 /** # Version 2.0 : from : 13 jul 1994 **/
46 /** to : 12 nov 1994 **/
47 /** # Version 3.0 : from : 18 sep 1995 **/
48 /** to : 19 sep 1995 **/
49 /** # Version 3.2 : from : 07 may 1997 **/
50 /** to : 07 may 1997 **/
51 /** # Version 3.3 : from : 02 oct 1998 **/
52 /** to : 02 oct 1998 **/
53 /** # Version 3.4 : from : 03 feb 2000 **/
54 /** to : 03 feb 2000 **/
55 /** # Version 5.0 : from : 23 dec 2007 **/
56 /** to : 16 mar 2008 **/
57 /** # Version 5.1 : from : 01 jul 2010 **/
58 /** to : 14 feb 2011 **/
59 /** # Version 6.0 : from : 01 jan 2012 **/
60 /** to : 12 nov 2014 **/
61 /** **/
62 /************************************************************/
63
64 /*
65 ** The defines and includes.
66 */
67
68 #define AMK_CCC
69
70 #include "module.h"
71 #include "common.h"
72 #include "scotch.h"
73 #include "amk_ccc.h"
74
75 /*
76 ** The static and global definitions.
77 */
78
79 static int C_paraNum = 0; /* Number of parameters */
80 static int C_fileNum = 0; /* Number of file in arg list */
81 static File C_fileTab[C_FILENBR] = { /* The file array */
82 { "w" } };
83
84 static C_VertDist * C_distaTab; /* Pointer to distance map table */
85 static C_Queue C_distaQueue; /* Distance queue */
86
87 static const char * C_usageList[] = { /* Usage list */
88 "amk_ccc <dim> [<output target file>] <options>",
89 " -h : Display this help",
90 " -V : Print program version and copyright",
91 NULL };
92
93 /*************************************************/
94 /* */
95 /* The main routine, which computes the distance */
96 /* triangular table. */
97 /* */
98 /*************************************************/
99
100 int
main(int argc,char * argv[])101 main (
102 int argc,
103 char * argv[])
104 {
105 SCOTCH_Num ccdim; /* Dimension of the graph */
106 SCOTCH_Num ccnbr; /* Number of vertices */
107 SCOTCH_Num ccbit; /* Mask variable */
108 SCOTCH_Num ccmax; /* Maximum terminal */
109 C_Vertex v, w, x; /* Vertex variables */
110 SCOTCH_Num d; /* Vertex distance to root */
111 SCOTCH_Num t; /* Vertex terminal value */
112 SCOTCH_Num i, j, k;
113
114 errorProg ("amk_ccc");
115
116 ccdim = 2;
117
118 if ((argc >= 2) && (argv[1][0] == '?')) { /* If need for help */
119 usagePrint (stdout, C_usageList);
120 return (0);
121 }
122
123 fileBlockInit (C_fileTab, C_FILENBR); /* Set default stream pointers */
124
125 for (i = 1; i < argc; i ++) { /* Loop for all option codes */
126 if ((argv[i][0] != '-') || (argv[i][1] == '\0') || (argv[i][1] == '.')) { /* If found a file name */
127 if (C_paraNum < 1) { /* If number of parameters not reached */
128 if ((ccdim = atoi (argv[i])) < 1) { /* Get the dimension */
129 errorPrint ("main: invalid dimension '%s'", argv[i]);
130 return (1);
131 }
132 C_paraNum ++;
133 continue; /* Process the other parameters */
134 }
135 if (C_fileNum < C_FILENBR) /* A file name has been given */
136 fileBlockName (C_fileTab, C_fileNum ++) = argv[i];
137 else {
138 errorPrint ("main: too many file names given");
139 return (1);
140 }
141 }
142 else { /* If found an option name */
143 switch (argv[i][1]) {
144 case 'H' : /* Give the usage message */
145 case 'h' :
146 usagePrint (stdout, C_usageList);
147 return (0);
148 case 'V' :
149 fprintf (stderr, "amk_ccc, version " SCOTCH_VERSION_STRING "\n");
150 fprintf (stderr, "Copyright 2004,2007,2008,2010-2012,2014 IPB, Universite de Bordeaux, INRIA & CNRS, France\n");
151 fprintf (stderr, "This software is libre/free software under CeCILL-C -- see the user's manual for more information\n");
152 return (0);
153 default :
154 errorPrint ("main: unprocessed option '%s'", argv[i]);
155 return (1);
156 }
157 }
158 }
159
160 fileBlockOpen (C_fileTab, C_FILENBR); /* Open all files */
161
162 ccnbr = ccdim * (1 << ccdim); /* Compute number of vertices */
163 ccbit = (1 << ccdim) - 1; /* Get maximum position number */
164 for (ccmax = ((1 << (ccdim + 1)) - 1), i = ccdim - 1; /* Compute biggest terminal value */
165 i != 0;
166 i >>= 1)
167 ccmax = (ccmax << 1) | (i & 1);
168
169 fprintf (C_filepntrarcout, "deco\n0\n" SCOTCH_NUMSTRING "\t" SCOTCH_NUMSTRING "\n", /* Print the file header */
170 (SCOTCH_Num) ccnbr, /* Print number of terminal domains */
171 (SCOTCH_Num) ccmax); /* Print biggest terminal value */
172
173 for (v.lvl = 0; v.lvl < ccdim; v.lvl ++) { /* For all levels */
174 for (v.pos = 0; v.pos <= ccbit; v.pos ++) { /* For all positions in these levels */
175 t = (1 << ccdim) | v.pos; /* Perform the hypercube cuts */
176 for (i = v.lvl, j = ccdim; j != 1; ) { /* Perform the cycle cuts */
177 t <<= 1;
178 k = (j + 1) >> 1;
179 if (i >= k) { /* If upper (smallest) half */
180 t |= 1;
181 i -= k;
182 j -= k;
183 }
184 else /* If lower (biggest) half */
185 j = k;
186 }
187 fprintf (C_filepntrarcout, SCOTCH_NUMSTRING "\t1\t" SCOTCH_NUMSTRING "\n",
188 (SCOTCH_Num) C_vertLabl (&v), /* Print terminal label */
189 (SCOTCH_Num) t); /* Print terminal number */
190 }
191 }
192
193 if ((C_queueInit (&C_distaQueue, ccmax) != 0) || /* Allocate the distance array */
194 ((C_distaTab = (C_VertDist *) memAlloc (ccmax * sizeof (C_VertDist))) == NULL)) {
195 errorPrint ("main: out of memory");
196 return (1);
197 }
198
199 for (v.lvl = 0; v.lvl < ccdim; v.lvl ++) { /* For all levels */
200 for (v.pos = 0; v.pos <= ccbit; v.pos ++) { /* For all positions in these levels */
201 for (i = 0; i < ccnbr; i ++) /* Initialize vertex table */
202 C_distaTab[i].queued = 0; /* Vertex not queued yet */
203
204 C_distaRoot (&v); /* Set the queue with root v */
205
206 while (C_distaGet (&w, &d)) { /* As long as the queue is not empty */
207 C_distaTab[C_vertLabl (&w)].dist = d; /* Keep the distance information */
208
209 d ++; /* Search for neighbors at next level */
210 x.lvl = w.lvl; /* Add neighbors to queue */
211 x.pos = w.pos ^ (1 << x.lvl);
212 C_distaPut (&x, d);
213 x.lvl = (w.lvl == 0) ? (ccdim - 1) : (w.lvl - 1);
214 x.pos = w.pos;
215 C_distaPut (&x, d);
216 x.lvl = (w.lvl == (ccdim - 1)) ? 0 : (w.lvl + 1);
217 C_distaPut (&x, d);
218 }
219
220 if (v.lvl + v.pos > 0) { /* Print distance triangular map line */
221 fprintf (C_filepntrarcout, SCOTCH_NUMSTRING,
222 (SCOTCH_Num) C_distaTab[0].dist);
223 for (i = 1; i < C_vertLabl (&v); i ++)
224 fprintf (C_filepntrarcout, " " SCOTCH_NUMSTRING,
225 (SCOTCH_Num) C_distaTab[i].dist);
226 fprintf (C_filepntrarcout, "\n");
227 }
228 }
229 }
230
231 fileBlockClose (C_fileTab, C_FILENBR); /* Always close explicitely to end eventual (un)compression tasks */
232
233 C_queueExit (&C_distaQueue);
234 memFree (C_distaTab);
235
236 #ifdef COMMON_PTHREAD
237 pthread_exit ((void *) 0); /* Allow potential (un)compression tasks to complete */
238 #endif /* COMMON_PTHREAD */
239 return (0);
240 }
241