Actual source code: partchaco.c

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

      3: PetscBool  ChacoPartitionerCite = PETSC_FALSE;
      4: const char ChacoPartitionerCitation[] =
      5:   "@inproceedings{Chaco95,\n"
      6:   "  author    = {Bruce Hendrickson and Robert Leland},\n"
      7:   "  title     = {A multilevel algorithm for partitioning graphs},\n"
      8:   "  booktitle = {Supercomputing '95: Proceedings of the 1995 ACM/IEEE Conference on Supercomputing (CDROM)},"
      9:   "  isbn      = {0-89791-816-9},\n"
     10:   "  pages     = {28},\n"
     11:   "  doi       = {https://doi.acm.org/10.1145/224170.224228},\n"
     12:   "  publisher = {ACM Press},\n"
     13:   "  address   = {New York},\n"
     14:   "  year      = {1995}\n"
     15:   "}\n";

     17: typedef struct {
     18:   PetscInt dummy;
     19: } PetscPartitioner_Chaco;

     21: static PetscErrorCode PetscPartitionerDestroy_Chaco(PetscPartitioner part)
     22: {
     23:   PetscPartitioner_Chaco *p = (PetscPartitioner_Chaco *) part->data;
     24:   PetscErrorCode          ierr;

     27:   PetscFree(p);
     28:   return(0);
     29: }

     31: static PetscErrorCode PetscPartitionerView_Chaco_ASCII(PetscPartitioner part, PetscViewer viewer)
     32: {
     34:   return(0);
     35: }

     37: static PetscErrorCode PetscPartitionerView_Chaco(PetscPartitioner part, PetscViewer viewer)
     38: {
     39:   PetscBool      iascii;

     45:   PetscObjectTypeCompare((PetscObject) viewer, PETSCVIEWERASCII, &iascii);
     46:   if (iascii) {PetscPartitionerView_Chaco_ASCII(part, viewer);}
     47:   return(0);
     48: }

     50: #if defined(PETSC_HAVE_CHACO)
     51: #if defined(PETSC_HAVE_UNISTD_H)
     52: #include <unistd.h>
     53: #endif
     54: #if defined(PETSC_HAVE_CHACO_INT_ASSIGNMENT)
     55: #include <chaco.h>
     56: #else
     57: /* Older versions of Chaco do not have an include file */
     58: PETSC_EXTERN int interface(int nvtxs, int *start, int *adjacency, int *vwgts,
     59:                        float *ewgts, float *x, float *y, float *z, char *outassignname,
     60:                        char *outfilename, short *assignment, int architecture, int ndims_tot,
     61:                        int mesh_dims[3], double *goal, int global_method, int local_method,
     62:                        int rqi_flag, int vmax, int ndims, double eigtol, long seed);
     63: #endif
     64: extern int FREE_GRAPH;
     65: #endif

     67: static PetscErrorCode PetscPartitionerPartition_Chaco(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertSection, PetscSection targetSection, PetscSection partSection, IS *partition)
     68: {
     69: #if defined(PETSC_HAVE_CHACO)
     70:   enum {DEFAULT_METHOD = 1, INERTIAL_METHOD = 3};
     71:   MPI_Comm       comm;
     72:   int            nvtxs          = numVertices; /* number of vertices in full graph */
     73:   int           *vwgts          = NULL;   /* weights for all vertices */
     74:   float         *ewgts          = NULL;   /* weights for all edges */
     75:   float         *x              = NULL, *y = NULL, *z = NULL; /* coordinates for inertial method */
     76:   char          *outassignname  = NULL;   /*  name of assignment output file */
     77:   char          *outfilename    = NULL;   /* output file name */
     78:   int            architecture   = 1;      /* 0 => hypercube, d => d-dimensional mesh */
     79:   int            ndims_tot      = 0;      /* total number of cube dimensions to divide */
     80:   int            mesh_dims[3];            /* dimensions of mesh of processors */
     81:   double        *goal          = NULL;    /* desired set sizes for each set */
     82:   int            global_method = 1;       /* global partitioning algorithm */
     83:   int            local_method  = 1;       /* local partitioning algorithm */
     84:   int            rqi_flag      = 0;       /* should I use RQI/Symmlq eigensolver? */
     85:   int            vmax          = 200;     /* how many vertices to coarsen down to? */
     86:   int            ndims         = 1;       /* number of eigenvectors (2^d sets) */
     87:   double         eigtol        = 0.001;   /* tolerance on eigenvectors */
     88:   long           seed          = 123636512; /* for random graph mutations */
     89: #if defined(PETSC_HAVE_CHACO_INT_ASSIGNMENT)
     90:   int           *assignment;              /* Output partition */
     91: #else
     92:   short int     *assignment;              /* Output partition */
     93: #endif
     94:   int            fd_stdout, fd_pipe[2];
     95:   PetscInt      *points;
     96:   int            i, v, p;

    100:   PetscObjectGetComm((PetscObject)part,&comm);
    101:   if (PetscDefined (USE_DEBUG)) {
    102:     int ival,isum;
    103:     PetscBool distributed;

    105:     ival = (numVertices > 0);
    106:     MPI_Allreduce(&ival, &isum, 1, MPI_INT, MPI_SUM, comm);
    107:     distributed = (isum > 1) ? PETSC_TRUE : PETSC_FALSE;
    108:     if (distributed) SETERRQ(comm, PETSC_ERR_SUP, "Chaco cannot partition a distributed graph");
    109:   }
    110:   if (!numVertices) { /* distributed case, return if not holding the graph */
    111:     ISCreateGeneral(comm, 0, NULL, PETSC_OWN_POINTER, partition);
    112:     return(0);
    113:   }
    114:   FREE_GRAPH = 0; /* Do not let Chaco free my memory */
    115:   for (i = 0; i < start[numVertices]; ++i) ++adjacency[i];

    117:   if (global_method == INERTIAL_METHOD) {
    118:     /* manager.createCellCoordinates(nvtxs, &x, &y, &z); */
    119:     SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "Inertial partitioning not yet supported");
    120:   }
    121:   mesh_dims[0] = nparts;
    122:   mesh_dims[1] = 1;
    123:   mesh_dims[2] = 1;
    124:   PetscMalloc1(nvtxs, &assignment);
    125:   /* Chaco outputs to stdout. We redirect this to a buffer. */
    126:   /* TODO: check error codes for UNIX calls */
    127: #if defined(PETSC_HAVE_UNISTD_H)
    128:   {
    129:     int piperet;
    130:     piperet = pipe(fd_pipe);
    131:     if (piperet) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_SYS,"Could not create pipe");
    132:     fd_stdout = dup(1);
    133:     close(1);
    134:     dup2(fd_pipe[1], 1);
    135:   }
    136: #endif
    137:   if (part->usevwgt) { PetscInfo(part,"PETSCPARTITIONERCHACO ignores vertex weights\n"); }
    138:   interface(nvtxs, (int*) start, (int*) adjacency, vwgts, ewgts, x, y, z, outassignname, outfilename,
    139:                    assignment, architecture, ndims_tot, mesh_dims, goal, global_method, local_method, rqi_flag,
    140:                    vmax, ndims, eigtol, seed);
    141: #if defined(PETSC_HAVE_UNISTD_H)
    142:   {
    143:     char msgLog[10000];
    144:     int  count;

    146:     fflush(stdout);
    147:     count = read(fd_pipe[0], msgLog, (10000-1)*sizeof(char));
    148:     if (count < 0) count = 0;
    149:     msgLog[count] = 0;
    150:     close(1);
    151:     dup2(fd_stdout, 1);
    152:     close(fd_stdout);
    153:     close(fd_pipe[0]);
    154:     close(fd_pipe[1]);
    155:     if (ierr) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_LIB, "Error in Chaco library: %s", msgLog);
    156:   }
    157: #else
    158:   if (ierr) SETERRQ1(PETSC_COMM_SELF, PETSC_ERR_LIB, "Error in Chaco library: %s", "error in stdout");
    159: #endif
    160:   /* Convert to PetscSection+IS */
    161:   for (v = 0; v < nvtxs; ++v) {
    162:     PetscSectionAddDof(partSection, assignment[v], 1);
    163:   }
    164:   PetscMalloc1(nvtxs, &points);
    165:   for (p = 0, i = 0; p < nparts; ++p) {
    166:     for (v = 0; v < nvtxs; ++v) {
    167:       if (assignment[v] == p) points[i++] = v;
    168:     }
    169:   }
    170:   if (i != nvtxs) SETERRQ2(PETSC_COMM_SELF, PETSC_ERR_PLIB, "Number of points %D should be %D", i, nvtxs);
    171:   ISCreateGeneral(comm, nvtxs, points, PETSC_OWN_POINTER, partition);
    172:   if (global_method == INERTIAL_METHOD) {
    173:     /* manager.destroyCellCoordinates(nvtxs, &x, &y, &z); */
    174:   }
    175:   PetscFree(assignment);
    176:   for (i = 0; i < start[numVertices]; ++i) --adjacency[i];
    177:   return(0);
    178: #else
    179:   SETERRQ(PetscObjectComm((PetscObject) part), PETSC_ERR_SUP, "Mesh partitioning needs external package support.\nPlease reconfigure with --download-chaco.");
    180: #endif
    181: }

    183: static PetscErrorCode PetscPartitionerInitialize_Chaco(PetscPartitioner part)
    184: {
    186:   part->noGraph        = PETSC_FALSE;
    187:   part->ops->view      = PetscPartitionerView_Chaco;
    188:   part->ops->destroy   = PetscPartitionerDestroy_Chaco;
    189:   part->ops->partition = PetscPartitionerPartition_Chaco;
    190:   return(0);
    191: }

    193: /*MC
    194:   PETSCPARTITIONERCHACO = "chaco" - A PetscPartitioner object using the Chaco library

    196:   Level: intermediate

    198: .seealso: PetscPartitionerType, PetscPartitionerCreate(), PetscPartitionerSetType()
    199: M*/

    201: PETSC_EXTERN PetscErrorCode PetscPartitionerCreate_Chaco(PetscPartitioner part)
    202: {
    203:   PetscPartitioner_Chaco *p;
    204:   PetscErrorCode          ierr;

    208:   PetscNewLog(part, &p);
    209:   part->data = p;

    211:   PetscPartitionerInitialize_Chaco(part);
    212:   PetscCitationsRegister(ChacoPartitionerCitation, &ChacoPartitionerCite);
    213:   return(0);
    214: }