Actual source code: partitioner.c
1: #include <petsc/private/partitionerimpl.h>
3: /*@
4: PetscPartitionerSetType - Builds a particular `PetscPartitioner`
6: Collective
8: Input Parameters:
9: + part - The `PetscPartitioner` object
10: - name - The kind of partitioner
12: Options Database Key:
13: . -petscpartitioner_type type - Sets the `PetscPartitionerType`
15: Level: intermediate
17: Note:
18: .vb
19: PETSCPARTITIONERCHACO - The Chaco partitioner (--download-chaco)
20: PETSCPARTITIONERPARMETIS - The ParMETIS partitioner (--download-parmetis)
21: PETSCPARTITIONERSHELL - A shell partitioner implemented by the user
22: PETSCPARTITIONERSIMPLE - A simple partitioner that divides cells into equal, contiguous chunks
23: PETSCPARTITIONERGATHER - Gathers all cells onto process 0
24: .ve
26: .seealso: `PetscPartitionerGetType()`, `PetscPartitionerCreate()`
27: @*/
28: PetscErrorCode PetscPartitionerSetType(PetscPartitioner part, PetscPartitionerType name)
29: {
30: PetscErrorCode (*r)(PetscPartitioner);
31: PetscBool match;
33: PetscFunctionBegin;
35: PetscCall(PetscObjectTypeCompare((PetscObject)part, name, &match));
36: if (match) PetscFunctionReturn(PETSC_SUCCESS);
38: PetscCall(PetscPartitionerRegisterAll());
39: PetscCall(PetscFunctionListFind(PetscPartitionerList, name, &r));
40: PetscCheck(r, PetscObjectComm((PetscObject)part), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unknown PetscPartitioner type: %s", name);
42: PetscTryTypeMethod(part, destroy);
43: part->noGraph = PETSC_FALSE;
44: PetscCall(PetscMemzero(part->ops, sizeof(*part->ops)));
45: PetscCall(PetscObjectChangeTypeName((PetscObject)part, name));
46: PetscCall((*r)(part));
47: PetscFunctionReturn(PETSC_SUCCESS);
48: }
50: /*@
51: PetscPartitionerGetType - Gets the PetscPartitioner type name (as a string) from the object.
53: Not Collective
55: Input Parameter:
56: . part - The PetscPartitioner
58: Output Parameter:
59: . name - The PetscPartitioner type name
61: Level: intermediate
63: .seealso: `PetscPartitionerSetType()`, `PetscPartitionerCreate()`
64: @*/
65: PetscErrorCode PetscPartitionerGetType(PetscPartitioner part, PetscPartitionerType *name)
66: {
67: PetscFunctionBegin;
69: PetscAssertPointer(name, 2);
70: *name = ((PetscObject)part)->type_name;
71: PetscFunctionReturn(PETSC_SUCCESS);
72: }
74: /*@
75: PetscPartitionerViewFromOptions - View a `PetscPartitioner` object based on options in the options database
77: Collective
79: Input Parameters:
80: + A - the `PetscPartitioner` object
81: . obj - optional `PetscObject` that provides the options prefix, pass `NULL` to use the options prefix of `A`
82: - name - command line option
84: Options Database Key:
85: . -name viewer_specification - See `PetscOptionsCreateViewer()` for the values of `viewer_specification`
87: Level: intermediate
89: Note:
90: This checks the options database, creates the viewer on-the-fly, uses it and then destroys it. Hence it should not be called in heavily used routines,
91: rather `PetscOptionsCreateViewer()` should be used to construct the viewer once which can then be utilized in the heavily used routine.
93: .seealso: `PetscPartitioner`, `PetscPartitionerView()`, `PetscObjectViewFromOptions()`, `PetscOptionsCreateViewer()`
94: @*/
95: PetscErrorCode PetscPartitionerViewFromOptions(PetscPartitioner A, PetscObject obj, const char name[])
96: {
97: PetscFunctionBegin;
99: PetscCall(PetscObjectViewFromOptions((PetscObject)A, obj, name));
100: PetscFunctionReturn(PETSC_SUCCESS);
101: }
103: /*@
104: PetscPartitionerView - Views a `PetscPartitioner`
106: Collective
108: Input Parameters:
109: + part - the `PetscPartitioner` object to view
110: - v - the viewer
112: Level: developer
114: .seealso: `PetscPartitionerDestroy()`
115: @*/
116: PetscErrorCode PetscPartitionerView(PetscPartitioner part, PetscViewer v)
117: {
118: PetscMPIInt size;
119: PetscBool isascii;
121: PetscFunctionBegin;
123: if (!v) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)part), &v));
124: PetscCall(PetscObjectTypeCompare((PetscObject)v, PETSCVIEWERASCII, &isascii));
125: if (isascii && part->printHeader) {
126: PetscCallMPI(MPI_Comm_size(PetscObjectComm((PetscObject)part), &size));
127: PetscCall(PetscViewerASCIIPrintf(v, "Graph Partitioner: %d MPI Process%s\n", size, size > 1 ? "es" : ""));
128: PetscCall(PetscViewerASCIIPrintf(v, " type: %s\n", ((PetscObject)part)->type_name));
129: PetscCall(PetscViewerASCIIPrintf(v, " edge cut: %" PetscInt_FMT "\n", part->edgeCut));
130: PetscCall(PetscViewerASCIIPrintf(v, " balance: %.2g\n", (double)part->balance));
131: PetscCall(PetscViewerASCIIPrintf(v, " use vertex weights: %d\n", part->usevwgt));
132: PetscCall(PetscViewerASCIIPrintf(v, " use edge weights: %d\n", part->useewgt));
133: }
134: PetscTryTypeMethod(part, view, v);
135: PetscFunctionReturn(PETSC_SUCCESS);
136: }
138: static PetscErrorCode PetscPartitionerGetDefaultType(MPI_Comm comm, const char **defaultType)
139: {
140: PetscMPIInt size;
142: PetscFunctionBegin;
143: PetscCallMPI(MPI_Comm_size(comm, &size));
144: if (size == 1) {
145: *defaultType = PETSCPARTITIONERSIMPLE;
146: } else {
147: #if PetscDefined(HAVE_PARMETIS)
148: *defaultType = PETSCPARTITIONERPARMETIS;
149: #elif PetscDefined(HAVE_PTSCOTCH)
150: *defaultType = PETSCPARTITIONERPTSCOTCH;
151: #elif PetscDefined(HAVE_CHACO)
152: *defaultType = PETSCPARTITIONERCHACO;
153: #else
154: *defaultType = PETSCPARTITIONERSIMPLE;
155: #endif
156: }
157: PetscFunctionReturn(PETSC_SUCCESS);
158: }
160: /*@
161: PetscPartitionerSetFromOptions - sets parameters in a `PetscPartitioner` from the options database
163: Collective
165: Input Parameter:
166: . part - the `PetscPartitioner` object to set options for
168: Options Database Keys:
169: + -petscpartitioner_type type - Sets the `PetscPartitionerType`
170: . -petscpartitioner_use_vertex_weights - Uses weights associated with the graph vertices
171: - -petscpartitioner_view_graph - View the graph each time PetscPartitionerPartition is called. Viewer can be customized, see `PetscOptionsCreateViewer()`
173: Level: developer
175: .seealso: `PetscPartitionerView()`, `PetscPartitionerSetType()`, `PetscPartitionerPartition()`
176: @*/
177: PetscErrorCode PetscPartitionerSetFromOptions(PetscPartitioner part)
178: {
179: const char *currentType = NULL;
180: char name[256];
181: PetscBool flg;
183: PetscFunctionBegin;
185: PetscObjectOptionsBegin((PetscObject)part);
186: PetscCall(PetscPartitionerGetType(part, ¤tType));
187: PetscCall(PetscOptionsFList("-petscpartitioner_type", "Graph partitioner", "PetscPartitionerSetType", PetscPartitionerList, currentType, name, sizeof(name), &flg));
188: if (flg) PetscCall(PetscPartitionerSetType(part, name));
189: PetscCall(PetscOptionsBool("-petscpartitioner_use_vertex_weights", "Use vertex weights", "", part->usevwgt, &part->usevwgt, NULL));
190: PetscCall(PetscOptionsBool("-petscpartitioner_use_edge_weights", "Use edge weights", "", part->useewgt, &part->useewgt, NULL));
191: PetscTryTypeMethod(part, setfromoptions, PetscOptionsObject);
192: PetscCall(PetscViewerDestroy(&part->viewer));
193: PetscCall(PetscViewerDestroy(&part->viewerGraph));
194: PetscCall(PetscOptionsCreateViewer(((PetscObject)part)->comm, ((PetscObject)part)->options, ((PetscObject)part)->prefix, "-petscpartitioner_view", &part->viewer, &part->viewerFmt, NULL));
195: PetscCall(PetscOptionsCreateViewer(((PetscObject)part)->comm, ((PetscObject)part)->options, ((PetscObject)part)->prefix, "-petscpartitioner_view_graph", &part->viewerGraph, NULL, NULL));
196: /* process any options handlers added with PetscObjectAddOptionsHandler() */
197: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)part, PetscOptionsObject));
198: PetscOptionsEnd();
199: PetscFunctionReturn(PETSC_SUCCESS);
200: }
202: /*@
203: PetscPartitionerSetUp - Construct data structures for the `PetscPartitioner`
205: Collective
207: Input Parameter:
208: . part - the `PetscPartitioner` object to setup
210: Level: developer
212: .seealso: `PetscPartitionerView()`, `PetscPartitionerDestroy()`
213: @*/
214: PetscErrorCode PetscPartitionerSetUp(PetscPartitioner part)
215: {
216: PetscFunctionBegin;
218: PetscTryTypeMethod(part, setup);
219: PetscFunctionReturn(PETSC_SUCCESS);
220: }
222: /*@
223: PetscPartitionerReset - Resets data structures for the `PetscPartitioner`
225: Collective
227: Input Parameter:
228: . part - the `PetscPartitioner` object to reset
230: Level: developer
232: .seealso: `PetscPartitionerSetUp()`, `PetscPartitionerDestroy()`
233: @*/
234: PetscErrorCode PetscPartitionerReset(PetscPartitioner part)
235: {
236: PetscFunctionBegin;
238: PetscTryTypeMethod(part, reset);
239: PetscFunctionReturn(PETSC_SUCCESS);
240: }
242: /*@
243: PetscPartitionerDestroy - Destroys a `PetscPartitioner` object
245: Collective
247: Input Parameter:
248: . part - the `PetscPartitioner` object to destroy
250: Level: developer
252: .seealso: `PetscPartitionerView()`
253: @*/
254: PetscErrorCode PetscPartitionerDestroy(PetscPartitioner *part)
255: {
256: PetscFunctionBegin;
257: if (!*part) PetscFunctionReturn(PETSC_SUCCESS);
260: if (--((PetscObject)*part)->refct > 0) {
261: *part = NULL;
262: PetscFunctionReturn(PETSC_SUCCESS);
263: }
264: ((PetscObject)*part)->refct = 0;
266: PetscCall(PetscPartitionerReset(*part));
268: PetscCall(PetscViewerDestroy(&(*part)->viewer));
269: PetscCall(PetscViewerDestroy(&(*part)->viewerGraph));
270: PetscTryTypeMethod(*part, destroy);
271: PetscCall(PetscHeaderDestroy(part));
272: PetscFunctionReturn(PETSC_SUCCESS);
273: }
275: /*@
276: PetscPartitionerPartition - Partition a graph
278: Collective
280: Input Parameters:
281: + part - the `PetscPartitioner`
282: . nparts - the number of partitions requested
283: . numVertices - the number of vertices in the local part of the graph
284: . start - row pointers for the local part of the graph (CSR style)
285: . adjacency - adjacency list (CSR style)
286: . vertexSection - the absolute weight of each local vertex (can be `NULL`)
287: . edgeSection - the absolute weight of each local edge (can be `NULL`)
288: - targetSection - the absolute weight of each partition (can be `NULL`)
290: Output Parameters:
291: + partSection - the `PetscSection` giving the division of points by the partitioner
292: - partition - the list of points by partition
294: Options Database Keys:
295: + -petscpartitioner_view viewer_specification - view the partitioner information. See `PetscOptionsCreateViewer()` for the format of `viewer_specification`
296: - -petscpartitioner_view_graph viewer_specification - view the graph we are partitioning. See `PetscOptionsCreateViewer()` for the format of `viewer_specification`
298: Level: developer
300: Notes:
301: 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.
303: 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.
304: This information must be the same across processes, PETSc does not check it.
306: .seealso: `PetscPartitionerCreate()`, `PetscPartitionerSetType()`, `PetscSectionCreate()`, `PetscSectionSetChart()`, `PetscSectionSetDof()`,
307: `PetscOptionsCreateViewer()`, `PetscIntCSRView()`
308: @*/
309: PetscErrorCode PetscPartitionerPartition(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertexSection, PetscSection edgeSection, PetscSection targetSection, PetscSection partSection, IS *partition)
310: {
311: PetscFunctionBegin;
314: PetscCheck(nparts > 0, PetscObjectComm((PetscObject)part), PETSC_ERR_ARG_OUTOFRANGE, "Number of parts must be positive");
315: PetscCheck(numVertices >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Number of vertices must be non-negative");
316: if (numVertices && !part->noGraph) {
317: PetscAssertPointer(start, 4);
318: PetscAssertPointer(start + numVertices, 4);
319: if (start[numVertices]) PetscAssertPointer(adjacency, 5);
320: }
321: if (vertexSection) {
322: PetscInt s, e;
325: PetscCall(PetscSectionGetChart(vertexSection, &s, &e));
326: PetscCheck(s <= 0 && e >= numVertices, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Invalid vertexSection chart [%" PetscInt_FMT ",%" PetscInt_FMT ")", s, e);
327: }
328: if (edgeSection) {
329: PetscInt s, e;
332: PetscCall(PetscSectionGetChart(edgeSection, &s, &e));
333: PetscCheck(s <= 0 && e >= start[numVertices], PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Invalid edgeSection chart [%" PetscInt_FMT ",%" PetscInt_FMT ")", s, e);
334: }
335: if (targetSection) {
336: PetscInt s, e;
339: PetscCall(PetscSectionGetChart(targetSection, &s, &e));
340: PetscCheck(s <= 0 && e >= nparts, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Invalid targetSection chart [%" PetscInt_FMT ",%" PetscInt_FMT ")", s, e);
341: }
343: PetscAssertPointer(partition, 10);
345: PetscCall(PetscSectionReset(partSection));
346: PetscCall(PetscSectionSetChart(partSection, 0, nparts));
347: if (nparts == 1) { /* quick */
348: PetscCall(PetscSectionSetDof(partSection, 0, numVertices));
349: PetscCall(ISCreateStride(PetscObjectComm((PetscObject)part), numVertices, 0, 1, partition));
350: } else PetscUseTypeMethod(part, partition, nparts, numVertices, start, adjacency, vertexSection, edgeSection, targetSection, partSection, partition);
351: PetscCall(PetscSectionSetUp(partSection));
352: if (part->viewerGraph) {
353: PetscBool isascii;
355: PetscCall(PetscObjectTypeCompare((PetscObject)part->viewerGraph, PETSCVIEWERASCII, &isascii));
356: if (isascii) PetscCall(PetscIntCSRView(numVertices, start, adjacency, part->viewerGraph));
357: }
358: if (part->viewer) {
359: PetscCall(PetscViewerPushFormat(part->viewer, part->viewerFmt));
360: PetscCall(PetscPartitionerView(part, part->viewer));
361: PetscCall(PetscViewerPopFormat(part->viewer));
362: }
363: PetscFunctionReturn(PETSC_SUCCESS);
364: }
366: /*@
367: PetscPartitionerCreate - Creates an empty `PetscPartitioner` object. The type can then be set with `PetscPartitionerSetType()`.
369: Collective
371: Input Parameter:
372: . comm - The communicator for the `PetscPartitioner` object
374: Output Parameter:
375: . part - The `PetscPartitioner` object
377: Level: beginner
379: .seealso: `PetscPartitionerSetType()`, `PetscPartitionerDestroy()`
380: @*/
381: PetscErrorCode PetscPartitionerCreate(MPI_Comm comm, PetscPartitioner *part)
382: {
383: PetscPartitioner p;
384: const char *partitionerType = NULL;
386: PetscFunctionBegin;
387: PetscAssertPointer(part, 2);
388: *part = NULL;
389: PetscCall(PetscPartitionerInitializePackage());
391: PetscCall(PetscHeaderCreate(p, PETSCPARTITIONER_CLASSID, "PetscPartitioner", "Graph Partitioner", "PetscPartitioner", comm, PetscPartitionerDestroy, PetscPartitionerView));
392: PetscCall(PetscPartitionerGetDefaultType(comm, &partitionerType));
393: PetscCall(PetscPartitionerSetType(p, partitionerType));
395: p->usevwgt = PETSC_TRUE;
396: p->printHeader = PETSC_TRUE;
398: *part = p;
399: PetscFunctionReturn(PETSC_SUCCESS);
400: }