Actual source code: hierarchical.c
1: #include <../src/mat/impls/adj/mpi/mpiadj.h>
2: #include <petscsf.h>
3: #include <petsc/private/matimpl.h>
5: /*
6: It is a hierarchical partitioning. The partitioner has two goals:
7: (1) Most of current partitioners fail at a large scale. The hierarchical partitioning
8: strategy is trying to produce large number of subdomains when number of processor cores is large.
9: (2) PCGASM needs one 'big' subdomain across multi-cores. The partitioner provides two
10: consistent partitions, coarse parts and fine parts. A coarse part is a 'big' subdomain consisting
11: of several small subdomains.
12: */
14: static PetscErrorCode MatPartitioningHierarchical_DetermineDestination(MatPartitioning, IS, PetscInt, PetscInt, IS *);
15: static PetscErrorCode MatPartitioningHierarchical_AssembleSubdomain(Mat, IS, IS, IS *, Mat *, ISLocalToGlobalMapping *);
16: static PetscErrorCode MatPartitioningHierarchical_ReassembleFineparts(Mat, IS, ISLocalToGlobalMapping, IS *);
18: typedef struct {
19: char *fineparttype; /* partitioner on fine level */
20: char *coarseparttype; /* partitioner on coarse level */
21: PetscInt nfineparts; /* number of fine parts on each coarse subdomain */
22: PetscInt ncoarseparts; /* number of coarse parts */
23: IS coarseparts; /* partitioning on coarse level */
24: IS fineparts; /* partitioning on fine level */
25: MatPartitioning coarseMatPart; /* MatPartititioning on coarse level (first level) */
26: MatPartitioning fineMatPart; /* MatPartitioning on fine level (second level) */
27: MatPartitioning improver; /* Improve the quality of a partition */
28: } MatPartitioning_Hierarchical;
30: /*
31: Uses a hierarchical partitioning strategy to partition the matrix in parallel.
32: Use this interface to make the partitioner consistent with others
33: */
34: static PetscErrorCode MatPartitioningApply_Hierarchical(MatPartitioning part, IS *partitioning)
35: {
36: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
37: const PetscInt *fineparts_indices, *coarseparts_indices;
38: PetscInt *fineparts_indices_tmp;
39: PetscInt *parts_indices, i, j, mat_localsize, *offsets;
40: Mat mat = part->adj, adj, sadj;
41: PetscReal *part_weights;
42: PetscBool flg;
43: PetscInt bs = 1;
44: PetscInt *coarse_vertex_weights = NULL;
45: PetscMPIInt size, rank;
46: MPI_Comm comm, scomm;
47: IS destination, fineparts_temp, vweights, svweights;
48: PetscInt nsvwegihts, *fp_vweights;
49: const PetscInt *svweights_indices;
50: ISLocalToGlobalMapping mapping;
51: const char *prefix;
52: PetscBool use_edge_weights;
54: PetscFunctionBegin;
55: PetscCall(PetscObjectGetComm((PetscObject)part, &comm));
56: PetscCallMPI(MPI_Comm_size(comm, &size));
57: PetscCallMPI(MPI_Comm_rank(comm, &rank));
58: PetscCall(PetscObjectTypeCompare((PetscObject)mat, MATMPIADJ, &flg));
59: if (flg) {
60: adj = mat;
61: PetscCall(PetscObjectReference((PetscObject)adj));
62: } else {
63: /* bs indicates if the converted matrix is "reduced" from the original and hence the
64: resulting partition results need to be stretched to match the original matrix */
65: PetscCall(MatConvert(mat, MATMPIADJ, MAT_INITIAL_MATRIX, &adj));
66: if (adj->rmap->n > 0) bs = mat->rmap->n / adj->rmap->n;
67: }
68: /* local size of mat */
69: mat_localsize = adj->rmap->n;
70: /* check parameters */
71: /* how many small subdomains we want from a given 'big' suddomain */
72: PetscCheck(hpart->nfineparts, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, " must set number of small subdomains for each big subdomain ");
73: PetscCheck(hpart->ncoarseparts || part->n, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONGSTATE, " did not either set number of coarse parts or total number of parts ");
75: /* Partitioning the domain into one single subdomain is a trivial case, and we should just return */
76: if (part->n == 1) {
77: PetscCall(PetscCalloc1(bs * adj->rmap->n, &parts_indices));
78: PetscCall(ISCreateGeneral(comm, bs * adj->rmap->n, parts_indices, PETSC_OWN_POINTER, partitioning));
79: hpart->ncoarseparts = 1;
80: hpart->nfineparts = 1;
81: PetscCall(PetscStrallocpy("NONE", &hpart->coarseparttype));
82: PetscCall(PetscStrallocpy("NONE", &hpart->fineparttype));
83: PetscCall(MatDestroy(&adj));
84: PetscFunctionReturn(PETSC_SUCCESS);
85: }
87: if (part->n) {
88: hpart->ncoarseparts = part->n / hpart->nfineparts;
90: if (part->n % hpart->nfineparts != 0) hpart->ncoarseparts++;
91: } else {
92: part->n = hpart->ncoarseparts * hpart->nfineparts;
93: }
95: PetscCall(PetscMalloc1(hpart->ncoarseparts + 1, &offsets));
96: PetscCall(PetscMalloc1(hpart->ncoarseparts, &part_weights));
98: offsets[0] = 0;
99: if (part->n % hpart->nfineparts != 0) offsets[1] = part->n % hpart->nfineparts;
100: else offsets[1] = hpart->nfineparts;
102: part_weights[0] = ((PetscReal)offsets[1]) / part->n;
104: for (i = 2; i <= hpart->ncoarseparts; i++) {
105: offsets[i] = hpart->nfineparts;
106: part_weights[i - 1] = ((PetscReal)offsets[i]) / part->n;
107: }
109: offsets[0] = 0;
110: for (i = 1; i <= hpart->ncoarseparts; i++) offsets[i] += offsets[i - 1];
112: /* If these exists a mat partitioner, we should delete it */
113: PetscCall(MatPartitioningDestroy(&hpart->coarseMatPart));
114: PetscCall(MatPartitioningCreate(comm, &hpart->coarseMatPart));
115: PetscCall(PetscObjectGetOptionsPrefix((PetscObject)part, &prefix));
116: PetscCall(PetscObjectSetOptionsPrefix((PetscObject)hpart->coarseMatPart, prefix));
117: PetscCall(PetscObjectAppendOptionsPrefix((PetscObject)hpart->coarseMatPart, "hierarch_coarse_"));
118: /* if did not set partitioning type yet, use parmetis by default */
119: if (!hpart->coarseparttype) {
120: #if defined(PETSC_HAVE_PARMETIS)
121: PetscCall(MatPartitioningSetType(hpart->coarseMatPart, MATPARTITIONINGPARMETIS));
122: PetscCall(PetscStrallocpy(MATPARTITIONINGPARMETIS, &hpart->coarseparttype));
123: #elif defined(PETSC_HAVE_PTSCOTCH)
124: PetscCall(MatPartitioningSetType(hpart->coarseMatPart, MATPARTITIONINGPTSCOTCH));
125: PetscCall(PetscStrallocpy(MATPARTITIONINGPTSCOTCH, &hpart->coarseparttype));
126: #else
127: SETERRQ(PetscObjectComm((PetscObject)mat), PETSC_ERR_SUP, "Requires PETSc be installed with ParMetis or run with -mat_partitioning_hierarchical_coarseparttype partitiontype");
128: #endif
129: } else {
130: PetscCall(MatPartitioningSetType(hpart->coarseMatPart, hpart->coarseparttype));
131: }
132: PetscCall(MatPartitioningSetAdjacency(hpart->coarseMatPart, adj));
133: PetscCall(MatPartitioningSetNParts(hpart->coarseMatPart, hpart->ncoarseparts));
134: /* copy over vertex weights */
135: if (part->vertex_weights) {
136: PetscCall(PetscMalloc1(mat_localsize, &coarse_vertex_weights));
137: PetscCall(PetscArraycpy(coarse_vertex_weights, part->vertex_weights, mat_localsize));
138: PetscCall(MatPartitioningSetVertexWeights(hpart->coarseMatPart, coarse_vertex_weights));
139: }
140: /* Copy use_edge_weights flag from part to coarse part */
141: PetscCall(MatPartitioningGetUseEdgeWeights(part, &use_edge_weights));
142: PetscCall(MatPartitioningSetUseEdgeWeights(hpart->coarseMatPart, use_edge_weights));
144: PetscCall(MatPartitioningSetPartitionWeights(hpart->coarseMatPart, part_weights));
145: PetscCall(MatPartitioningApply(hpart->coarseMatPart, &hpart->coarseparts));
147: /* Wrap the original vertex weights into an index set so that we can extract the corresponding
148: * vertex weights for each big subdomain using ISCreateSubIS().
149: * */
150: if (part->vertex_weights) PetscCall(ISCreateGeneral(comm, mat_localsize, part->vertex_weights, PETSC_COPY_VALUES, &vweights));
152: PetscCall(PetscCalloc1(mat_localsize, &fineparts_indices_tmp));
153: for (i = 0; i < hpart->ncoarseparts; i += size) {
154: /* Determine where we want to send big subdomains */
155: PetscCall(MatPartitioningHierarchical_DetermineDestination(part, hpart->coarseparts, i, i + size, &destination));
156: /* Assemble a submatrix and its vertex weights for partitioning subdomains */
157: PetscCall(MatPartitioningHierarchical_AssembleSubdomain(adj, part->vertex_weights ? vweights : NULL, destination, part->vertex_weights ? &svweights : NULL, &sadj, &mapping));
158: /* We have to create a new array to hold vertex weights since coarse partitioner needs to own the vertex-weights array */
159: if (part->vertex_weights) {
160: PetscCall(ISGetLocalSize(svweights, &nsvwegihts));
161: PetscCall(PetscMalloc1(nsvwegihts, &fp_vweights));
162: PetscCall(ISGetIndices(svweights, &svweights_indices));
163: PetscCall(PetscArraycpy(fp_vweights, svweights_indices, nsvwegihts));
164: PetscCall(ISRestoreIndices(svweights, &svweights_indices));
165: PetscCall(ISDestroy(&svweights));
166: }
168: PetscCall(ISDestroy(&destination));
169: PetscCall(PetscObjectGetComm((PetscObject)sadj, &scomm));
171: /*
172: * If the number of big subdomains is smaller than the number of processor cores, the higher ranks do not
173: * need to do partitioning
174: * */
175: if ((i + rank) < hpart->ncoarseparts) {
176: PetscCall(MatPartitioningDestroy(&hpart->fineMatPart));
177: /* create a fine partitioner */
178: PetscCall(MatPartitioningCreate(scomm, &hpart->fineMatPart));
179: PetscCall(PetscObjectSetOptionsPrefix((PetscObject)hpart->fineMatPart, prefix));
180: PetscCall(PetscObjectAppendOptionsPrefix((PetscObject)hpart->fineMatPart, "hierarch_fine_"));
181: /* if do not set partitioning type, use parmetis by default */
182: if (!hpart->fineparttype) {
183: #if defined(PETSC_HAVE_PARMETIS)
184: PetscCall(MatPartitioningSetType(hpart->fineMatPart, MATPARTITIONINGPARMETIS));
185: PetscCall(PetscStrallocpy(MATPARTITIONINGPARMETIS, &hpart->fineparttype));
186: #elif defined(PETSC_HAVE_PTSCOTCH)
187: PetscCall(MatPartitioningSetType(hpart->fineMatPart, MATPARTITIONINGPTSCOTCH));
188: PetscCall(PetscStrallocpy(MATPARTITIONINGPTSCOTCH, &hpart->fineparttype));
189: #elif defined(PETSC_HAVE_CHACO)
190: PetscCall(MatPartitioningSetType(hpart->fineMatPart, MATPARTITIONINGCHACO));
191: PetscCall(PetscStrallocpy(MATPARTITIONINGCHACO, &hpart->fineparttype));
192: #elif defined(PETSC_HAVE_PARTY)
193: PetscCall(MatPartitioningSetType(hpart->fineMatPart, MATPARTITIONINGPARTY));
194: PetscCall(PetscStrallocpy(PETSC_HAVE_PARTY, &hpart->fineparttype));
195: #else
196: SETERRQ(PetscObjectComm((PetscObject)mat), PETSC_ERR_SUP, "Requires PETSc be installed with ParMetis or run with -mat_partitioning_hierarchical_coarseparttype partitiontype");
197: #endif
198: } else {
199: PetscCall(MatPartitioningSetType(hpart->fineMatPart, hpart->fineparttype));
200: }
201: PetscCall(MatPartitioningSetUseEdgeWeights(hpart->fineMatPart, use_edge_weights));
202: PetscCall(MatPartitioningSetAdjacency(hpart->fineMatPart, sadj));
203: PetscCall(MatPartitioningSetNParts(hpart->fineMatPart, offsets[rank + 1 + i] - offsets[rank + i]));
204: if (part->vertex_weights) PetscCall(MatPartitioningSetVertexWeights(hpart->fineMatPart, fp_vweights));
205: PetscCall(MatPartitioningApply(hpart->fineMatPart, &fineparts_temp));
206: } else {
207: PetscCall(ISCreateGeneral(scomm, 0, NULL, PETSC_OWN_POINTER, &fineparts_temp));
208: }
210: PetscCall(MatDestroy(&sadj));
212: /* Send partition back to the original owners */
213: PetscCall(MatPartitioningHierarchical_ReassembleFineparts(adj, fineparts_temp, mapping, &hpart->fineparts));
214: PetscCall(ISGetIndices(hpart->fineparts, &fineparts_indices));
215: for (j = 0; j < mat_localsize; j++)
216: if (fineparts_indices[j] >= 0) fineparts_indices_tmp[j] = fineparts_indices[j];
218: PetscCall(ISRestoreIndices(hpart->fineparts, &fineparts_indices));
219: PetscCall(ISDestroy(&hpart->fineparts));
220: PetscCall(ISDestroy(&fineparts_temp));
221: PetscCall(ISLocalToGlobalMappingDestroy(&mapping));
222: }
224: if (part->vertex_weights) PetscCall(ISDestroy(&vweights));
226: PetscCall(ISCreateGeneral(comm, mat_localsize, fineparts_indices_tmp, PETSC_OWN_POINTER, &hpart->fineparts));
227: PetscCall(ISGetIndices(hpart->fineparts, &fineparts_indices));
228: PetscCall(ISGetIndices(hpart->coarseparts, &coarseparts_indices));
229: PetscCall(PetscMalloc1(bs * adj->rmap->n, &parts_indices));
230: /* Modify the local indices to the global indices by combing the coarse partition and the fine partitions */
231: for (i = 0; i < adj->rmap->n; i++) {
232: for (j = 0; j < bs; j++) parts_indices[bs * i + j] = fineparts_indices[i] + offsets[coarseparts_indices[i]];
233: }
234: PetscCall(ISRestoreIndices(hpart->fineparts, &fineparts_indices));
235: PetscCall(ISRestoreIndices(hpart->coarseparts, &coarseparts_indices));
236: PetscCall(PetscFree(offsets));
237: PetscCall(ISCreateGeneral(comm, bs * adj->rmap->n, parts_indices, PETSC_OWN_POINTER, partitioning));
238: PetscCall(MatDestroy(&adj));
239: PetscFunctionReturn(PETSC_SUCCESS);
240: }
242: static PetscErrorCode MatPartitioningHierarchical_ReassembleFineparts(Mat adj, IS fineparts, ISLocalToGlobalMapping mapping, IS *sfineparts)
243: {
244: PetscInt *local_indices, *global_indices, *sfineparts_indices, localsize, i;
245: const PetscInt *ranges, *fineparts_indices;
246: PetscMPIInt rank, *owners;
247: MPI_Comm comm;
248: PetscLayout rmap;
249: PetscSFNode *remote;
250: PetscSF sf;
252: PetscFunctionBegin;
253: PetscAssertPointer(sfineparts, 4);
254: PetscCall(PetscObjectGetComm((PetscObject)adj, &comm));
255: PetscCallMPI(MPI_Comm_rank(comm, &rank));
256: PetscCall(MatGetLayouts(adj, &rmap, NULL));
257: PetscCall(ISGetLocalSize(fineparts, &localsize));
258: PetscCall(PetscMalloc2(localsize, &global_indices, localsize, &local_indices));
259: for (i = 0; i < localsize; i++) local_indices[i] = i;
260: /* map local indices back to global so that we can permulate data globally */
261: PetscCall(ISLocalToGlobalMappingApply(mapping, localsize, local_indices, global_indices));
262: PetscCall(PetscCalloc1(localsize, &owners));
263: /* find owners for global indices */
264: for (i = 0; i < localsize; i++) PetscCall(PetscLayoutFindOwner(rmap, global_indices[i], &owners[i]));
265: PetscCall(PetscLayoutGetRanges(rmap, &ranges));
266: PetscCall(PetscMalloc1(ranges[rank + 1] - ranges[rank], &sfineparts_indices));
268: for (i = 0; i < ranges[rank + 1] - ranges[rank]; i++) sfineparts_indices[i] = -1;
270: PetscCall(ISGetIndices(fineparts, &fineparts_indices));
271: PetscCall(PetscSFCreate(comm, &sf));
272: PetscCall(PetscMalloc1(localsize, &remote));
273: for (i = 0; i < localsize; i++) {
274: remote[i].rank = owners[i];
275: remote[i].index = global_indices[i] - ranges[owners[i]];
276: }
277: PetscCall(PetscSFSetType(sf, PETSCSFBASIC));
278: /* not sure how to add prefix to sf */
279: PetscCall(PetscSFSetFromOptions(sf));
280: PetscCall(PetscSFSetGraph(sf, localsize, localsize, NULL, PETSC_OWN_POINTER, remote, PETSC_OWN_POINTER));
281: PetscCall(PetscSFReduceBegin(sf, MPIU_INT, fineparts_indices, sfineparts_indices, MPI_REPLACE));
282: PetscCall(PetscSFReduceEnd(sf, MPIU_INT, fineparts_indices, sfineparts_indices, MPI_REPLACE));
283: PetscCall(PetscSFDestroy(&sf));
284: PetscCall(ISRestoreIndices(fineparts, &fineparts_indices));
285: PetscCall(ISCreateGeneral(comm, ranges[rank + 1] - ranges[rank], sfineparts_indices, PETSC_OWN_POINTER, sfineparts));
286: PetscCall(PetscFree2(global_indices, local_indices));
287: PetscCall(PetscFree(owners));
288: PetscFunctionReturn(PETSC_SUCCESS);
289: }
291: static PetscErrorCode MatPartitioningHierarchical_AssembleSubdomain(Mat adj, IS vweights, IS destination, IS *svweights, Mat *sadj, ISLocalToGlobalMapping *mapping)
292: {
293: IS irows, icols;
294: PetscInt irows_ln;
295: PetscMPIInt rank;
296: const PetscInt *irows_indices;
297: MPI_Comm comm;
299: PetscFunctionBegin;
300: PetscCall(PetscObjectGetComm((PetscObject)adj, &comm));
301: PetscCallMPI(MPI_Comm_rank(comm, &rank));
302: /* figure out where data comes from */
303: PetscCall(ISBuildTwoSided(destination, NULL, &irows));
304: PetscCall(ISDuplicate(irows, &icols));
305: PetscCall(ISGetLocalSize(irows, &irows_ln));
306: PetscCall(ISGetIndices(irows, &irows_indices));
307: PetscCall(ISLocalToGlobalMappingCreate(comm, 1, irows_ln, irows_indices, PETSC_COPY_VALUES, mapping));
308: PetscCall(ISRestoreIndices(irows, &irows_indices));
309: PetscCall(MatCreateSubMatrices(adj, 1, &irows, &icols, MAT_INITIAL_MATRIX, &sadj));
310: if (vweights && svweights) PetscCall(ISCreateSubIS(vweights, irows, svweights));
311: PetscCall(ISDestroy(&irows));
312: PetscCall(ISDestroy(&icols));
313: PetscFunctionReturn(PETSC_SUCCESS);
314: }
316: static PetscErrorCode MatPartitioningHierarchical_DetermineDestination(MatPartitioning part, IS partitioning, PetscInt pstart, PetscInt pend, IS *destination)
317: {
318: MPI_Comm comm;
319: PetscMPIInt rank, size;
320: PetscInt plocalsize, *dest_indices, target;
321: const PetscInt *part_indices;
323: PetscFunctionBegin;
324: PetscCall(PetscObjectGetComm((PetscObject)part, &comm));
325: PetscCallMPI(MPI_Comm_rank(comm, &rank));
326: PetscCallMPI(MPI_Comm_size(comm, &size));
327: PetscCheck((pend - pstart) <= size, PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, "range [%" PetscInt_FMT ", %" PetscInt_FMT "] should be smaller than or equal to size %d", pstart, pend, size);
328: PetscCheck(pstart <= pend, PETSC_COMM_SELF, PETSC_ERR_ARG_INCOMP, " pstart %" PetscInt_FMT " should be smaller than pend %" PetscInt_FMT, pstart, pend);
329: PetscCall(ISGetLocalSize(partitioning, &plocalsize));
330: PetscCall(PetscMalloc1(plocalsize, &dest_indices));
331: PetscCall(ISGetIndices(partitioning, &part_indices));
332: for (PetscInt i = 0; i < plocalsize; i++) {
333: /* compute target */
334: target = part_indices[i] - pstart;
335: /* mark out of range entity as -1 */
336: if (part_indices[i] < pstart || part_indices[i] >= pend) target = -1;
337: dest_indices[i] = target;
338: }
339: PetscCall(ISCreateGeneral(comm, plocalsize, dest_indices, PETSC_OWN_POINTER, destination));
340: PetscFunctionReturn(PETSC_SUCCESS);
341: }
343: static PetscErrorCode MatPartitioningView_Hierarchical(MatPartitioning part, PetscViewer viewer)
344: {
345: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
346: PetscMPIInt rank;
347: PetscBool isascii;
348: PetscViewer sviewer;
350: PetscFunctionBegin;
351: PetscCallMPI(MPI_Comm_rank(PetscObjectComm((PetscObject)part), &rank));
352: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
353: if (isascii) {
354: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of coarse parts: %" PetscInt_FMT "\n", hpart->ncoarseparts));
355: PetscCall(PetscViewerASCIIPrintf(viewer, " Coarse partitioner: %s\n", hpart->coarseparttype));
356: if (hpart->coarseMatPart) {
357: PetscCall(PetscViewerASCIIPushTab(viewer));
358: PetscCall(MatPartitioningView(hpart->coarseMatPart, viewer));
359: PetscCall(PetscViewerASCIIPopTab(viewer));
360: }
361: PetscCall(PetscViewerASCIIPrintf(viewer, " Number of fine parts: %" PetscInt_FMT "\n", hpart->nfineparts));
362: PetscCall(PetscViewerASCIIPrintf(viewer, " Fine partitioner: %s\n", hpart->fineparttype));
363: PetscCall(PetscViewerGetSubViewer(viewer, PETSC_COMM_SELF, &sviewer));
364: if (rank == 0 && hpart->fineMatPart) {
365: PetscCall(PetscViewerASCIIPushTab(viewer));
366: PetscCall(MatPartitioningView(hpart->fineMatPart, sviewer));
367: PetscCall(PetscViewerASCIIPopTab(viewer));
368: }
369: PetscCall(PetscViewerRestoreSubViewer(viewer, PETSC_COMM_SELF, &sviewer));
370: }
371: PetscFunctionReturn(PETSC_SUCCESS);
372: }
374: /*@
375: MatPartitioningHierarchicalGetFineparts - Get the fine-level partitioning of a hierarchical `MatPartitioning`.
377: Not Collective
379: Input Parameter:
380: . part - the `MatPartitioning` of type `MATPARTITIONINGHIERARCH`
382: Output Parameter:
383: . fineparts - the `IS` mapping each local row to its fine partition; the caller must destroy it with `ISDestroy()`
385: Level: advanced
387: .seealso: `MatPartitioning`, `MATPARTITIONINGHIERARCH`, `MatPartitioningHierarchicalGetCoarseparts()`, `MatPartitioningHierarchicalSetNfineparts()`
388: @*/
389: PetscErrorCode MatPartitioningHierarchicalGetFineparts(MatPartitioning part, IS *fineparts)
390: {
391: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
393: PetscFunctionBegin;
394: *fineparts = hpart->fineparts;
395: PetscCall(PetscObjectReference((PetscObject)hpart->fineparts));
396: PetscFunctionReturn(PETSC_SUCCESS);
397: }
399: /*@
400: MatPartitioningHierarchicalGetCoarseparts - Get the coarse-level partitioning of a hierarchical `MatPartitioning`.
402: Not Collective
404: Input Parameter:
405: . part - the `MatPartitioning` of type `MATPARTITIONINGHIERARCH`
407: Output Parameter:
408: . coarseparts - the `IS` mapping each local row to its coarse partition; the caller must destroy it with `ISDestroy()`
410: Level: advanced
412: .seealso: `MatPartitioning`, `MATPARTITIONINGHIERARCH`, `MatPartitioningHierarchicalGetFineparts()`, `MatPartitioningHierarchicalSetNcoarseparts()`
413: @*/
414: PetscErrorCode MatPartitioningHierarchicalGetCoarseparts(MatPartitioning part, IS *coarseparts)
415: {
416: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
418: PetscFunctionBegin;
419: *coarseparts = hpart->coarseparts;
420: PetscCall(PetscObjectReference((PetscObject)hpart->coarseparts));
421: PetscFunctionReturn(PETSC_SUCCESS);
422: }
424: /*@
425: MatPartitioningHierarchicalSetNcoarseparts - Set the number of coarse partitions produced by a hierarchical `MatPartitioning`.
427: Logically Collective
429: Input Parameters:
430: + part - the `MatPartitioning` of type `MATPARTITIONINGHIERARCH`
431: - ncoarseparts - the number of coarse partitions
433: Level: advanced
435: .seealso: `MatPartitioning`, `MATPARTITIONINGHIERARCH`, `MatPartitioningHierarchicalSetNfineparts()`, `MatPartitioningHierarchicalGetCoarseparts()`
436: @*/
437: PetscErrorCode MatPartitioningHierarchicalSetNcoarseparts(MatPartitioning part, PetscInt ncoarseparts)
438: {
439: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
441: PetscFunctionBegin;
442: hpart->ncoarseparts = ncoarseparts;
443: PetscFunctionReturn(PETSC_SUCCESS);
444: }
446: /*@
447: MatPartitioningHierarchicalSetNfineparts - Set the number of fine partitions per coarse partition produced by a hierarchical `MatPartitioning`.
449: Logically Collective
451: Input Parameters:
452: + part - the `MatPartitioning` of type `MATPARTITIONINGHIERARCH`
453: - nfineparts - the number of fine partitions per coarse partition
455: Level: advanced
457: .seealso: `MatPartitioning`, `MATPARTITIONINGHIERARCH`, `MatPartitioningHierarchicalSetNcoarseparts()`, `MatPartitioningHierarchicalGetFineparts()`
458: @*/
459: PetscErrorCode MatPartitioningHierarchicalSetNfineparts(MatPartitioning part, PetscInt nfineparts)
460: {
461: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
463: PetscFunctionBegin;
464: hpart->nfineparts = nfineparts;
465: PetscFunctionReturn(PETSC_SUCCESS);
466: }
468: static PetscErrorCode MatPartitioningSetFromOptions_Hierarchical(MatPartitioning part, PetscOptionItems PetscOptionsObject)
469: {
470: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
471: char value[1024];
472: PetscBool flag = PETSC_FALSE;
474: PetscFunctionBegin;
475: PetscOptionsHeadBegin(PetscOptionsObject, "Set hierarchical partitioning options");
476: PetscCall(PetscOptionsString("-mat_partitioning_hierarchical_coarseparttype", "coarse part type", NULL, NULL, value, sizeof(value), &flag));
477: if (flag) {
478: PetscCall(PetscFree(hpart->coarseparttype));
479: PetscCall(PetscStrallocpy(value, &hpart->coarseparttype));
480: }
481: PetscCall(PetscOptionsString("-mat_partitioning_hierarchical_fineparttype", "fine part type", NULL, NULL, value, sizeof(value), &flag));
482: if (flag) {
483: PetscCall(PetscFree(hpart->fineparttype));
484: PetscCall(PetscStrallocpy(value, &hpart->fineparttype));
485: }
486: PetscCall(PetscOptionsInt("-mat_partitioning_hierarchical_ncoarseparts", "number of coarse parts", NULL, hpart->ncoarseparts, &hpart->ncoarseparts, &flag));
487: PetscCall(PetscOptionsInt("-mat_partitioning_hierarchical_nfineparts", "number of fine parts", NULL, hpart->nfineparts, &hpart->nfineparts, &flag));
488: PetscOptionsHeadEnd();
489: PetscFunctionReturn(PETSC_SUCCESS);
490: }
492: static PetscErrorCode MatPartitioningDestroy_Hierarchical(MatPartitioning part)
493: {
494: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
496: PetscFunctionBegin;
497: PetscCall(PetscFree(hpart->coarseparttype));
498: PetscCall(PetscFree(hpart->fineparttype));
499: PetscCall(ISDestroy(&hpart->fineparts));
500: PetscCall(ISDestroy(&hpart->coarseparts));
501: PetscCall(MatPartitioningDestroy(&hpart->coarseMatPart));
502: PetscCall(MatPartitioningDestroy(&hpart->fineMatPart));
503: PetscCall(MatPartitioningDestroy(&hpart->improver));
504: PetscCall(PetscFree(hpart));
505: PetscFunctionReturn(PETSC_SUCCESS);
506: }
508: /*
509: Improves the quality of a partition
510: */
511: static PetscErrorCode MatPartitioningImprove_Hierarchical(MatPartitioning part, IS *partitioning)
512: {
513: MatPartitioning_Hierarchical *hpart = (MatPartitioning_Hierarchical *)part->data;
514: Mat mat = part->adj, adj;
515: PetscBool flg;
516: const char *prefix;
517: #if defined(PETSC_HAVE_PARMETIS)
518: PetscInt *vertex_weights;
519: #endif
521: PetscFunctionBegin;
522: PetscCall(PetscObjectTypeCompare((PetscObject)mat, MATMPIADJ, &flg));
523: if (flg) {
524: adj = mat;
525: PetscCall(PetscObjectReference((PetscObject)adj));
526: } else {
527: /* bs indicates if the converted matrix is "reduced" from the original and hence the
528: resulting partition results need to be stretched to match the original matrix */
529: PetscCall(MatConvert(mat, MATMPIADJ, MAT_INITIAL_MATRIX, &adj));
530: }
532: /* If there exists a mat partitioner, we should delete it */
533: PetscCall(MatPartitioningDestroy(&hpart->improver));
534: PetscCall(MatPartitioningCreate(PetscObjectComm((PetscObject)part), &hpart->improver));
535: PetscCall(PetscObjectGetOptionsPrefix((PetscObject)part, &prefix));
536: PetscCall(PetscObjectSetOptionsPrefix((PetscObject)hpart->improver, prefix));
537: PetscCall(PetscObjectAppendOptionsPrefix((PetscObject)hpart->improver, "hierarch_improver_"));
538: /* Only parmetis supports to refine a partition */
539: #if defined(PETSC_HAVE_PARMETIS)
540: PetscCall(MatPartitioningSetType(hpart->improver, MATPARTITIONINGPARMETIS));
541: PetscCall(MatPartitioningSetAdjacency(hpart->improver, adj));
542: PetscCall(MatPartitioningSetNParts(hpart->improver, part->n));
543: /* copy over vertex weights */
544: if (part->vertex_weights) {
545: PetscCall(PetscMalloc1(adj->rmap->n, &vertex_weights));
546: PetscCall(PetscArraycpy(vertex_weights, part->vertex_weights, adj->rmap->n));
547: PetscCall(MatPartitioningSetVertexWeights(hpart->improver, vertex_weights));
548: }
549: PetscCall(MatPartitioningImprove(hpart->improver, partitioning));
550: PetscCall(MatDestroy(&adj));
551: PetscFunctionReturn(PETSC_SUCCESS);
552: #else
553: SETERRQ(PetscObjectComm((PetscObject)adj), PETSC_ERR_SUP, "Requires PETSc be installed with ParMetis");
554: #endif
555: }
557: /*MC
558: MATPARTITIONINGHIERARCH - Creates a partitioning context via hierarchical partitioning strategy.
559: The graph is partitioned into a number of subgraphs, and each subgraph is further split into a few smaller
560: subgraphs. The idea can be applied in a recursive manner. It is useful when you want to partition the graph
561: into a large number of subgraphs (often more than 10K) since partitions obtained with existing partitioners
562: such as ParMETIS and PTScotch are far from ideal. The hierarchical partitioning also tries to avoid off-node
563: communication as much as possible for multi-core processor. Another user case for the hierarchical partitioning
564: is to improve `PCGASM` convergence by generating multi-process connected subdomain.
566: Collective
568: Input Parameter:
569: . part - the partitioning context
571: Options Database Keys:
572: + -mat_partitioning_hierarchical_coarseparttype - partitioner type at the first level and parmetis is used by default
573: . -mat_partitioning_hierarchical_fineparttype - partitioner type at the second level and parmetis is used by default
574: . -mat_partitioning_hierarchical_ncoarseparts - number of subgraphs is required at the first level, which is often the number of compute nodes
575: - -mat_partitioning_hierarchical_nfineparts - number of smaller subgraphs for each subgraph, which is often the number of cores per compute node
577: Level: beginner
579: Note:
580: See {cite}`kong2016highly` and {cite}`kongstognergastonpetersonpermannslaughtermartineau2018`.
582: .seealso: `MatPartitioningSetType()`, `MatPartitioningType`, `MATPARTITIONINGMETIS`, `MATPARTITIONINGPARMETIS`
583: M*/
585: PETSC_EXTERN PetscErrorCode MatPartitioningCreate_Hierarchical(MatPartitioning part)
586: {
587: MatPartitioning_Hierarchical *hpart;
589: PetscFunctionBegin;
590: PetscCall(PetscNew(&hpart));
591: part->data = (void *)hpart;
593: hpart->fineparttype = NULL; /* fine level (second) partitioner */
594: hpart->coarseparttype = NULL; /* coarse level (first) partitioner */
595: hpart->nfineparts = 1; /* we do not further partition coarse partition any more by default */
596: hpart->ncoarseparts = 0; /* number of coarse parts (first level) */
597: hpart->coarseparts = NULL;
598: hpart->fineparts = NULL;
599: hpart->coarseMatPart = NULL;
600: hpart->fineMatPart = NULL;
602: part->ops->apply = MatPartitioningApply_Hierarchical;
603: part->ops->view = MatPartitioningView_Hierarchical;
604: part->ops->destroy = MatPartitioningDestroy_Hierarchical;
605: part->ops->setfromoptions = MatPartitioningSetFromOptions_Hierarchical;
606: part->ops->improve = MatPartitioningImprove_Hierarchical;
607: PetscFunctionReturn(PETSC_SUCCESS);
608: }