1 #include <petsc/private/partitionerimpl.h>        /*I "petscpartitioner.h" I*/
2 
3 /*@C
4   PetscPartitionerSetType - Builds a particular PetscPartitioner
5 
6   Collective on PetscPartitioner
7 
8   Input Parameters:
9 + part - The PetscPartitioner object
10 - name - The kind of partitioner
11 
12   Options Database Key:
13 . -petscpartitioner_type <type> - Sets the PetscPartitioner type; use -help for a list of available types
14 
15   Level: intermediate
16 
17 .seealso: PetscPartitionerGetType(), PetscPartitionerCreate()
18 @*/
PetscPartitionerSetType(PetscPartitioner part,PetscPartitionerType name)19 PetscErrorCode PetscPartitionerSetType(PetscPartitioner part, PetscPartitionerType name)
20 {
21   PetscErrorCode (*r)(PetscPartitioner);
22   PetscBool      match;
23   PetscErrorCode ierr;
24 
25   PetscFunctionBegin;
26   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
27   ierr = PetscObjectTypeCompare((PetscObject) part, name, &match);CHKERRQ(ierr);
28   if (match) PetscFunctionReturn(0);
29 
30   ierr = PetscPartitionerRegisterAll();CHKERRQ(ierr);
31   ierr = PetscFunctionListFind(PetscPartitionerList, name, &r);CHKERRQ(ierr);
32   if (!r) SETERRQ1(PetscObjectComm((PetscObject) part), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unknown PetscPartitioner type: %s", name);
33 
34   if (part->ops->destroy) {
35     ierr = (*part->ops->destroy)(part);CHKERRQ(ierr);
36   }
37   part->noGraph = PETSC_FALSE;
38   ierr = PetscMemzero(part->ops, sizeof(*part->ops));CHKERRQ(ierr);
39   ierr = PetscObjectChangeTypeName((PetscObject) part, name);CHKERRQ(ierr);
40   ierr = (*r)(part);CHKERRQ(ierr);
41   PetscFunctionReturn(0);
42 }
43 
44 /*@C
45   PetscPartitionerGetType - Gets the PetscPartitioner type name (as a string) from the object.
46 
47   Not Collective
48 
49   Input Parameter:
50 . part - The PetscPartitioner
51 
52   Output Parameter:
53 . name - The PetscPartitioner type name
54 
55   Level: intermediate
56 
57 .seealso: PetscPartitionerSetType(), PetscPartitionerCreate()
58 @*/
PetscPartitionerGetType(PetscPartitioner part,PetscPartitionerType * name)59 PetscErrorCode PetscPartitionerGetType(PetscPartitioner part, PetscPartitionerType *name)
60 {
61   PetscFunctionBegin;
62   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
63   PetscValidPointer(name, 2);
64   *name = ((PetscObject) part)->type_name;
65   PetscFunctionReturn(0);
66 }
67 
68 /*@C
69    PetscPartitionerViewFromOptions - View from Options
70 
71    Collective on PetscPartitioner
72 
73    Input Parameters:
74 +  A - the PetscPartitioner object
75 .  obj - Optional object
76 -  name - command line option
77 
78    Level: intermediate
79 .seealso:  PetscPartitionerView(), PetscObjectViewFromOptions()
80 @*/
PetscPartitionerViewFromOptions(PetscPartitioner A,PetscObject obj,const char name[])81 PetscErrorCode PetscPartitionerViewFromOptions(PetscPartitioner A,PetscObject obj,const char name[])
82 {
83   PetscErrorCode ierr;
84 
85   PetscFunctionBegin;
86   PetscValidHeaderSpecific(A,PETSCPARTITIONER_CLASSID,1);
87   ierr = PetscObjectViewFromOptions((PetscObject)A,obj,name);CHKERRQ(ierr);
88   PetscFunctionReturn(0);
89 }
90 
91 /*@
92   PetscPartitionerView - Views a PetscPartitioner
93 
94   Collective on PetscPartitioner
95 
96   Input Parameter:
97 + part - the PetscPartitioner object to view
98 - v    - the viewer
99 
100   Level: developer
101 
102 .seealso: PetscPartitionerDestroy()
103 @*/
PetscPartitionerView(PetscPartitioner part,PetscViewer v)104 PetscErrorCode PetscPartitionerView(PetscPartitioner part, PetscViewer v)
105 {
106   PetscMPIInt    size;
107   PetscBool      isascii;
108   PetscErrorCode ierr;
109 
110   PetscFunctionBegin;
111   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
112   if (!v) {ierr = PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject) part), &v);CHKERRQ(ierr);}
113   ierr = PetscObjectTypeCompare((PetscObject) v, PETSCVIEWERASCII, &isascii);CHKERRQ(ierr);
114   if (isascii) {
115     ierr = MPI_Comm_size(PetscObjectComm((PetscObject) part), &size);CHKERRQ(ierr);
116     ierr = PetscViewerASCIIPrintf(v, "Graph Partitioner: %d MPI Process%s\n", size, size > 1 ? "es" : "");CHKERRQ(ierr);
117     ierr = PetscViewerASCIIPrintf(v, "  type: %s\n", ((PetscObject)part)->type_name);CHKERRQ(ierr);
118     ierr = PetscViewerASCIIPrintf(v, "  edge cut: %D\n", part->edgeCut);CHKERRQ(ierr);
119     ierr = PetscViewerASCIIPrintf(v, "  balance: %.2g\n", part->balance);CHKERRQ(ierr);
120     ierr = PetscViewerASCIIPrintf(v, "  use vertex weights: %d\n", part->usevwgt);CHKERRQ(ierr);
121   }
122   if (part->ops->view) {ierr = (*part->ops->view)(part, v);CHKERRQ(ierr);}
123   PetscFunctionReturn(0);
124 }
125 
PetscPartitionerGetDefaultType(MPI_Comm comm,const char ** defaultType)126 static PetscErrorCode PetscPartitionerGetDefaultType(MPI_Comm comm, const char **defaultType)
127 {
128   PetscMPIInt    size;
129   PetscErrorCode ierr;
130 
131   PetscFunctionBegin;
132   ierr = MPI_Comm_size(comm, &size);CHKERRQ(ierr);
133   if (size == 1) {
134     *defaultType = PETSCPARTITIONERSIMPLE;
135   } else {
136 #if defined(PETSC_HAVE_PARMETIS)
137     *defaultType = PETSCPARTITIONERPARMETIS;
138 #elif defined(PETSC_HAVE_PTSCOTCH)
139     *defaultType = PETSCPARTITIONERPTSCOTCH;
140 #elif defined(PETSC_HAVE_CHACO)
141     *defaultType = PETSCPARTITIONERCHACO;
142 #else
143     *defaultType = PETSCPARTITIONERSIMPLE;
144 #endif
145   }
146   PetscFunctionReturn(0);
147 }
148 
149 /*@
150   PetscPartitionerSetFromOptions - sets parameters in a PetscPartitioner from the options database
151 
152   Collective on PetscPartitioner
153 
154   Input Parameter:
155 . part - the PetscPartitioner object to set options for
156 
157   Options Database Keys:
158 +  -petscpartitioner_type <type> - Sets the PetscPartitioner type; use -help for a list of available types
159 .  -petscpartitioner_use_vertex_weights - Uses weights associated with the graph vertices
160 -  -petscpartitioner_view_graph - View the graph each time PetscPartitionerPartition is called. Viewer can be customized, see PetscOptionsGetViewer()
161 
162   Level: developer
163 
164 .seealso: PetscPartitionerView(), PetscPartitionerSetType(), PetscPartitionerPartition()
165 @*/
PetscPartitionerSetFromOptions(PetscPartitioner part)166 PetscErrorCode PetscPartitionerSetFromOptions(PetscPartitioner part)
167 {
168   const char    *currentType = NULL;
169   char           name[256];
170   PetscBool      flg;
171   PetscErrorCode ierr;
172 
173   PetscFunctionBegin;
174   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
175   ierr = PetscObjectOptionsBegin((PetscObject) part);CHKERRQ(ierr);
176   ierr = PetscPartitionerGetType(part, &currentType);CHKERRQ(ierr);
177   ierr = PetscOptionsFList("-petscpartitioner_type", "Graph partitioner", "PetscPartitionerSetType", PetscPartitionerList, currentType, name, sizeof(name), &flg);CHKERRQ(ierr);
178   if (flg) {
179     ierr = PetscPartitionerSetType(part, name);CHKERRQ(ierr);
180   }
181   ierr = PetscOptionsBool("-petscpartitioner_use_vertex_weights","Use vertex weights","",part->usevwgt,&part->usevwgt,NULL);CHKERRQ(ierr);
182   if (part->ops->setfromoptions) {
183     ierr = (*part->ops->setfromoptions)(PetscOptionsObject,part);CHKERRQ(ierr);
184   }
185   ierr = PetscViewerDestroy(&part->viewer);CHKERRQ(ierr);
186   ierr = PetscViewerDestroy(&part->viewerGraph);CHKERRQ(ierr);
187   ierr = PetscOptionsGetViewer(((PetscObject) part)->comm, ((PetscObject) part)->options, ((PetscObject) part)->prefix, "-petscpartitioner_view", &part->viewer, NULL, NULL);CHKERRQ(ierr);
188   ierr = PetscOptionsGetViewer(((PetscObject) part)->comm, ((PetscObject) part)->options, ((PetscObject) part)->prefix, "-petscpartitioner_view_graph", &part->viewerGraph, NULL, &part->viewGraph);CHKERRQ(ierr);
189   /* process any options handlers added with PetscObjectAddOptionsHandler() */
190   ierr = PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject) part);CHKERRQ(ierr);
191   ierr = PetscOptionsEnd();CHKERRQ(ierr);
192   PetscFunctionReturn(0);
193 }
194 
195 /*@
196   PetscPartitionerSetUp - Construct data structures for the PetscPartitioner
197 
198   Collective on PetscPartitioner
199 
200   Input Parameter:
201 . part - the PetscPartitioner object to setup
202 
203   Level: developer
204 
205 .seealso: PetscPartitionerView(), PetscPartitionerDestroy()
206 @*/
PetscPartitionerSetUp(PetscPartitioner part)207 PetscErrorCode PetscPartitionerSetUp(PetscPartitioner part)
208 {
209   PetscErrorCode ierr;
210 
211   PetscFunctionBegin;
212   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
213   if (part->ops->setup) {ierr = (*part->ops->setup)(part);CHKERRQ(ierr);}
214   PetscFunctionReturn(0);
215 }
216 
217 /*@
218   PetscPartitionerReset - Resets data structures for the PetscPartitioner
219 
220   Collective on PetscPartitioner
221 
222   Input Parameter:
223 . part - the PetscPartitioner object to reset
224 
225   Level: developer
226 
227 .seealso: PetscPartitionerSetUp(), PetscPartitionerDestroy()
228 @*/
PetscPartitionerReset(PetscPartitioner part)229 PetscErrorCode PetscPartitionerReset(PetscPartitioner part)
230 {
231   PetscErrorCode ierr;
232 
233   PetscFunctionBegin;
234   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
235   if (part->ops->reset) {ierr = (*part->ops->reset)(part);CHKERRQ(ierr);}
236   PetscFunctionReturn(0);
237 }
238 
239 /*@
240   PetscPartitionerDestroy - Destroys a PetscPartitioner object
241 
242   Collective on PetscPartitioner
243 
244   Input Parameter:
245 . part - the PetscPartitioner object to destroy
246 
247   Level: developer
248 
249 .seealso: PetscPartitionerView()
250 @*/
PetscPartitionerDestroy(PetscPartitioner * part)251 PetscErrorCode PetscPartitionerDestroy(PetscPartitioner *part)
252 {
253   PetscErrorCode ierr;
254 
255   PetscFunctionBegin;
256   if (!*part) PetscFunctionReturn(0);
257   PetscValidHeaderSpecific((*part), PETSCPARTITIONER_CLASSID, 1);
258 
259   if (--((PetscObject)(*part))->refct > 0) {*part = NULL; PetscFunctionReturn(0);}
260   ((PetscObject) (*part))->refct = 0;
261 
262   ierr = PetscPartitionerReset(*part);CHKERRQ(ierr);
263 
264   ierr = PetscViewerDestroy(&(*part)->viewer);CHKERRQ(ierr);
265   ierr = PetscViewerDestroy(&(*part)->viewerGraph);CHKERRQ(ierr);
266   if ((*part)->ops->destroy) {ierr = (*(*part)->ops->destroy)(*part);CHKERRQ(ierr);}
267   ierr = PetscHeaderDestroy(part);CHKERRQ(ierr);
268   PetscFunctionReturn(0);
269 }
270 
271 /*@
272   PetscPartitionerPartition - Partition a graph
273 
274   Collective on PetscPartitioner
275 
276   Input Parameters:
277 + part    - The PetscPartitioner
278 . nparts  - Number of partitions
279 . numVertices - Number of vertices in the local part of the graph
280 . start - row pointers for the local part of the graph (CSR style)
281 . adjacency - adjacency list (CSR style)
282 . vertexSection - PetscSection describing the absolute weight of each local vertex (can be NULL)
283 - targetSection - PetscSection describing the absolute weight of each partition (can be NULL)
284 
285   Output Parameters:
286 + partSection     - The PetscSection giving the division of points by partition
287 - partition       - The list of points by partition
288 
289   Options Database:
290 + -petscpartitioner_view - View the partitioner information
291 - -petscpartitioner_view_graph - View the graph we are partitioning
292 
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.
296 
297   Level: developer
298 
299 .seealso PetscPartitionerCreate(), PetscSectionCreate(), PetscSectionSetChart(), PetscSectionSetDof()
300 @*/
PetscPartitionerPartition(PetscPartitioner part,PetscInt nparts,PetscInt numVertices,PetscInt start[],PetscInt adjacency[],PetscSection vertexSection,PetscSection targetSection,PetscSection partSection,IS * partition)301 PetscErrorCode PetscPartitionerPartition(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertexSection, PetscSection targetSection, PetscSection partSection, IS *partition)
302 {
303   PetscErrorCode ierr;
304 
305   PetscFunctionBegin;
306   PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1);
307   PetscValidLogicalCollectiveInt(part, nparts, 2);
308   if (nparts <= 0) SETERRQ(PetscObjectComm((PetscObject) part), PETSC_ERR_ARG_OUTOFRANGE, "Number of parts must be positive");
309   if (numVertices < 0) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Number of vertices must be non-negative");
310   if (numVertices && !part->noGraph) {
311     PetscValidIntPointer(start, 4);
312     PetscValidIntPointer(start + numVertices, 4);
313     if (start[numVertices]) PetscValidIntPointer(adjacency, 5);
314   }
315   if (vertexSection) {
316     PetscInt s,e;
317 
318     PetscValidHeaderSpecific(vertexSection, PETSC_SECTION_CLASSID, 6);
319     ierr = PetscSectionGetChart(vertexSection, &s, &e);CHKERRQ(ierr);
320     if (s > 0 || e < numVertices) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Invalid vertexSection chart [%D,%D)",s,e);
321   }
322   if (targetSection) {
323     PetscInt s,e;
324 
325     PetscValidHeaderSpecific(targetSection, PETSC_SECTION_CLASSID, 7);
326     ierr = PetscSectionGetChart(targetSection, &s, &e);CHKERRQ(ierr);
327     if (s > 0 || e < nparts) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Invalid targetSection chart [%D,%D)",s,e);
328   }
329   PetscValidHeaderSpecific(partSection, PETSC_SECTION_CLASSID, 8);
330   PetscValidPointer(partition, 9);
331 
332   ierr = PetscSectionReset(partSection);CHKERRQ(ierr);
333   ierr = PetscSectionSetChart(partSection, 0, nparts);CHKERRQ(ierr);
334   if (nparts == 1) { /* quick */
335     ierr = PetscSectionSetDof(partSection, 0, numVertices);CHKERRQ(ierr);
336     ierr = ISCreateStride(PetscObjectComm((PetscObject)part),numVertices,0,1,partition);CHKERRQ(ierr);
337   } else {
338     if (!part->ops->partition) SETERRQ1(PetscObjectComm((PetscObject) part), PETSC_ERR_SUP, "PetscPartitioner %s has no partitioning method", ((PetscObject)part)->type_name);
339     ierr = (*part->ops->partition)(part, nparts, numVertices, start, adjacency, vertexSection, targetSection, partSection, partition);CHKERRQ(ierr);
340   }
341   ierr = PetscSectionSetUp(partSection);CHKERRQ(ierr);
342   if (part->viewerGraph) {
343     PetscViewer viewer = part->viewerGraph;
344     PetscBool   isascii;
345     PetscInt    v, i;
346     PetscMPIInt rank;
347 
348     ierr = MPI_Comm_rank(PetscObjectComm((PetscObject) viewer), &rank);CHKERRQ(ierr);
349     ierr = PetscObjectTypeCompare((PetscObject) viewer, PETSCVIEWERASCII, &isascii);CHKERRQ(ierr);
350     if (isascii) {
351       ierr = PetscViewerASCIIPushSynchronized(viewer);CHKERRQ(ierr);
352       ierr = PetscViewerASCIISynchronizedPrintf(viewer, "[%d]Nv: %D\n", rank, numVertices);CHKERRQ(ierr);
353       for (v = 0; v < numVertices; ++v) {
354         const PetscInt s = start[v];
355         const PetscInt e = start[v+1];
356 
357         ierr = PetscViewerASCIISynchronizedPrintf(viewer, "[%d]  ", rank);CHKERRQ(ierr);
358         for (i = s; i < e; ++i) {ierr = PetscViewerASCIISynchronizedPrintf(viewer, "%D ", adjacency[i]);CHKERRQ(ierr);}
359         ierr = PetscViewerASCIISynchronizedPrintf(viewer, "[%D-%D)\n", s, e);CHKERRQ(ierr);
360       }
361       ierr = PetscViewerFlush(viewer);CHKERRQ(ierr);
362       ierr = PetscViewerASCIIPopSynchronized(viewer);CHKERRQ(ierr);
363     }
364   }
365   if (part->viewer) {
366     ierr = PetscPartitionerView(part,part->viewer);CHKERRQ(ierr);
367   }
368   PetscFunctionReturn(0);
369 }
370 
371 /*@
372   PetscPartitionerCreate - Creates an empty PetscPartitioner object. The type can then be set with PetscPartitionerSetType().
373 
374   Collective
375 
376   Input Parameter:
377 . comm - The communicator for the PetscPartitioner object
378 
379   Output Parameter:
380 . part - The PetscPartitioner object
381 
382   Level: beginner
383 
384 .seealso: PetscPartitionerSetType(), PETSCPARTITIONERCHACO, PETSCPARTITIONERPARMETIS, PETSCPARTITIONERSHELL, PETSCPARTITIONERSIMPLE, PETSCPARTITIONERGATHER
385 @*/
PetscPartitionerCreate(MPI_Comm comm,PetscPartitioner * part)386 PetscErrorCode PetscPartitionerCreate(MPI_Comm comm, PetscPartitioner *part)
387 {
388   PetscPartitioner p;
389   const char       *partitionerType = NULL;
390   PetscErrorCode   ierr;
391 
392   PetscFunctionBegin;
393   PetscValidPointer(part, 2);
394   *part = NULL;
395   ierr = PetscPartitionerInitializePackage();CHKERRQ(ierr);
396 
397   ierr = PetscHeaderCreate(p, PETSCPARTITIONER_CLASSID, "PetscPartitioner", "Graph Partitioner", "PetscPartitioner", comm, PetscPartitionerDestroy, PetscPartitionerView);CHKERRQ(ierr);
398   ierr = PetscPartitionerGetDefaultType(comm, &partitionerType);CHKERRQ(ierr);
399   ierr = PetscPartitionerSetType(p, partitionerType);CHKERRQ(ierr);
400 
401   p->edgeCut = 0;
402   p->balance = 0.0;
403   p->usevwgt = PETSC_TRUE;
404 
405   *part = p;
406   PetscFunctionReturn(0);
407 }
408 
409