Actual source code: partitioner.c
1: #include <petsc/private/partitionerimpl.h>
3: /*@C
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 `PetscPartitioner` type
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: /*@C
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: /*@C
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
82: - name - command line option
84: Level: intermediate
86: Note:
87: See `PetscObjectViewFromOptions()` for the various forms of viewers that may be used
89: .seealso: `PetscPartitionerView()`, `PetscObjectViewFromOptions()`
90: @*/
91: PetscErrorCode PetscPartitionerViewFromOptions(PetscPartitioner A, PetscObject obj, const char name[])
92: {
93: PetscFunctionBegin;
95: PetscCall(PetscObjectViewFromOptions((PetscObject)A, obj, name));
96: PetscFunctionReturn(PETSC_SUCCESS);
97: }
99: /*@
100: PetscPartitionerView - Views a `PetscPartitioner`
102: Collective
104: Input Parameters:
105: + part - the `PetscPartitioner` object to view
106: - v - the viewer
108: Level: developer
110: .seealso: `PetscPartitionerDestroy()`
111: @*/
112: PetscErrorCode PetscPartitionerView(PetscPartitioner part, PetscViewer v)
113: {
114: PetscMPIInt size;
115: PetscBool isascii;
117: PetscFunctionBegin;
119: if (!v) PetscCall(PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)part), &v));
120: PetscCall(PetscObjectTypeCompare((PetscObject)v, PETSCVIEWERASCII, &isascii));
121: if (isascii) {
122: PetscCallMPI(MPI_Comm_size(PetscObjectComm((PetscObject)part), &size));
123: PetscCall(PetscViewerASCIIPrintf(v, "Graph Partitioner: %d MPI Process%s\n", size, size > 1 ? "es" : ""));
124: PetscCall(PetscViewerASCIIPrintf(v, " type: %s\n", ((PetscObject)part)->type_name));
125: PetscCall(PetscViewerASCIIPrintf(v, " edge cut: %" PetscInt_FMT "\n", part->edgeCut));
126: PetscCall(PetscViewerASCIIPrintf(v, " balance: %.2g\n", (double)part->balance));
127: PetscCall(PetscViewerASCIIPrintf(v, " use vertex weights: %d\n", part->usevwgt));
128: }
129: PetscTryTypeMethod(part, view, v);
130: PetscFunctionReturn(PETSC_SUCCESS);
131: }
133: static PetscErrorCode PetscPartitionerGetDefaultType(MPI_Comm comm, const char **defaultType)
134: {
135: PetscMPIInt size;
137: PetscFunctionBegin;
138: PetscCallMPI(MPI_Comm_size(comm, &size));
139: if (size == 1) {
140: *defaultType = PETSCPARTITIONERSIMPLE;
141: } else {
142: #if defined(PETSC_HAVE_PARMETIS)
143: *defaultType = PETSCPARTITIONERPARMETIS;
144: #elif defined(PETSC_HAVE_PTSCOTCH)
145: *defaultType = PETSCPARTITIONERPTSCOTCH;
146: #elif defined(PETSC_HAVE_CHACO)
147: *defaultType = PETSCPARTITIONERCHACO;
148: #else
149: *defaultType = PETSCPARTITIONERSIMPLE;
150: #endif
151: }
152: PetscFunctionReturn(PETSC_SUCCESS);
153: }
155: /*@
156: PetscPartitionerSetFromOptions - sets parameters in a `PetscPartitioner` from the options database
158: Collective
160: Input Parameter:
161: . part - the `PetscPartitioner` object to set options for
163: Options Database Keys:
164: + -petscpartitioner_type <type> - Sets the `PetscPartitioner` type; use -help for a list of available types
165: . -petscpartitioner_use_vertex_weights - Uses weights associated with the graph vertices
166: - -petscpartitioner_view_graph - View the graph each time PetscPartitionerPartition is called. Viewer can be customized, see `PetscOptionsGetViewer()`
168: Level: developer
170: .seealso: `PetscPartitionerView()`, `PetscPartitionerSetType()`, `PetscPartitionerPartition()`
171: @*/
172: PetscErrorCode PetscPartitionerSetFromOptions(PetscPartitioner part)
173: {
174: const char *currentType = NULL;
175: char name[256];
176: PetscBool flg;
178: PetscFunctionBegin;
180: PetscObjectOptionsBegin((PetscObject)part);
181: PetscCall(PetscPartitionerGetType(part, ¤tType));
182: PetscCall(PetscOptionsFList("-petscpartitioner_type", "Graph partitioner", "PetscPartitionerSetType", PetscPartitionerList, currentType, name, sizeof(name), &flg));
183: if (flg) PetscCall(PetscPartitionerSetType(part, name));
184: PetscCall(PetscOptionsBool("-petscpartitioner_use_vertex_weights", "Use vertex weights", "", part->usevwgt, &part->usevwgt, NULL));
185: PetscTryTypeMethod(part, setfromoptions, PetscOptionsObject);
186: PetscCall(PetscViewerDestroy(&part->viewer));
187: PetscCall(PetscViewerDestroy(&part->viewerGraph));
188: PetscCall(PetscOptionsGetViewer(((PetscObject)part)->comm, ((PetscObject)part)->options, ((PetscObject)part)->prefix, "-petscpartitioner_view", &part->viewer, NULL, NULL));
189: PetscCall(PetscOptionsGetViewer(((PetscObject)part)->comm, ((PetscObject)part)->options, ((PetscObject)part)->prefix, "-petscpartitioner_view_graph", &part->viewerGraph, NULL, &part->viewGraph));
190: /* process any options handlers added with PetscObjectAddOptionsHandler() */
191: PetscCall(PetscObjectProcessOptionsHandlers((PetscObject)part, PetscOptionsObject));
192: PetscOptionsEnd();
193: PetscFunctionReturn(PETSC_SUCCESS);
194: }
196: /*@
197: PetscPartitionerSetUp - Construct data structures for the `PetscPartitioner`
199: Collective
201: Input Parameter:
202: . part - the `PetscPartitioner` object to setup
204: Level: developer
206: .seealso: `PetscPartitionerView()`, `PetscPartitionerDestroy()`
207: @*/
208: PetscErrorCode PetscPartitionerSetUp(PetscPartitioner part)
209: {
210: PetscFunctionBegin;
212: PetscTryTypeMethod(part, setup);
213: PetscFunctionReturn(PETSC_SUCCESS);
214: }
216: /*@
217: PetscPartitionerReset - Resets data structures for the `PetscPartitioner`
219: Collective
221: Input Parameter:
222: . part - the `PetscPartitioner` object to reset
224: Level: developer
226: .seealso: `PetscPartitionerSetUp()`, `PetscPartitionerDestroy()`
227: @*/
228: PetscErrorCode PetscPartitionerReset(PetscPartitioner part)
229: {
230: PetscFunctionBegin;
232: PetscTryTypeMethod(part, reset);
233: PetscFunctionReturn(PETSC_SUCCESS);
234: }
236: /*@
237: PetscPartitionerDestroy - Destroys a `PetscPartitioner` object
239: Collective
241: Input Parameter:
242: . part - the `PetscPartitioner` object to destroy
244: Level: developer
246: .seealso: `PetscPartitionerView()`
247: @*/
248: PetscErrorCode PetscPartitionerDestroy(PetscPartitioner *part)
249: {
250: PetscFunctionBegin;
251: if (!*part) PetscFunctionReturn(PETSC_SUCCESS);
254: if (--((PetscObject)(*part))->refct > 0) {
255: *part = NULL;
256: PetscFunctionReturn(PETSC_SUCCESS);
257: }
258: ((PetscObject)(*part))->refct = 0;
260: PetscCall(PetscPartitionerReset(*part));
262: PetscCall(PetscViewerDestroy(&(*part)->viewer));
263: PetscCall(PetscViewerDestroy(&(*part)->viewerGraph));
264: PetscTryTypeMethod((*part), destroy);
265: PetscCall(PetscHeaderDestroy(part));
266: PetscFunctionReturn(PETSC_SUCCESS);
267: }
269: /*@
270: PetscPartitionerPartition - Partition a graph
272: Collective
274: Input Parameters:
275: + part - The `PetscPartitioner`
276: . nparts - Number of partitions
277: . numVertices - Number of vertices in the local part of the graph
278: . start - row pointers for the local part of the graph (CSR style)
279: . adjacency - adjacency list (CSR style)
280: . vertexSection - PetscSection describing the absolute weight of each local vertex (can be NULL)
281: - targetSection - PetscSection describing the absolute weight of each partition (can be NULL)
283: Output Parameters:
284: + partSection - The `PetscSection` giving the division of points by partition
285: - partition - The list of points by partition
287: Options Databasen Keys:
288: + -petscpartitioner_view - View the partitioner information
289: - -petscpartitioner_view_graph - View the graph we are partitioning
291: Level: developer
293: Notes:
294: 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.
295: 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.
297: .seealso: `PetscPartitionerCreate()`, `PetscPartitionerSetType()`, `PetscSectionCreate()`, `PetscSectionSetChart()`, `PetscSectionSetDof()`
298: @*/
299: PetscErrorCode PetscPartitionerPartition(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertexSection, PetscSection targetSection, PetscSection partSection, IS *partition)
300: {
301: PetscFunctionBegin;
304: PetscCheck(nparts > 0, PetscObjectComm((PetscObject)part), PETSC_ERR_ARG_OUTOFRANGE, "Number of parts must be positive");
305: PetscCheck(numVertices >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Number of vertices must be non-negative");
306: if (numVertices && !part->noGraph) {
307: PetscAssertPointer(start, 4);
308: PetscAssertPointer(start + numVertices, 4);
309: if (start[numVertices]) PetscAssertPointer(adjacency, 5);
310: }
311: if (vertexSection) {
312: PetscInt s, e;
315: PetscCall(PetscSectionGetChart(vertexSection, &s, &e));
316: PetscCheck(s <= 0 && e >= numVertices, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Invalid vertexSection chart [%" PetscInt_FMT ",%" PetscInt_FMT ")", s, e);
317: }
318: if (targetSection) {
319: PetscInt s, e;
322: PetscCall(PetscSectionGetChart(targetSection, &s, &e));
323: PetscCheck(s <= 0 && e >= nparts, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Invalid targetSection chart [%" PetscInt_FMT ",%" PetscInt_FMT ")", s, e);
324: }
326: PetscAssertPointer(partition, 9);
328: PetscCall(PetscSectionReset(partSection));
329: PetscCall(PetscSectionSetChart(partSection, 0, nparts));
330: if (nparts == 1) { /* quick */
331: PetscCall(PetscSectionSetDof(partSection, 0, numVertices));
332: PetscCall(ISCreateStride(PetscObjectComm((PetscObject)part), numVertices, 0, 1, partition));
333: } else PetscUseTypeMethod(part, partition, nparts, numVertices, start, adjacency, vertexSection, targetSection, partSection, partition);
334: PetscCall(PetscSectionSetUp(partSection));
335: if (part->viewerGraph) {
336: PetscViewer viewer = part->viewerGraph;
337: PetscBool isascii;
338: PetscInt v, i;
339: PetscMPIInt rank;
341: PetscCallMPI(MPI_Comm_rank(PetscObjectComm((PetscObject)viewer), &rank));
342: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
343: if (isascii) {
344: PetscCall(PetscViewerASCIIPushSynchronized(viewer));
345: PetscCall(PetscViewerASCIISynchronizedPrintf(viewer, "[%d]Nv: %" PetscInt_FMT "\n", rank, numVertices));
346: for (v = 0; v < numVertices; ++v) {
347: const PetscInt s = start[v];
348: const PetscInt e = start[v + 1];
350: PetscCall(PetscViewerASCIISynchronizedPrintf(viewer, "[%d] ", rank));
351: for (i = s; i < e; ++i) PetscCall(PetscViewerASCIISynchronizedPrintf(viewer, "%" PetscInt_FMT " ", adjacency[i]));
352: PetscCall(PetscViewerASCIISynchronizedPrintf(viewer, "[%" PetscInt_FMT "-%" PetscInt_FMT ")\n", s, e));
353: }
354: PetscCall(PetscViewerFlush(viewer));
355: PetscCall(PetscViewerASCIIPopSynchronized(viewer));
356: }
357: }
358: if (part->viewer) PetscCall(PetscPartitionerView(part, part->viewer));
359: PetscFunctionReturn(PETSC_SUCCESS);
360: }
362: /*@
363: PetscPartitionerCreate - Creates an empty `PetscPartitioner` object. The type can then be set with `PetscPartitionerSetType()`.
365: Collective
367: Input Parameter:
368: . comm - The communicator for the `PetscPartitioner` object
370: Output Parameter:
371: . part - The `PetscPartitioner` object
373: Level: beginner
375: .seealso: `PetscPartitionerSetType()`, `PetscPartitionerDestroy()`
376: @*/
377: PetscErrorCode PetscPartitionerCreate(MPI_Comm comm, PetscPartitioner *part)
378: {
379: PetscPartitioner p;
380: const char *partitionerType = NULL;
382: PetscFunctionBegin;
383: PetscAssertPointer(part, 2);
384: *part = NULL;
385: PetscCall(PetscPartitionerInitializePackage());
387: PetscCall(PetscHeaderCreate(p, PETSCPARTITIONER_CLASSID, "PetscPartitioner", "Graph Partitioner", "PetscPartitioner", comm, PetscPartitionerDestroy, PetscPartitionerView));
388: PetscCall(PetscPartitionerGetDefaultType(comm, &partitionerType));
389: PetscCall(PetscPartitionerSetType(p, partitionerType));
391: p->edgeCut = 0;
392: p->balance = 0.0;
393: p->usevwgt = PETSC_TRUE;
395: *part = p;
396: PetscFunctionReturn(PETSC_SUCCESS);
397: }