Actual source code: partptscotch.c
1: #include <petsc/private/partitionerimpl.h>
2: #include <petsc/private/matimpl.h>
4: #if PetscDefined(HAVE_PTSCOTCH)
5: EXTERN_C_BEGIN
6: #include <ptscotch.h>
7: EXTERN_C_END
8: #endif
10: PetscBool PTScotchPartitionerCite = PETSC_FALSE;
11: const char PTScotchPartitionerCitation[] = "@article{PTSCOTCH,\n"
12: " author = {C. Chevalier and F. Pellegrini},\n"
13: " title = {{PT-SCOTCH}: a tool for efficient parallel graph ordering},\n"
14: " journal = {Parallel Computing},\n"
15: " volume = {34},\n"
16: " number = {6},\n"
17: " pages = {318--331},\n"
18: " year = {2008},\n"
19: " doi = {https://doi.org/10.1016/j.parco.2007.12.001}\n"
20: "}\n";
22: typedef struct {
23: MPI_Comm pcomm;
24: PetscInt strategy;
25: PetscReal imbalance;
26: } PetscPartitioner_PTScotch;
28: #if PetscDefined(HAVE_PTSCOTCH)
30: static int PTScotch_Strategy(PetscInt strategy)
31: {
32: switch (strategy) {
33: case 0:
34: return SCOTCH_STRATDEFAULT;
35: case 1:
36: return SCOTCH_STRATQUALITY;
37: case 2:
38: return SCOTCH_STRATSPEED;
39: case 3:
40: return SCOTCH_STRATBALANCE;
41: case 4:
42: return SCOTCH_STRATSAFETY;
43: case 5:
44: return SCOTCH_STRATSCALABILITY;
45: case 6:
46: return SCOTCH_STRATRECURSIVE;
47: case 7:
48: return SCOTCH_STRATREMAP;
49: default:
50: return SCOTCH_STRATDEFAULT;
51: }
52: }
54: #endif /* PETSC_HAVE_PTSCOTCH */
56: static const char *const PTScotchStrategyList[] = {"DEFAULT", "QUALITY", "SPEED", "BALANCE", "SAFETY", "SCALABILITY", "RECURSIVE", "REMAP"};
58: static PetscErrorCode PetscPartitionerDestroy_PTScotch(PetscPartitioner part)
59: {
60: PetscPartitioner_PTScotch *p = (PetscPartitioner_PTScotch *)part->data;
62: PetscFunctionBegin;
63: PetscCallMPI(MPI_Comm_free(&p->pcomm));
64: PetscCall(PetscFree(part->data));
65: PetscFunctionReturn(PETSC_SUCCESS);
66: }
68: static PetscErrorCode PetscPartitionerView_PTScotch_ASCII(PetscPartitioner part, PetscViewer viewer)
69: {
70: PetscPartitioner_PTScotch *p = (PetscPartitioner_PTScotch *)part->data;
72: PetscFunctionBegin;
73: PetscCall(PetscViewerASCIIPushTab(viewer));
74: PetscCall(PetscViewerASCIIPrintf(viewer, "using partitioning strategy %s\n", PTScotchStrategyList[p->strategy]));
75: PetscCall(PetscViewerASCIIPrintf(viewer, "using load imbalance ratio %g\n", (double)p->imbalance));
76: PetscCall(PetscViewerASCIIPopTab(viewer));
77: PetscFunctionReturn(PETSC_SUCCESS);
78: }
80: static PetscErrorCode PetscPartitionerView_PTScotch(PetscPartitioner part, PetscViewer viewer)
81: {
82: PetscBool isascii;
84: PetscFunctionBegin;
87: PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
88: if (isascii) PetscCall(PetscPartitionerView_PTScotch_ASCII(part, viewer));
89: PetscFunctionReturn(PETSC_SUCCESS);
90: }
92: static PetscErrorCode PetscPartitionerSetFromOptions_PTScotch(PetscPartitioner part, PetscOptionItems PetscOptionsObject)
93: {
94: PetscPartitioner_PTScotch *p = (PetscPartitioner_PTScotch *)part->data;
95: const char *const *slist = PTScotchStrategyList;
96: PetscInt nlist = PETSC_STATIC_ARRAY_LENGTH(PTScotchStrategyList);
97: PetscBool flag;
99: PetscFunctionBegin;
100: PetscOptionsHeadBegin(PetscOptionsObject, "PetscPartitioner PTScotch Options");
101: PetscCall(PetscOptionsEList("-petscpartitioner_ptscotch_strategy", "Partitioning strategy", "", slist, nlist, slist[p->strategy], &p->strategy, &flag));
102: PetscCall(PetscOptionsReal("-petscpartitioner_ptscotch_imbalance", "Load imbalance ratio", "", p->imbalance, &p->imbalance, &flag));
103: PetscOptionsHeadEnd();
104: PetscFunctionReturn(PETSC_SUCCESS);
105: }
107: static PetscErrorCode PetscPartitionerPartition_PTScotch(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertSection, PetscSection edgeSection, PetscSection targetSection, PetscSection partSection, IS *partition)
108: {
109: #if PetscDefined(HAVE_PTSCOTCH)
110: MPI_Comm comm;
111: PetscInt nvtxs = numVertices; /* The number of vertices in full graph */
112: PetscInt *vtxdist; /* Distribution of vertices across processes */
113: PetscInt *xadj = start; /* Start of edge list for each vertex */
114: PetscInt *adjncy = adjacency; /* Edge lists for all vertices */
115: PetscInt *vwgt = NULL; /* Vertex weights */
116: PetscInt *adjwgt = NULL; /* Edge weights */
117: PetscInt v, i, *assignment, *points;
118: PetscMPIInt size, p;
119: PetscInt *tpwgts = NULL;
121: PetscFunctionBegin;
122: PetscCall(PetscObjectGetComm((PetscObject)part, &comm));
123: PetscCallMPI(MPI_Comm_size(comm, &size));
124: PetscCall(PetscMalloc2(size + 1, &vtxdist, PetscMax(nvtxs, 1), &assignment));
125: /* Calculate vertex distribution */
126: vtxdist[0] = 0;
127: PetscCallMPI(MPI_Allgather(&nvtxs, 1, MPIU_INT, &vtxdist[1], 1, MPIU_INT, comm));
128: for (p = 2; p <= size; ++p) vtxdist[p] += vtxdist[p - 1];
129: /* null graph */
130: if (vtxdist[size] == 0) {
131: PetscCall(PetscFree2(vtxdist, assignment));
132: PetscCall(ISCreateGeneral(comm, 0, NULL, PETSC_OWN_POINTER, partition));
133: PetscFunctionReturn(PETSC_SUCCESS);
134: }
136: /* Calculate vertex weights */
137: if (vertSection) {
138: PetscCall(PetscMalloc1(nvtxs, &vwgt));
139: for (v = 0; v < nvtxs; ++v) PetscCall(PetscSectionGetDof(vertSection, v, &vwgt[v]));
140: }
141: // Weight edges
142: if (edgeSection) {
143: PetscCall(PetscMalloc1(xadj[nvtxs], &adjwgt));
144: for (PetscInt e = 0; e < xadj[nvtxs]; ++e) PetscCall(PetscSectionGetDof(edgeSection, e, &adjwgt[e]));
145: }
147: /* Calculate partition weights */
148: if (targetSection) {
149: PetscInt sumw;
151: PetscCall(PetscCalloc1(nparts, &tpwgts));
152: for (p = 0, sumw = 0; p < nparts; ++p) {
153: PetscCall(PetscSectionGetDof(targetSection, p, &tpwgts[p]));
154: sumw += tpwgts[p];
155: }
156: if (!sumw) PetscCall(PetscFree(tpwgts));
157: }
159: {
160: PetscPartitioner_PTScotch *pts = (PetscPartitioner_PTScotch *)part->data;
161: PetscBool usevwgt = PETSC_TRUE;
162: int strat = PTScotch_Strategy(pts->strategy);
164: PetscCall(PetscOptionsDeprecatedNoObject(comm, NULL, "-petscpartititoner_ptscotch_vertex_weight", "-petscpartitioner_use_vertex_weights", "3.13", NULL));
165: /*
166: Cannot remove the PetscOptionsGetBool() below since the PetscOptionsDeprecatedNoObject() above is called after the non-deprecated version
167: has already been checked in PetscPartitionerSetFromOptions().
168: */
169: PetscCall(PetscOptionsGetBool(NULL, NULL, "-petscpartititoner_use_vertex_weight", &usevwgt, NULL));
170: /* edgeSection is the same on every process, so it reports edge weights where adjwgt cannot:
171: a process owning no edges allocates nothing and passes a null array. */
172: PetscCall(PetscPTSCOTCHPartitionGraph_Private(pts->pcomm, vtxdist, xadj, adjncy, usevwgt ? vwgt : NULL, adjwgt, (PetscBool)(edgeSection != NULL), nparts, tpwgts, strat, (double)pts->imbalance, assignment));
173: }
174: PetscCall(PetscFree(vwgt));
175: PetscCall(PetscFree(adjwgt));
176: PetscCall(PetscFree(tpwgts));
178: /* Convert to PetscSection+IS */
179: for (v = 0; v < nvtxs; ++v) PetscCall(PetscSectionAddDof(partSection, assignment[v], 1));
180: PetscCall(PetscMalloc1(nvtxs, &points));
181: for (p = 0, i = 0; p < nparts; ++p) {
182: for (v = 0; v < nvtxs; ++v) {
183: if (assignment[v] == p) points[i++] = v;
184: }
185: }
186: PetscCheck(i == nvtxs, comm, PETSC_ERR_PLIB, "Number of points %" PetscInt_FMT " should be %" PetscInt_FMT, i, nvtxs);
187: PetscCall(ISCreateGeneral(comm, nvtxs, points, PETSC_OWN_POINTER, partition));
189: PetscCall(PetscFree2(vtxdist, assignment));
190: PetscFunctionReturn(PETSC_SUCCESS);
191: #else
192: SETERRQ(PetscObjectComm((PetscObject)part), PETSC_ERR_SUP, "Mesh partitioning needs external package support.\nPlease reconfigure with --download-ptscotch.");
193: #endif
194: }
196: static PetscErrorCode PetscPartitionerInitialize_PTScotch(PetscPartitioner part)
197: {
198: PetscFunctionBegin;
199: part->noGraph = PETSC_FALSE;
200: part->ops->view = PetscPartitionerView_PTScotch;
201: part->ops->destroy = PetscPartitionerDestroy_PTScotch;
202: part->ops->partition = PetscPartitionerPartition_PTScotch;
203: part->ops->setfromoptions = PetscPartitionerSetFromOptions_PTScotch;
204: PetscFunctionReturn(PETSC_SUCCESS);
205: }
207: /*MC
208: PETSCPARTITIONERPTSCOTCH = "ptscotch" - A PetscPartitioner object using the PT-Scotch library
210: Level: intermediate
212: Options Database Keys:
213: + -petscpartitioner_ptscotch_strategy (default|quality|speed|balance|safety|scalability|recursive|remap) - PT-SCOTCH strategy.
214: - -petscpartitioner_ptscotch_imbalance ratio - Load imbalance ratio
216: Notes: when the graph is on a single process, this partitioner actually uses Scotch and not PT-Scotch
218: .seealso: `PetscPartitionerType`, `PetscPartitionerCreate()`, `PetscPartitionerSetType()`
219: M*/
221: PETSC_EXTERN PetscErrorCode PetscPartitionerCreate_PTScotch(PetscPartitioner part)
222: {
223: PetscPartitioner_PTScotch *p;
225: PetscFunctionBegin;
227: PetscCall(PetscNew(&p));
228: part->data = p;
230: PetscCallMPI(MPI_Comm_dup(PetscObjectComm((PetscObject)part), &p->pcomm));
231: p->strategy = 0;
232: p->imbalance = 0.01;
234: PetscCall(PetscPartitionerInitialize_PTScotch(part));
235: PetscCall(PetscCitationsRegister(PTScotchPartitionerCitation, &PTScotchPartitionerCite));
236: PetscFunctionReturn(PETSC_SUCCESS);
237: }