1
/* Copyright 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 : hdgraph_gather.c **/
36
/** AUTHORS : Francois PELLEGRINI **/
38
/** FUNCTION : This module contains the routine which **/
39
/** builds a centralized halo graph by **/
40
/** gathering the pieces of a distributed **/
43
/** DATES : # Version 5.0 : from : 19 apr 2006 **/
44
/** to : 10 sep 2007 **/
46
/************************************************************/
49
** The defines and includes.
52
#define HDGRAPH_GATHER
61
/******************************/
63
/* These routines handle halo */
64
/* distributed source graphs. */
66
/******************************/
68
/* This function gathers the pieces of
69
** a distributed halo graph to build a
70
** centralized halo graph.
71
** There is no gathered vnumtab array if
72
** the original graph did not have one, as
73
** vertices are gathered in global order, or
74
** else the original vnumloctab is gathered.
76
** - 0 : if graph data are consistent.
82
Hdgraph * restrict const dgrfptr, /* Distributed halo graph */
83
Hgraph * restrict const cgrfptr) /* Centralized halo graph */
86
Gnum vertlocadj; /* Local vertex array adjust */
88
int vhallocnbr; /* Local copy for sending as a MPI_INT */
89
Gnum * restrict verthaltax;
90
Gnum * restrict edgehaltax;
92
int ehallocnbr; /* Local copy for sending as a MPI_INT */
93
int rootnum; /* Index of root process */
94
Gnum reduloctab[4]; /* Arrays for reductions */
96
int * restrict recvcnttab; /* Arrays for parametrizing gather operations */
97
int * restrict recvdsptab;
102
if (cgrfptr != NULL) { /* If centralized graph provided */
103
reduloctab[0] = 1; /* This process is the root */
104
reduloctab[1] = (Gnum) dgrfptr->s.proclocnum; /* Get its rank */
107
reduloctab[0] = /* This process is not the root */
110
reduloctab[2] = dgrfptr->vhallocnbr;
111
reduloctab[3] = dgrfptr->ehallocnbr;
112
if (MPI_Allreduce (reduloctab, reduglbtab, 4, GNUM_MPI, MPI_SUM, dgrfptr->s.proccomm) != MPI_SUCCESS) {
113
errorPrint ("hdgraphGather: communication error (1)");
116
if (reduglbtab[0] != 1) {
117
errorPrint ("hdgraphGather: should have only one root");
120
rootnum = (int) reduglbtab[1]; /* Get rank of root process */
121
degrmax = dgrfptr->s.degrglbmax; /* Distributed degree does not account for halo edges */
124
if (cgrfptr != NULL) { /* If process is root */
129
Gnum * restrict velotax;
130
Gnum * restrict vnumtax;
133
vnohnbr = dgrfptr->s.vertglbnbr;
134
vertnbr = vnohnbr + reduglbtab[2];
135
velonbr = (dgrfptr->s.veloloctax != NULL) ? vertnbr : 0;
136
vnumnbr = (dgrfptr->s.vnumloctax != NULL) ? vnohnbr : 0; /* Vertex numbers only serve for non-halo vertices */
137
edgenbr = dgrfptr->s.edgeglbnbr + 2 * reduglbtab[3]; /* Twice since halo vertices will be created for real */
139
cgrfptr->s.flagval = GRAPHFREEEDGE | GRAPHEDGEGROUP | GRAPHFREEVERT | GRAPHVERTGROUP; /* In case of premature freeing on error */
141
if (memAllocGroup ((void **) (void *)
142
&cgrfptr->s.verttax, (size_t) ((vertnbr + 1) * sizeof (Gnum)), /* Compact vertex array */
143
&velotax, (size_t) (velonbr * sizeof (Gnum)),
144
&vnumtax, (size_t) (vnumnbr * sizeof (Gnum)),
145
&cgrfptr->vnhdtax, (size_t) (vnohnbr * sizeof (Gnum)), NULL) == NULL) {
146
errorPrint ("hdgraphGather: out of memory (1)");
149
else if (cgrfptr->s.verttax -= dgrfptr->s.baseval,
150
cgrfptr->s.velotax = (dgrfptr->s.veloloctax != NULL) ? velotax - dgrfptr->s.baseval : NULL,
151
cgrfptr->s.vnumtax = (dgrfptr->s.vnumloctax != NULL) ? vnumtax - dgrfptr->s.baseval : NULL,
152
cgrfptr->vnhdtax -= dgrfptr->s.baseval,
153
((cgrfptr->s.edgetax = (Gnum *) memAlloc (edgenbr * sizeof (Gnum))) == NULL)) {
154
errorPrint ("hdgraphGather: out of memory (2)");
157
else if (cgrfptr->s.edgetax -= dgrfptr->s.baseval,
158
memAllocGroup ((void **) (void *)
159
&recvcnttab, (size_t) (dgrfptr->s.procglbnbr * sizeof (int)),
160
&recvdsptab, (size_t) (dgrfptr->s.procglbnbr * sizeof (int)), NULL) == NULL) {
161
errorPrint ("hdgraphGather: out of memory (3)");
165
cgrfptr->s.baseval = dgrfptr->s.baseval;
166
cgrfptr->s.vertnbr = vertnbr;
167
cgrfptr->s.vertnnd = vertnbr + dgrfptr->s.baseval;
168
cgrfptr->s.vendtax = cgrfptr->s.verttax + 1; /* Compact edge array */
169
cgrfptr->s.velosum = dgrfptr->s.veloglbsum + reduglbtab[2]; /* Halo vertices have unity vertex loads */
170
cgrfptr->s.vlbltax = NULL;
171
cgrfptr->s.edgenbr = edgenbr;
172
cgrfptr->s.edlotax = NULL;
173
cgrfptr->s.edlosum = edgenbr;
174
cgrfptr->s.proccomm = MPI_COMM_NULL; /* Not a multi-sequential gather: no communication possible */
175
cgrfptr->s.procglbnbr =
176
cgrfptr->s.proclocnum = 0;
177
cgrfptr->vnohnbr = vnohnbr;
178
cgrfptr->vnohnnd = vnohnbr + dgrfptr->s.baseval;
179
cgrfptr->vnlosum = dgrfptr->s.veloglbsum;
181
cgrfptr->enohsum = dgrfptr->s.edgeglbnbr;
182
cgrfptr->levlnum = dgrfptr->levlnum;
185
if ((cheklocval == 0) &&
186
(memAllocGroup ((void **) (void *)
187
&verthaltax, (size_t) (dgrfptr->vhallocnbr * sizeof (Gnum)),
188
&edgehaltax, (size_t) (dgrfptr->ehallocnbr * sizeof (Gnum)), NULL) == NULL)) {
189
errorPrint ("hdgraphGather: out of memory (4)");
193
verthaltax -= dgrfptr->s.baseval;
194
edgehaltax -= dgrfptr->s.baseval;
196
if (MPI_Allreduce (&cheklocval, &chekglbval, 1, MPI_INT, MPI_SUM, dgrfptr->s.proccomm) != MPI_SUCCESS) {
197
errorPrint ("hdgraphGather: communication error (2)");
200
if (chekglbval != 0) {
201
if (verthaltax != NULL)
202
memFree (verthaltax + dgrfptr->s.baseval);
203
if (cgrfptr != NULL) { /* If data were previously allocated */
204
if (recvcnttab != NULL)
205
memFree (recvcnttab);
206
hgraphExit (cgrfptr);
211
if (dgrfptr->vhndloctax == dgrfptr->s.vertloctax + 1) { /* If distributed halo graph is compact */
215
if (cgrfptr != NULL) {
218
cgrfptr->s.verttax[dgrfptr->s.baseval] = dgrfptr->s.baseval;
219
if (MPI_Gatherv (dgrfptr->s.vertloctax + 1 + dgrfptr->s.baseval, /* Do not send first index, it is always equal to baseval */
220
(int) dgrfptr->s.vertlocnbr, GNUM_MPI,
221
cgrfptr->s.verttax + 1, /* First index will always be equal to baseval too, and procdsptab holds based values */
222
dgrfptr->s.proccnttab, dgrfptr->s.procdsptab, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
223
errorPrint ("hdgraphGather: communication error (3)");
226
if (MPI_Gatherv (dgrfptr->s.vendloctax + dgrfptr->s.baseval,
227
(int) dgrfptr->s.vertlocnbr, GNUM_MPI, cgrfptr->vnhdtax, /* procdsptab holds based values */
228
dgrfptr->s.proccnttab, dgrfptr->s.procdsptab, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
229
errorPrint ("hdgraphGather: communication error (4)");
233
for (procglbnum = 1, vertnum = dgrfptr->s.procdsptab[1] + 1; /* Adjust index sub-arrays for all processors except the first one */
234
procglbnum < dgrfptr->s.procglbnbr; procglbnum ++) {
238
for (vertnnd = dgrfptr->s.procdsptab[procglbnum + 1] + 1,
239
edgeadj = cgrfptr->s.verttax[vertnum - 1] - dgrfptr->s.baseval;
240
vertnum < vertnnd; vertnum ++) {
241
cgrfptr->s.verttax[vertnum] += edgeadj;
242
cgrfptr->vnhdtax[vertnum - 1] += edgeadj;
246
for (procglbnum = 0, edgenum = dgrfptr->s.baseval; /* Build arrays for MPI_Gatherv on edge arrays */
247
procglbnum < dgrfptr->s.procglbnbr; procglbnum ++) {
248
recvcnttab[procglbnum] = cgrfptr->s.verttax[dgrfptr->s.procdsptab[procglbnum + 1]] -
249
cgrfptr->s.verttax[dgrfptr->s.procdsptab[procglbnum]]; /* verttax used twice since centralized graph is compact */
250
recvdsptab[procglbnum] = edgenum;
251
edgenum += recvcnttab[procglbnum];
253
if (MPI_Gatherv (dgrfptr->s.edgeloctax + dgrfptr->s.baseval, /* Gather edge arrays with global vertex indices */
254
(int) (dgrfptr->s.edgelocnbr + dgrfptr->ehallocnbr), GNUM_MPI, cgrfptr->s.edgetax,
255
recvcnttab, recvdsptab, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
256
errorPrint ("hdgraphGather: communication error (5)");
261
if (MPI_Gatherv (dgrfptr->s.vertloctax + 1 + dgrfptr->s.baseval, /* Do not send first index, it is always equal to baseval */
262
(int) dgrfptr->s.vertlocnbr, GNUM_MPI, NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
263
errorPrint ("hdgraphGather: communication error (6)");
266
if (MPI_Gatherv (dgrfptr->s.vendloctax + dgrfptr->s.baseval,
267
(int) dgrfptr->s.vertlocnbr, GNUM_MPI, NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
268
errorPrint ("hdgraphGather: communication error (7)");
271
if (MPI_Gatherv (dgrfptr->s.edgeloctax + dgrfptr->s.baseval, /* Gather edge arrays with global vertex indices */
272
(int) (dgrfptr->s.edgelocnbr + dgrfptr->ehallocnbr), GNUM_MPI,
273
NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
274
errorPrint ("hdgraphGather: communication error (8)");
280
errorPrint ("hdgraphGather: Not implemented"); /* TODO, but not really necessary as all Hdgraph structures created by Scotch itself are compact */
284
memSet (verthaltax + dgrfptr->s.baseval, 0, dgrfptr->vhallocnbr * sizeof (Gnum)); /* Initialize halo end vertex count array */
285
for (vertlocnum = dgrfptr->s.baseval; vertlocnum < dgrfptr->s.vertlocnnd; vertlocnum ++) {
288
for (edgelocnum = dgrfptr->s.vendloctax[vertlocnum]; edgelocnum < dgrfptr->vhndloctax[vertlocnum]; edgelocnum ++)
289
verthaltax[dgrfptr->s.edgeloctax[edgelocnum]] ++; /* One more edge to this halo vertex */
291
vhallocnbr = (int) dgrfptr->vhallocnbr;
292
if (MPI_Gather (&vhallocnbr, 1, MPI_INT, recvcnttab, 1, MPI_INT, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
293
errorPrint ("hdgraphGather: communication error (9)");
296
if (cgrfptr != NULL) { /* Build gather parameter array to receive halo edge counts */
300
for (procglbnum = 0, vertnum = 0; procglbnum < dgrfptr->s.procglbnbr; procglbnum ++) { /* Displacements start from zero because adjusted later */
301
recvdsptab[procglbnum] = vertnum;
302
vertnum += recvcnttab[procglbnum];
304
if (MPI_Gatherv (verthaltax + dgrfptr->s.baseval, (int) dgrfptr->vhallocnbr, GNUM_MPI, /* Gather count arrays of halo vertices */
305
cgrfptr->s.verttax + cgrfptr->vnohnnd + 1, recvcnttab, recvdsptab, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
306
errorPrint ("hdgraphGather: communication error (10)");
310
for (procglbnum = 0, vertnum = dgrfptr->s.baseval; /* Adjust end vertex indices for halo edges */
311
procglbnum < dgrfptr->s.procglbnbr; procglbnum ++) {
315
for (vertnnd = dgrfptr->s.procdsptab[procglbnum + 1], vertadj = cgrfptr->vnohnbr + recvdsptab[procglbnum];
316
vertnum < vertnnd; vertnum ++) {
319
if (degrmax < (cgrfptr->s.vendtax[vertnum] - cgrfptr->s.verttax[vertnum])) /* Account for halo edges in maximum degree */
320
degrmax = (cgrfptr->s.vendtax[vertnum] - cgrfptr->s.verttax[vertnum]);
321
for (edgenum = cgrfptr->vnhdtax[vertnum]; edgenum < cgrfptr->s.vendtax[vertnum]; edgenum ++)
322
cgrfptr->s.edgetax[edgenum] += vertadj;
327
if (MPI_Gatherv (verthaltax + dgrfptr->s.baseval, (int) dgrfptr->vhallocnbr, GNUM_MPI, /* Gather count arrays of halo vertices */
328
NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
329
errorPrint ("hdgraphGather: communication error (11)");
333
for (vertlocnum = edgehalnum = dgrfptr->s.baseval, vhallocnnd = dgrfptr->vhallocnbr + dgrfptr->s.baseval;
334
vertlocnum < vhallocnnd; vertlocnum ++) { /* Prepare index array for edge collection */
337
degrlocval = verthaltax[vertlocnum];
338
verthaltax[vertlocnum] = edgehalnum;
339
edgehalnum += degrlocval;
341
vertlocadj = dgrfptr->s.procdsptab[dgrfptr->s.proclocnum] - dgrfptr->s.baseval;
342
for (vertlocnum = dgrfptr->s.baseval; vertlocnum < dgrfptr->s.vertlocnnd; vertlocnum ++) { /* Collect halo edge ends */
345
for (edgelocnum = dgrfptr->s.vendloctax[vertlocnum]; edgelocnum < dgrfptr->vhndloctax[vertlocnum]; edgelocnum ++)
346
edgehaltax[verthaltax[dgrfptr->s.edgeloctax[edgelocnum]] ++] = vertlocnum + vertlocadj;
348
ehallocnbr = (int) dgrfptr->ehallocnbr;
349
if (MPI_Gather (&ehallocnbr, 1, MPI_INT, recvcnttab, 1, MPI_INT, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) { /* Gather halo edge counts */
350
errorPrint ("hdgraphGather: communication error (12)");
353
if (cgrfptr != NULL) { /* Compute receive arrays for edge sub-arrays of halo vertices */
357
for (procglbnum = 0, edgeadj = 0; procglbnum < dgrfptr->s.procglbnbr; procglbnum ++) {
358
recvdsptab[procglbnum] = edgeadj;
359
edgeadj += recvcnttab[procglbnum];
361
if (MPI_Gatherv (edgehaltax + dgrfptr->s.baseval, (int) dgrfptr->ehallocnbr, GNUM_MPI, /* Gather edge arrays of halo vertices */
362
cgrfptr->s.edgetax + cgrfptr->enohnbr + reduglbtab[3] + dgrfptr->s.baseval, recvcnttab, recvdsptab, GNUM_MPI,
363
rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
364
errorPrint ("hdgraphGather: communication error (13)");
369
if (MPI_Gatherv (edgehaltax + dgrfptr->s.baseval, (int) dgrfptr->ehallocnbr, GNUM_MPI, /* Gather edge arrays of halo vertices */
370
NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
371
errorPrint ("hdgraphGather: communication error (14)");
376
memFree (verthaltax + dgrfptr->s.baseval); /* Free group leader */
378
if (cgrfptr != NULL) { /* Finalize vertex and edge arrays of centralized graph */
382
if (dgrfptr->s.veloloctax != NULL) { /* Get vertex loads if any */
383
if (MPI_Gatherv (dgrfptr->s.veloloctax + dgrfptr->s.baseval, (int) dgrfptr->s.vertlocnbr, GNUM_MPI,
384
cgrfptr->s.velotax, dgrfptr->s.proccnttab, dgrfptr->s.procdsptab, GNUM_MPI,
385
rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
386
errorPrint ("hdgraphGather: communication error (15)");
390
for (vertnum = cgrfptr->vnohnnd; vertnum < cgrfptr->s.vertnnd; vertnum ++) /* complete filling of vertex load array */
391
cgrfptr->s.velotax[vertnum] = 1;
393
if (dgrfptr->s.vnumloctax != NULL) { /* Get vertex numbers if any */
394
if (MPI_Gatherv (dgrfptr->s.vnumloctax + dgrfptr->s.baseval, (int) dgrfptr->s.vertlocnbr, GNUM_MPI,
395
cgrfptr->s.vnumtax, dgrfptr->s.proccnttab, dgrfptr->s.procdsptab, GNUM_MPI,
396
rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
397
errorPrint ("hdgraphGather: communication error (16)");
402
memFree (recvcnttab); /* Free group leader */
404
for (vertnum = cgrfptr->vnohnnd + 1, edgeadj = cgrfptr->s.verttax[cgrfptr->vnohnnd]; /* Adjust vertex array for halo vertices */
405
vertnum <= cgrfptr->s.vertnnd; vertnum ++) {
408
degrval = cgrfptr->s.verttax[vertnum];
409
if (degrmax < degrval) /* Account for halo edges in maximum degree */
412
cgrfptr->s.verttax[vertnum] = edgeadj;
414
cgrfptr->s.degrmax = degrmax;
417
if (dgrfptr->s.veloloctax != NULL) { /* Get vertex loads if any */
418
if (MPI_Gatherv (dgrfptr->s.veloloctax + dgrfptr->s.baseval, (int) dgrfptr->s.vertlocnbr, GNUM_MPI,
419
NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
420
errorPrint ("hdgraphGather: communication error (17)");
424
if (dgrfptr->s.vnumloctax != NULL) { /* Get vertex numbers if any */
425
if (MPI_Gatherv (dgrfptr->s.vnumloctax + dgrfptr->s.baseval, (int) dgrfptr->s.vertlocnbr, GNUM_MPI,
426
NULL, NULL, NULL, GNUM_MPI, rootnum, dgrfptr->s.proccomm) != MPI_SUCCESS) {
427
errorPrint ("hdgraphGather: communication error (18)");
433
#ifdef SCOTCH_DEBUG_HDGRAPH2
434
cheklocval = (cgrfptr != NULL) ? hgraphCheck (cgrfptr) : 0;
435
if (MPI_Allreduce (&cheklocval, &chekglbval, 1, MPI_INT, MPI_MAX, dgrfptr->s.proccomm) != MPI_SUCCESS) {
436
errorPrint ("hdgraphGather: communication error (19)");
439
if (chekglbval != 0) {
440
errorPrint ("hdgraphGather: internal error");
442
hgraphExit (cgrfptr);
445
#endif /* SCOTCH_DEBUG_HDGRAPH2 */
added
removed
src/libscotch/hdgraph_gather.c
