Actual source code: partition.c
petsc-3.3-p7 2013-05-11
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(((PetscObject)part)->comm,&size);
20: if (part->n != size) {
21: const char *prefix;
22: PetscObjectGetOptionsPrefix((PetscObject)part,&prefix);
23: SETERRQ1(((PetscObject)part)->comm,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(((PetscObject)part)->comm,&rank);
27: MatGetLocalSize(part->adj,&m,PETSC_NULL);
28: ISCreateStride(((PetscObject)part)->comm,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(((PetscObject)part)->comm,&size);
42: if (part->n != size) SETERRQ(((PetscObject)part)->comm,PETSC_ERR_SUP,"Currently only supports one domain per processor");
43: p = (PetscInt)sqrt((double)part->n);
44: if (p*p != part->n) SETERRQ(((PetscObject)part)->comm,PETSC_ERR_SUP,"Square partitioning requires \"perfect square\" number of domains");
46: MatGetSize(part->adj,&N,PETSC_NULL);
47: n = (PetscInt)sqrt((double)N);
48: if (n*n != N) SETERRQ(((PetscObject)part)->comm,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(((PetscObject)part)->comm,rend-rstart,color,PETSC_OWN_POINTER,partitioning);
57: return(0);
58: }
60: EXTERN_C_BEGIN
63: PetscErrorCode MatPartitioningCreate_Current(MatPartitioning part)
64: {
66: part->ops->apply = MatPartitioningApply_Current;
67: part->ops->view = 0;
68: part->ops->destroy = 0;
69: return(0);
70: }
71: EXTERN_C_END
73: EXTERN_C_BEGIN
76: PetscErrorCode MatPartitioningCreate_Square(MatPartitioning part)
77: {
79: part->ops->apply = MatPartitioningApply_Square;
80: part->ops->view = 0;
81: part->ops->destroy = 0;
82: return(0);
83: }
84: EXTERN_C_END
86: /* ===========================================================================================*/
88: PetscFList MatPartitioningList = 0;
89: PetscBool MatPartitioningRegisterAllCalled = PETSC_FALSE;
94: PetscErrorCode MatPartitioningRegister(const char sname[],const char path[],const char name[],PetscErrorCode (*function)(MatPartitioning))
95: {
97: char fullname[PETSC_MAX_PATH_LEN];
100: PetscFListConcat(path,name,fullname);
101: PetscFListAdd(&MatPartitioningList,sname,fullname,(void (*)(void))function);
102: return(0);
103: }
107: /*@C
108: MatPartitioningRegisterDestroy - Frees the list of partitioning routines.
110: Not Collective
112: Level: developer
114: .keywords: matrix, register, destroy
116: .seealso: MatPartitioningRegisterDynamic(), MatPartitioningRegisterAll()
117: @*/
118: PetscErrorCode MatPartitioningRegisterDestroy(void)
119: {
123: MatPartitioningRegisterAllCalled = PETSC_FALSE;
124: PetscFListDestroy(&MatPartitioningList);
125: return(0);
126: }
130: /*@C
131: MatPartitioningGetType - Gets the Partitioning method type and name (as a string)
132: from the partitioning context.
134: Not collective
136: Input Parameter:
137: . partitioning - the partitioning context
139: Output Parameter:
140: . type - partitioner type
142: Level: intermediate
144: Not Collective
146: .keywords: Partitioning, get, method, name, type
147: @*/
148: PetscErrorCode MatPartitioningGetType(MatPartitioning partitioning,const MatPartitioningType *type)
149: {
153: *type = ((PetscObject)partitioning)->type_name;
154: return(0);
155: }
159: /*@C
160: MatPartitioningSetNParts - Set how many partitions need to be created;
161: by default this is one per processor. Certain partitioning schemes may
162: in fact only support that option.
164: Not collective
166: Input Parameter:
167: . partitioning - the partitioning context
168: . n - the number of partitions
170: Level: intermediate
172: Not Collective
174: .keywords: Partitioning, set
176: .seealso: MatPartitioningCreate(), MatPartitioningApply()
177: @*/
178: PetscErrorCode MatPartitioningSetNParts(MatPartitioning part,PetscInt n)
179: {
181: part->n = n;
182: return(0);
183: }
187: /*@
188: MatPartitioningApply - Gets a partitioning for a matrix.
190: Collective on Mat
192: Input Parameters:
193: . matp - the matrix partitioning object
195: Output Parameters:
196: . partitioning - the partitioning. For each local node this tells the processor
197: number that that node is assigned to.
199: Options Database Keys:
200: To specify the partitioning through the options database, use one of
201: the following
202: $ -mat_partitioning_type parmetis, -mat_partitioning current
203: To see the partitioning result
204: $ -mat_partitioning_view
206: Level: beginner
208: The user can define additional partitionings; see MatPartitioningRegisterDynamic().
210: .keywords: matrix, get, partitioning
212: .seealso: MatPartitioningRegisterDynamic(), MatPartitioningCreate(),
213: MatPartitioningDestroy(), MatPartitioningSetAdjacency(), ISPartitioningToNumbering(),
214: ISPartitioningCount()
215: @*/
216: PetscErrorCode MatPartitioningApply(MatPartitioning matp,IS *partitioning)
217: {
219: PetscBool flag = PETSC_FALSE;
224: if (!matp->adj->assembled) SETERRQ(((PetscObject)matp)->comm,PETSC_ERR_ARG_WRONGSTATE,"Not for unassembled matrix");
225: if (matp->adj->factortype) SETERRQ(((PetscObject)matp)->comm,PETSC_ERR_ARG_WRONGSTATE,"Not for factored matrix");
226: if (!matp->ops->apply) SETERRQ(((PetscObject)matp)->comm,PETSC_ERR_ARG_WRONGSTATE,"Must set type with MatPartitioningSetFromOptions() or MatPartitioningSetType()");
227: PetscLogEventBegin(MAT_Partitioning,matp,0,0,0);
228: (*matp->ops->apply)(matp,partitioning);
229: PetscLogEventEnd(MAT_Partitioning,matp,0,0,0);
231: PetscOptionsGetBool(PETSC_NULL,"-mat_partitioning_view",&flag,PETSC_NULL);
232: if (flag) {
233: PetscViewer viewer;
234: PetscViewerASCIIGetStdout(((PetscObject)matp)->comm,&viewer);
235: MatPartitioningView(matp,viewer);
236: ISView(*partitioning,viewer);
237: }
238: return(0);
239: }
240:
243: /*@
244: MatPartitioningSetAdjacency - Sets the adjacency graph (matrix) of the thing to be
245: partitioned.
247: Collective on MatPartitioning and Mat
249: Input Parameters:
250: + part - the partitioning context
251: - adj - the adjacency matrix
253: Level: beginner
255: .keywords: Partitioning, adjacency
257: .seealso: MatPartitioningCreate()
258: @*/
259: PetscErrorCode MatPartitioningSetAdjacency(MatPartitioning part,Mat adj)
260: {
264: part->adj = adj;
265: return(0);
266: }
270: /*@
271: MatPartitioningDestroy - Destroys the partitioning context.
273: Collective on Partitioning
275: Input Parameters:
276: . part - the partitioning context
278: Level: beginner
280: .keywords: Partitioning, destroy, context
282: .seealso: MatPartitioningCreate()
283: @*/
284: PetscErrorCode MatPartitioningDestroy(MatPartitioning *part)
285: {
289: if (!*part) return(0);
291: if (--((PetscObject)(*part))->refct > 0) {*part = 0; return(0);}
293: if ((*part)->ops->destroy) {
294: (*(*part)->ops->destroy)((*part));
295: }
296: PetscFree((*part)->vertex_weights);
297: PetscFree((*part)->part_weights);
298: PetscHeaderDestroy(part);
299: return(0);
300: }
304: /*@C
305: MatPartitioningSetVertexWeights - Sets the weights for vertices for a partitioning.
307: Logically Collective on Partitioning
309: Input Parameters:
310: + part - the partitioning context
311: - weights - the weights, on each process this array must have the same size as the number of local rows
313: Level: beginner
315: Notes:
316: The array weights is freed by PETSc so the user should not free the array. In C/C++
317: the array must be obtained with a call to PetscMalloc(), not malloc().
319: .keywords: Partitioning, destroy, context
321: .seealso: MatPartitioningCreate(), MatPartitioningSetType(), MatPartitioningSetPartitionWeights()
322: @*/
323: PetscErrorCode MatPartitioningSetVertexWeights(MatPartitioning part,const PetscInt weights[])
324: {
330: PetscFree(part->vertex_weights);
331: part->vertex_weights = (PetscInt*)weights;
332: return(0);
333: }
337: /*@C
338: MatPartitioningSetPartitionWeights - Sets the weights for each partition.
340: Logically Collective on Partitioning
342: Input Parameters:
343: + part - the partitioning context
344: - weights - An array of size nparts that is used to specify the fraction of
345: vertex weight that should be distributed to each sub-domain for
346: the balance constraint. If all of the sub-domains are to be of
347: the same size, then each of the nparts elements should be set
348: to a value of 1/nparts. Note that the sum of all of the weights
349: should be one.
351: Level: beginner
353: Notes:
354: The array weights is freed by PETSc so the user should not free the array. In C/C++
355: the array must be obtained with a call to PetscMalloc(), not malloc().
357: .keywords: Partitioning, destroy, context
359: .seealso: MatPartitioningCreate(), MatPartitioningSetType(), MatPartitioningSetVertexWeights()
360: @*/
361: PetscErrorCode MatPartitioningSetPartitionWeights(MatPartitioning part,const PetscReal weights[])
362: {
368: PetscFree(part->part_weights);
369: part->part_weights = (PetscReal*)weights;
370: return(0);
371: }
375: /*@
376: MatPartitioningCreate - Creates a partitioning context.
378: Collective on MPI_Comm
380: Input Parameter:
381: . comm - MPI communicator
383: Output Parameter:
384: . newp - location to put the context
386: Level: beginner
388: .keywords: Partitioning, create, context
390: .seealso: MatPartitioningSetType(), MatPartitioningApply(), MatPartitioningDestroy(),
391: MatPartitioningSetAdjacency()
393: @*/
394: PetscErrorCode MatPartitioningCreate(MPI_Comm comm,MatPartitioning *newp)
395: {
396: MatPartitioning part;
397: PetscErrorCode ierr;
398: PetscMPIInt size;
401: *newp = 0;
403: #ifndef PETSC_USE_DYNAMIC_LIBRARIES
404: MatInitializePackage(PETSC_NULL);
405: #endif
406: PetscHeaderCreate(part,_p_MatPartitioning,struct _MatPartitioningOps,MAT_PARTITIONING_CLASSID,-1,"MatPartitioning","Matrix/graph partitioning","MatOrderings",comm,MatPartitioningDestroy,
407: MatPartitioningView);
408: part->vertex_weights = PETSC_NULL;
409: part->part_weights = PETSC_NULL;
410: MPI_Comm_size(comm,&size);
411: part->n = (PetscInt)size;
413: *newp = part;
414: return(0);
415: }
419: /*@C
420: MatPartitioningView - Prints the partitioning data structure.
422: Collective on MatPartitioning
424: Input Parameters:
425: . part - the partitioning context
426: . viewer - optional visualization context
428: Level: intermediate
430: Note:
431: The available visualization contexts include
432: + PETSC_VIEWER_STDOUT_SELF - standard output (default)
433: - PETSC_VIEWER_STDOUT_WORLD - synchronized standard
434: output where only the first processor opens
435: the file. All other processors send their
436: data to the first processor to print.
438: The user can open alternative visualization contexts with
439: . PetscViewerASCIIOpen() - output to a specified file
441: .keywords: Partitioning, view
443: .seealso: PetscViewerASCIIOpen()
444: @*/
445: PetscErrorCode MatPartitioningView(MatPartitioning part,PetscViewer viewer)
446: {
447: PetscErrorCode ierr;
448: PetscBool iascii;
452: if (!viewer) {
453: PetscViewerASCIIGetStdout(((PetscObject)part)->comm,&viewer);
454: }
458: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&iascii);
459: if (iascii) {
460: PetscObjectPrintClassNamePrefixType((PetscObject)part,viewer,"MatPartitioning Object");
461: if (part->vertex_weights) {
462: PetscViewerASCIIPrintf(viewer," Using vertex weights\n");
463: }
464: } else {
465: SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_SUP,"Viewer type %s not supported for this MatParitioning",((PetscObject)viewer)->type_name);
466: }
468: if (part->ops->view) {
469: PetscViewerASCIIPushTab(viewer);
470: (*part->ops->view)(part,viewer);
471: PetscViewerASCIIPopTab(viewer);
472: }
474: return(0);
475: }
479: /*@C
480: MatPartitioningSetType - Sets the type of partitioner to use
482: Collective on MatPartitioning
484: Input Parameter:
485: . part - the partitioning context.
486: . type - a known method
488: Options Database Command:
489: $ -mat_partitioning_type <type>
490: $ Use -help for a list of available methods
491: $ (for instance, parmetis)
493: Level: intermediate
495: .keywords: partitioning, set, method, type
497: .seealso: MatPartitioningCreate(), MatPartitioningApply(), MatPartitioningType
499: @*/
500: PetscErrorCode MatPartitioningSetType(MatPartitioning part,const MatPartitioningType type)
501: {
502: PetscErrorCode ierr,(*r)(MatPartitioning);
503: PetscBool match;
509: PetscObjectTypeCompare((PetscObject)part,type,&match);
510: if (match) return(0);
512: if (part->setupcalled) {
513: (*part->ops->destroy)(part);
514: part->ops->destroy = PETSC_NULL;
515: part->data = 0;
516: part->setupcalled = 0;
517: }
519: PetscFListFind(MatPartitioningList,((PetscObject)part)->comm,type,PETSC_TRUE,(void (**)(void)) &r);
521: if (!r) SETERRQ1(((PetscObject)part)->comm,PETSC_ERR_ARG_UNKNOWN_TYPE,"Unknown partitioning type %s",type);
523: part->ops->destroy = (PetscErrorCode (*)(MatPartitioning)) 0;
524: part->ops->view = (PetscErrorCode (*)(MatPartitioning,PetscViewer)) 0;
525: (*r)(part);
527: PetscFree(((PetscObject)part)->type_name);
528: PetscStrallocpy(type,&((PetscObject)part)->type_name);
529: return(0);
530: }
534: /*@
535: MatPartitioningSetFromOptions - Sets various partitioning options from the
536: options database.
538: Collective on MatPartitioning
540: Input Parameter:
541: . part - the partitioning context.
543: Options Database Command:
544: $ -mat_partitioning_type <type>
545: $ Use -help for a list of available methods
546: $ (for instance, parmetis)
548: Level: beginner
550: .keywords: partitioning, set, method, type
551: @*/
552: PetscErrorCode MatPartitioningSetFromOptions(MatPartitioning part)
553: {
555: PetscBool flag;
556: char type[256];
557: const char *def;
560: PetscObjectOptionsBegin((PetscObject)part);
561: if (!((PetscObject)part)->type_name) {
562: #if defined(PETSC_HAVE_PARMETIS)
563: def = MATPARTITIONINGPARMETIS;
564: #else
565: def = MATPARTITIONINGCURRENT;
566: #endif
567: } else {
568: def = ((PetscObject)part)->type_name;
569: }
570: PetscOptionsList("-mat_partitioning_type","Type of partitioner","MatPartitioningSetType",MatPartitioningList,def,type,256,&flag);
571: if (flag) {
572: MatPartitioningSetType(part,type);
573: }
574: /*
575: Set the type if it was never set.
576: */
577: if (!((PetscObject)part)->type_name) {
578: MatPartitioningSetType(part,def);
579: }
581: if (part->ops->setfromoptions) {
582: (*part->ops->setfromoptions)(part);
583: }
584: PetscOptionsEnd();
585: return(0);
586: }