Actual source code: partitioner.c

  1: #include <petsc/private/partitionerimpl.h>

  3: /*@C
  4:   PetscPartitionerSetType - Builds a particular PetscPartitioner

  6:   Collective on PetscPartitioner

  8:   Input Parameters:
  9: + part - The PetscPartitioner object
 10: - name - The kind of partitioner

 12:   Options Database Key:
 13: . -petscpartitioner_type <type> - Sets the PetscPartitioner type; use -help for a list of available types

 15:   Note:
 16: $ PETSCPARTITIONERCHACO    - The Chaco partitioner (--download-chaco)
 17: $ PETSCPARTITIONERPARMETIS - The ParMetis partitioner (--download-parmetis)
 18: $ PETSCPARTITIONERSHELL    - A shell partitioner implemented by the user
 19: $ PETSCPARTITIONERSIMPLE   - A simple partitioner that divides cells into equal, contiguous chunks
 20: $ PETSCPARTITIONERGATHER   - Gathers all cells onto process 0

 22:   Level: intermediate

 24: .seealso: `PetscPartitionerGetType()`, `PetscPartitionerCreate()`
 25: @*/
 26: PetscErrorCode PetscPartitionerSetType(PetscPartitioner part, PetscPartitionerType name)
 27: {
 28:   PetscErrorCode (*r)(PetscPartitioner);
 29:   PetscBool match;

 32:   PetscObjectTypeCompare((PetscObject)part, name, &match);
 33:   if (match) return 0;

 35:   PetscPartitionerRegisterAll();
 36:   PetscFunctionListFind(PetscPartitionerList, name, &r);

 39:   PetscTryTypeMethod(part, destroy);
 40:   part->noGraph = PETSC_FALSE;
 41:   PetscMemzero(part->ops, sizeof(*part->ops));
 42:   PetscObjectChangeTypeName((PetscObject)part, name);
 43:   (*r)(part);
 44:   return 0;
 45: }

 47: /*@C
 48:   PetscPartitionerGetType - Gets the PetscPartitioner type name (as a string) from the object.

 50:   Not Collective

 52:   Input Parameter:
 53: . part - The PetscPartitioner

 55:   Output Parameter:
 56: . name - The PetscPartitioner type name

 58:   Level: intermediate

 60: .seealso: `PetscPartitionerSetType()`, `PetscPartitionerCreate()`
 61: @*/
 62: PetscErrorCode PetscPartitionerGetType(PetscPartitioner part, PetscPartitionerType *name)
 63: {
 66:   *name = ((PetscObject)part)->type_name;
 67:   return 0;
 68: }

 70: /*@C
 71:    PetscPartitionerViewFromOptions - View from Options

 73:    Collective on PetscPartitioner

 75:    Input Parameters:
 76: +  A - the PetscPartitioner object
 77: .  obj - Optional object
 78: -  name - command line option

 80:    Level: intermediate
 81: .seealso: `PetscPartitionerView()`, `PetscObjectViewFromOptions()`
 82: @*/
 83: PetscErrorCode PetscPartitionerViewFromOptions(PetscPartitioner A, PetscObject obj, const char name[])
 84: {
 86:   PetscObjectViewFromOptions((PetscObject)A, obj, name);
 87:   return 0;
 88: }

 90: /*@
 91:   PetscPartitionerView - Views a PetscPartitioner

 93:   Collective on PetscPartitioner

 95:   Input Parameters:
 96: + part - the PetscPartitioner object to view
 97: - v    - the viewer

 99:   Level: developer

101: .seealso: `PetscPartitionerDestroy()`
102: @*/
103: PetscErrorCode PetscPartitionerView(PetscPartitioner part, PetscViewer v)
104: {
105:   PetscMPIInt size;
106:   PetscBool   isascii;

109:   if (!v) PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)part), &v);
110:   PetscObjectTypeCompare((PetscObject)v, PETSCVIEWERASCII, &isascii);
111:   if (isascii) {
112:     MPI_Comm_size(PetscObjectComm((PetscObject)part), &size);
113:     PetscViewerASCIIPrintf(v, "Graph Partitioner: %d MPI Process%s\n", size, size > 1 ? "es" : "");
114:     PetscViewerASCIIPrintf(v, "  type: %s\n", ((PetscObject)part)->type_name);
115:     PetscViewerASCIIPrintf(v, "  edge cut: %" PetscInt_FMT "\n", part->edgeCut);
116:     PetscViewerASCIIPrintf(v, "  balance: %.2g\n", (double)part->balance);
117:     PetscViewerASCIIPrintf(v, "  use vertex weights: %d\n", part->usevwgt);
118:   }
119:   PetscTryTypeMethod(part, view, v);
120:   return 0;
121: }

123: static PetscErrorCode PetscPartitionerGetDefaultType(MPI_Comm comm, const char **defaultType)
124: {
125:   PetscMPIInt size;

127:   MPI_Comm_size(comm, &size);
128:   if (size == 1) {
129:     *defaultType = PETSCPARTITIONERSIMPLE;
130:   } else {
131: #if defined(PETSC_HAVE_PARMETIS)
132:     *defaultType = PETSCPARTITIONERPARMETIS;
133: #elif defined(PETSC_HAVE_PTSCOTCH)
134:     *defaultType = PETSCPARTITIONERPTSCOTCH;
135: #elif defined(PETSC_HAVE_CHACO)
136:     *defaultType = PETSCPARTITIONERCHACO;
137: #else
138:     *defaultType = PETSCPARTITIONERSIMPLE;
139: #endif
140:   }
141:   return 0;
142: }

144: /*@
145:   PetscPartitionerSetFromOptions - sets parameters in a PetscPartitioner from the options database

147:   Collective on PetscPartitioner

149:   Input Parameter:
150: . part - the PetscPartitioner object to set options for

152:   Options Database Keys:
153: +  -petscpartitioner_type <type> - Sets the PetscPartitioner type; use -help for a list of available types
154: .  -petscpartitioner_use_vertex_weights - Uses weights associated with the graph vertices
155: -  -petscpartitioner_view_graph - View the graph each time PetscPartitionerPartition is called. Viewer can be customized, see PetscOptionsGetViewer()

157:   Level: developer

159: .seealso: `PetscPartitionerView()`, `PetscPartitionerSetType()`, `PetscPartitionerPartition()`
160: @*/
161: PetscErrorCode PetscPartitionerSetFromOptions(PetscPartitioner part)
162: {
163:   const char *currentType = NULL;
164:   char        name[256];
165:   PetscBool   flg;

168:   PetscObjectOptionsBegin((PetscObject)part);
169:   PetscPartitionerGetType(part, &currentType);
170:   PetscOptionsFList("-petscpartitioner_type", "Graph partitioner", "PetscPartitionerSetType", PetscPartitionerList, currentType, name, sizeof(name), &flg);
171:   if (flg) PetscPartitionerSetType(part, name);
172:   PetscOptionsBool("-petscpartitioner_use_vertex_weights", "Use vertex weights", "", part->usevwgt, &part->usevwgt, NULL);
173:   PetscTryTypeMethod(part, setfromoptions, PetscOptionsObject);
174:   PetscViewerDestroy(&part->viewer);
175:   PetscViewerDestroy(&part->viewerGraph);
176:   PetscOptionsGetViewer(((PetscObject)part)->comm, ((PetscObject)part)->options, ((PetscObject)part)->prefix, "-petscpartitioner_view", &part->viewer, NULL, NULL);
177:   PetscOptionsGetViewer(((PetscObject)part)->comm, ((PetscObject)part)->options, ((PetscObject)part)->prefix, "-petscpartitioner_view_graph", &part->viewerGraph, NULL, &part->viewGraph);
178:   /* process any options handlers added with PetscObjectAddOptionsHandler() */
179:   PetscObjectProcessOptionsHandlers((PetscObject)part, PetscOptionsObject);
180:   PetscOptionsEnd();
181:   return 0;
182: }

184: /*@
185:   PetscPartitionerSetUp - Construct data structures for the PetscPartitioner

187:   Collective on PetscPartitioner

189:   Input Parameter:
190: . part - the PetscPartitioner object to setup

192:   Level: developer

194: .seealso: `PetscPartitionerView()`, `PetscPartitionerDestroy()`
195: @*/
196: PetscErrorCode PetscPartitionerSetUp(PetscPartitioner part)
197: {
199:   PetscTryTypeMethod(part, setup);
200:   return 0;
201: }

203: /*@
204:   PetscPartitionerReset - Resets data structures for the PetscPartitioner

206:   Collective on PetscPartitioner

208:   Input Parameter:
209: . part - the PetscPartitioner object to reset

211:   Level: developer

213: .seealso: `PetscPartitionerSetUp()`, `PetscPartitionerDestroy()`
214: @*/
215: PetscErrorCode PetscPartitionerReset(PetscPartitioner part)
216: {
218:   PetscTryTypeMethod(part, reset);
219:   return 0;
220: }

222: /*@
223:   PetscPartitionerDestroy - Destroys a PetscPartitioner object

225:   Collective on PetscPartitioner

227:   Input Parameter:
228: . part - the PetscPartitioner object to destroy

230:   Level: developer

232: .seealso: `PetscPartitionerView()`
233: @*/
234: PetscErrorCode PetscPartitionerDestroy(PetscPartitioner *part)
235: {
236:   if (!*part) return 0;

239:   if (--((PetscObject)(*part))->refct > 0) {
240:     *part = NULL;
241:     return 0;
242:   }
243:   ((PetscObject)(*part))->refct = 0;

245:   PetscPartitionerReset(*part);

247:   PetscViewerDestroy(&(*part)->viewer);
248:   PetscViewerDestroy(&(*part)->viewerGraph);
249:   PetscTryTypeMethod((*part), destroy);
250:   PetscHeaderDestroy(part);
251:   return 0;
252: }

254: /*@
255:   PetscPartitionerPartition - Partition a graph

257:   Collective on PetscPartitioner

259:   Input Parameters:
260: + part    - The PetscPartitioner
261: . nparts  - Number of partitions
262: . numVertices - Number of vertices in the local part of the graph
263: . start - row pointers for the local part of the graph (CSR style)
264: . adjacency - adjacency list (CSR style)
265: . vertexSection - PetscSection describing the absolute weight of each local vertex (can be NULL)
266: - targetSection - PetscSection describing the absolute weight of each partition (can be NULL)

268:   Output Parameters:
269: + partSection     - The PetscSection giving the division of points by partition
270: - partition       - The list of points by partition

272:   Options Database:
273: + -petscpartitioner_view - View the partitioner information
274: - -petscpartitioner_view_graph - View the graph we are partitioning

276:   Notes:
277:     The chart of the vertexSection (if present) must contain [0,numVertices), with the number of dofs in the section specifying the absolute weight for each vertex.
278:     The chart of the targetSection (if present) must contain [0,nparts), with the number of dofs in the section specifying the absolute weight for each partition. This information must be the same across processes, PETSc does not check it.

280:   Level: developer

282: .seealso `PetscPartitionerCreate()`, `PetscPartitionerSetType()`, `PetscSectionCreate()`, `PetscSectionSetChart()`, `PetscSectionSetDof()`
283: @*/
284: PetscErrorCode PetscPartitionerPartition(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertexSection, PetscSection targetSection, PetscSection partSection, IS *partition)
285: {
290:   if (numVertices && !part->noGraph) {
294:   }
295:   if (vertexSection) {
296:     PetscInt s, e;

299:     PetscSectionGetChart(vertexSection, &s, &e);
301:   }
302:   if (targetSection) {
303:     PetscInt s, e;

306:     PetscSectionGetChart(targetSection, &s, &e);
308:   }

312:   PetscSectionReset(partSection);
313:   PetscSectionSetChart(partSection, 0, nparts);
314:   if (nparts == 1) { /* quick */
315:     PetscSectionSetDof(partSection, 0, numVertices);
316:     ISCreateStride(PetscObjectComm((PetscObject)part), numVertices, 0, 1, partition);
317:   } else PetscUseTypeMethod(part, partition, nparts, numVertices, start, adjacency, vertexSection, targetSection, partSection, partition);
318:   PetscSectionSetUp(partSection);
319:   if (part->viewerGraph) {
320:     PetscViewer viewer = part->viewerGraph;
321:     PetscBool   isascii;
322:     PetscInt    v, i;
323:     PetscMPIInt rank;

325:     MPI_Comm_rank(PetscObjectComm((PetscObject)viewer), &rank);
326:     PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii);
327:     if (isascii) {
328:       PetscViewerASCIIPushSynchronized(viewer);
329:       PetscViewerASCIISynchronizedPrintf(viewer, "[%d]Nv: %" PetscInt_FMT "\n", rank, numVertices);
330:       for (v = 0; v < numVertices; ++v) {
331:         const PetscInt s = start[v];
332:         const PetscInt e = start[v + 1];

334:         PetscViewerASCIISynchronizedPrintf(viewer, "[%d]  ", rank);
335:         for (i = s; i < e; ++i) PetscViewerASCIISynchronizedPrintf(viewer, "%" PetscInt_FMT " ", adjacency[i]);
336:         PetscViewerASCIISynchronizedPrintf(viewer, "[%" PetscInt_FMT "-%" PetscInt_FMT ")\n", s, e);
337:       }
338:       PetscViewerFlush(viewer);
339:       PetscViewerASCIIPopSynchronized(viewer);
340:     }
341:   }
342:   if (part->viewer) PetscPartitionerView(part, part->viewer);
343:   return 0;
344: }

346: /*@
347:   PetscPartitionerCreate - Creates an empty PetscPartitioner object. The type can then be set with PetscPartitionerSetType().

349:   Collective

351:   Input Parameter:
352: . comm - The communicator for the PetscPartitioner object

354:   Output Parameter:
355: . part - The PetscPartitioner object

357:   Level: beginner

359: .seealso: `PetscPartitionerSetType()`, `PetscPartitionerDestroy()`
360: @*/
361: PetscErrorCode PetscPartitionerCreate(MPI_Comm comm, PetscPartitioner *part)
362: {
363:   PetscPartitioner p;
364:   const char      *partitionerType = NULL;

367:   *part = NULL;
368:   PetscPartitionerInitializePackage();

370:   PetscHeaderCreate(p, PETSCPARTITIONER_CLASSID, "PetscPartitioner", "Graph Partitioner", "PetscPartitioner", comm, PetscPartitionerDestroy, PetscPartitionerView);
371:   PetscPartitionerGetDefaultType(comm, &partitionerType);
372:   PetscPartitionerSetType(p, partitionerType);

374:   p->edgeCut = 0;
375:   p->balance = 0.0;
376:   p->usevwgt = PETSC_TRUE;

378:   *part = p;
379:   return 0;
380: }