Actual source code: party.c

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

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

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

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

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

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

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

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

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

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

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

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

     95:   /* library call */
     96:   party_lib_times_start();
     97:   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);

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

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

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

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

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

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

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

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

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

    155:   Collective

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

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

    164:   Level: advanced

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

    172:   Developer Note:
    173:   Should be `MatPartitioningPartySetGlobalType()` and all uses of method should be changed to type

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

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

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

    194: /*@
    195:   MatPartitioningPartySetLocal - Set local method used by the Party partitioner.

    197:   Collective

    199:   Input Parameters:
    200: + part  - the partitioning context
    201: - local - a string representing the method

    203:   Options Database Key:
    204: . -mat_partitioning_party_local <method> - the local method

    206:   Level: advanced

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

    212:   Developer Note:
    213:   Should be `MatPartitioningPartySetLocalType()` and all uses of method should be changed to type

    215: .seealso: `MATPARTITIONINGPARTY`, `MatPartitioningPartySetGlobal()`
    216: @*/
    217: PetscErrorCode MatPartitioningPartySetLocal(MatPartitioning part, const char *local)
    218: {
    219:   PetscFunctionBegin;
    221:   PetscTryMethod(part, "MatPartitioningPartySetLocal_C", (MatPartitioning, const char *), (part, local));
    222:   PetscFunctionReturn(PETSC_SUCCESS);
    223: }

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

    227: {
    228:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

    230:   PetscFunctionBegin;
    231:   PetscCall(PetscStrncpy(party->local, local, 15));
    232:   PetscFunctionReturn(PETSC_SUCCESS);
    233: }

    235: /*@
    236:   MatPartitioningPartySetCoarseLevel - Set the coarse level parameter for the
    237:   Party partitioner.

    239:   Collective

    241:   Input Parameters:
    242: + part  - the partitioning context
    243: - level - the coarse level in range [0.0,1.0]

    245:   Options Database Key:
    246: . -mat_partitioning_party_coarse <l> - Coarse level

    248:   Level: advanced

    250: .seealso: `MATPARTITIONINGPARTY`
    251: @*/
    252: PetscErrorCode MatPartitioningPartySetCoarseLevel(MatPartitioning part, PetscReal level)
    253: {
    254:   PetscFunctionBegin;
    257:   PetscTryMethod(part, "MatPartitioningPartySetCoarseLevel_C", (MatPartitioning, PetscReal), (part, level));
    258:   PetscFunctionReturn(PETSC_SUCCESS);
    259: }

    261: static PetscErrorCode MatPartitioningPartySetCoarseLevel_Party(MatPartitioning part, PetscReal level)
    262: {
    263:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

    265:   PetscFunctionBegin;
    266:   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]");
    267:   party->nbvtxcoarsed = (PetscInt)(part->adj->cmap->N * level);
    268:   if (party->nbvtxcoarsed < 20) party->nbvtxcoarsed = 20;
    269:   PetscFunctionReturn(PETSC_SUCCESS);
    270: }

    272: /*@
    273:   MatPartitioningPartySetMatchOptimization - Activate matching optimization for
    274:   graph reduction.

    276:   Collective

    278:   Input Parameters:
    279: + part - the partitioning context
    280: - opt  - boolean flag

    282:   Options Database Key:
    283: . -mat_partitioning_party_match_optimization - Matching optimization on/off

    285:   Level: advanced

    287: .seealso: `MATPARTITIONINGPARTY`
    288: @*/
    289: PetscErrorCode MatPartitioningPartySetMatchOptimization(MatPartitioning part, PetscBool opt)
    290: {
    291:   PetscFunctionBegin;
    294:   PetscTryMethod(part, "MatPartitioningPartySetMatchOptimization_C", (MatPartitioning, PetscBool), (part, opt));
    295:   PetscFunctionReturn(PETSC_SUCCESS);
    296: }

    298: static PetscErrorCode MatPartitioningPartySetMatchOptimization_Party(MatPartitioning part, PetscBool opt)
    299: {
    300:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

    302:   PetscFunctionBegin;
    303:   party->redo = opt;
    304:   PetscFunctionReturn(PETSC_SUCCESS);
    305: }

    307: /*@
    308:   MatPartitioningPartySetBipart - Activate or deactivate recursive bisection in the Party partitioner

    310:   Collective

    312:   Input Parameters:
    313: + part - the partitioning context
    314: - bp   - boolean flag

    316:   Options Database Key:
    317: . -mat_partitioning_party_bipart - Bipartitioning option on/off

    319:   Level: advanced

    321: .seealso: `MATPARTITIONINGPARTY`
    322: @*/
    323: PetscErrorCode MatPartitioningPartySetBipart(MatPartitioning part, PetscBool bp)
    324: {
    325:   PetscFunctionBegin;
    328:   PetscTryMethod(part, "MatPartitioningPartySetBipart_C", (MatPartitioning, PetscBool), (part, bp));
    329:   PetscFunctionReturn(PETSC_SUCCESS);
    330: }

    332: static PetscErrorCode MatPartitioningPartySetBipart_Party(MatPartitioning part, PetscBool bp)
    333: {
    334:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

    336:   PetscFunctionBegin;
    337:   party->recursive = bp;
    338:   PetscFunctionReturn(PETSC_SUCCESS);
    339: }

    341: static PetscErrorCode MatPartitioningSetFromOptions_Party(MatPartitioning part, PetscOptionItems PetscOptionsObject)
    342: {
    343:   PetscBool              flag;
    344:   char                   value[256];
    345:   PetscReal              r;
    346:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

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

    363: static PetscErrorCode MatPartitioningDestroy_Party(MatPartitioning part)
    364: {
    365:   MatPartitioning_Party *party = (MatPartitioning_Party *)part->data;

    367:   PetscFunctionBegin;
    368:   PetscCall(PetscFree(party));
    369:   /* clear composed functions */
    370:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetGlobal_C", NULL));
    371:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetLocal_C", NULL));
    372:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetCoarseLevel_C", NULL));
    373:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetMatchOptimization_C", NULL));
    374:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetBipart_C", NULL));
    375:   PetscFunctionReturn(PETSC_SUCCESS);
    376: }

    378: /*MC
    379:    MATPARTITIONINGPARTY - Creates a partitioning context via the external package Party <
    380:    http://wwwcs.upb.de/fachbereich/AG/monien/RESEARCH/PART/party.htm>.

    382:    Level: beginner

    384:    Note:
    385:    Does not support the `MatPartitioningSetUseEdgeWeights()` option

    387: .seealso: `MatPartitioningSetType()`, `MatPartitioningType`, `MatPartitioningPartySetGlobal()`, `MatPartitioningPartySetLocal()`,
    388:           `MatPartitioningPartySetCoarseLevel()`, `MatPartitioningPartySetMatchOptimization()`, `MatPartitioningPartySetBipart()`
    389: M*/

    391: PETSC_EXTERN PetscErrorCode MatPartitioningCreate_Party(MatPartitioning part)
    392: {
    393:   MatPartitioning_Party *party;

    395:   PetscFunctionBegin;
    396:   PetscCall(PetscNew(&party));
    397:   part->data = (void *)party;

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

    402:   party->redm         = PETSC_TRUE;
    403:   party->redo         = PETSC_TRUE;
    404:   party->recursive    = PETSC_TRUE;
    405:   party->verbose      = PETSC_FALSE;
    406:   party->nbvtxcoarsed = 200;

    408:   part->ops->apply          = MatPartitioningApply_Party;
    409:   part->ops->view           = MatPartitioningView_Party;
    410:   part->ops->destroy        = MatPartitioningDestroy_Party;
    411:   part->ops->setfromoptions = MatPartitioningSetFromOptions_Party;

    413:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetGlobal_C", MatPartitioningPartySetGlobal_Party));
    414:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetLocal_C", MatPartitioningPartySetLocal_Party));
    415:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetCoarseLevel_C", MatPartitioningPartySetCoarseLevel_Party));
    416:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetMatchOptimization_C", MatPartitioningPartySetMatchOptimization_Party));
    417:   PetscCall(PetscObjectComposeFunction((PetscObject)part, "MatPartitioningPartySetBipart_C", MatPartitioningPartySetBipart_Party));
    418:   PetscFunctionReturn(PETSC_SUCCESS);
    419: }