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 : arch_build.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module builds a decomposition- **/
39
/** based architecture from a source graph. **/
41
/** DATES : # Version 3.2 : from : 29 may 1997 **/
42
/** to 30 aug 1998 **/
43
/** # Version 3.3 : from : 01 oct 1998 **/
44
/** to 01 oct 1998 **/
45
/** # Version 3.4 : from : 30 oct 2001 **/
46
/** to 08 nov 2001 **/
47
/** # Version 4.0 : from : 29 nov 2003 **/
48
/** to 10 mar 2005 **/
49
/** # Version 5.0 : from : 10 sep 2007 **/
50
/** to 10 sep 2007 **/
52
/************************************************************/
55
** The defines and includes.
65
#include "arch_deco.h"
66
#include "arch_vcmplt.h"
69
#include "bgraph_bipart_st.h"
70
#include "arch_build.h"
72
/************************************/
74
/* These routines handle job pools. */
76
/************************************/
78
/* This routine frees the contents of
79
** the given job pool.
81
** - VOID : in all cases.
87
ArchBuildJob * const jobtab)
89
ArchBuildJob * jobptr;
93
graphExit (&jobptr->grafdat);
94
jobptr = jobptr->joblink;
95
} while (jobptr != NULL);
98
/********************************************/
100
/* The main routine, which computes the */
101
/* decomposition-based target architecture. */
103
/********************************************/
106
** This routine builds a target architecture from
107
** the given source graph and the optional vertex
116
Arch * restrict const tgtarchptr, /*+ Decomposition architecture to build +*/
117
const Graph * const tgtgrafptr, /*+ Source graph modeling the architecture +*/
118
const VertList * const tgtlistptr, /*+ Subset of source graph vertices +*/
119
const Strat * const mapstrat) /*+ Bipartitioning strategy +*/
121
Gnum * restrict mapparttax; /* Based access to mapping part array */
122
ArchDom domsub0; /* Temporary space for subdomain 0 */
123
Gnum termdomnbr; /* Number of terminal domains */
124
Gnum termdommax; /* Maximum terminal number */
125
ArchDecoTermVert * restrict termverttab; /* Terminal vertex table */
126
Anum * restrict termdisttab; /* Vertex distance table */
127
ArchBuildDistElem * restrict disttab; /* Distance table */
128
ArchBuildQueuElem * restrict queutab; /* Distance queue table */
129
Gnum queuhead; /* Head-of-queue index */
130
Gnum queutail; /* Tail-of-queue index */
131
Mapping mapdat; /* Partial and final mapping data */
132
ArchBuildJob * restrict jobtab; /* Job array */
133
ArchBuildJob * joblink; /* Linked list of jobs to process */
134
ArchBuildJob * joborgptr; /* Pointer to original job and first subjob */
135
ArchBuildJob * jobsubptr; /* Pointer to second subjob */
136
Bgraph actgrafdat; /* Active graph for bipartitioning */
137
Gnum * restrict actfrontab; /* Frontier array for all bipartitionings */
138
GraphPart * restrict actparttax; /* Part array for all bipartitionings */
139
GraphPart actpartval; /* Part value to put to subjob */
140
Gnum actpartnbr; /* Size of part value to put to subjob */
143
archInit (tgtarchptr); /* Initialize architecture body */
144
tgtarchptr->class = archClass ("deco"); /* Set architecture class */
146
termdomnbr = (tgtlistptr != NULL) ? tgtlistptr->vnumnbr : tgtgrafptr->vertnbr;
147
if (termdomnbr == 0) /* If nothing to do */
150
if ((memAllocGroup ((void **) (void *)
151
&jobtab, (size_t) (termdomnbr * sizeof (ArchBuildJob)),
152
&actfrontab, (size_t) (termdomnbr * sizeof (Gnum)),
153
&actparttax, (size_t) (termdomnbr * sizeof (GraphPart)), NULL) == NULL) ||
154
(memAllocGroup ((void **) (void *)
155
&mapdat.domntab, (size_t) (termdomnbr * sizeof (ArchDom)),
156
&mapdat.parttax, (size_t) (termdomnbr * sizeof (ArchDomNum)), NULL) == NULL)) {
157
errorPrint ("archBuild: out of memory (1)");
162
actparttax -= tgtgrafptr->baseval;
163
memSet (mapdat.parttax, 0, termdomnbr * sizeof (ArchDomNum));
164
mapdat.flagval = MAPNONE; /* mapdat.domntab is the group leader */
165
mapdat.baseval = tgtgrafptr->baseval;
166
mapdat.vertnbr = termdomnbr;
167
mapdat.parttax -= tgtgrafptr->baseval;
168
mapdat.domnmax = termdomnbr;
170
intRandInit (); /* Initialize random generator */
172
archInit (&mapdat.archdat); /* Initialize terminal architecture */
173
mapdat.archdat.class = archClass ("varcmplt"); /* Set architecture class */
174
archDomFrst (&mapdat.archdat, &mapdat.domntab[0]); /* Get initial domain */
177
jobtab[0].domnum = 0; /* All vertices mapped to first domain */
178
if ((tgtlistptr != NULL) && (tgtlistptr->vnumtab != NULL)) /* If vertex list given */
179
graphInduceList (tgtgrafptr, tgtlistptr, &jobtab[0].grafdat); /* Restrict initial job */
180
else { /* If no vertex list given */
181
memCpy (&jobtab[0].grafdat, tgtgrafptr, sizeof (Graph)); /* Job takes whole graph */
182
jobtab[0].grafdat.flagval &= ~GRAPHFREETABS; /* Graph is a clone */
185
mapparttax = mapdat.parttax;
187
actgrafdat.veextax = NULL; /* No external gain array */
188
actgrafdat.parttax = actparttax; /* Set global auxiliary arrays */
189
actgrafdat.frontab = actfrontab;
190
joblink = NULL; /* Initialize job list */
191
if (jobtab[0].grafdat.vertnbr > 1) { /* If job is worth bipartitioning */
192
jobtab[0].joblink = joblink; /* Add initial job to list */
193
joblink = &jobtab[0];
195
while (joblink != NULL) { /* For all jobs in list */
196
joborgptr = joblink; /* Get job */
197
joblink = joblink->joblink; /* Remove job from list */
198
joborgptr->joblink = NULL; /* In case of freeing */
200
memCpy (&actgrafdat.s, &joborgptr->grafdat, sizeof (Graph));
201
actgrafdat.s.flagval = joborgptr->grafdat.flagval & ~GRAPHFREETABS;
202
bgraphInit2 (&actgrafdat, 1, 1, 1); /* Create active graph */
203
if (bgraphBipartSt (&actgrafdat, mapstrat) != 0) { /* Perform bipartitioning */
204
errorPrint ("archBuild: internal error (1)");
205
archBuildJobExit (joborgptr);
206
archBuildJobExit (joblink);
211
if ((actgrafdat.compsize0 == 0) || /* If one of the jobs is empty */
212
(actgrafdat.compsize0 == actgrafdat.s.vertnbr)) {
213
errorPrint ("archBuild: strategy leads to empty domains");
214
graphExit (&actgrafdat.s); /* Only free graph part, global arrays kept */
215
archBuildJobExit (joborgptr);
216
archBuildJobExit (joblink);
222
archVcmpltDomBipart ((const ArchVcmplt * const) (void *) &mapdat.archdat, /* Update mapping domains */
223
(const ArchVcmpltDom * const) (void *) &mapdat.domntab[joborgptr->domnum],
224
(ArchVcmpltDom * const) (void *) &domsub0,
225
(ArchVcmpltDom * const) (void *) &mapdat.domntab[mapdat.domnnbr]);
226
mapdat.domntab[joborgptr->domnum] = domsub0;
227
actpartval = actgrafdat.parttax[actgrafdat.s.baseval]; /* Always keep first vertex in sub0 */
228
actpartnbr = (actpartval == 0) ? actgrafdat.compsize0 : (actgrafdat.s.vertnbr - actgrafdat.compsize0);
229
if (actgrafdat.s.vnumtax != NULL) { /* Update mapping fraction */
232
for (actvertnum = actgrafdat.s.baseval; actvertnum < actgrafdat.s.vertnnd; actvertnum ++) {
233
if (actgrafdat.parttax[actvertnum] != actpartval)
234
mapdat.parttax[actgrafdat.s.vnumtax[actvertnum]] = mapdat.domnnbr;
240
for (actvertnum = actgrafdat.s.baseval; actvertnum < actgrafdat.s.vertnnd; actvertnum ++) {
241
if (actgrafdat.parttax[actvertnum] != actpartval)
242
mapdat.parttax[actvertnum] = mapdat.domnnbr;
246
jobsubptr = jobtab + mapdat.domnnbr; /* Point to new subjob */
247
jobsubptr->domnum = mapdat.domnnbr ++; /* Build subjobs */
248
actgrafdat.s.flagval = joborgptr->grafdat.flagval; /* Active is now main copy */
250
if (actpartnbr < (actgrafdat.s.vertnbr - 1)) { /* If part 1 splittable */
251
graphInducePart (&actgrafdat.s, actgrafdat.parttax, actgrafdat.s.vertnbr - actpartnbr,
252
1 - actpartval, &jobsubptr->grafdat);
253
jobsubptr->joblink = joblink; /* Link subjobs in list */
256
if (actpartnbr > 1) { /* If part 0 splittable */
257
graphInducePart (&actgrafdat.s, actgrafdat.parttax, actpartnbr,
258
actpartval, &joborgptr->grafdat);
259
joborgptr->joblink = joblink; /* Link subjobs in list */
262
graphExit (&actgrafdat.s); /* Only free graph part, global arrays kept */
265
memFree (jobtab); /* Free group leader */
267
if (memAllocGroup ((void **) (void *)
268
&termverttab, (size_t) (termdomnbr * sizeof (ArchDecoTermVert)),
269
&termdisttab, (size_t) (((termdomnbr * (termdomnbr - 1)) / 2) * sizeof (Anum)),
270
&disttab, (size_t) (tgtgrafptr->vertnbr * sizeof (ArchBuildDistElem)),
271
&queutab, (size_t) (tgtgrafptr->vertnbr * sizeof (ArchBuildQueuElem)), NULL) == NULL) {
272
errorPrint ("archBuild: out of memory (2)");
277
if (tgtlistptr != NULL) {
278
for (i = 0, termdommax = 0; i < termdomnbr; i ++) { /* Set terminal vertex array */
279
termverttab[i].labl = (tgtgrafptr->vnumtax != NULL) ? tgtgrafptr->vnumtax[tgtlistptr->vnumtab[i]] : i;
280
termverttab[i].wght = (tgtgrafptr->velotax != NULL) ? tgtgrafptr->velotax[tgtlistptr->vnumtab[i]] : 1;
281
termverttab[i].num = archDomNum (&mapdat.archdat, mapDomain (&mapdat, tgtlistptr->vnumtab[i]));
282
if (termverttab[i].num > termdommax) /* Find maximum terminal number */
283
termdommax = termverttab[i].num;
287
for (i = 0, termdommax = 0; i < termdomnbr; i ++) { /* Set terminal vertex array */
288
termverttab[i].labl = (tgtgrafptr->vnumtax != NULL) ? tgtgrafptr->vnumtax[i + tgtgrafptr->baseval] : (i + tgtgrafptr->baseval);
289
termverttab[i].wght = (tgtgrafptr->velotax != NULL) ? tgtgrafptr->velotax[i + tgtgrafptr->baseval] : 1;
290
termverttab[i].num = archDomNum (&mapdat.archdat, mapDomain (&mapdat, (i + tgtgrafptr->baseval)));
291
if (termverttab[i].num > termdommax) /* Find maximum terminal number */
292
termdommax = termverttab[i].num;
296
for (i = 1; i < termdomnbr; i ++) { /* For all active vertices except the first */
297
for (j = 0; j < tgtgrafptr->vertnbr; j ++) {
298
disttab[j].queued = 0; /* Vertex not queued */
299
disttab[j].distval = INT_MAX; /* Assume maximum distance */
302
queuhead = /* Reset the queue */
304
if (tgtlistptr != NULL) {
305
queutab[queutail].vertnum = tgtlistptr->vnumtab[i]; /* Insert root vertex */
306
queutab[queutail ++].distval = 0;
307
disttab[tgtlistptr->vnumtab[i]].queued = 1; /* Mark vertex as queued */
308
disttab[tgtlistptr->vnumtab[i]].distval = 0;
311
queutab[queutail].vertnum = i + tgtgrafptr->baseval; /* Insert root vertex */
312
queutab[queutail ++].distval = 0;
313
disttab[i].queued = 1; /* Mark vertex as queued */
314
disttab[i].distval = 0;
317
while (queuhead < queutail) { /* As long as there are vertices in queue */
318
Gnum vertnum; /* Number of current vertex */
319
Gnum vertdist; /* Current distance value */
322
vertnum = queutab[queuhead].vertnum; /* Retrieve vertex from queue */
323
vertdist = queutab[queuhead ++].distval;
325
for (edgenum = tgtgrafptr->verttax[vertnum]; /* For all vertex edges */
326
edgenum < tgtgrafptr->vendtax[vertnum]; edgenum ++) {
329
vertend = tgtgrafptr->edgetax[edgenum];
330
if (disttab[vertend].queued == 0) { /* If end vertex not queued */
331
queutab[queutail].vertnum = vertend; /* Queue the vertex */
332
queutab[queutail ++].distval =
333
disttab[vertend - tgtgrafptr->baseval].distval = vertdist + ((tgtgrafptr->edlotax != NULL) ? tgtgrafptr->edlotax[edgenum] : 1);
334
disttab[vertend - tgtgrafptr->baseval].queued = 1; /* Mark vertex as queued */
339
for (j = 0; j < i; j ++) /* For all previous vertices */
340
termdisttab[((i * (i - 1)) / 2) + j] = /* Retrieve distance */
344
archDecoArchBuild ((ArchDeco *) (void *) &tgtarchptr->data, termdomnbr, termdommax, termverttab, termdisttab);
346
memFree (termverttab); /* Free group leader */
added
removed
src/libscotch/arch_build.c
