Actual source code: party.c


  2: #include <../src/mat/impls/adj/mpi/mpiadj.h>

  4: #if defined(PETSC_HAVE_UNISTD_H)
  5:   #include <unistd.h>
  6: #endif

  8: EXTERN_C_BEGIN
  9: #include <party_lib.h>
 10: EXTERN_C_END

 12: typedef struct {
 13:   PetscBool redm;
 14:   PetscBool redo;
 15:   PetscBool recursive;
 16:   PetscBool verbose;
 17:   char      global[15];   /* global method */
 18:   char      local[15];    /* local method */
 19:   PetscInt  nbvtxcoarsed; /* number of vertices for the coarse graph */
 20: } MatPartitioning_Party;

 22: #define SIZE_LOG 10000 /* size of buffer for mesg_log */

 24: static PetscErrorCode MatPartitioningApply_Party(MatPartitioning part, IS *partitioning)
 25: {
 26:   int                    perr;
 27:   PetscInt               i, *parttab, *locals, nb_locals, M, N;
 28:   PetscMPIInt            size, rank;
 29:   Mat                    mat = part->adj, matAdj, matSeq, *A;
 30:   Mat_MPIAdj            *adj;
 31:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;
 32:   PetscBool              flg;
 33:   IS                     isrow, iscol;
 34:   int                    n, *edge_p, *edge, *vertex_w, p, *part_party, cutsize, redl, rec;
 35:   const char            *redm, *redo;
 36:   char                  *mesg_log;
 37: #if defined(PETSC_HAVE_UNISTD_H)
 38:   int fd_stdout, fd_pipe[2], count;
 39: #endif

 41:   PetscFunctionBegin;
 42:   PetscCheck(!part->use_edge_weights, PetscObjectComm((PetscObject)part), PETSC_ERR_SUP, "Party does not support edge weights");
 43:   PetscCallMPI(MPI_Comm_size(PetscObjectComm((PetscObject)mat), &size));
 44:   PetscCallMPI(MPI_Comm_rank(PetscObjectComm((PetscObject)mat), &rank));
 45:   PetscCall(PetscObjectTypeCompare((PetscObject)mat, MATMPIADJ, &flg));
 46:   if (size > 1) {
 47:     if (flg) {
 48:       PetscCall(MatMPIAdjToSeq(mat, &matSeq));
 49:     } else {
 50:       PetscCall(PetscInfo(part, "Converting distributed matrix to sequential: this could be a performance loss\n"));
 51:       PetscCall(MatGetSize(mat, &M, &N));
 52:       PetscCall(ISCreateStride(PETSC_COMM_SELF, M, 0, 1, &isrow));
 53:       PetscCall(ISCreateStride(PETSC_COMM_SELF, N, 0, 1, &iscol));
 54:       PetscCall(MatCreateSubMatrices(mat, 1, &isrow, &iscol, MAT_INITIAL_MATRIX, &A));
 55:       PetscCall(ISDestroy(&isrow));
 56:       PetscCall(ISDestroy(&iscol));
 57:       matSeq = *A;
 58:       PetscCall(PetscFree(A));
 59:     }
 60:   } else {
 61:     PetscCall(PetscObjectReference((PetscObject)mat));
 62:     matSeq = mat;
 63:   }

 65:   if (!flg) { /* convert regular matrix to MPIADJ */
 66:     PetscCall(MatConvert(matSeq, MATMPIADJ, MAT_INITIAL_MATRIX, &matAdj));
 67:   } else {
 68:     PetscCall(PetscObjectReference((PetscObject)matSeq));
 69:     matAdj = matSeq;
 70:   }

 72:   adj = (Mat_MPIAdj *)matAdj->data; /* finally adj contains adjacency graph */

 74:   /* arguments for Party library */
 75:   n        = mat->rmap->N;             /* number of vertices in full graph */
 76:   edge_p   = adj->i;                   /* start of edge list for each vertex */
 77:   edge     = adj->j;                   /* edge list data */
 78:   vertex_w = part->vertex_weights;     /* weights for all vertices */
 79:   p        = part->n;                  /* number of parts to create */
 80:   redl     = party->nbvtxcoarsed;      /* how many vertices to coarsen down to? */
 81:   rec      = party->recursive ? 1 : 0; /* recursive bisection */
 82:   redm     = party->redm ? "lam" : ""; /* matching method */
 83:   redo     = party->redo ? "w3" : "";  /* matching optimization method */

 85:   PetscCall(PetscMalloc1(mat->rmap->N, &part_party));

 87:   /* redirect output to buffer */
 88: #if defined(PETSC_HAVE_UNISTD_H)
 89:   fd_stdout = dup(1);
 90:   PetscCheck(!pipe(fd_pipe), PETSC_COMM_SELF, PETSC_ERR_SYS, "Could not open pipe");
 91:   close(1);
 92:   dup2(fd_pipe[1], 1);
 93:   PetscCall(PetscMalloc1(SIZE_LOG, &mesg_log));
 94: #endif

 96:   /* library call */
 97:   party_lib_times_start();
 98:   perr = party_lib(n, vertex_w, NULL, NULL, NULL, edge_p, edge, NULL, p, part_party, &cutsize, redl, (char *)redm, (char *)redo, party->global, party->local, rec, 1);

100:   party_lib_times_output(1);
101:   part_info(n, vertex_w, edge_p, edge, NULL, p, part_party, 1);

103: #if defined(PETSC_HAVE_UNISTD_H)
104:   PetscCall(PetscFFlush(stdout));
105:   count = read(fd_pipe[0], mesg_log, (SIZE_LOG - 1) * sizeof(char));
106:   if (count < 0) count = 0;
107:   mesg_log[count] = 0;
108:   close(1);
109:   dup2(fd_stdout, 1);
110:   close(fd_stdout);
111:   close(fd_pipe[0]);
112:   close(fd_pipe[1]);
113:   if (party->verbose) PetscCall(PetscPrintf(PetscObjectComm((PetscObject)mat), "%s", mesg_log));
114:   PetscCall(PetscFree(mesg_log));
115: #endif
116:   PetscCheck(!perr, PETSC_COMM_SELF, PETSC_ERR_LIB, "Party failed");

118:   PetscCall(PetscMalloc1(mat->rmap->N, &parttab));
119:   for (i = 0; i < mat->rmap->N; i++) parttab[i] = part_party[i];

121:   /* creation of the index set */
122:   nb_locals = mat->rmap->n;
123:   locals    = parttab + mat->rmap->rstart;

125:   PetscCall(ISCreateGeneral(PetscObjectComm((PetscObject)part), nb_locals, locals, PETSC_COPY_VALUES, partitioning));

127:   /* clean up */
128:   PetscCall(PetscFree(parttab));
129:   PetscCall(PetscFree(part_party));
130:   PetscCall(MatDestroy(&matSeq));
131:   PetscCall(MatDestroy(&matAdj));
132:   PetscFunctionReturn(PETSC_SUCCESS);
133: }

135: PetscErrorCode MatPartitioningView_Party(MatPartitioning part, PetscViewer viewer)
136: {
137:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;
138:   PetscBool              isascii;

140:   PetscFunctionBegin;
141:   PetscCall(PetscObjectTypeCompare((PetscObject)viewer, PETSCVIEWERASCII, &isascii));
142:   if (isascii) {
143:     PetscCall(PetscViewerASCIIPrintf(viewer, "  Global method: %s\n", party->global));
144:     PetscCall(PetscViewerASCIIPrintf(viewer, "  Local method: %s\n", party->local));
145:     PetscCall(PetscViewerASCIIPrintf(viewer, "  Number of vertices for the coarse graph: %d\n", party->nbvtxcoarsed));
146:     if (party->redm) PetscCall(PetscViewerASCIIPrintf(viewer, "  Using matching method for graph reduction\n"));
147:     if (party->redo) PetscCall(PetscViewerASCIIPrintf(viewer, "  Using matching optimization\n"));
148:     if (party->recursive) PetscCall(PetscViewerASCIIPrintf(viewer, "  Using recursive bipartitioning\n"));
149:   }
150:   PetscFunctionReturn(PETSC_SUCCESS);
151: }

153: /*@C
154:    MatPartitioningPartySetGlobal - Set global method for Party partitioner.

156:    Collective

158:    Input Parameters:
159: +  part - the partitioning context
160: -  method - a string representing the method

162:    Options Database Key:
163: .  -mat_partitioning_party_global <method> - the global method

165:    Level: advanced

167:    Note:
168:    The method may be one of `MP_PARTY_OPT`, `MP_PARTY_LIN`, `MP_PARTY_SCA`,
169:    `MP_PARTY_RAN`, `MP_PARTY_GBF`, `MP_PARTY_GCF`, `MP_PARTY_BUB` or `MP_PARTY_DEF`, or
170:    alternatively a string describing the method. Two or more methods can be
171:    combined like "gbf,gcf". Check the Party Library Users Manual for details.

173: .seealso: `MATPARTITIONINGPARTY`, `MatPartitioningPartySetLocal()`
174: @*/
175: PetscErrorCode MatPartitioningPartySetGlobal(MatPartitioning part, const char *global)
176: {
177:   PetscFunctionBegin;
179:   PetscTryMethod(part, "MatPartitioningPartySetGlobal_C", (MatPartitioning, const char *), (part, global));
180:   PetscFunctionReturn(PETSC_SUCCESS);
181: }

183: PetscErrorCode MatPartitioningPartySetGlobal_Party(MatPartitioning part, const char *global)
184: {
185:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

187:   PetscFunctionBegin;
188:   PetscCall(PetscStrncpy(party->global, global, 15));
189:   PetscFunctionReturn(PETSC_SUCCESS);
190: }

192: /*@C
193:    MatPartitioningPartySetLocal - Set local method used by the Party partitioner.

195:    Collective

197:    Input Parameters:
198: +  part - the partitioning context
199: -  method - a string representing the method

201:    Options Database Key:
202: .  -mat_partitioning_party_local <method> - the local method

204:    Level: advanced

206:    Note:
207:    The method may be one of `MP_PARTY_HELPFUL_SETS`, `MP_PARTY_KERNIGHAN_LIN`, or
208:    `MP_PARTY_NONE`. Check the Party Library Users Manual for details.

210: .seealso: `MATPARTITIONINGPARTY`, `MatPartitioningPartySetGlobal()`
211: @*/
212: PetscErrorCode MatPartitioningPartySetLocal(MatPartitioning part, const char *local)
213: {
214:   PetscFunctionBegin;
216:   PetscTryMethod(part, "MatPartitioningPartySetLocal_C", (MatPartitioning, const char *), (part, local));
217:   PetscFunctionReturn(PETSC_SUCCESS);
218: }

220: PetscErrorCode MatPartitioningPartySetLocal_Party(MatPartitioning part, const char *local)

222: {
223:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

225:   PetscFunctionBegin;
226:   PetscCall(PetscStrncpy(party->local, local, 15));
227:   PetscFunctionReturn(PETSC_SUCCESS);
228: }

230: /*@
231:    MatPartitioningPartySetCoarseLevel - Set the coarse level parameter for the
232:    Party partitioner.

234:    Collective

236:    Input Parameters:
237: +  part - the partitioning context
238: -  level - the coarse level in range [0.0,1.0]

240:    Options Database Key:
241: .  -mat_partitioning_party_coarse <l> - Coarse level

243:    Level: advanced

245: .seealso: `MATPARTITIONINGPARTY`
246: @*/
247: PetscErrorCode MatPartitioningPartySetCoarseLevel(MatPartitioning part, PetscReal level)
248: {
249:   PetscFunctionBegin;
252:   PetscTryMethod(part, "MatPartitioningPartySetCoarseLevel_C", (MatPartitioning, PetscReal), (part, level));
253:   PetscFunctionReturn(PETSC_SUCCESS);
254: }

256: PetscErrorCode MatPartitioningPartySetCoarseLevel_Party(MatPartitioning part, PetscReal level)
257: {
258:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

260:   PetscFunctionBegin;
261:   PetscCheck(level >= 0.0 && level <= 1.0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Party: level of coarsening out of range [0.0-1.0]");
262:   party->nbvtxcoarsed = (PetscInt)(part->adj->cmap->N * level);
263:   if (party->nbvtxcoarsed < 20) party->nbvtxcoarsed = 20;
264:   PetscFunctionReturn(PETSC_SUCCESS);
265: }

267: /*@
268:    MatPartitioningPartySetMatchOptimization - Activate matching optimization for
269:    graph reduction.

271:    Collective

273:    Input Parameters:
274: +  part - the partitioning context
275: -  opt - boolean flag

277:    Options Database Key:
278: .  -mat_partitioning_party_match_optimization - Matching optimization on/off

280:    Level: advanced

282: .seealso:  `MATPARTITIONINGPARTY`
283: @*/
284: PetscErrorCode MatPartitioningPartySetMatchOptimization(MatPartitioning part, PetscBool opt)
285: {
286:   PetscFunctionBegin;
289:   PetscTryMethod(part, "MatPartitioningPartySetMatchOptimization_C", (MatPartitioning, PetscBool), (part, opt));
290:   PetscFunctionReturn(PETSC_SUCCESS);
291: }

293: PetscErrorCode MatPartitioningPartySetMatchOptimization_Party(MatPartitioning part, PetscBool opt)
294: {
295:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

297:   PetscFunctionBegin;
298:   party->redo = opt;
299:   PetscFunctionReturn(PETSC_SUCCESS);
300: }

302: /*@
303:    MatPartitioningPartySetBipart - Activate or deactivate recursive bisection in the Party partitioner

305:    Collective

307:    Input Parameters:
308: +  part - the partitioning context
309: -  bp - boolean flag

311:    Options Database Key:
312: -  -mat_partitioning_party_bipart - Bipartitioning option on/off

314:    Level: advanced

316: .seealso:  `MATPARTITIONINGPARTY`
317: @*/
318: PetscErrorCode MatPartitioningPartySetBipart(MatPartitioning part, PetscBool bp)
319: {
320:   PetscFunctionBegin;
323:   PetscTryMethod(part, "MatPartitioningPartySetBipart_C", (MatPartitioning, PetscBool), (part, bp));
324:   PetscFunctionReturn(PETSC_SUCCESS);
325: }

327: PetscErrorCode MatPartitioningPartySetBipart_Party(MatPartitioning part, PetscBool bp)
328: {
329:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

331:   PetscFunctionBegin;
332:   party->recursive = bp;
333:   PetscFunctionReturn(PETSC_SUCCESS);
334: }

336: PetscErrorCode MatPartitioningSetFromOptions_Party(MatPartitioning part, PetscOptionItems *PetscOptionsObject)
337: {
338:   PetscBool              flag;
339:   char                   value[256];
340:   PetscReal              r;
341:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

343:   PetscFunctionBegin;
344:   PetscOptionsHeadBegin(PetscOptionsObject, "Set Party partitioning options");
345:   PetscCall(PetscOptionsString("-mat_partitioning_party_global", "Global method", "MatPartitioningPartySetGlobal", party->global, value, sizeof(value), &flag));
346:   if (flag) PetscCall(MatPartitioningPartySetGlobal(part, value));
347:   PetscCall(PetscOptionsString("-mat_partitioning_party_local", "Local method", "MatPartitioningPartySetLocal", party->local, value, sizeof(value), &flag));
348:   if (flag) PetscCall(MatPartitioningPartySetLocal(part, value));
349:   PetscCall(PetscOptionsReal("-mat_partitioning_party_coarse", "Coarse level", "MatPartitioningPartySetCoarseLevel", 0.0, &r, &flag));
350:   if (flag) PetscCall(MatPartitioningPartySetCoarseLevel(part, r));
351:   PetscCall(PetscOptionsBool("-mat_partitioning_party_match_optimization", "Matching optimization on/off", "MatPartitioningPartySetMatchOptimization", party->redo, &party->redo, NULL));
352:   PetscCall(PetscOptionsBool("-mat_partitioning_party_bipart", "Bipartitioning on/off", "MatPartitioningPartySetBipart", party->recursive, &party->recursive, NULL));
353:   PetscCall(PetscOptionsBool("-mat_partitioning_party_verbose", "Show library output", "", party->verbose, &party->verbose, NULL));
354:   PetscOptionsHeadEnd();
355:   PetscFunctionReturn(PETSC_SUCCESS);
356: }

358: PetscErrorCode MatPartitioningDestroy_Party(MatPartitioning part)
359: {
360:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

362:   PetscFunctionBegin;
363:   PetscCall(PetscFree(party));
364:   /* clear composed functions */
365:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetGlobal_C", NULL));
366:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetLocal_C", NULL));
367:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetCoarseLevel_C", NULL));
368:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetMatchOptimization_C", NULL));
369:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetBipart_C", NULL));
370:   PetscFunctionReturn(PETSC_SUCCESS);
371: }

373: /*MC
374:    MATPARTITIONINGPARTY - Creates a partitioning context via the external package Party.

376:    Level: beginner

378:    Notes:
379:     See http://wwwcs.upb.de/fachbereich/AG/monien/RESEARCH/PART/party.html

381:     Does not support the `MatPartitioningSetUseEdgeWeights()` option

383: .seealso: `MatPartitioningSetType()`, `MatPartitioningType`, `MatPartitioningPartySetGlobal()`, `MatPartitioningPartySetLocal()`,
384:           `MatPartitioningPartySetCoarseLevel()`, `MatPartitioningPartySetMatchOptimization()`, `MatPartitioningPartySetBipart()`
385: M*/

387: PETSC_EXTERN PetscErrorCode MatPartitioningCreate_Party(MatPartitioning part)
388: {
389:   MatPartitioning_Party *party;

391:   PetscFunctionBegin;
392:   PetscCall(PetscNew(&party));
393:   part->data = (void *)party;

395:   PetscCall(PetscStrncpy(party->global, "gcf,gbf", sizeof(party->global)));
396:   PetscCall(PetscStrncpy(party->local, "kl", sizeof(party->local)));

398:   party->redm         = PETSC_TRUE;
399:   party->redo         = PETSC_TRUE;
400:   party->recursive    = PETSC_TRUE;
401:   party->verbose      = PETSC_FALSE;
402:   party->nbvtxcoarsed = 200;

404:   part->ops->apply          = MatPartitioningApply_Party;
405:   part->ops->view           = MatPartitioningView_Party;
406:   part->ops->destroy        = MatPartitioningDestroy_Party;
407:   part->ops->setfromoptions = MatPartitioningSetFromOptions_Party;

409:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetGlobal_C", MatPartitioningPartySetGlobal_Party));
410:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetLocal_C", MatPartitioningPartySetLocal_Party));
411:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetCoarseLevel_C", MatPartitioningPartySetCoarseLevel_Party));
412:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetMatchOptimization_C", MatPartitioningPartySetMatchOptimization_Party));
413:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetBipart_C", MatPartitioningPartySetBipart_Party));
414:   PetscFunctionReturn(PETSC_SUCCESS);
415: }