Actual source code: scotch.c
2: #include <../src/mat/impls/adj/mpi/mpiadj.h>
4: EXTERN_C_BEGIN
5: #include <ptscotch.h>
6: #if defined(PETSC_HAVE_SCOTCH_PARMETIS_V3_NODEND)
7: /* we define the prototype instead of include SCOTCH's parmetis.h */
8: void SCOTCH_ParMETIS_V3_NodeND(const SCOTCH_Num *const, SCOTCH_Num *const, SCOTCH_Num *const, const SCOTCH_Num *const, const SCOTCH_Num *const, SCOTCH_Num *const, SCOTCH_Num *const, MPI_Comm *);
9: #endif
10: EXTERN_C_END
12: typedef struct {
13: double imbalance;
14: SCOTCH_Num strategy;
15: } MatPartitioning_PTScotch;
17: /*@
18: MatPartitioningPTScotchSetImbalance - Sets the value of the load imbalance
19: ratio to be used during strategy selection.
21: Collective
23: Input Parameters:
24: + part - the partitioning context
25: - imb - the load imbalance ratio
27: Options Database Key:
28: . -mat_partitioning_ptscotch_imbalance <imb> - set load imbalance ratio
30: Note:
31: Must be in the range [0,1]. The default value is 0.01.
33: Level: advanced
35: .seealso: `MATPARTITIONINGSCOTCH`, `MatPartitioningPTScotchSetStrategy()`, `MatPartitioningPTScotchGetImbalance()`
36: @*/
37: PetscErrorCode MatPartitioningPTScotchSetImbalance(MatPartitioning part, PetscReal imb)
38: {
41: PetscTryMethod(part, "MatPartitioningPTScotchSetImbalance_C", (MatPartitioning, PetscReal), (part, imb));
42: return 0;
43: }
45: PetscErrorCode MatPartitioningPTScotchSetImbalance_PTScotch(MatPartitioning part, PetscReal imb)
46: {
47: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
49: if (imb == PETSC_DEFAULT) scotch->imbalance = 0.01;
50: else {
52: scotch->imbalance = (double)imb;
53: }
54: return 0;
55: }
57: /*@
58: MatPartitioningPTScotchGetImbalance - Gets the value of the load imbalance
59: ratio used during strategy selection.
61: Not Collective
63: Input Parameter:
64: . part - the partitioning context
66: Output Parameter:
67: . imb - the load imbalance ratio
69: Level: advanced
71: .seealso: `MATPARTITIONINGSCOTCH`, `MatPartitioningPTScotchSetImbalance()`
72: @*/
73: PetscErrorCode MatPartitioningPTScotchGetImbalance(MatPartitioning part, PetscReal *imb)
74: {
77: PetscUseMethod(part, "MatPartitioningPTScotchGetImbalance_C", (MatPartitioning, PetscReal *), (part, imb));
78: return 0;
79: }
81: PetscErrorCode MatPartitioningPTScotchGetImbalance_PTScotch(MatPartitioning part, PetscReal *imb)
82: {
83: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
85: *imb = scotch->imbalance;
86: return 0;
87: }
89: /*@
90: MatPartitioningPTScotchSetStrategy - Sets the strategy to be used in PTScotch.
92: Collective
94: Input Parameters:
95: + part - the partitioning context
96: - strategy - the strategy, one of
97: .vb
98: MP_PTSCOTCH_DEFAULT - Default behavior
99: MP_PTSCOTCH_QUALITY - Prioritize quality over speed
100: MP_PTSCOTCH_SPEED - Prioritize speed over quality
101: MP_PTSCOTCH_BALANCE - Enforce load balance
102: MP_PTSCOTCH_SAFETY - Avoid methods that may fail
103: MP_PTSCOTCH_SCALABILITY - Favor scalability as much as possible
104: .ve
106: Options Database Key:
107: . -mat_partitioning_ptscotch_strategy [quality,speed,balance,safety,scalability] - strategy
109: Level: advanced
111: Note:
112: The default is `MP_SCOTCH_QUALITY`. See the PTScotch documentation for more information.
114: .seealso: `MATPARTITIONINGSCOTCH`, `MatPartitioningPTScotchSetImbalance()`, `MatPartitioningPTScotchGetStrategy()`
115: @*/
116: PetscErrorCode MatPartitioningPTScotchSetStrategy(MatPartitioning part, MPPTScotchStrategyType strategy)
117: {
120: PetscTryMethod(part, "MatPartitioningPTScotchSetStrategy_C", (MatPartitioning, MPPTScotchStrategyType), (part, strategy));
121: return 0;
122: }
124: PetscErrorCode MatPartitioningPTScotchSetStrategy_PTScotch(MatPartitioning part, MPPTScotchStrategyType strategy)
125: {
126: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
128: switch (strategy) {
129: case MP_PTSCOTCH_QUALITY:
130: scotch->strategy = SCOTCH_STRATQUALITY;
131: break;
132: case MP_PTSCOTCH_SPEED:
133: scotch->strategy = SCOTCH_STRATSPEED;
134: break;
135: case MP_PTSCOTCH_BALANCE:
136: scotch->strategy = SCOTCH_STRATBALANCE;
137: break;
138: case MP_PTSCOTCH_SAFETY:
139: scotch->strategy = SCOTCH_STRATSAFETY;
140: break;
141: case MP_PTSCOTCH_SCALABILITY:
142: scotch->strategy = SCOTCH_STRATSCALABILITY;
143: break;
144: default:
145: scotch->strategy = SCOTCH_STRATDEFAULT;
146: break;
147: }
148: return 0;
149: }
151: /*@
152: MatPartitioningPTScotchGetStrategy - Gets the strategy used in PTScotch.
154: Not Collective
156: Input Parameter:
157: . part - the partitioning context
159: Output Parameter:
160: . strategy - the strategy
162: Level: advanced
164: .seealso: `MATPARTITIONINGSCOTCH`, `MatPartitioningPTScotchSetStrategy()`
165: @*/
166: PetscErrorCode MatPartitioningPTScotchGetStrategy(MatPartitioning part, MPPTScotchStrategyType *strategy)
167: {
170: PetscUseMethod(part, "MatPartitioningPTScotchGetStrategy_C", (MatPartitioning, MPPTScotchStrategyType *), (part, strategy));
171: return 0;
172: }
174: PetscErrorCode MatPartitioningPTScotchGetStrategy_PTScotch(MatPartitioning part, MPPTScotchStrategyType *strategy)
175: {
176: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
178: switch (scotch->strategy) {
179: case SCOTCH_STRATQUALITY:
180: *strategy = MP_PTSCOTCH_QUALITY;
181: break;
182: case SCOTCH_STRATSPEED:
183: *strategy = MP_PTSCOTCH_SPEED;
184: break;
185: case SCOTCH_STRATBALANCE:
186: *strategy = MP_PTSCOTCH_BALANCE;
187: break;
188: case SCOTCH_STRATSAFETY:
189: *strategy = MP_PTSCOTCH_SAFETY;
190: break;
191: case SCOTCH_STRATSCALABILITY:
192: *strategy = MP_PTSCOTCH_SCALABILITY;
193: break;
194: default:
195: *strategy = MP_PTSCOTCH_DEFAULT;
196: break;
197: }
198: return 0;
199: }
201: PetscErrorCode MatPartitioningView_PTScotch(MatPartitioning part, PetscViewer viewer)
202: {
203: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
204: PetscBool isascii;
205: const char *str = NULL;
207: PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii);
208: if (isascii) {
209: switch (scotch->strategy) {
210: case SCOTCH_STRATQUALITY:
211: str = "Prioritize quality over speed";
212: break;
213: case SCOTCH_STRATSPEED:
214: str = "Prioritize speed over quality";
215: break;
216: case SCOTCH_STRATBALANCE:
217: str = "Enforce load balance";
218: break;
219: case SCOTCH_STRATSAFETY:
220: str = "Avoid methods that may fail";
221: break;
222: case SCOTCH_STRATSCALABILITY:
223: str = "Favor scalability as much as possible";
224: break;
225: default:
226: str = "Default behavior";
227: break;
228: }
229: PetscViewerASCIIPrintf(viewer, " Strategy=%s\n", str);
230: PetscViewerASCIIPrintf(viewer, " Load imbalance ratio=%g\n", scotch->imbalance);
231: }
232: return 0;
233: }
235: PetscErrorCode MatPartitioningSetFromOptions_PTScotch(MatPartitioning part, PetscOptionItems *PetscOptionsObject)
236: {
237: PetscBool flag;
238: PetscReal r;
239: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
240: MPPTScotchStrategyType strat;
242: MatPartitioningPTScotchGetStrategy(part, &strat);
243: PetscOptionsHeadBegin(PetscOptionsObject, "PTScotch partitioning options");
244: PetscOptionsEnum("-mat_partitioning_ptscotch_strategy", "Strategy", "MatPartitioningPTScotchSetStrategy", MPPTScotchStrategyTypes, (PetscEnum)strat, (PetscEnum *)&strat, &flag);
245: if (flag) MatPartitioningPTScotchSetStrategy(part, strat);
246: PetscOptionsReal("-mat_partitioning_ptscotch_imbalance", "Load imbalance ratio", "MatPartitioningPTScotchSetImbalance", scotch->imbalance, &r, &flag);
247: if (flag) MatPartitioningPTScotchSetImbalance(part, r);
248: PetscOptionsHeadEnd();
249: return 0;
250: }
252: static PetscErrorCode MatPartitioningApply_PTScotch_Private(MatPartitioning part, PetscBool useND, IS *partitioning)
253: {
254: MPI_Comm pcomm, comm;
255: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
256: PetscMPIInt rank;
257: Mat mat = part->adj;
258: Mat_MPIAdj *adj = (Mat_MPIAdj *)mat->data;
259: PetscBool flg, distributed;
260: PetscBool proc_weight_flg;
261: PetscInt i, j, p, bs = 1, nold;
262: PetscInt *NDorder = NULL;
263: PetscReal *vwgttab, deltval;
264: SCOTCH_Num *locals, *velotab, *veloloctab, *edloloctab, vertlocnbr, edgelocnbr, nparts = part->n;
266: PetscObjectGetComm((PetscObject)part, &pcomm);
267: /* Duplicate the communicator to be sure that PTSCOTCH attribute caching does not interfere with PETSc. */
268: MPI_Comm_dup(pcomm, &comm);
269: MPI_Comm_rank(comm, &rank);
270: PetscObjectTypeCompare((PetscObject)mat, MATMPIADJ, &flg);
271: if (!flg) {
272: /* bs indicates if the converted matrix is "reduced" from the original and hence the
273: resulting partition results need to be stretched to match the original matrix */
274: nold = mat->rmap->n;
275: MatConvert(mat, MATMPIADJ, MAT_INITIAL_MATRIX, &mat);
276: if (mat->rmap->n > 0) bs = nold / mat->rmap->n;
277: adj = (Mat_MPIAdj *)mat->data;
278: }
280: proc_weight_flg = part->part_weights ? PETSC_TRUE : PETSC_FALSE;
281: PetscOptionsGetBool(NULL, NULL, "-mat_partitioning_ptscotch_proc_weight", &proc_weight_flg, NULL);
283: PetscMalloc1(mat->rmap->n + 1, &locals);
285: if (useND) {
286: #if defined(PETSC_HAVE_SCOTCH_PARMETIS_V3_NODEND)
287: PetscInt *sizes, *seps, log2size, subd, *level, base = 0;
288: PetscMPIInt size;
290: MPI_Comm_size(comm, &size);
291: log2size = PetscLog2Real(size);
292: subd = PetscPowInt(2, log2size);
294: PetscMalloc1(mat->rmap->n, &NDorder);
295: PetscMalloc3(2 * size, &sizes, 4 * size, &seps, size, &level);
296: SCOTCH_ParMETIS_V3_NodeND(mat->rmap->range, adj->i, adj->j, &base, NULL, NDorder, sizes, &comm);
297: MatPartitioningSizesToSep_Private(subd, sizes, seps, level);
298: for (i = 0; i < mat->rmap->n; i++) {
299: PetscInt loc;
301: PetscFindInt(NDorder[i], 2 * subd, seps, &loc);
302: if (loc < 0) {
303: loc = -(loc + 1);
304: if (loc % 2) { /* part of subdomain */
305: locals[i] = loc / 2;
306: } else {
307: PetscFindInt(NDorder[i], 2 * (subd - 1), seps + 2 * subd, &loc);
308: loc = loc < 0 ? -(loc + 1) / 2 : loc / 2;
309: locals[i] = level[loc];
310: }
311: } else locals[i] = loc / 2;
312: }
313: PetscFree3(sizes, seps, level);
314: #else
315: SETERRQ(pcomm, PETSC_ERR_SUP, "Need libptscotchparmetis.a compiled with -DSCOTCH_METIS_PREFIX");
316: #endif
317: } else {
318: velotab = NULL;
319: if (proc_weight_flg) {
320: PetscMalloc1(nparts, &vwgttab);
321: PetscMalloc1(nparts, &velotab);
322: for (j = 0; j < nparts; j++) {
323: if (part->part_weights) vwgttab[j] = part->part_weights[j] * nparts;
324: else vwgttab[j] = 1.0;
325: }
326: for (i = 0; i < nparts; i++) {
327: deltval = PetscAbsReal(vwgttab[i] - PetscFloorReal(vwgttab[i] + 0.5));
328: if (deltval > 0.01) {
329: for (j = 0; j < nparts; j++) vwgttab[j] /= deltval;
330: }
331: }
332: for (i = 0; i < nparts; i++) velotab[i] = (SCOTCH_Num)(vwgttab[i] + 0.5);
333: PetscFree(vwgttab);
334: }
336: vertlocnbr = mat->rmap->range[rank + 1] - mat->rmap->range[rank];
337: edgelocnbr = adj->i[vertlocnbr];
338: veloloctab = part->vertex_weights;
339: edloloctab = part->use_edge_weights ? adj->values : NULL;
341: /* detect whether all vertices are located at the same process in original graph */
342: for (p = 0; !mat->rmap->range[p + 1] && p < nparts; ++p)
343: ;
344: distributed = (mat->rmap->range[p + 1] == mat->rmap->N) ? PETSC_FALSE : PETSC_TRUE;
345: if (distributed) {
346: SCOTCH_Arch archdat;
347: SCOTCH_Dgraph grafdat;
348: SCOTCH_Dmapping mappdat;
349: SCOTCH_Strat stradat;
351: SCOTCH_dgraphInit(&grafdat, comm);
352: SCOTCH_dgraphBuild(&grafdat, 0, vertlocnbr, vertlocnbr, adj->i, adj->i + 1, veloloctab, NULL, edgelocnbr, edgelocnbr, adj->j, NULL, edloloctab);
354: if (PetscDefined(USE_DEBUG)) SCOTCH_dgraphCheck(&grafdat);
356: SCOTCH_archInit(&archdat);
357: SCOTCH_stratInit(&stradat);
358: SCOTCH_stratDgraphMapBuild(&stradat, scotch->strategy, nparts, nparts, scotch->imbalance);
360: if (velotab) {
361: SCOTCH_archCmpltw(&archdat, nparts, velotab);
362: } else {
363: SCOTCH_archCmplt(&archdat, nparts);
364: }
365: SCOTCH_dgraphMapInit(&grafdat, &mappdat, &archdat, locals);
366: SCOTCH_dgraphMapCompute(&grafdat, &mappdat, &stradat);
368: SCOTCH_dgraphMapExit(&grafdat, &mappdat);
369: SCOTCH_archExit(&archdat);
370: SCOTCH_stratExit(&stradat);
371: SCOTCH_dgraphExit(&grafdat);
373: } else if (rank == p) {
374: SCOTCH_Graph grafdat;
375: SCOTCH_Strat stradat;
377: SCOTCH_graphInit(&grafdat);
378: SCOTCH_graphBuild(&grafdat, 0, vertlocnbr, adj->i, adj->i + 1, veloloctab, NULL, edgelocnbr, adj->j, edloloctab);
379: if (PetscDefined(USE_DEBUG)) SCOTCH_graphCheck(&grafdat);
380: SCOTCH_stratInit(&stradat);
381: SCOTCH_stratGraphMapBuild(&stradat, scotch->strategy, nparts, scotch->imbalance);
382: if (velotab) {
383: SCOTCH_Arch archdat;
384: SCOTCH_archInit(&archdat);
385: SCOTCH_archCmpltw(&archdat, nparts, velotab);
386: SCOTCH_graphMap(&grafdat, &archdat, &stradat, locals);
387: SCOTCH_archExit(&archdat);
388: } else {
389: SCOTCH_graphPart(&grafdat, nparts, &stradat, locals);
390: }
391: SCOTCH_stratExit(&stradat);
392: SCOTCH_graphExit(&grafdat);
393: }
395: PetscFree(velotab);
396: }
397: MPI_Comm_free(&comm);
399: if (bs > 1) {
400: PetscInt *newlocals;
401: PetscMalloc1(bs * mat->rmap->n, &newlocals);
402: for (i = 0; i < mat->rmap->n; i++) {
403: for (j = 0; j < bs; j++) newlocals[bs * i + j] = locals[i];
404: }
405: PetscFree(locals);
406: ISCreateGeneral(pcomm, bs * mat->rmap->n, newlocals, PETSC_OWN_POINTER, partitioning);
407: } else {
408: ISCreateGeneral(pcomm, mat->rmap->n, locals, PETSC_OWN_POINTER, partitioning);
409: }
410: if (useND) {
411: IS ndis;
413: if (bs > 1) {
414: ISCreateBlock(pcomm, bs, mat->rmap->n, NDorder, PETSC_OWN_POINTER, &ndis);
415: } else {
416: ISCreateGeneral(pcomm, mat->rmap->n, NDorder, PETSC_OWN_POINTER, &ndis);
417: }
418: ISSetPermutation(ndis);
419: PetscObjectCompose((PetscObject)(*partitioning), "_petsc_matpartitioning_ndorder", (PetscObject)ndis);
420: ISDestroy(&ndis);
421: }
423: if (!flg) MatDestroy(&mat);
424: return 0;
425: }
427: PetscErrorCode MatPartitioningApply_PTScotch(MatPartitioning part, IS *partitioning)
428: {
429: MatPartitioningApply_PTScotch_Private(part, PETSC_FALSE, partitioning);
430: return 0;
431: }
433: PetscErrorCode MatPartitioningApplyND_PTScotch(MatPartitioning part, IS *partitioning)
434: {
435: MatPartitioningApply_PTScotch_Private(part, PETSC_TRUE, partitioning);
436: return 0;
437: }
439: PetscErrorCode MatPartitioningDestroy_PTScotch(MatPartitioning part)
440: {
441: MatPartitioning_PTScotch *scotch = (MatPartitioning_PTScotch *)part->data;
443: PetscFree(scotch);
444: /* clear composed functions */
445: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchSetImbalance_C", NULL);
446: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchGetImbalance_C", NULL);
447: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchSetStrategy_C", NULL);
448: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchGetStrategy_C", NULL);
449: return 0;
450: }
452: /*MC
453: MATPARTITIONINGPTSCOTCH - Creates a partitioning context that uses the external package SCOTCH.
455: Level: beginner
457: Note:
458: See http://www.labri.fr/perso/pelegrin/scotch/
460: .seealso: `MatPartitioningSetType()`, `MatPartitioningType`, `MatPartitioningPTScotchSetImbalance()`, `MatPartitioningPTScotchGetImbalance()`,
461: `MatPartitioningPTScotchSetStrategy()`, `MatPartitioningPTScotchGetStrategy()`
462: M*/
464: PETSC_EXTERN PetscErrorCode MatPartitioningCreate_PTScotch(MatPartitioning part)
465: {
466: MatPartitioning_PTScotch *scotch;
468: PetscNew(&scotch);
469: part->data = (void *)scotch;
471: scotch->imbalance = 0.01;
472: scotch->strategy = SCOTCH_STRATDEFAULT;
474: part->ops->apply = MatPartitioningApply_PTScotch;
475: part->ops->applynd = MatPartitioningApplyND_PTScotch;
476: part->ops->view = MatPartitioningView_PTScotch;
477: part->ops->setfromoptions = MatPartitioningSetFromOptions_PTScotch;
478: part->ops->destroy = MatPartitioningDestroy_PTScotch;
480: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchSetImbalance_C", MatPartitioningPTScotchSetImbalance_PTScotch);
481: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchGetImbalance_C", MatPartitioningPTScotchGetImbalance_PTScotch);
482: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchSetStrategy_C", MatPartitioningPTScotchSetStrategy_PTScotch);
483: PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPTScotchGetStrategy_C", MatPartitioningPTScotchGetStrategy_PTScotch);
484: return 0;
485: }