Actual source code: partitioner.c

      1: #include <petsc/private/partitionerimpl.h>

      3: /*@C
      4:   PetscPartitionerSetType - Builds a particular PetscPartitioner

      6:   Collective on PetscPartitioner

      8:   Input Parameters:
      9: + part - The PetscPartitioner object
     10: - name - The kind of partitioner

     12:   Options Database Key:
     13: . -petscpartitioner_type <type> - Sets the PetscPartitioner type; use -help for a list of available types

     15:   Level: intermediate

     17: .seealso: PetscPartitionerGetType(), PetscPartitionerCreate()
     18: @*/
     19: PetscErrorCode PetscPartitionerSetType(PetscPartitioner part, PetscPartitionerType name)
     20: {
     21:   PetscErrorCode (*r)(PetscPartitioner);
     22:   PetscBool      match;

     27:   PetscObjectTypeCompare((PetscObject) part, name, &match);
     28:   if (match) return(0);

     30:   PetscPartitionerRegisterAll();
     31:   PetscFunctionListFind(PetscPartitionerList, name, &r);
     32:   if (!r) SETERRQ1(PetscObjectComm((PetscObject) part), PETSC_ERR_ARG_UNKNOWN_TYPE, "Unknown PetscPartitioner type: %s", name);

     34:   if (part->ops->destroy) {
     35:     (*part->ops->destroy)(part);
     36:   }
     37:   part->noGraph = PETSC_FALSE;
     38:   PetscMemzero(part->ops, sizeof(*part->ops));
     39:   PetscObjectChangeTypeName((PetscObject) part, name);
     40:   (*r)(part);
     41:   return(0);
     42: }

     44: /*@C
     45:   PetscPartitionerGetType - Gets the PetscPartitioner type name (as a string) from the object.

     47:   Not Collective

     49:   Input Parameter:
     50: . part - The PetscPartitioner

     52:   Output Parameter:
     53: . name - The PetscPartitioner type name

     55:   Level: intermediate

     57: .seealso: PetscPartitionerSetType(), PetscPartitionerCreate()
     58: @*/
     59: PetscErrorCode PetscPartitionerGetType(PetscPartitioner part, PetscPartitionerType *name)
     60: {
     64:   *name = ((PetscObject) part)->type_name;
     65:   return(0);
     66: }

     68: /*@C
     69:    PetscPartitionerViewFromOptions - View from Options

     71:    Collective on PetscPartitioner

     73:    Input Parameters:
     74: +  A - the PetscPartitioner object
     75: .  obj - Optional object
     76: -  name - command line option

     78:    Level: intermediate
     79: .seealso:  PetscPartitionerView(), PetscObjectViewFromOptions()
     80: @*/
     81: PetscErrorCode PetscPartitionerViewFromOptions(PetscPartitioner A,PetscObject obj,const char name[])
     82: {

     87:   PetscObjectViewFromOptions((PetscObject)A,obj,name);
     88:   return(0);
     89: }

     91: /*@
     92:   PetscPartitionerView - Views a PetscPartitioner

     94:   Collective on PetscPartitioner

     96:   Input Parameter:
     97: + part - the PetscPartitioner object to view
     98: - v    - the viewer

    100:   Level: developer

    102: .seealso: PetscPartitionerDestroy()
    103: @*/
    104: PetscErrorCode PetscPartitionerView(PetscPartitioner part, PetscViewer v)
    105: {
    106:   PetscMPIInt    size;
    107:   PetscBool      isascii;

    112:   if (!v) {PetscViewerASCIIGetStdout(PetscObjectComm((PetscObject) part), &v);}
    113:   PetscObjectTypeCompare((PetscObject) v, PETSCVIEWERASCII, &isascii);
    114:   if (isascii) {
    115:     MPI_Comm_size(PetscObjectComm((PetscObject) part), &size);
    116:     PetscViewerASCIIPrintf(v, "Graph Partitioner: %d MPI Process%s\n", size, size > 1 ? "es" : "");
    117:     PetscViewerASCIIPrintf(v, "  type: %s\n", ((PetscObject)part)->type_name);
    118:     PetscViewerASCIIPrintf(v, "  edge cut: %D\n", part->edgeCut);
    119:     PetscViewerASCIIPrintf(v, "  balance: %.2g\n", part->balance);
    120:     PetscViewerASCIIPrintf(v, "  use vertex weights: %d\n", part->usevwgt);
    121:   }
    122:   if (part->ops->view) {(*part->ops->view)(part, v);}
    123:   return(0);
    124: }

    126: static PetscErrorCode PetscPartitionerGetDefaultType(MPI_Comm comm, const char **defaultType)
    127: {
    128:   PetscMPIInt    size;

    132:   MPI_Comm_size(comm, &size);
    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:   return(0);
    147: }

    149: /*@
    150:   PetscPartitionerSetFromOptions - sets parameters in a PetscPartitioner from the options database

    152:   Collective on PetscPartitioner

    154:   Input Parameter:
    155: . part - the PetscPartitioner object to set options for

    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()

    162:   Level: developer

    164: .seealso: PetscPartitionerView(), PetscPartitionerSetType(), PetscPartitionerPartition()
    165: @*/
    166: PetscErrorCode PetscPartitionerSetFromOptions(PetscPartitioner part)
    167: {
    168:   const char    *currentType = NULL;
    169:   char           name[256];
    170:   PetscBool      flg;

    175:   PetscObjectOptionsBegin((PetscObject) part);
    176:   PetscPartitionerGetType(part, &currentType);
    177:   PetscOptionsFList("-petscpartitioner_type", "Graph partitioner", "PetscPartitionerSetType", PetscPartitionerList, currentType, name, sizeof(name), &flg);
    178:   if (flg) {
    179:     PetscPartitionerSetType(part, name);
    180:   }
    181:   PetscOptionsBool("-petscpartitioner_use_vertex_weights","Use vertex weights","",part->usevwgt,&part->usevwgt,NULL);
    182:   if (part->ops->setfromoptions) {
    183:     (*part->ops->setfromoptions)(PetscOptionsObject,part);
    184:   }
    185:   PetscViewerDestroy(&part->viewer);
    186:   PetscViewerDestroy(&part->viewerGraph);
    187:   PetscOptionsGetViewer(((PetscObject) part)->comm, ((PetscObject) part)->options, ((PetscObject) part)->prefix, "-petscpartitioner_view", &part->viewer, NULL, NULL);
    188:   PetscOptionsGetViewer(((PetscObject) part)->comm, ((PetscObject) part)->options, ((PetscObject) part)->prefix, "-petscpartitioner_view_graph", &part->viewerGraph, NULL, &part->viewGraph);
    189:   /* process any options handlers added with PetscObjectAddOptionsHandler() */
    190:   PetscObjectProcessOptionsHandlers(PetscOptionsObject,(PetscObject) part);
    191:   PetscOptionsEnd();
    192:   return(0);
    193: }

    195: /*@
    196:   PetscPartitionerSetUp - Construct data structures for the PetscPartitioner

    198:   Collective on PetscPartitioner

    200:   Input Parameter:
    201: . part - the PetscPartitioner object to setup

    203:   Level: developer

    205: .seealso: PetscPartitionerView(), PetscPartitionerDestroy()
    206: @*/
    207: PetscErrorCode PetscPartitionerSetUp(PetscPartitioner part)
    208: {

    213:   if (part->ops->setup) {(*part->ops->setup)(part);}
    214:   return(0);
    215: }

    217: /*@
    218:   PetscPartitionerReset - Resets data structures for the PetscPartitioner

    220:   Collective on PetscPartitioner

    222:   Input Parameter:
    223: . part - the PetscPartitioner object to reset

    225:   Level: developer

    227: .seealso: PetscPartitionerSetUp(), PetscPartitionerDestroy()
    228: @*/
    229: PetscErrorCode PetscPartitionerReset(PetscPartitioner part)
    230: {

    235:   if (part->ops->reset) {(*part->ops->reset)(part);}
    236:   return(0);
    237: }

    239: /*@
    240:   PetscPartitionerDestroy - Destroys a PetscPartitioner object

    242:   Collective on PetscPartitioner

    244:   Input Parameter:
    245: . part - the PetscPartitioner object to destroy

    247:   Level: developer

    249: .seealso: PetscPartitionerView()
    250: @*/
    251: PetscErrorCode PetscPartitionerDestroy(PetscPartitioner *part)
    252: {

    256:   if (!*part) return(0);

    259:   if (--((PetscObject)(*part))->refct > 0) {*part = NULL; return(0);}
    260:   ((PetscObject) (*part))->refct = 0;

    262:   PetscPartitionerReset(*part);

    264:   PetscViewerDestroy(&(*part)->viewer);
    265:   PetscViewerDestroy(&(*part)->viewerGraph);
    266:   if ((*part)->ops->destroy) {(*(*part)->ops->destroy)(*part);}
    267:   PetscHeaderDestroy(part);
    268:   return(0);
    269: }

    271: /*@
    272:   PetscPartitionerPartition - Partition a graph

    274:   Collective on PetscPartitioner

    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)

    285:   Output Parameters:
    286: + partSection     - The PetscSection giving the division of points by partition
    287: - partition       - The list of points by partition

    289:   Options Database:
    290: + -petscpartitioner_view - View the partitioner information
    291: - -petscpartitioner_view_graph - View the graph we are partitioning

    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.

    297:   Level: developer

    299: .seealso PetscPartitionerCreate(), PetscSectionCreate(), PetscSectionSetChart(), PetscSectionSetDof()
    300: @*/
    301: PetscErrorCode PetscPartitionerPartition(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertexSection, PetscSection targetSection, PetscSection partSection, IS *partition)
    302: {

    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) {
    314:   }
    315:   if (vertexSection) {
    316:     PetscInt s,e;

    319:     PetscSectionGetChart(vertexSection, &s, &e);
    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;

    326:     PetscSectionGetChart(targetSection, &s, &e);
    327:     if (s > 0 || e < nparts) SETERRQ2(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"Invalid targetSection chart [%D,%D)",s,e);
    328:   }

    332:   PetscSectionReset(partSection);
    333:   PetscSectionSetChart(partSection, 0, nparts);
    334:   if (nparts == 1) { /* quick */
    335:     PetscSectionSetDof(partSection, 0, numVertices);
    336:     ISCreateStride(PetscObjectComm((PetscObject)part),numVertices,0,1,partition);
    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:     (*part->ops->partition)(part, nparts, numVertices, start, adjacency, vertexSection, targetSection, partSection, partition);
    340:   }
    341:   PetscSectionSetUp(partSection);
    342:   if (part->viewerGraph) {
    343:     PetscViewer viewer = part->viewerGraph;
    344:     PetscBool   isascii;
    345:     PetscInt    v, i;
    346:     PetscMPIInt rank;

    348:     MPI_Comm_rank(PetscObjectComm((PetscObject) viewer), &rank);
    349:     PetscObjectTypeCompare((PetscObject) viewer, PETSCVIEWERASCII, &isascii);
    350:     if (isascii) {
    351:       PetscViewerASCIIPushSynchronized(viewer);
    352:       PetscViewerASCIISynchronizedPrintf(viewer, "[%d]Nv: %D\n", rank, numVertices);
    353:       for (v = 0; v < numVertices; ++v) {
    354:         const PetscInt s = start[v];
    355:         const PetscInt e = start[v+1];

    357:         PetscViewerASCIISynchronizedPrintf(viewer, "[%d]  ", rank);
    358:         for (i = s; i < e; ++i) {PetscViewerASCIISynchronizedPrintf(viewer, "%D ", adjacency[i]);}
    359:         PetscViewerASCIISynchronizedPrintf(viewer, "[%D-%D)\n", s, e);
    360:       }
    361:       PetscViewerFlush(viewer);
    362:       PetscViewerASCIIPopSynchronized(viewer);
    363:     }
    364:   }
    365:   if (part->viewer) {
    366:     PetscPartitionerView(part,part->viewer);
    367:   }
    368:   return(0);
    369: }

    371: /*@
    372:   PetscPartitionerCreate - Creates an empty PetscPartitioner object. The type can then be set with PetscPartitionerSetType().

    374:   Collective

    376:   Input Parameter:
    377: . comm - The communicator for the PetscPartitioner object

    379:   Output Parameter:
    380: . part - The PetscPartitioner object

    382:   Level: beginner

    384: .seealso: PetscPartitionerSetType(), PETSCPARTITIONERCHACO, PETSCPARTITIONERPARMETIS, PETSCPARTITIONERSHELL, PETSCPARTITIONERSIMPLE, PETSCPARTITIONERGATHER
    385: @*/
    386: PetscErrorCode PetscPartitionerCreate(MPI_Comm comm, PetscPartitioner *part)
    387: {
    388:   PetscPartitioner p;
    389:   const char       *partitionerType = NULL;
    390:   PetscErrorCode   ierr;

    394:   *part = NULL;
    395:   PetscPartitionerInitializePackage();

    397:   PetscHeaderCreate(p, PETSCPARTITIONER_CLASSID, "PetscPartitioner", "Graph Partitioner", "PetscPartitioner", comm, PetscPartitionerDestroy, PetscPartitionerView);
    398:   PetscPartitionerGetDefaultType(comm, &partitionerType);
    399:   PetscPartitionerSetType(p, partitionerType);

    401:   p->edgeCut = 0;
    402:   p->balance = 0.0;
    403:   p->usevwgt = PETSC_TRUE;

    405:   *part = p;
    406:   return(0);
    407: }