Actual source code: partchaco.c

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

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

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

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

 24:   PetscFree(p);
 25:   return 0;
 26: }

 28: static PetscErrorCode PetscPartitionerView_Chaco_ASCII(PetscPartitioner part, PetscViewer viewer)
 29: {
 30:   return 0;
 31: }

 33: static PetscErrorCode PetscPartitionerView_Chaco(PetscPartitioner part, PetscViewer viewer)
 34: {
 35:   PetscBool iascii;

 39:   PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &iascii);
 40:   if (iascii) PetscPartitionerView_Chaco_ASCII(part, viewer);
 41:   return 0;
 42: }

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

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

 92:   PetscObjectGetComm((PetscObject)part, &comm);
 93:   if (PetscDefined(USE_DEBUG)) {
 94:     int       ival, isum;
 95:     PetscBool distributed;

 97:     ival = (numVertices > 0);
 98:     MPI_Allreduce(&ival, &isum, 1, MPI_INT, MPI_SUM, comm);
 99:     distributed = (isum > 1) ? PETSC_TRUE : PETSC_FALSE;
101:   }
102:   if (!numVertices) { /* distributed case, return if not holding the graph */
103:     ISCreateGeneral(comm, 0, NULL, PETSC_OWN_POINTER, partition);
104:     return 0;
105:   }
106:   FREE_GRAPH = 0; /* Do not let Chaco free my memory */
107:   for (i = 0; i < start[numVertices]; ++i) ++adjacency[i];

109:   /* code would use manager.createCellCoordinates(nvtxs, &x, &y, &z); */

112:   mesh_dims[0] = nparts;
113:   mesh_dims[1] = 1;
114:   mesh_dims[2] = 1;
115:   PetscMalloc1(nvtxs, &assignment);
116:   /* Chaco outputs to stdout. We redirect this to a buffer. */
117:   /* TODO: check error codes for UNIX calls */
118:   #if defined(PETSC_HAVE_UNISTD_H)
119:   {
120:     int piperet;
121:     piperet = pipe(fd_pipe);
123:     fd_stdout = dup(1);
124:     close(1);
125:     dup2(fd_pipe[1], 1);
126:   }
127:   #endif
128:   if (part->usevwgt) PetscInfo(part, "PETSCPARTITIONERCHACO ignores vertex weights\n");
129:   err = interface(nvtxs, (int *)start, (int *)adjacency, vwgts, ewgts, x, y, z, outassignname, outfilename, assignment, architecture, ndims_tot, mesh_dims, goal, global_method, local_method, rqi_flag, vmax, ndims, eigtol, seed);
130:   #if defined(PETSC_HAVE_UNISTD_H)
131:   {
132:     char msgLog[10000];
133:     int  count;

135:     fflush(stdout);
136:     count = read(fd_pipe[0], msgLog, (10000 - 1) * sizeof(char));
137:     if (count < 0) count = 0;
138:     msgLog[count] = 0;
139:     close(1);
140:     dup2(fd_stdout, 1);
141:     close(fd_stdout);
142:     close(fd_pipe[0]);
143:     close(fd_pipe[1]);
145:   }
146:   #else
148:   #endif
149:   /* Convert to PetscSection+IS */
150:   for (v = 0; v < nvtxs; ++v) PetscSectionAddDof(partSection, assignment[v], 1);
151:   PetscMalloc1(nvtxs, &points);
152:   for (p = 0, i = 0; p < nparts; ++p) {
153:     for (v = 0; v < nvtxs; ++v) {
154:       if (assignment[v] == p) points[i++] = v;
155:     }
156:   }
158:   ISCreateGeneral(comm, nvtxs, points, PETSC_OWN_POINTER, partition);
159:   /* code would use manager.destroyCellCoordinates(nvtxs, &x, &y, &z); */
161:   PetscFree(assignment);
162:   for (i = 0; i < start[numVertices]; ++i) --adjacency[i];
163:   return 0;
164: #else
165:   SETERRQ(PetscObjectComm((PetscObject)part), PETSC_ERR_SUP, "Mesh partitioning needs external package support.\nPlease reconfigure with --download-chaco.");
166: #endif
167: }

169: static PetscErrorCode PetscPartitionerInitialize_Chaco(PetscPartitioner part)
170: {
171:   part->noGraph        = PETSC_FALSE;
172:   part->ops->view      = PetscPartitionerView_Chaco;
173:   part->ops->destroy   = PetscPartitionerDestroy_Chaco;
174:   part->ops->partition = PetscPartitionerPartition_Chaco;
175:   return 0;
176: }

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

181:   Level: intermediate

183: .seealso: `PetscPartitionerType`, `PetscPartitionerCreate()`, `PetscPartitionerSetType()`
184: M*/

186: PETSC_EXTERN PetscErrorCode PetscPartitionerCreate_Chaco(PetscPartitioner part)
187: {
188:   PetscPartitioner_Chaco *p;

191:   PetscNew(&p);
192:   part->data = p;

194:   PetscPartitionerInitialize_Chaco(part);
195:   PetscCitationsRegister(ChacoPartitionerCitation, &ChacoPartitionerCite);
196:   return 0;
197: }