Actual source code: partition.c

  1: /*$Id: partition.c,v 1.60 2001/06/21 21:17:23 bsmith Exp $*/
  2: 
 3:  #include src/mat/matimpl.h

  5: /* Logging support */
  6: int MAT_PARTITIONING_COOKIE;

  8: /*
  9:    Simplest partitioning, keeps the current partitioning.
 10: */
 11: #undef __FUNCT__  
 13: static int MatPartitioningApply_Current(MatPartitioning part,IS *partitioning)
 14: {
 15:   int   ierr,m,rank,size;

 18:   MPI_Comm_size(part->comm,&size);
 19:   if (part->n != size) {
 20:     SETERRQ(PETSC_ERR_SUP,"Currently only supports one domain per processor");
 21:   }
 22:   MPI_Comm_rank(part->comm,&rank);

 24:   MatGetLocalSize(part->adj,&m,PETSC_NULL);
 25:   ISCreateStride(part->comm,m,rank,0,partitioning);
 26:   return(0);
 27: }

 29: #undef __FUNCT__  
 31: static int MatPartitioningApply_Square(MatPartitioning part,IS *partitioning)
 32: {
 33:   int   cell,ierr,n,N,p,rstart,rend,*color,size;

 36:   MPI_Comm_size(part->comm,&size);
 37:   if (part->n != size) {
 38:     SETERRQ(PETSC_ERR_SUP,"Currently only supports one domain per processor");
 39:   }
 40:   p = (int)sqrt((double)part->n);
 41:   if (p*p != part->n) {
 42:     SETERRQ(PETSC_ERR_SUP,"Square partitioning requires "perfect square" number of domains");
 43:   }
 44:   MatGetSize(part->adj,&N,PETSC_NULL);
 45:   n = (int)sqrt((double)N);
 46:   if (n*n != N) {  /* This condition is NECESSARY, but NOT SUFFICIENT in order to the domain be square */
 47:     SETERRQ(PETSC_ERR_SUP,"Square partitioning requires square domain");
 48:   }
 49:   if (n%p != 0) {
 50:     SETERRQ(PETSC_ERR_SUP,"Square partitioning requires p to divide n");
 51:   }
 52:   MatGetOwnershipRange(part->adj,&rstart,&rend);
 53:   PetscMalloc((rend-rstart)*sizeof(int),&color);
 54:   /* for (int cell=rstart; cell<rend; cell++) { color[cell-rstart] = ((cell%n) < (n/2)) + 2 * ((cell/n) < (n/2)); } */
 55:   for (cell=rstart; cell<rend; cell++) {
 56:     color[cell-rstart] = ((cell%n) / (n/p)) + p * ((cell/n) / (n/p));
 57:   }
 58:   ISCreateGeneral(part->comm,rend-rstart,color,partitioning);
 59:   PetscFree(color);

 61:   return(0);
 62: }

 64: EXTERN_C_BEGIN
 65: #undef __FUNCT__  
 67: int MatPartitioningCreate_Current(MatPartitioning part)
 68: {
 70:   part->ops->apply   = MatPartitioningApply_Current;
 71:   part->ops->view    = 0;
 72:   part->ops->destroy = 0;
 73:   return(0);
 74: }
 75: EXTERN_C_END

 77: EXTERN_C_BEGIN
 78: #undef __FUNCT__  
 80: int MatPartitioningCreate_Square(MatPartitioning part)
 81: {
 83:   part->ops->apply   = MatPartitioningApply_Square;
 84:   part->ops->view    = 0;
 85:   part->ops->destroy = 0;
 86:   return(0);
 87: }
 88: EXTERN_C_END

 90: /* ===========================================================================================*/

 92:  #include petscsys.h

 94: PetscFList      MatPartitioningList = 0;
 95: PetscTruth MatPartitioningRegisterAllCalled = PETSC_FALSE;

 97: /*MC
 98:    MatPartitioningRegisterDynamic - Adds a new sparse matrix partitioning to the 
 99:    matrix package. 

101:    Synopsis:
102:    int MatPartitioningRegisterDynamic(char *name_partitioning,char *path,char *name_create,int (*routine_create)(MatPartitioning))

104:    Not Collective

106:    Input Parameters:
107: +  sname - name of partitioning (for example MAT_PARTITIONING_CURRENT) or parmetis
108: .  path - location of library where creation routine is 
109: .  name - name of function that creates the partitioning type, a string
110: -  function - function pointer that creates the partitioning type

112:    Level: developer

114:    If dynamic libraries are used, then the fourth input argument (function)
115:    is ignored.

117:    Sample usage:
118: .vb
119:    MatPartitioningRegisterDynamic("my_part",/home/username/my_lib/lib/libO/solaris/mylib.a,
120:                "MyPartCreate",MyPartCreate);
121: .ve

123:    Then, your partitioner can be chosen with the procedural interface via
124: $     MatPartitioningSetType(part,"my_part")
125:    or at runtime via the option
126: $     -mat_partitioning_type my_part

128:    $PETSC_ARCH and $BOPT occuring in pathname will be replaced with appropriate values.

130: .keywords: matrix, partitioning, register

132: .seealso: MatPartitioningRegisterDestroy(), MatPartitioningRegisterAll()
133: M*/

135: #undef __FUNCT__  
137: int MatPartitioningRegister(char *sname,char *path,char *name,int (*function)(MatPartitioning))
138: {
139:   int  ierr;
140:   char fullname[256];

143:   PetscFListConcat(path,name,fullname);
144:   PetscFListAdd(&MatPartitioningList,sname,fullname,(void (*)(void))function);
145:   return(0);
146: }

148: #undef __FUNCT__  
150: /*@C
151:    MatPartitioningRegisterDestroy - Frees the list of partitioning routines.

153:   Not Collective

155:   Level: developer

157: .keywords: matrix, register, destroy

159: .seealso: MatPartitioningRegisterDynamic(), MatPartitioningRegisterAll()
160: @*/
161: int MatPartitioningRegisterDestroy(void)
162: {

166:   if (MatPartitioningList) {
167:     PetscFListDestroy(&MatPartitioningList);
168:     MatPartitioningList = 0;
169:   }
170:   return(0);
171: }

173: #undef __FUNCT__  
175: /*@C
176:    MatPartitioningGetType - Gets the Partitioning method type and name (as a string) 
177:         from the partitioning context.

179:    Not collective

181:    Input Parameter:
182: .  partitioning - the partitioning context

184:    Output Parameter:
185: .  type - partitioner type

187:    Level: intermediate

189:    Not Collective

191: .keywords: Partitioning, get, method, name, type
192: @*/
193: int MatPartitioningGetType(MatPartitioning partitioning,MatPartitioningType *type)
194: {
196:   *type = partitioning->type_name;
197:   return(0);
198: }

200: #undef __FUNCT__  
202: /*@C
203:    MatPartitioningApply - Gets a partitioning for a matrix.

205:    Collective on Mat

207:    Input Parameters:
208: .  matp - the matrix partitioning object

210:    Output Parameters:
211: .   partitioning - the partitioning. For each local node this tells the processor
212:                    number that that node is assigned to.

214:    Options Database Keys:
215:    To specify the partitioning through the options database, use one of
216:    the following 
217: $    -mat_partitioning_type parmetis, -mat_partitioning current
218:    To see the partitioning result
219: $    -mat_partitioning_view

221:    Level: beginner

223:    The user can define additional partitionings; see MatPartitioningRegisterDynamic().

225: .keywords: matrix, get, partitioning

227: .seealso:  MatPartitioningGetTypeFromOptions(), MatPartitioningRegisterDynamic(), MatPartitioningCreate(),
228:            MatPartitioningDestroy(), MatPartitiongSetAdjacency(), ISPartitioningToNumbering(),
229:            ISPartitioningCount()
230: @*/
231: int MatPartitioningApply(MatPartitioning matp,IS *partitioning)
232: {
233:   int        ierr;
234:   PetscTruth flag;

238:   if (!matp->adj->assembled) SETERRQ(PETSC_ERR_ARG_WRONGSTATE,"Not for unassembled matrix");
239:   if (matp->adj->factor) SETERRQ(PETSC_ERR_ARG_WRONGSTATE,"Not for factored matrix");
240:   if (!matp->ops->apply) SETERRQ(PETSC_ERR_ARG_WRONGSTATE,"Must set type with MatPartitioningSetFromOptions() or MatPartitioningSetType()");
241:   PetscLogEventBegin(MAT_Partitioning,matp,0,0,0);
242:   (*matp->ops->apply)(matp,partitioning);
243:   PetscLogEventEnd(MAT_Partitioning,matp,0,0,0);

245:   PetscOptionsHasName(PETSC_NULL,"-mat_partitioning_view",&flag);
246:   if (flag) {
247:     MatPartitioningView(matp,PETSC_VIEWER_STDOUT_(matp->comm));
248:     ISView(*partitioning,PETSC_VIEWER_STDOUT_(matp->comm));
249:   }
250:   return(0);
251: }
252: 
253: #undef __FUNCT__  
255: /*@C
256:    MatPartitioningSetAdjacency - Sets the adjacency graph (matrix) of the thing to be
257:       partitioned.

259:    Collective on MatPartitioning and Mat

261:    Input Parameters:
262: +  part - the partitioning context
263: -  adj - the adjacency matrix

265:    Level: beginner

267: .keywords: Partitioning, adjacency

269: .seealso: MatPartitioningCreate()
270: @*/
271: int MatPartitioningSetAdjacency(MatPartitioning part,Mat adj)
272: {
276:   part->adj = adj;
277:   return(0);
278: }

280: #undef __FUNCT__  
282: /*@C
283:    MatPartitioningDestroy - Destroys the partitioning context.

285:    Collective on Partitioning

287:    Input Parameters:
288: .  part - the partitioning context

290:    Level: beginner

292: .keywords: Partitioning, destroy, context

294: .seealso: MatPartitioningCreate()
295: @*/
296: int MatPartitioningDestroy(MatPartitioning part)
297: {

302:   if (--part->refct > 0) return(0);

304:   if (part->ops->destroy) {
305:     (*part->ops->destroy)(part);
306:   }
307:   if (part->vertex_weights){
308:     PetscFree(part->vertex_weights);
309:   }
310:   PetscLogObjectDestroy(part);
311:   PetscHeaderDestroy(part);
312:   return(0);
313: }

315: #undef __FUNCT__  
317: /*@C
318:    MatPartitioningSetVertexWeights - Sets the weights for vertices for a partitioning.

320:    Collective on Partitioning

322:    Input Parameters:
323: +  part - the partitioning context
324: -  weights - the weights

326:    Level: beginner

328:    Notes:
329:       The array weights is freed by PETSc so the user should not free the array. In C/C++
330:    the array must be obtained with a call to PetscMalloc(), not malloc().

332: .keywords: Partitioning, destroy, context

334: .seealso: MatPartitioningCreate(), MatPartitioningSetType(), MatPartitioningSetAdjacency()
335: @*/
336: int MatPartitioningSetVertexWeights(MatPartitioning part,int *weights)
337: {


343:   if (part->vertex_weights){
344:     PetscFree(part->vertex_weights);
345:   }
346:   part->vertex_weights = weights;
347:   return(0);
348: }

350: #undef __FUNCT__  
352: /*@C
353:    MatPartitioningCreate - Creates a partitioning context.

355:    Collective on MPI_Comm

357:    Input Parameter:
358: .   comm - MPI communicator 

360:    Output Parameter:
361: .  newp - location to put the context

363:    Level: beginner

365: .keywords: Partitioning, create, context

367: .seealso: MatPartitioningSetUp(), MatPartitioningApply(), MatPartitioningDestroy(),
368:           MatPartitioningSetAdjacency()

370: @*/
371: int MatPartitioningCreate(MPI_Comm comm,MatPartitioning *newp)
372: {
373:   MatPartitioning part;
374:   int             ierr;

377:   *newp          = 0;

379:   PetscHeaderCreate(part,_p_MatPartitioning,struct _MatPartitioningOps,MAT_PARTITIONING_COOKIE,-1,"MatPartitioning",comm,MatPartitioningDestroy,
380:                     MatPartitioningView);
381:   PetscLogObjectCreate(part);
382:   part->type           = -1;
383:   part->vertex_weights = 0;
384:   MPI_Comm_size(comm,&part->n);

386:   *newp = part;
387:   return(0);
388: }

390: #undef __FUNCT__  
392: /*@C 
393:    MatPartitioningView - Prints the partitioning data structure.

395:    Collective on MatPartitioning

397:    Input Parameters:
398: .  part - the partitioning context
399: .  viewer - optional visualization context

401:    Level: intermediate

403:    Note:
404:    The available visualization contexts include
405: +     PETSC_VIEWER_STDOUT_SELF - standard output (default)
406: -     PETSC_VIEWER_STDOUT_WORLD - synchronized standard
407:          output where only the first processor opens
408:          the file.  All other processors send their 
409:          data to the first processor to print. 

411:    The user can open alternative visualization contexts with
412: .     PetscViewerASCIIOpen() - output to a specified file

414: .keywords: Partitioning, view

416: .seealso: PetscViewerASCIIOpen()
417: @*/
418: int MatPartitioningView(MatPartitioning part,PetscViewer viewer)
419: {
420:   int                 ierr;
421:   PetscTruth          isascii;
422:   MatPartitioningType name;

426:   if (!viewer) viewer = PETSC_VIEWER_STDOUT_(part->comm);

430:   PetscTypeCompare((PetscObject)viewer,PETSC_VIEWER_ASCII,&isascii);
431:   if (isascii) {
432:     MatPartitioningGetType(part,&name);
433:     PetscViewerASCIIPrintf(viewer,"MatPartitioning Object: %sn",name);
434:     if (part->vertex_weights) {
435:       PetscViewerASCIIPrintf(viewer,"  Using vertex weightsn");
436:     }
437:   } else {
438:     SETERRQ1(1,"Viewer type %s not supported for this MatParitioning",((PetscObject)viewer)->type_name);
439:   }

441:   if (part->ops->view) {
442:     PetscViewerASCIIPushTab(viewer);
443:     (*part->ops->view)(part,viewer);
444:     PetscViewerASCIIPopTab(viewer);
445:   }

447:   return(0);
448: }

450: #undef __FUNCT__  
452: /*@C
453:    MatPartitioningSetType - Sets the type of partitioner to use

455:    Collective on MatPartitioning

457:    Input Parameter:
458: .  part - the partitioning context.
459: .  type - a known method

461:    Options Database Command:
462: $  -mat_partitioning_type  <type>
463: $      Use -help for a list of available methods
464: $      (for instance, parmetis)

466:    Level: intermediate

468: .keywords: partitioning, set, method, type

470: .seealso: MatPartitioningCreate(), MatPartitioningApply()

472: @*/
473: int MatPartitioningSetType(MatPartitioning part,MatPartitioningType type)
474: {
475:   int        ierr,(*r)(MatPartitioning);
476:   PetscTruth match;


482:   PetscTypeCompare((PetscObject)part,type,&match);
483:   if (match) return(0);

485:   if (part->setupcalled) {
486:      (*part->ops->destroy)(part);
487:     part->data        = 0;
488:     part->setupcalled = 0;
489:   }

491:   /* Get the function pointers for the method requested */
492:   if (!MatPartitioningRegisterAllCalled){ MatPartitioningRegisterAll(0);}
493:    PetscFListFind(part->comm,MatPartitioningList,type,(void (**)(void)) &r);

495:   if (!r) {SETERRQ1(PETSC_ERR_ARG_OUTOFRANGE,"Unknown partitioning type %s",type);}

497:   part->ops->destroy      = (int (*)(MatPartitioning)) 0;
498:   part->ops->view         = (int (*)(MatPartitioning,PetscViewer)) 0;
499:   (*r)(part);

501:   PetscStrfree(part->type_name);
502:   PetscStrallocpy(type,&part->type_name);
503:   return(0);
504: }

506: #undef __FUNCT__  
508: /*@
509:    MatPartitioningSetFromOptions - Sets various partitioning options from the 
510:         options database.

512:    Collective on MatPartitioning

514:    Input Parameter:
515: .  part - the partitioning context.

517:    Options Database Command:
518: $  -mat_partitioning_type  <type>
519: $      Use -help for a list of available methods
520: $      (for instance, parmetis)

522:    Level: beginner

524: .keywords: partitioning, set, method, type
525: @*/
526: int MatPartitioningSetFromOptions(MatPartitioning part)
527: {
528:   int        ierr;
529:   PetscTruth flag;
530:   char       type[256],*def;

533:   if (!MatPartitioningRegisterAllCalled){ MatPartitioningRegisterAll(0);}
534:   PetscOptionsBegin(part->comm,part->prefix,"Partitioning options","MatOrderings");
535:     if (!part->type_name) {
536: #if defined(PETSC_HAVE_PARMETIS)
537:       def = MAT_PARTITIONING_PARMETIS;
538: #else
539:       def = MAT_PARTITIONING_CURRENT;
540: #endif
541:     } else {
542:       def = part->type_name;
543:     }
544:     PetscOptionsList("-mat_partitioning_type","Type of partitioner","MatPartitioningSetType",MatPartitioningList,def,type,256,&flag);
545:     if (flag) {
546:       MatPartitioningSetType(part,type);
547:     }
548:     /*
549:       Set the type if it was never set.
550:     */
551:     if (!part->type_name) {
552:       MatPartitioningSetType(part,def);
553:     }

555:     if (part->ops->setfromoptions) {
556:       (*part->ops->setfromoptions)(part);
557:     }
558:   PetscOptionsEnd();
559:   return(0);
560: }