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 : kgraph_map_rb.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module performs the Dual Recursive **/
39
/** Bipartitioning mapping algorithm. **/
41
/** DATES : # Version 0.0 : from : 31 mar 1993 **/
42
/** to 31 mar 1993 **/
43
/** # Version 1.0 : from : 04 oct 1993 **/
44
/** to 06 oct 1993 **/
45
/** # Version 1.1 : from : 15 oct 1993 **/
46
/** to 15 oct 1993 **/
47
/** # Version 1.3 : from : 09 apr 1994 **/
48
/** to 11 may 1994 **/
49
/** # Version 2.0 : from : 06 jun 1994 **/
50
/** to 17 nov 1994 **/
51
/** # Version 2.1 : from : 07 apr 1995 **/
52
/** to 18 jun 1995 **/
53
/** # Version 3.0 : from : 01 jul 1995 **/
54
/** to 19 oct 1995 **/
55
/** # Version 3.1 : from : 30 oct 1995 **/
56
/** to 14 jun 1996 **/
57
/** # Version 3.2 : from : 23 aug 1996 **/
58
/** to 07 sep 1998 **/
59
/** # Version 3.3 : from : 19 oct 1998 **/
60
/** to 08 dec 1998 **/
61
/** # Version 3.4 : from : 01 jun 2001 **/
62
/** to 07 nov 2001 **/
63
/** # Version 4.0 : from : 12 jan 2004 **/
64
/** to 06 mar 2005 **/
66
/************************************************************/
69
** The defines and includes.
81
#include "bgraph_bipart_st.h"
83
#include "kgraph_map_rb.h"
86
** The static variables.
89
static KgraphMapRbPoolLink kgraphmaprbpooldummy; /* Dummy links for pool routines; TRICK */
91
/************************************/
93
/* These routines handle job pools. */
95
/************************************/
97
/* This routine initializes the contents
100
** - VOID : in all cases.
105
kgraphMapRbPoolInit (
106
KgraphMapRbPool * restrict const poolptr,
107
KgraphMapRbPolicy polival)
109
poolptr->poollink.prev =
110
poolptr->poollink.next = &kgraphmaprbpooldummy;
111
poolptr->polival = polival;
114
/* This routine frees the contents of
115
** the given job pool.
117
** - VOID : in all cases.
122
kgraphMapRbPoolExit (
123
KgraphMapRbPool * restrict const poolptr)
125
KgraphMapRbJob * jobptr;
127
for (jobptr = (KgraphMapRbJob *) poolptr->poollink.next; /* For all jobs in pool */
128
jobptr != (KgraphMapRbJob *) &kgraphmaprbpooldummy;
129
jobptr = (KgraphMapRbJob *) jobptr->poollink.next)
130
graphFree (&jobptr->grafdat); /* Free job graph, if not clone of original graph */
133
/* This routine adds a job to the given pool.
135
** - VOID : in all cases.
141
KgraphMapRbPool * const poolptr,
142
KgraphMapRbJob * const jobptr)
144
jobptr->poollink.prev = &poolptr->poollink; /* Link job in pool: TRICK */
145
jobptr->poollink.next = poolptr->poollink.next;
146
jobptr->poolflag = 1; /* Job is in pool */
147
jobptr->poolptr = poolptr; /* Point to the pool */
148
poolptr->poollink.next->prev = &jobptr->poollink;
149
poolptr->poollink.next = &jobptr->poollink;
152
/* This routine deletes a job from the given pool.
154
** - VOID : in all cases.
160
KgraphMapRbPool * const poolptr,
161
KgraphMapRbJob * const jobptr)
163
jobptr->poolflag = 0; /* Job is no longer in pool */
164
jobptr->poollink.next->prev = jobptr->poollink.prev; /* Remove job from pool; TRICK */
165
jobptr->poollink.prev->next = jobptr->poollink.next;
168
/* This routine gets the best job
169
** available from the given pool,
170
** according to the given policy.
172
** - !NULL : pointer to the job.
173
** - NULL : if the pool is empty.
179
KgraphMapRbPool * const poolptr)
181
KgraphMapRbJob * jobbest; /* Best job found */
182
KgraphMapRbJob * jobptr;
184
jobbest = (KgraphMapRbJob *) poolptr->poollink.next; /* Get first job in pool */
185
for (jobptr = jobbest; /* For all jobs in pool */
186
jobptr != (KgraphMapRbJob *) &kgraphmaprbpooldummy;
187
jobptr = (KgraphMapRbJob *) jobptr->poollink.next) {
188
if (jobptr->priolvl > jobbest->priolvl) /* If the current job has stronger priority */
189
jobbest = jobptr; /* Select it as the best job */
192
if (jobbest != (KgraphMapRbJob *) &kgraphmaprbpooldummy) /* If job found */
193
kgraphMapRbPoolDel (poolptr, jobbest); /* Remove it from pool */
194
else /* Dummy job means no job found */
200
/* This routine adds a job to the given pool
201
** as the first bipartitioning job.
203
** - VOID : in all cases.
209
KgraphMapRbPool * const poolptr, /* New pool */
210
KgraphMapRbJob * const jobptr) /* Job to be added */
213
switch (poolptr->polival) { /* Set job priority value */
214
case KGRAPHMAPRBPOLIRANDOM :
216
jobptr->priolvl = intRandVal (INT_MAX);
218
case KGRAPHMAPRBPOLILEVEL :
219
case KGRAPHMAPRBPOLINGLEVEL :
220
jobptr->prioval = jobptr->grafdat.vertnbr;
223
case KGRAPHMAPRBPOLISIZE :
224
case KGRAPHMAPRBPOLINGSIZE :
226
jobptr->priolvl = jobptr->grafdat.vertnbr;
228
case KGRAPHMAPRBPOLIOLD :
232
#ifdef SCOTCH_DEBUG_KGRAPH2
234
errorPrint ("kgraphMapRbPoolNew: unknown job selection policy");
238
#endif /* SCOTCH_DEBUG_KGRAPH2 */
241
kgraphMapRbPoolAdd (poolptr, jobptr); /* Add job to pool */
244
/* This routine updates the given job
245
** table with the given job data.
246
** This routine can be called only if
247
** the parent jobs of the vertices to
248
** be updated still exist.
250
** - VOID : in all cases.
255
kgraphMapRbPoolUpdt (
256
KgraphMapRbPool * const poolptr, /* Current pool */
257
const Graph * restrict const srcgrafptr, /* Pointer to original source graph */
258
const Mapping * const mapptr, /* Current mapping */
259
KgraphMapRbJob * restrict const joboldptr, /* Job to be removed */
260
KgraphMapRbJob * restrict const jobnewptr, /* Job to be added */
261
KgraphMapRbJob * const jobtab) /* Job table */
263
const Anum * restrict mapparttax; /* Based pointer to part array */
264
const Graph * restrict jobgrafptr; /* Pointer to job source graph */
265
Gnum jobvertnum; /* Number of current vertex */
266
KgraphMapRbJob * joblistptr; /* List of jobs unlinked from pools */
267
Gnum jobpriolvl; /* New job priority level */
269
switch (poolptr->polival) { /* Set job priority value */
270
case KGRAPHMAPRBPOLIRANDOM :
272
jobnewptr->priolvl = intRandVal (INT_MAX);
274
case KGRAPHMAPRBPOLILEVEL :
275
jobnewptr->priolvl = joboldptr->priolvl + 1;
276
case KGRAPHMAPRBPOLINGLEVEL :
277
jobnewptr->prioval = joboldptr->prioval - 1;
279
case KGRAPHMAPRBPOLISIZE :
280
jobnewptr->priolvl = jobnewptr->grafdat.vertnbr;
281
case KGRAPHMAPRBPOLINGSIZE :
282
jobnewptr->prioval = jobnewptr->grafdat.vertnbr;
284
case KGRAPHMAPRBPOLIOLD :
285
jobnewptr->priolvl = (jobnewptr->grafdat.vnumtax == NULL) /* If new graph is original graph */
286
? joboldptr->priolvl /* Take same priority as before */
287
: ((joboldptr->priolvl ^ 1) << 1) + /* Else compute it "old-style" */
288
((joboldptr->grafdat.vnumtax == NULL)
289
? ((jobnewptr->grafdat.vnumtax[0] == 0) ? 0 : 1)
290
: ((jobnewptr->grafdat.vnumtax[0] == joboldptr->grafdat.vnumtax[0]) ? 0 : 1));
292
#ifdef SCOTCH_DEBUG_KGRAPH2
294
errorPrint ("kgraphMapRbPoolUpdt: unknown job selection policy");
295
jobnewptr->prioval = 0;
296
jobnewptr->priolvl = 0;
298
#endif /* SCOTCH_DEBUG_KGRAPH2 */
301
if (poolptr->polival >= KGRAPHMAPRBPOLINEIGHBOR) { /* If neighbors have to be updated */
302
mapparttax = mapptr->parttax;
303
jobgrafptr = &jobnewptr->grafdat; /* Point to job source graph */
304
joblistptr = NULL; /* No temporarily unlinked jobs yet */
305
jobpriolvl = 0; /* Priority level not yet set */
307
for (jobvertnum = jobgrafptr->baseval; jobvertnum < jobgrafptr->vertnnd; jobvertnum ++) {
308
Gnum srcvertnum; /* Source graph vertex number */
309
const Gnum * srcedgeptr; /* Pointer to current edge */
311
srcvertnum = (jobgrafptr->vnumtax == NULL) ? jobvertnum : jobgrafptr->vnumtax[jobvertnum];
313
if ((srcgrafptr->vendtax[srcvertnum] - srcgrafptr->verttax[srcvertnum]) == /* If vertex is internal, skip it */
314
(jobgrafptr->vendtax[jobvertnum] - jobgrafptr->verttax[jobvertnum]))
317
for (srcedgeptr = srcgrafptr->edgetax + srcgrafptr->verttax[srcvertnum];
318
srcedgeptr < srcgrafptr->edgetax + srcgrafptr->vendtax[srcvertnum];
320
KgraphMapRbJob * restrict jobnghbptr; /* (Old ?) job of neighbor vertex */
322
jobnghbptr = &jobtab[mapparttax[*srcedgeptr]]; /* Get pointer to neighboring job */
324
if ((jobnghbptr->poolflag != 0) && /* If neighbor in active job */
325
(jobnghbptr->prioval > jobnewptr->prioval) && /* Over which we have gained priority */
326
(jobnghbptr->prioval <= joboldptr->prioval)) {
327
jobnghbptr->priolvl ++; /* Update neighbor priority */
329
if ((jobnghbptr->poolflag == 0) || /* If neighbor is fully known */
330
(jobnghbptr->prioval < jobnewptr->prioval)) /* Or has stronger priority value */
331
jobpriolvl ++; /* Then we should be processed */
334
jobnewptr->priolvl = jobpriolvl; /* Then we should be processed */
337
kgraphMapRbPoolAdd (poolptr, jobnewptr); /* Add job to pool */
341
** This routine removes the vertices of the
342
** given job from the given job table.
350
kgraphMapRbPoolRemv (
351
KgraphMapRbPool * const poolptr, /* Current pool */
352
const Graph * restrict const srcgrafptr, /* Pointer to original source graph */
353
Mapping * const mapptr, /* Current mapping */
354
KgraphMapRbJob * const joboldptr, /* Job to be removed */
355
GraphPart * const joboldparttax, /* Job part array */
356
const GraphPart joboldpartnum, /* Number of part to remove */
357
KgraphMapRbJob * const jobtab) /* Job table */
359
const Anum * restrict mapparttax; /* Based pointer to part array */
360
const Graph * restrict jobgrafptr; /* Pointer to job source graph */
361
const Gnum * restrict srcedgetax; /* Pointer to edge array of source graph */
362
Gnum jobvertnum; /* Number of current vertex */
363
KgraphMapRbJob * joblistptr; /* List of jobs unlinked from pools */
365
if (poolptr->polival >= KGRAPHMAPRBPOLINEIGHBOR) { /* If neighbors have to be modified */
366
mapparttax = mapptr->parttax;
367
srcedgetax = srcgrafptr->edgetax; /* Point to edge array of source graph */
368
jobgrafptr = &joboldptr->grafdat; /* Point to job source graph */
369
joblistptr = NULL; /* No temporarily unlinked jobs yet */
371
for (jobvertnum = jobgrafptr->baseval; jobvertnum < jobgrafptr->vertnnd; jobvertnum ++) {
372
Gnum srcvertnum; /* Source graph vertex number */
373
Gnum srcedgenum; /* Source graph edge number */
375
if (joboldparttax[jobvertnum] != joboldpartnum) /* If vertex is not in the right part */
378
srcvertnum = (jobgrafptr->vnumtax == NULL) ? jobvertnum : jobgrafptr->vnumtax[jobvertnum];
380
for (srcedgenum = srcgrafptr->verttax[srcvertnum]; srcedgenum < srcgrafptr->vendtax[srcvertnum]; srcedgenum ++) {
381
KgraphMapRbJob * jobnghbptr; /* (Old ?) job of neighbor vertex */
383
jobnghbptr = &jobtab[mapparttax[srcedgetax[srcedgenum]]]; /* Get pointer to neighboring job */
385
if ((jobnghbptr->poolflag != 0) && /* If neighbor is in active job */
386
(jobnghbptr->prioval < joboldptr->prioval)) { /* Which had a stronger priority */
387
jobnghbptr->priolvl ++; /* Update neighbor priority */
394
/********************************************/
396
/* This is the entry point for the Dual */
397
/* Recursive Bipartitioning mapping method. */
399
/********************************************/
402
** This routine runs the Dual Recursive
403
** Bipartitioning algorithm.
411
Kgraph * restrict const grafptr,
412
const KgraphMapRbParam * restrict const paraptr)
414
ArchDom domorg; /* Initial architecture domain */
415
ArchDom domsub[2]; /* Initial subdomains */
416
Anum jobnbr; /* Current number of jobs in job table */
417
Anum jobmax; /* Maximum number of jobs in table (i.e. size) */
418
KgraphMapRbJob * jobtab; /* Job table */
419
KgraphMapRbJob * joborgptr; /* Pointer to current job */
420
KgraphMapRbJob joborgdat; /* Aera to save original job data */
421
Anum jobsubnum[2]; /* Number of subjob slots in job array */
422
Gnum jobsubsiz[2]; /* Sizes of subjobs */
423
KgraphMapRbPool pooldat[2]; /* Job pools */
424
KgraphMapRbPool * poolptr[2]; /* Pointers to job pools */
425
KgraphMapRbPool * pooltmp; /* Temporary variable for pool swapping */
426
Mapping mapdat; /* Other mapping used by pools */
427
Mapping * mapptr[2]; /* Pointers to previous and current mappings */
428
Mapping * maptmp; /* Temporary pointer for mapping swapping */
429
Bgraph actgraph; /* Active bipartitioning graph */
430
Gnum actvertnum; /* Current vertex number */
431
Graph * srcgrafptr; /* Pointer to source graph if mapping distances required */
432
int cocyflag; /* Flag set if cocycle data relevant */
433
int varsflag; /* Flag set if variable-sized architecture */
436
archDomFrst (&grafptr->m.archdat, &domorg); /* Get first domain */
437
grafptr->m.domnnbr = 1; /* Only one valid domain to date */
438
grafptr->m.domntab[0] = domorg; /* All vertices are mapped to it */
439
memSet (grafptr->m.parttax + grafptr->m.baseval, 0, grafptr->s.vertnbr * sizeof (ArchDomNum)); /* Initialize partition data */
441
switch (archDomBipart (&grafptr->m.archdat, &domorg, &domsub[0], &domsub[1])) {
442
case 1 : /* If nothing to bipartition */
443
return (0); /* Return without error */
444
case 2 : /* On error */
445
errorPrint ("kgraphMapRb: cannot bipartition domain (1)");
449
cocyflag = 1; /* Assume cocycle data are relevant */
450
if ((strcmp (archName (&grafptr->m.archdat), "cmplt") == 0) || /* If target architecture is complete graph */
451
(strcmp (archName (&grafptr->m.archdat), "varcmplt") == 0)) /* Or the terminal decomposition architecture */
452
cocyflag = 0; /* Do not account for cocycle data */
454
if (strncmp (archName (&grafptr->m.archdat), "var", 3) == 0) /* If target architecture is variable sized */
456
srcgrafptr = (cocyflag == 0) ? NULL : &grafptr->s; /* If no need for external data */
458
#ifdef SCOTCH_DEBUG_KGRAPH2
459
jobmax = 1; /* Set minimum size in order to test resizing */
460
#else /* SCOTCH_DEBUG_KGRAPH2 */
461
jobmax = grafptr->m.domnmax; /* Set size of job array */
462
#endif /* SCOTCH_DEBUG_KGRAPH2 */
463
if ((jobtab = (KgraphMapRbJob *) memAlloc (jobmax * sizeof (KgraphMapRbJob))) == NULL) {
464
errorPrint ("kgraphMapRb: out of memory (1)");
468
kgraphMapRbPoolInit (&pooldat[0], (cocyflag == 0) ? KGRAPHMAPRBPOLILEVEL : paraptr->poli); /* Initialize first pool (done first for success of kgraphMapRbExit()) */
470
poolptr[0] = &pooldat[0]; /* Point to first pool */
471
if ((paraptr->flagjobtie != 0) || (cocyflag == 0)) /* If pools are tied */
472
poolptr[1] = poolptr[0]; /* They are the same */
474
kgraphMapRbPoolInit (&pooldat[1], (cocyflag == 0) ? KGRAPHMAPRBPOLILEVEL : paraptr->poli); /* Allocate another pool */
475
poolptr[1] = &pooldat[1];
478
mapptr[0] = /* First mapping is graph mapping */
479
mapptr[1] = &grafptr->m; /* Assume mappings are tied */
480
if ((paraptr->flagmaptie == 0) && (cocyflag == 1)) { /* If mappings are not tied */
481
mapptr[1] = &mapdat; /* Point to second mapping */
483
mapdat.flagval = MAPNONE; /* Partition data is shared */
484
mapdat.baseval = grafptr->s.baseval;
485
mapdat.vertnbr = grafptr->s.vertnbr;
486
mapdat.parttax = grafptr->m.parttax; /* Partition data is shared */
487
mapdat.domnmax = grafptr->m.domnmax; /* Will not be used anyway */
488
mapdat.domnnbr = 1; /* Will not be used anyway */
489
mapdat.domntab = NULL; /* In case first allocation fails */
490
if ((mapdat.domntab = (ArchDom *) memAlloc (grafptr->m.domnmax * sizeof (ArchDom))) == NULL) {
491
errorPrint ("kgraphMapRb: out of memory (2)");
492
kgraphMapRbExit (1, jobtab, poolptr, mapptr, grafptr);
495
mapdat.domntab[0] = domorg; /* Initialize partition data */
498
jobnbr = 1; /* One job in table yet */
499
jobtab[0].domorg = domorg; /* Build first job */
500
jobtab[0].domsub[0] = domsub[0];
501
jobtab[0].domsub[1] = domsub[1];
502
jobtab[0].grafdat = grafptr->s; /* Clone original graph as first job graph */
503
jobtab[0].grafdat.flagval &= ~GRAPHFREETABS; /* Do not free its arrays on exit */
504
kgraphMapRbPoolNew (poolptr[0], &jobtab[0]); /* Add initial job */
506
while (! kgraphMapRbPoolEmpty (poolptr[0])) { /* For all non-empty pools */
507
while ((joborgptr = kgraphMapRbPoolGet (poolptr[0])) != NULL) { /* For all jobs in pool */
508
Anum * restrict mapparttax; /* Part array of mapping to be updated */
510
joborgdat = *joborgptr; /* Save current job data (clone graph) */
512
if ((bgraphInit (&actgraph, &joborgdat.grafdat, /* Create active graph */
513
srcgrafptr, mapptr[0], joborgdat.domsub) != 0) ||
514
(bgraphBipartSt (&actgraph, paraptr->strat) != 0)) { /* Perform bipartitioning */
515
errorPrint ("kgraphMapRb: cannot bipartition job");
516
kgraphMapRbExit (jobnbr, jobtab, poolptr, mapptr, grafptr);
520
jobsubnum[0] = joborgptr - jobtab; /* Get current (and first son) job slot number (before possible move of pointers) */
521
jobsubsiz[0] = actgraph.compsize0;
522
if (jobnbr == jobmax) { /* If all job slots busy */
523
if (kgraphMapRbResize (&jobmax, &jobtab, poolptr, mapptr) != 0) { /* And if cannot resize */
524
errorPrint ("kgraphMapRb: cannot resize structures");
525
kgraphMapRbExit (jobnbr, jobtab, poolptr, mapptr, grafptr);
529
jobsubnum[1] = jobnbr ++; /* Get slot number of new subdomain */
530
jobsubsiz[1] = actgraph.s.vertnbr - actgraph.compsize0;
531
mapptr[0]->domntab[jobsubnum[1]] = domorg; /* Copy original domain to new subdomain as old mapping shares parttax with new */
533
mapparttax = mapptr[1]->parttax;
534
if (mapptr[1] == mapptr[0]) { /* If mappings are tied, update new fraction */
535
if (actgraph.s.vnumtax != NULL) {
536
for (actvertnum = actgraph.s.baseval; actvertnum < actgraph.s.vertnnd; actvertnum ++)
537
if (actgraph.parttax[actvertnum] == 1)
538
mapparttax[actgraph.s.vnumtax[actvertnum]] = jobsubnum[1];
541
for (actvertnum = actgraph.s.baseval; actvertnum < actgraph.s.vertnnd; actvertnum ++)
542
if (actgraph.parttax[actvertnum] == 1)
543
mapparttax[actvertnum] = jobsubnum[1];
547
if (actgraph.s.vnumtax != NULL) {
548
for (actvertnum = actgraph.s.baseval; actvertnum < actgraph.s.vertnnd; actvertnum ++)
549
mapparttax[actgraph.s.vnumtax[actvertnum]] = jobsubnum[actgraph.parttax[actvertnum]];
552
for (actvertnum = 0; actvertnum < actgraph.s.vertnbr; actvertnum ++)
553
mapparttax[actvertnum] = jobsubnum[actgraph.parttax[actvertnum]];
558
for (i = 1; i >= 0; i --) { /* For both subdomains, in inverse order */
559
if (jobsubsiz[i] > 0) { /* If subdomain is not empty */
560
jobtab[jobsubnum[i]].poolflag = 0; /* Activate job slot */
561
jobtab[jobsubnum[i]].domorg =
562
mapptr[1]->domntab[jobsubnum[i]] = joborgdat.domsub[i]; /* Update terminal domain array */
564
switch (archDomBipart (&grafptr->m.archdat, &jobtab[jobsubnum[i]].domorg,
565
&jobtab[jobsubnum[i]].domsub[0],
566
&jobtab[jobsubnum[i]].domsub[1])) {
567
case 0 : /* Add re-shaped job to other pool */
568
graphInducePart (&actgraph.s, actgraph.parttax, jobsubsiz[i], (GraphPart) i, &jobtab[jobsubnum[i]].grafdat);
569
kgraphMapRbPoolUpdt (poolptr[1], &grafptr->s, mapptr[1], &joborgdat, &jobtab[jobsubnum[i]], jobtab);
571
case 1 : /* New domain is terminal */
572
kgraphMapRbPoolRemv (poolptr[1], &grafptr->s, mapptr[1], &joborgdat, actgraph.parttax, (GraphPart) i, jobtab);
574
#ifdef SCOTCH_DEBUG_KGRAPH2
575
case 2 : /* On error */
576
errorPrint ("kgraphMapRb: cannot bipartition domain (2)");
577
kgraphMapRbExit (jobnbr, jobtab, poolptr, mapptr, grafptr);
579
#endif /* SCOTCH_DEBUG_KGRAPH2 */
582
else { /* Subdomain is empty */
583
jobtab[jobsubnum[i]].poolflag = 1; /* Inactivate job slot */
584
jobtab[jobsubnum[i]].poollink.prev = &kgraphmaprbpooldummy; /* Will not be considered in resizing */
585
archDomTerm (&grafptr->m.archdat, &mapptr[1]->domntab[jobsubnum[i]], archDomNum (&grafptr->m.archdat, &joborgdat.domsub[i])); /* set terminal domain */
589
else { /* If variable-sized architecture */
590
for (i = 1; i >= 0; i --) { /* For both subdomains, in inverse order */
591
mapptr[1]->domntab[jobsubnum[i]] = joborgdat.domsub[i]; /* Update domain array */
592
if ((jobsubsiz[i] > 1) && (jobsubsiz[1 - i] > 0)) { /* If worth going on */
593
jobtab[jobsubnum[i]].domorg =
594
mapptr[1]->domntab[jobsubnum[i]] = joborgdat.domsub[i]; /* Update terminal domain array */
596
switch (archDomBipart (&grafptr->m.archdat, &jobtab[jobsubnum[i]].domorg,
597
&jobtab[jobsubnum[i]].domsub[0],
598
&jobtab[jobsubnum[i]].domsub[1])) {
599
case 0 : /* Add re-shaped job to other pool */
600
graphInducePart (&actgraph.s, actgraph.parttax, jobsubsiz[i], (GraphPart) i, &jobtab[jobsubnum[i]].grafdat);
601
kgraphMapRbPoolUpdt (poolptr[1], &grafptr->s, mapptr[1], &joborgdat, &jobtab[jobsubnum[i]], jobtab);
603
default : /* If domain is terminal or on error */
604
errorPrint ("kgraphMapRb: cannot bipartition domain (2)");
605
kgraphMapRbExit (jobnbr, jobtab, poolptr, mapptr, grafptr);
609
else /* No use going on further */
610
kgraphMapRbPoolRemv (poolptr[1], &grafptr->s, mapptr[1], &joborgdat, actgraph.parttax, (GraphPart) i, jobtab);
614
bgraphExit (&actgraph); /* Free active graph data */
615
graphExit (&joborgdat.grafdat); /* Free (cloned) graph data */
618
maptmp = mapptr[0]; /* Swap current and next levels */
619
mapptr[0] = mapptr[1];
621
pooltmp = poolptr[0];
622
poolptr[0] = poolptr[1];
623
poolptr[1] = pooltmp;
626
kgraphMapRbExit (jobnbr, jobtab, poolptr, mapptr, grafptr); /* Free internal structures */
627
grafptr->m.domnmax = jobmax; /* Set maximum number of domains */
628
grafptr->m.domnnbr = jobnbr; /* Set number of domains */
633
/**********************************************/
635
/* These routines handle internal structures. */
637
/**********************************************/
639
/* This routine frees all of the internal arrays
640
** involved in the DRB algorithms. Great care
641
** should be taken that this routine always
642
** succeeds, whatever part of the algorithm it
645
** - VOID : in all cases.
651
const Anum jobnbr, /* Current number of jobs/domains */
652
KgraphMapRbJob * const jobtab, /* Pointer to job table */
653
KgraphMapRbPool ** const poolptr, /* Pointer to pool pointer array */
654
Mapping ** const maptab, /* Pointers to mapping array */
655
Kgraph * restrict const grafptr) /* Pointer to graph */
657
kgraphMapRbPoolExit (poolptr[0]); /* Always free pool contents */
658
if (poolptr[1] != poolptr[0])
659
kgraphMapRbPoolExit (poolptr[1]);
661
memFree (jobtab); /* Always free job array */
663
if (maptab[0] != maptab[1]) { /* If mappings not tied */
664
if (maptab[0] != &grafptr->m) { /* If graph mapping out of date */
665
memCpy (grafptr->m.domntab, maptab[0]->domntab, jobnbr * sizeof (ArchDom));
666
memFree (maptab[0]->domntab); /* Free mapping data */
668
else { /* Graph mapping is up to date */
669
if (maptab[1]->domntab != NULL) /* Free other mapping data */
670
memFree (maptab[1]->domntab);
675
/* This routine doubles the size all of the arrays
676
** involved in handling the target architecture,
677
** to make room for new domains of variable-sized
680
** - 0 : if resize succeeded.
681
** - !0 : if out of memory.
687
Anum * const jobmax, /* Pointer to maximum number of jobs */
688
KgraphMapRbJob ** const jobptr, /* Pointer to job table pointer */
689
KgraphMapRbPool ** const poolptr, /* Pointer to job pool array */
690
Mapping * restrict * const mapptr) /* Pointers to mapping array */
692
KgraphMapRbJob * restrict joboldtab; /* Pointer to old job array */
694
joboldtab = *jobptr; /* Save old job table address */
695
if ((*jobptr = (KgraphMapRbJob *) memRealloc (joboldtab, 2 * *jobmax * sizeof (KgraphMapRbJob))) == NULL) {
696
errorPrint ("kgraphMapRbResize: out of memory (1)");
701
if (*jobptr != joboldtab) { /* If job array moved */
702
KgraphMapRbJob * joboldtnd; /* Pointer to end of old job array */
703
Anum jobnum; /* Temporary job index */
704
size_t jobdlt; /* Address delta value */
706
joboldtnd = joboldtab + *jobmax;
707
jobdlt = (byte *) *jobptr - (byte *) joboldtab; /* Compute delta between addresses */
709
for (jobnum = 0; jobnum < *jobmax; jobnum ++) {
710
if (((*jobptr)[jobnum].poollink.prev >= (KgraphMapRbPoolLink *) joboldtab) && /* If old pointers within bounds of old array, adjust them */
711
((*jobptr)[jobnum].poollink.prev < (KgraphMapRbPoolLink *) joboldtnd))
712
(*jobptr)[jobnum].poollink.prev = (KgraphMapRbPoolLink *) ((byte *) (*jobptr)[jobnum].poollink.prev + jobdlt);
713
if (((*jobptr)[jobnum].poollink.next >= (KgraphMapRbPoolLink *) joboldtab) &&
714
((*jobptr)[jobnum].poollink.next < (KgraphMapRbPoolLink *) joboldtnd))
715
(*jobptr)[jobnum].poollink.next = (KgraphMapRbPoolLink *) ((byte *) (*jobptr)[jobnum].poollink.next + jobdlt);
717
if (poolptr[0]->poollink.next != &kgraphmaprbpooldummy) /* Update first pool pointer */
718
poolptr[0]->poollink.next = (KgraphMapRbPoolLink *) ((byte *) poolptr[0]->poollink.next + jobdlt);
719
if (poolptr[0] != poolptr[1]) { /* If job pools not tied */
720
if (poolptr[1]->poollink.next != &kgraphmaprbpooldummy) /* Update second pool pointer */
721
poolptr[1]->poollink.next = (KgraphMapRbPoolLink *) ((byte *) poolptr[1]->poollink.next + jobdlt);
725
*jobmax *= 2; /* Double job slot limit */
727
if (mapptr[0]->domnmax < *jobmax) { /* If need to increase size of domain array */
728
ArchDom * domtmp; /* Temporary pointer to domain array */
730
domtmp = mapptr[0]->domntab;
731
if ((mapptr[0]->domntab = (ArchDom *) memRealloc (mapptr[0]->domntab, *jobmax * sizeof (ArchDom))) == NULL) {
732
errorPrint ("kgraphMapRbResize: out of memory (2)");
733
mapptr[0]->domntab = domtmp;
736
mapptr[0]->domnmax = *jobmax;
738
if ((mapptr[1]->domntab != mapptr[0]->domntab) && /* If mappings not tied */
739
(mapptr[1]->domnmax < *jobmax)) { /* and need to increase size of domain array */
740
ArchDom * domtmp; /* Temporary pointer to domain array */
742
domtmp = mapptr[1]->domntab;
743
if ((mapptr[1]->domntab = (ArchDom *) memRealloc (mapptr[1]->domntab, *jobmax * sizeof (ArchDom))) == NULL) {
744
errorPrint ("kgraphMapRbResize: out of memory (3)");
745
mapptr[1]->domntab = domtmp;
748
mapptr[1]->domnmax = *jobmax;
added
removed
src/libscotch/kgraph_map_rb.c
