Actual source code: partition.c
petsc-3.4.5 2014-06-29
2: #include <petsc-private/matimpl.h> /*I "petscmat.h" I*/
4: /* Logging support */
5: PetscClassId MAT_PARTITIONING_CLASSID;
7: /*
8: Simplest partitioning, keeps the current partitioning.
9: */
12: static PetscErrorCode MatPartitioningApply_Current(MatPartitioning part,IS *partitioning)
13: {
15: PetscInt m;
16: PetscMPIInt rank,size;
19: MPI_Comm_size(PetscObjectComm((PetscObject)part),&size);
20: if (part->n != size) {
21: const char *prefix;
22: PetscObjectGetOptionsPrefix((PetscObject)part,&prefix);
23: SETERRQ1(PetscObjectComm((PetscObject)part),PETSC_ERR_SUP,"This is the DEFAULT NO-OP partitioner, it currently only supports one domain per processor\nuse -%smat_partitioning_type parmetis or chaco or ptscotch for more than one subdomain per processor",prefix ? prefix : "");
24: }
25: MPI_Comm_rank(PetscObjectComm((PetscObject)part),&rank);
27: MatGetLocalSize(part->adj,&m,NULL);
28: ISCreateStride(PetscObjectComm((PetscObject)part),m,rank,0,partitioning);
29: return(0);
30: }
34: static PetscErrorCode MatPartitioningApply_Square(MatPartitioning part,IS *partitioning)
35: {
37: PetscInt cell,n,N,p,rstart,rend,*color;
38: PetscMPIInt size;
41: MPI_Comm_size(PetscObjectComm((PetscObject)part),&size);
42: if (part->n != size) SETERRQ(PetscObjectComm((PetscObject)part),PETSC_ERR_SUP,"Currently only supports one domain per processor");
43: p = (PetscInt)sqrt((double)part->n);
44: if (p*p != part->n) SETERRQ(PetscObjectComm((PetscObject)part),PETSC_ERR_SUP,"Square partitioning requires \"perfect square\" number of domains");
46: MatGetSize(part->adj,&N,NULL);
47: n = (PetscInt)sqrt((double)N);
48: if (n*n != N) SETERRQ(PetscObjectComm((PetscObject)part),PETSC_ERR_SUP,"Square partitioning requires square domain");
49: if (n%p != 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SUP,"Square partitioning requires p to divide n");
50: MatGetOwnershipRange(part->adj,&rstart,&rend);
51: PetscMalloc((rend-rstart)*sizeof(PetscInt),&color);
52: /* for (int cell=rstart; cell<rend; cell++) { color[cell-rstart] = ((cell%n) < (n/2)) + 2 * ((cell/n) < (n/2)); } */
53: for (cell=rstart; cell<rend; cell++) {
54: color[cell-rstart] = ((cell%n) / (n/p)) + p * ((cell/n) / (n/p));
55: }
56: ISCreateGeneral(PetscObjectComm((PetscObject)part),rend-rstart,color,PETSC_OWN_POINTER,partitioning);
57: return(0);
58: }
62: PETSC_EXTERN PetscErrorCode MatPartitioningCreate_Current(MatPartitioning part)
63: {
65: part->ops->apply = MatPartitioningApply_Current;
66: part->ops->view = 0;
67: part->ops->destroy = 0;
68: return(0);
69: }
73: PETSC_EXTERN PetscErrorCode MatPartitioningCreate_Square(MatPartitioning part)
74: {
76: part->ops->apply = MatPartitioningApply_Square;
77: part->ops->view = 0;
78: part->ops->destroy = 0;
79: return(0);
80: }
83: /* ===========================================================================================*/
85: PetscFunctionList MatPartitioningList = 0;
86: PetscBool MatPartitioningRegisterAllCalled = PETSC_FALSE;
91: /*@C
92: MatPartitioningRegister - Adds a new sparse matrix partitioning to the matrix package.
94: Not Collective
96: Input Parameters:
97: + sname - name of partitioning (for example MATPARTITIONINGCURRENT) or parmetis
98: - function - function pointer that creates the partitioning type
100: Level: developer
102: Sample usage:
103: .vb
104: MatPartitioningRegister("my_part",MyPartCreate);
105: .ve
107: Then, your partitioner can be chosen with the procedural interface via
108: $ MatPartitioningSetType(part,"my_part")
109: or at runtime via the option
110: $ -mat_partitioning_type my_part
112: .keywords: matrix, partitioning, register
114: .seealso: MatPartitioningRegisterDestroy(), MatPartitioningRegisterAll()
115: @*/
116: PetscErrorCode MatPartitioningRegister(const char sname[],PetscErrorCode (*function)(MatPartitioning))
117: {
121: PetscFunctionListAdd(&MatPartitioningList,sname,function);
122: return(0);
123: }
127: /*@C
128: MatPartitioningGetType - Gets the Partitioning method type and name (as a string)
129: from the partitioning context.
131: Not collective
133: Input Parameter:
134: . partitioning - the partitioning context
136: Output Parameter:
137: . type - partitioner type
139: Level: intermediate
141: Not Collective
143: .keywords: Partitioning, get, method, name, type
144: @*/
145: PetscErrorCode MatPartitioningGetType(MatPartitioning partitioning,MatPartitioningType *type)
146: {
150: *type = ((PetscObject)partitioning)->type_name;
151: return(0);
152: }
156: /*@C
157: MatPartitioningSetNParts - Set how many partitions need to be created;
158: by default this is one per processor. Certain partitioning schemes may
159: in fact only support that option.
161: Not collective
163: Input Parameter:
164: . partitioning - the partitioning context
165: . n - the number of partitions
167: Level: intermediate
169: Not Collective
171: .keywords: Partitioning, set
173: .seealso: MatPartitioningCreate(), MatPartitioningApply()
174: @*/
175: PetscErrorCode MatPartitioningSetNParts(MatPartitioning part,PetscInt n)
176: {
178: part->n = n;
179: return(0);
180: }
184: /*@
185: MatPartitioningApply - Gets a partitioning for a matrix.
187: Collective on Mat
189: Input Parameters:
190: . matp - the matrix partitioning object
192: Output Parameters:
193: . partitioning - the partitioning. For each local node this tells the processor
194: number that that node is assigned to.
196: Options Database Keys:
197: To specify the partitioning through the options database, use one of
198: the following
199: $ -mat_partitioning_type parmetis, -mat_partitioning current
200: To see the partitioning result
201: $ -mat_partitioning_view
203: Level: beginner
205: The user can define additional partitionings; see MatPartitioningRegister().
207: .keywords: matrix, get, partitioning
209: .seealso: MatPartitioningRegister(), MatPartitioningCreate(),
210: MatPartitioningDestroy(), MatPartitioningSetAdjacency(), ISPartitioningToNumbering(),
211: ISPartitioningCount()
212: @*/
213: PetscErrorCode MatPartitioningApply(MatPartitioning matp,IS *partitioning)
214: {
216: PetscBool flag = PETSC_FALSE;
221: if (!matp->adj->assembled) SETERRQ(PetscObjectComm((PetscObject)matp),PETSC_ERR_ARG_WRONGSTATE,"Not for unassembled matrix");
222: if (matp->adj->factortype) SETERRQ(PetscObjectComm((PetscObject)matp),PETSC_ERR_ARG_WRONGSTATE,"Not for factored matrix");
223: if (!matp->ops->apply) SETERRQ(PetscObjectComm((PetscObject)matp),PETSC_ERR_ARG_WRONGSTATE,"Must set type with MatPartitioningSetFromOptions() or MatPartitioningSetType()");
224: PetscLogEventBegin(MAT_Partitioning,matp,0,0,0);
225: (*matp->ops->apply)(matp,partitioning);
226: PetscLogEventEnd(MAT_Partitioning,matp,0,0,0);
228: PetscOptionsGetBool(NULL,"-mat_partitioning_view",&flag,NULL);
229: if (flag) {
230: PetscViewer viewer;
231: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)matp),&viewer);
232: MatPartitioningView(matp,viewer);
233: ISView(*partitioning,viewer);
234: }
235: return(0);
236: }
240: /*@
241: MatPartitioningSetAdjacency - Sets the adjacency graph (matrix) of the thing to be
242: partitioned.
244: Collective on MatPartitioning and Mat
246: Input Parameters:
247: + part - the partitioning context
248: - adj - the adjacency matrix
250: Level: beginner
252: .keywords: Partitioning, adjacency
254: .seealso: MatPartitioningCreate()
255: @*/
256: PetscErrorCode MatPartitioningSetAdjacency(MatPartitioning part,Mat adj)
257: {
261: part->adj = adj;
262: return(0);
263: }
267: /*@
268: MatPartitioningDestroy - Destroys the partitioning context.
270: Collective on Partitioning
272: Input Parameters:
273: . part - the partitioning context
275: Level: beginner
277: .keywords: Partitioning, destroy, context
279: .seealso: MatPartitioningCreate()
280: @*/
281: PetscErrorCode MatPartitioningDestroy(MatPartitioning *part)
282: {
286: if (!*part) return(0);
288: if (--((PetscObject)(*part))->refct > 0) {*part = 0; return(0);}
290: if ((*part)->ops->destroy) {
291: (*(*part)->ops->destroy)((*part));
292: }
293: PetscFree((*part)->vertex_weights);
294: PetscFree((*part)->part_weights);
295: PetscHeaderDestroy(part);
296: return(0);
297: }
301: /*@C
302: MatPartitioningSetVertexWeights - Sets the weights for vertices for a partitioning.
304: Logically Collective on Partitioning
306: Input Parameters:
307: + part - the partitioning context
308: - weights - the weights, on each process this array must have the same size as the number of local rows
310: Level: beginner
312: Notes:
313: The array weights is freed by PETSc so the user should not free the array. In C/C++
314: the array must be obtained with a call to PetscMalloc(), not malloc().
316: .keywords: Partitioning, destroy, context
318: .seealso: MatPartitioningCreate(), MatPartitioningSetType(), MatPartitioningSetPartitionWeights()
319: @*/
320: PetscErrorCode MatPartitioningSetVertexWeights(MatPartitioning part,const PetscInt weights[])
321: {
327: PetscFree(part->vertex_weights);
329: part->vertex_weights = (PetscInt*)weights;
330: return(0);
331: }
335: /*@C
336: MatPartitioningSetPartitionWeights - Sets the weights for each partition.
338: Logically Collective on Partitioning
340: Input Parameters:
341: + part - the partitioning context
342: - weights - An array of size nparts that is used to specify the fraction of
343: vertex weight that should be distributed to each sub-domain for
344: the balance constraint. If all of the sub-domains are to be of
345: the same size, then each of the nparts elements should be set
346: to a value of 1/nparts. Note that the sum of all of the weights
347: should be one.
349: Level: beginner
351: Notes:
352: The array weights is freed by PETSc so the user should not free the array. In C/C++
353: the array must be obtained with a call to PetscMalloc(), not malloc().
355: .keywords: Partitioning, destroy, context
357: .seealso: MatPartitioningCreate(), MatPartitioningSetType(), MatPartitioningSetVertexWeights()
358: @*/
359: PetscErrorCode MatPartitioningSetPartitionWeights(MatPartitioning part,const PetscReal weights[])
360: {
366: PetscFree(part->part_weights);
368: part->part_weights = (PetscReal*)weights;
369: return(0);
370: }
374: /*@
375: MatPartitioningCreate - Creates a partitioning context.
377: Collective on MPI_Comm
379: Input Parameter:
380: . comm - MPI communicator
382: Output Parameter:
383: . newp - location to put the context
385: Level: beginner
387: .keywords: Partitioning, create, context
389: .seealso: MatPartitioningSetType(), MatPartitioningApply(), MatPartitioningDestroy(),
390: MatPartitioningSetAdjacency()
392: @*/
393: PetscErrorCode MatPartitioningCreate(MPI_Comm comm,MatPartitioning *newp)
394: {
395: MatPartitioning part;
396: PetscErrorCode ierr;
397: PetscMPIInt size;
400: *newp = 0;
402: #if !defined(PETSC_USE_DYNAMIC_LIBRARIES)
403: MatInitializePackage();
404: #endif
405: PetscHeaderCreate(part,_p_MatPartitioning,struct _MatPartitioningOps,MAT_PARTITIONING_CLASSID,"MatPartitioning","Matrix/graph partitioning","MatOrderings",comm,MatPartitioningDestroy,MatPartitioningView);
406: part->vertex_weights = NULL;
407: part->part_weights = NULL;
409: MPI_Comm_size(comm,&size);
410: part->n = (PetscInt)size;
412: *newp = part;
413: return(0);
414: }
418: /*@C
419: MatPartitioningView - Prints the partitioning data structure.
421: Collective on MatPartitioning
423: Input Parameters:
424: . part - the partitioning context
425: . viewer - optional visualization context
427: Level: intermediate
429: Note:
430: The available visualization contexts include
431: + PETSC_VIEWER_STDOUT_SELF - standard output (default)
432: - PETSC_VIEWER_STDOUT_WORLD - synchronized standard
433: output where only the first processor opens
434: the file. All other processors send their
435: data to the first processor to print.
437: The user can open alternative visualization contexts with
438: . PetscViewerASCIIOpen() - output to a specified file
440: .keywords: Partitioning, view
442: .seealso: PetscViewerASCIIOpen()
443: @*/
444: PetscErrorCode MatPartitioningView(MatPartitioning part,PetscViewer viewer)
445: {
447: PetscBool iascii;
451: if (!viewer) {
452: PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject)part),&viewer);
453: }
457: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
458: if (iascii) {
459: PetscObjectPrintClassNamePrefixType((PetscObject)part,viewer,"MatPartitioning Object");
460: if (part->vertex_weights) {
461: PetscViewerASCIIPrintf(viewer," Using vertex weights\n");
462: }
463: }
464: if (part->ops->view) {
465: PetscViewerASCIIPushTab(viewer);
466: (*part->ops->view)(part,viewer);
467: PetscViewerASCIIPopTab(viewer);
468: }
469: return(0);
470: }
474: /*@C
475: MatPartitioningSetType - Sets the type of partitioner to use
477: Collective on MatPartitioning
479: Input Parameter:
480: . part - the partitioning context.
481: . type - a known method
483: Options Database Command:
484: $ -mat_partitioning_type <type>
485: $ Use -help for a list of available methods
486: $ (for instance, parmetis)
488: Level: intermediate
490: .keywords: partitioning, set, method, type
492: .seealso: MatPartitioningCreate(), MatPartitioningApply(), MatPartitioningType
494: @*/
495: PetscErrorCode MatPartitioningSetType(MatPartitioning part,MatPartitioningType type)
496: {
497: PetscErrorCode ierr,(*r)(MatPartitioning);
498: PetscBool match;
504: PetscObjectTypeCompare((PetscObject)part,type,&match);
505: if (match) return(0);
507: if (part->setupcalled) {
508: (*part->ops->destroy)(part);
510: part->ops->destroy = NULL;
511: part->data = 0;
512: part->setupcalled = 0;
513: }
515: PetscFunctionListFind(MatPartitioningList,type,&r);
516: if (!r) SETERRQ1(PetscObjectComm((PetscObject)part),PETSC_ERR_ARG_UNKNOWN_TYPE,"Unknown partitioning type %s",type);
518: part->ops->destroy = (PetscErrorCode (*)(MatPartitioning)) 0;
519: part->ops->view = (PetscErrorCode (*)(MatPartitioning,PetscViewer)) 0;
521: (*r)(part);
523: PetscFree(((PetscObject)part)->type_name);
524: PetscStrallocpy(type,&((PetscObject)part)->type_name);
525: return(0);
526: }
530: /*@
531: MatPartitioningSetFromOptions - Sets various partitioning options from the
532: options database.
534: Collective on MatPartitioning
536: Input Parameter:
537: . part - the partitioning context.
539: Options Database Command:
540: $ -mat_partitioning_type <type>
541: $ Use -help for a list of available methods
542: $ (for instance, parmetis)
544: Level: beginner
546: .keywords: partitioning, set, method, type
547: @*/
548: PetscErrorCode MatPartitioningSetFromOptions(MatPartitioning part)
549: {
551: PetscBool flag;
552: char type[256];
553: const char *def;
556: PetscObjectOptionsBegin((PetscObject)part);
557: if (!((PetscObject)part)->type_name) {
558: #if defined(PETSC_HAVE_PARMETIS)
559: def = MATPARTITIONINGPARMETIS;
560: #else
561: def = MATPARTITIONINGCURRENT;
562: #endif
563: } else {
564: def = ((PetscObject)part)->type_name;
565: }
566: PetscOptionsList("-mat_partitioning_type","Type of partitioner","MatPartitioningSetType",MatPartitioningList,def,type,256,&flag);
567: if (flag) {
568: MatPartitioningSetType(part,type);
569: }
570: /*
571: Set the type if it was never set.
572: */
573: if (!((PetscObject)part)->type_name) {
574: MatPartitioningSetType(part,def);
575: }
577: if (part->ops->setfromoptions) {
578: (*part->ops->setfromoptions)(part);
579: }
580: PetscOptionsEnd();
581: return(0);
582: }