1
/* Copyright 2010 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 : kgraph_map_rb.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module performs the Dual Recursive **/
39
/** Bipartitioning mapping algorithm. **/
40
/** It is now a branching routine. **/
42
/** DATES : # Version 5.1 : from : 13 jul 2010 **/
43
/** to 14 jul 2010 **/
45
/************************************************************/
48
** The defines and includes.
57
#include "graph_coarsen.h"
61
#include "kgraph_map_ml.h"
62
#include "kgraph_map_st.h"
64
/*********************************************/
66
/* The coarsening and uncoarsening routines. */
68
/*********************************************/
70
/* This routine builds a coarser graph from the
71
** graph that is given on input. The coarser
72
** graphs differ at this stage from classical
73
** active graphs as their internal gains are not
76
** - 0 : if the coarse graph has been built.
77
** - 1 : if threshold achieved or on error.
83
const Kgraph * restrict const finegrafptr, /*+ Finer graph +*/
84
Kgraph * restrict const coargrafptr, /*+ Coarser graph to build +*/
85
GraphCoarsenMulti * restrict * const coarmultptr, /*+ Pointer to multinode table to build +*/
86
const KgraphMapMlParam * const paraptr) /*+ Method parameters +*/
90
vertmax = (archVar (&finegrafptr->m.archdat) ? 1 : finegrafptr->m.domnnbr) * paraptr->coarnbr;
92
if (graphCoarsen (&finegrafptr->s, &coargrafptr->s, coarmultptr, vertmax,
93
paraptr->coarrat, paraptr->coartype) != 0)
94
return (1); /* Return if coarsening failed */
96
coargrafptr->m.baseval = finegrafptr->m.baseval;
97
coargrafptr->m.vertnbr = coargrafptr->s.vertnbr;
98
coargrafptr->m.parttax = NULL; /* Do not allocate part array yet */
99
coargrafptr->m.domntab = finegrafptr->m.domntab; /* Re-use domain array */
100
coargrafptr->m.domnnbr = finegrafptr->m.domnnbr;
101
coargrafptr->m.domnmax = finegrafptr->m.domnmax;
102
coargrafptr->m.archdat = finegrafptr->m.archdat;
103
coargrafptr->m.domnorg = finegrafptr->m.domnorg;
104
coargrafptr->frontab = finegrafptr->frontab; /* Re-use frontier array if it exists */
105
coargrafptr->comploadavg = finegrafptr->comploadavg; /* Re-use existing load arrays */
106
coargrafptr->comploaddlt = finegrafptr->comploaddlt;
107
coargrafptr->levlnum = finegrafptr->levlnum + 1; /* Graph level is coarsening level */
112
/* This routine propagates the separation of the
113
** coarser graph back to the finer graph, according
114
** to the multinode table of collapsed vertices.
115
** After the separation is propagated, it finishes
116
** to compute the parameters of the finer graph that
117
** were not computed at the coarsening stage.
119
** - 0 : if coarse graph data has been propagated to fine graph.
125
kgraphMapMlUncoarsen (
126
Kgraph * restrict const finegrafptr, /*+ Finer graph +*/
127
Kgraph * restrict const coargrafptr, /*+ Coarser graph +*/
128
const GraphCoarsenMulti * restrict const coarmulttax) /*+ Multinode array +*/
131
const Anum * restrict coarparttax;
132
Gnum * coarfrontab; /* [norestrict] */
134
Anum * restrict fineparttax;
135
Gnum * finefrontab; /* [norestrict] */
138
const Gnum * restrict const fineverttax = finegrafptr->s.verttax;
139
const Gnum * restrict const finevendtax = finegrafptr->s.vendtax;
140
const Gnum * restrict const fineedgetax = finegrafptr->s.edgetax;
142
if (finegrafptr->m.parttax == NULL) { /* If partition array not yet allocated */
143
if ((finegrafptr->m.parttax = (Anum *) memAlloc (finegrafptr->s.vertnbr * sizeof (Anum))) == NULL) {
144
errorPrint ("kgraphMapMlUncoarsen: out of memory (1)");
147
finegrafptr->s.flagval |= KGRAPHFREEPART; /* Allocated data will be freed along with graph structure */
148
finegrafptr->m.parttax -= finegrafptr->s.baseval;
150
if (finegrafptr->frontab == NULL) { /* If frontier array not yet allocated */
151
if ((finegrafptr->frontab = (Gnum *) memAlloc (finegrafptr->s.vertnbr * sizeof (Gnum))) == NULL) {
152
errorPrint ("kgraphMapMlUncoarsen: out of memory (2)");
157
if (coargrafptr == NULL) { /* If no coarse graph provided */
158
kgraphFrst (finegrafptr); /* Assign all vertices to first subdomain */
162
finegrafptr->m.domntab = coargrafptr->m.domntab; /* Get pointer to domain array again in case it was reallocated */
163
finegrafptr->m.domnnbr = coargrafptr->m.domnnbr;
164
finegrafptr->m.domnmax = coargrafptr->m.domnmax;
165
coargrafptr->m.domntab = NULL; /* Do not doubly free array */
167
finegrafptr->comploadavg = coargrafptr->comploadavg; /* Get pointer to load array again in case it was reallocated */
168
finegrafptr->comploaddlt = coargrafptr->comploaddlt;
169
coargrafptr->comploadavg = NULL; /* Do not doubly free array */
171
coarparttax = coargrafptr->m.parttax;
172
fineparttax = finegrafptr->m.parttax;
173
for (coarvertnum = coargrafptr->s.baseval; coarvertnum < coargrafptr->s.vertnnd; coarvertnum ++) {
174
Gnum finevertnum0; /* First multinode vertex */
175
Gnum finevertnum1; /* Second multinode vertex */
178
finevertnum0 = coarmulttax[coarvertnum].vertnum[0];
179
finevertnum1 = coarmulttax[coarvertnum].vertnum[1];
180
partval = coarparttax[coarvertnum];
182
fineparttax[finevertnum0] = partval;
183
if (finevertnum0 != finevertnum1)
184
fineparttax[finevertnum1] = partval;
187
coarfrontab = coargrafptr->frontab; /* TRICK: may also be equal to finefrontab */
188
finefrontab = finegrafptr->frontab;
189
for (coarfronnum = 0, finefronnbr = coargrafptr->fronnbr; /* Re-cycle frontier array from coarse to fine graph */
190
coarfronnum < coargrafptr->fronnbr; coarfronnum ++) {
192
Gnum finevertnum0; /* First multinode vertex */
193
Gnum finevertnum1; /* Second multinode vertex */
195
coarvertnum = coarfrontab[coarfronnum];
196
finevertnum0 = coarmulttax[coarvertnum].vertnum[0];
197
finevertnum1 = coarmulttax[coarvertnum].vertnum[1];
199
if (finevertnum0 != finevertnum1) { /* If multinode si made of two distinct vertices */
203
coarpartval = coarparttax[coarvertnum];
205
#ifdef SCOTCH_DEBUG_KGRAPH2
206
finefrontab[coarfronnum] = ~0;
207
#endif /* SCOTCH_DEBUG_KGRAPH2 */
209
for (fineedgenum = fineverttax[finevertnum0];
210
fineedgenum < finevendtax[finevertnum0]; fineedgenum ++) {
211
if (fineparttax[fineedgetax[fineedgenum]] != coarpartval) { /* If first vertex belongs to frontier */
212
finefrontab[coarfronnum] = finevertnum0; /* Record it in lieu of the coarse frontier vertex */
216
if (fineedgenum >= finegrafptr->s.vendtax[finevertnum0]) { /* If first vertex not in frontier */
217
finefrontab[coarfronnum] = finevertnum1; /* Then second vertex must be in frontier */
218
continue; /* Skip to next multinode */
221
for (fineedgenum = fineverttax[finevertnum1]; /* Check if second vertex belong to frontier too */
222
fineedgenum < finevendtax[finevertnum1]; fineedgenum ++) {
223
if (fineparttax[fineedgetax[fineedgenum]] != coarpartval) { /* If second vertex belongs to frontier */
224
finefrontab[finefronnbr ++] = finevertnum1; /* Record it at the end of the (recycled ?) frontier array */
229
#ifdef SCOTCH_DEBUG_KGRAPH2
230
if (finefrontab[coarfronnum] == ~0) {
231
errorPrint ("kgraphMapMlUncoarsen: internal error");
234
#endif /* SCOTCH_DEBUG_KGRAPH2 */
236
else /* If coarse vertex is single node */
237
finefrontab[coarfronnum] = finevertnum0; /* Then it belongs to the frontier */
239
finegrafptr->fronnbr = finefronnbr;
241
#ifdef SCOTCH_DEBUG_KGRAPH2
242
if (kgraphCheck (finegrafptr) != 0) {
243
errorPrint ("kgraphMapMlUncoarsen: inconsistent graph data");
246
#endif /* SCOTCH_DEBUG_KGRAPH2 */
251
/* This routine recursively performs the partitioning.
253
** - 0 : if separator could be computed.
260
Kgraph * restrict const grafptr,
261
const KgraphMapMlParam * const paraptr)
264
GraphCoarsenMulti * restrict coarmulttax;
267
if (kgraphMapMlCoarsen (grafptr, &coargrafdat, &coarmulttax, paraptr) == 0) {
268
if (((o = kgraphMapMl2 (&coargrafdat, paraptr)) == 0) &&
269
((o = kgraphMapMlUncoarsen (grafptr, &coargrafdat, coarmulttax)) == 0) &&
270
((o = kgraphMapSt (grafptr, paraptr->stratasc)) != 0)) /* Apply ascending strategy */
271
errorPrint ("kgraphMapMl2: cannot apply ascending strategy");
272
kgraphExit (&coargrafdat);
274
else { /* Cannot coarsen due to lack of memory or error */
275
if (((o = kgraphMapMlUncoarsen (grafptr, NULL, NULL)) == 0) && /* Finalize graph */
276
((o = kgraphMapSt (grafptr, paraptr->stratlow)) != 0)) /* Apply low strategy */
277
errorPrint ("kgraphMapMl2: cannot apply low strategy");
283
/*****************************/
285
/* This is the main routine. */
287
/*****************************/
289
/* This routine performs the muti-level mapping.
291
** - 0 : if separator could be computed.
297
Kgraph * const grafptr, /*+ Graph to map +*/
298
const KgraphMapMlParam * const paraptr) /*+ Method parameters +*/
300
Gnum levlnum; /* Save value for graph level */
303
levlnum = grafptr->levlnum; /* Save graph level */
304
grafptr->levlnum = 0; /* Initialize coarsening level */
305
o = kgraphMapMl2 (grafptr, paraptr); /* Perform multi-level mapping */
306
grafptr->levlnum = levlnum; /* Restore graph level */
added
removed
src/libscotch/kgraph_map_ml.c
