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;

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

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

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

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

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

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

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

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

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

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

177: static PetscErrorCode PetscPartitionerInitialize_Chaco(PetscPartitioner part)
178: {
179:   part->noGraph        = PETSC_FALSE;
180:   part->ops->view      = PetscPartitionerView_Chaco;
181:   part->ops->destroy   = PetscPartitionerDestroy_Chaco;
182:   part->ops->partition = PetscPartitionerPartition_Chaco;
183:   return 0;
184: }

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

189:   Level: intermediate

191: .seealso: PetscPartitionerType, PetscPartitionerCreate(), PetscPartitionerSetType()
192: M*/

194: PETSC_EXTERN PetscErrorCode PetscPartitionerCreate_Chaco(PetscPartitioner part)
195: {
196:   PetscPartitioner_Chaco *p;

199:   PetscNewLog(part, &p);
200:   part->data = p;

202:   PetscPartitionerInitialize_Chaco(part);
203:   PetscCitationsRegister(ChacoPartitionerCitation, &ChacoPartitionerCite);
204:   return 0;
205: }