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: }