1
/* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
3
** This file is part of the Scotch software package for static mapping,
4
** graph partitioning and sparse matrix ordering.
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".
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
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.
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.
32
/************************************************************/
34
/** NAME : amk_fft2.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : Creates the distance map for FFT **/
39
/** graphs, to be used to build the archi- **/
40
/** tecture description files for these **/
43
/** DATES : # Version 1.3 : from : 19 apr 1994 **/
44
/** to : 20 apr 1994 **/
45
/** # Version 3.0 : from : 01 jul 1995 **/
46
/** to : 19 sep 1995 **/
47
/** # Version 3.2 : from : 07 may 1997 **/
48
/** to : 07 may 1997 **/
49
/** # Version 3.3 : from : 02 oct 1998 **/
50
/** to : 02 oct 1998 **/
51
/** # Version 3.4 : from : 03 feb 2000 **/
52
/** to : 03 feb 2000 **/
54
/************************************************************/
57
** The defines and includes.
67
** The static and global definitions.
70
static int C_paraNum = 0; /* Number of parameters */
71
static int C_fileNum = 0; /* Number of file in arg list */
72
static File C_fileTab[C_FILENBR] = { /* The file array */
75
static C_VertDist * C_distaTab; /* Pointer to distance map table */
76
static C_Queue C_distaQueue; /* Distance queue */
78
static const char * C_usageList[] = { /* Usage list */
79
"amk_fft2 [<dim> [<output target file>]] <options>",
80
" -h : Display this help",
81
" -V : Print program version and copyright",
84
/*************************************************/
86
/* The main routine, which computes the distance */
87
/* triangular table. */
89
/*************************************************/
96
SCOTCH_Num fdim; /* FFT dimension */
97
SCOTCH_Num fnbr; /* Number of FFT vertices */
98
SCOTCH_Num fmax; /* Maximum terminal number */
99
SCOTCH_Num fmsk; /* Position bit mask */
100
C_Vertex v, w, x; /* A FFT vertex (lvl, pos) */
101
SCOTCH_Num b, d; /* Mask and bit variables */
102
SCOTCH_Num i; /* Loop counter */
103
SCOTCH_Num t; /* Vertex terminal value */
105
errorProg ("amk_fft2");
109
if ((argc >= 2) && (argv[1][0] == '?')) { /* If need for help */
110
usagePrint (stdout, C_usageList);
114
for (i = 0; i < C_FILENBR; i ++) /* Set default stream pointers */
115
C_fileTab[i].pntr = (C_fileTab[i].mode[0] == 'r') ? stdin : stdout;
116
for (i = 1; i < argc; i ++) { /* Loop for all option codes */
117
if ((argv[i][0] != '+') && /* If found a file name */
118
((argv[i][0] != '-') || (argv[i][1] == '\0'))) {
119
if (C_paraNum < 1) { /* If number of parameters not reached */
120
if ((fdim = atoi (argv[i])) < 1) { /* Get the dimension */
121
errorPrint ("main: invalid dimension (\"%s\")", argv[i]);
125
continue; /* Process the other parameters */
127
if (C_fileNum < C_FILENBR) /* A file name has been given */
128
C_fileTab[C_fileNum ++].name = argv[i];
130
errorPrint ("main: too many file names given");
134
else { /* If found an option name */
135
switch (argv[i][1]) {
136
case 'H' : /* Give the usage message */
138
usagePrint (stdout, C_usageList);
141
fprintf (stderr, "amk_fft2, version %s - F. Pellegrini\n", SCOTCH_VERSION);
142
fprintf (stderr, "Copyright 2004,2007 ENSEIRB, INRIA & CNRS, France\n");
143
fprintf (stderr, "This software is libre/free software under CeCILL-C -- see the user's manual for more information\n");
146
errorPrint ("main: unprocessed option (\"%s\")", argv[i]);
152
for (i = 0; i < C_FILENBR; i ++) { /* For all file names */
153
if ((C_fileTab[i].name[0] != '-') || /* If not standard stream */
154
(C_fileTab[i].name[1] != '\0')) {
155
if ((C_fileTab[i].pntr = fopen (C_fileTab[i].name, C_fileTab[i].mode)) == NULL) { /* Open the file */
156
errorPrint ("main: cannot open file (%d)", i);
162
fnbr = (fdim + 1) * (1 << fdim); /* Compute number of vertices */
163
fmax = (1 << (fdim * 2 - 1)) - 1; /* Compute maximum terminal number */
164
fmsk = (1 << fdim) - 1; /* Get maximum position number */
166
fprintf (C_filepntrarcout, "deco\n0\n%ld\t%ld\n", /* Print file header */
167
(long) fnbr, /* Print number of terminal domains */
168
(long) fmax); /* Print the biggest terminal value */
170
for (v.lvl = 0; v.lvl <= fdim; v.lvl ++) { /* For all vertices */
171
for (v.pos = 0; v.pos <= fmsk; v.pos ++) {
172
for (i = v.lvl, b = 1 << (fdim - 1), t = 1; /* Recurse through the vertical + horizontal cuts */
175
t <<= 1; /* Vertical cut: tell if vertex is in left or... */
176
t |= (v.pos & b) ? 1 : 0; /* right part from the position heaviest bits */
177
t <<= 1; /* Vertex is still in upper part of horizontal cut */
179
if (v.lvl == 0) /* If vertex is in the first level... */
180
t >>= 2; /* We have gone one step too far */
182
t |= 1; /* This time vertex is in the lower part */
183
t <<= (v.lvl - 1); /* Make space for the chain bipartition */
184
t |= v.pos & ((1 << (v.lvl - 1)) - 1); /* Bipartition the chain following the lowest bits */
187
printf (((v.lvl == fdim) && (v.pos == fmsk)) /* Print terminal domain number */
188
? "%u\n\n" : "%u ", t);
192
if ((C_queueInit (&C_distaQueue, fnbr) != 0) || /* Allocate distance array */
193
((C_distaTab = (C_VertDist *) memAlloc (fnbr * sizeof (C_VertDist))) == NULL)) {
194
errorPrint ("main: out of memory");
198
for (v.lvl = 0; v.lvl <= fdim; v.lvl ++) { /* For all vertices */
199
for (v.pos = 0; v.pos <= fmsk; v.pos ++) {
200
for (i = 0; i < fnbr; i ++) /* Initialize the vertex table */
201
C_distaTab[i].queued = 0; /* Vertex not queued yet */
203
C_distaRoot (&v); /* Set the queue with root v */
205
while (C_distaGet (&w, &d)) { /* As long as the queue is not empty */
206
C_distaTab[C_vertLabl (&w)].dist = d; /* Keep the distance information */
208
d ++; /* Search for neighbors at next level */
209
if (w.lvl > 0) { /* Add new neighbors to the queue */
213
x.pos = w.pos ^ (1 << (w.lvl - 1));
220
x.pos = w.pos ^ (1 << w.lvl);
225
if (v.lvl + v.pos > 0) { /* Print the distance triangular map line */
226
fprintf (C_filepntrarcout, "%ld",
227
(long) C_distaTab[0].dist);
228
for (i = 1; i < (v.lvl << fdim) + v.pos; i ++)
229
fprintf (C_filepntrarcout, " %ld",
230
(long) C_distaTab[i].dist);
231
fprintf (C_filepntrarcout, "\n");
236
#ifdef SCOTCH_DEBUG_MAIN1
237
C_queueExit (&C_distaQueue);
238
memFree (C_distaTab);
240
for (i = 0; i < C_FILENBR; i ++) { /* For all file names */
241
if ((C_fileTab[i].name[0] != '-') || /* If not standard stream */
242
(C_fileTab[i].name[1] != '\0')) {
243
fclose (C_fileTab[i].pntr); /* Close the stream */
246
#endif /* SCOTCH_DEBUG_MAIN1 */
added
removed
src/scotch/amk_fft2.c
