1 #include <petsc/private/partitionerimpl.h> /*I "petscpartitioner.h" I*/ 2 3 #if defined(PETSC_HAVE_PTSCOTCH) 4 EXTERN_C_BEGIN 5 #include <ptscotch.h> 6 EXTERN_C_END 7 #endif 8 9 PetscBool PTScotchPartitionerCite = PETSC_FALSE; 10 const char PTScotchPartitionerCitation[] = 11 "@article{PTSCOTCH,\n" 12 " author = {C. Chevalier and F. Pellegrini},\n" 13 " title = {{PT-SCOTCH}: a tool for efficient parallel graph ordering},\n" 14 " journal = {Parallel Computing},\n" 15 " volume = {34},\n" 16 " number = {6},\n" 17 " pages = {318--331},\n" 18 " year = {2008},\n" 19 " doi = {https://doi.org/10.1016/j.parco.2007.12.001}\n" 20 "}\n"; 21 22 typedef struct { 23 MPI_Comm pcomm; 24 PetscInt strategy; 25 PetscReal imbalance; 26 } PetscPartitioner_PTScotch; 27 28 #if defined(PETSC_HAVE_PTSCOTCH) 29 30 #define CHKERRPTSCOTCH(ierr) do { if (ierr) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_LIB,"Error calling PT-Scotch library"); } while(0) 31 32 static int PTScotch_Strategy(PetscInt strategy) 33 { 34 switch (strategy) { 35 case 0: return SCOTCH_STRATDEFAULT; 36 case 1: return SCOTCH_STRATQUALITY; 37 case 2: return SCOTCH_STRATSPEED; 38 case 3: return SCOTCH_STRATBALANCE; 39 case 4: return SCOTCH_STRATSAFETY; 40 case 5: return SCOTCH_STRATSCALABILITY; 41 case 6: return SCOTCH_STRATRECURSIVE; 42 case 7: return SCOTCH_STRATREMAP; 43 default: return SCOTCH_STRATDEFAULT; 44 } 45 } 46 47 static PetscErrorCode PTScotch_PartGraph_Seq(SCOTCH_Num strategy, double imbalance, SCOTCH_Num n, SCOTCH_Num xadj[], SCOTCH_Num adjncy[], 48 SCOTCH_Num vtxwgt[], SCOTCH_Num adjwgt[], SCOTCH_Num nparts, SCOTCH_Num tpart[], SCOTCH_Num part[]) 49 { 50 SCOTCH_Graph grafdat; 51 SCOTCH_Strat stradat; 52 SCOTCH_Num vertnbr = n; 53 SCOTCH_Num edgenbr = xadj[n]; 54 SCOTCH_Num* velotab = vtxwgt; 55 SCOTCH_Num* edlotab = adjwgt; 56 SCOTCH_Num flagval = strategy; 57 double kbalval = imbalance; 58 PetscErrorCode ierr; 59 60 PetscFunctionBegin; 61 { 62 PetscBool flg = PETSC_TRUE; 63 ierr = PetscOptionsDeprecatedNoObject("-petscpartititoner_ptscotch_vertex_weight",NULL,"3.13","Use -petscpartitioner_use_vertex_weights");CHKERRQ(ierr); 64 ierr = PetscOptionsGetBool(NULL, NULL, "-petscpartititoner_ptscotch_vertex_weight", &flg, NULL);CHKERRQ(ierr); 65 if (!flg) velotab = NULL; 66 } 67 ierr = SCOTCH_graphInit(&grafdat);CHKERRPTSCOTCH(ierr); 68 ierr = SCOTCH_graphBuild(&grafdat, 0, vertnbr, xadj, xadj + 1, velotab, NULL, edgenbr, adjncy, edlotab);CHKERRPTSCOTCH(ierr); 69 ierr = SCOTCH_stratInit(&stradat);CHKERRPTSCOTCH(ierr); 70 ierr = SCOTCH_stratGraphMapBuild(&stradat, flagval, nparts, kbalval);CHKERRPTSCOTCH(ierr); 71 if (tpart) { 72 SCOTCH_Arch archdat; 73 ierr = SCOTCH_archInit(&archdat);CHKERRPTSCOTCH(ierr); 74 ierr = SCOTCH_archCmpltw(&archdat, nparts, tpart);CHKERRPTSCOTCH(ierr); 75 ierr = SCOTCH_graphMap(&grafdat, &archdat, &stradat, part);CHKERRPTSCOTCH(ierr); 76 SCOTCH_archExit(&archdat); 77 } else { 78 ierr = SCOTCH_graphPart(&grafdat, nparts, &stradat, part);CHKERRPTSCOTCH(ierr); 79 } 80 SCOTCH_stratExit(&stradat); 81 SCOTCH_graphExit(&grafdat); 82 PetscFunctionReturn(0); 83 } 84 85 static PetscErrorCode PTScotch_PartGraph_MPI(SCOTCH_Num strategy, double imbalance, SCOTCH_Num vtxdist[], SCOTCH_Num xadj[], SCOTCH_Num adjncy[], 86 SCOTCH_Num vtxwgt[], SCOTCH_Num adjwgt[], SCOTCH_Num nparts, SCOTCH_Num tpart[], SCOTCH_Num part[], MPI_Comm comm) 87 { 88 PetscMPIInt procglbnbr; 89 PetscMPIInt proclocnum; 90 SCOTCH_Arch archdat; 91 SCOTCH_Dgraph grafdat; 92 SCOTCH_Dmapping mappdat; 93 SCOTCH_Strat stradat; 94 SCOTCH_Num vertlocnbr; 95 SCOTCH_Num edgelocnbr; 96 SCOTCH_Num* veloloctab = vtxwgt; 97 SCOTCH_Num* edloloctab = adjwgt; 98 SCOTCH_Num flagval = strategy; 99 double kbalval = imbalance; 100 PetscErrorCode ierr; 101 102 PetscFunctionBegin; 103 { 104 PetscBool flg = PETSC_TRUE; 105 ierr = PetscOptionsDeprecatedNoObject("-petscpartititoner_ptscotch_vertex_weight",NULL,"3.13","Use -petscpartitioner_use_vertex_weights");CHKERRQ(ierr); 106 ierr = PetscOptionsGetBool(NULL, NULL, "-petscpartititoner_ptscotch_vertex_weight", &flg, NULL);CHKERRQ(ierr); 107 if (!flg) veloloctab = NULL; 108 } 109 ierr = MPI_Comm_size(comm, &procglbnbr);CHKERRQ(ierr); 110 ierr = MPI_Comm_rank(comm, &proclocnum);CHKERRQ(ierr); 111 vertlocnbr = vtxdist[proclocnum + 1] - vtxdist[proclocnum]; 112 edgelocnbr = xadj[vertlocnbr]; 113 114 ierr = SCOTCH_dgraphInit(&grafdat, comm);CHKERRPTSCOTCH(ierr); 115 ierr = SCOTCH_dgraphBuild(&grafdat, 0, vertlocnbr, vertlocnbr, xadj, xadj + 1, veloloctab, NULL, edgelocnbr, edgelocnbr, adjncy, NULL, edloloctab);CHKERRPTSCOTCH(ierr); 116 ierr = SCOTCH_stratInit(&stradat);CHKERRPTSCOTCH(ierr); 117 ierr = SCOTCH_stratDgraphMapBuild(&stradat, flagval, procglbnbr, nparts, kbalval);CHKERRQ(ierr); 118 ierr = SCOTCH_archInit(&archdat);CHKERRPTSCOTCH(ierr); 119 if (tpart) { /* target partition weights */ 120 ierr = SCOTCH_archCmpltw(&archdat, nparts, tpart);CHKERRPTSCOTCH(ierr); 121 } else { 122 ierr = SCOTCH_archCmplt(&archdat, nparts);CHKERRPTSCOTCH(ierr); 123 } 124 ierr = SCOTCH_dgraphMapInit(&grafdat, &mappdat, &archdat, part);CHKERRPTSCOTCH(ierr); 125 126 ierr = SCOTCH_dgraphMapCompute(&grafdat, &mappdat, &stradat);CHKERRPTSCOTCH(ierr); 127 SCOTCH_dgraphMapExit(&grafdat, &mappdat); 128 SCOTCH_archExit(&archdat); 129 SCOTCH_stratExit(&stradat); 130 SCOTCH_dgraphExit(&grafdat); 131 PetscFunctionReturn(0); 132 } 133 134 #endif /* PETSC_HAVE_PTSCOTCH */ 135 136 static const char *const 137 PTScotchStrategyList[] = { 138 "DEFAULT", 139 "QUALITY", 140 "SPEED", 141 "BALANCE", 142 "SAFETY", 143 "SCALABILITY", 144 "RECURSIVE", 145 "REMAP" 146 }; 147 148 static PetscErrorCode PetscPartitionerDestroy_PTScotch(PetscPartitioner part) 149 { 150 PetscPartitioner_PTScotch *p = (PetscPartitioner_PTScotch *) part->data; 151 PetscErrorCode ierr; 152 153 PetscFunctionBegin; 154 ierr = MPI_Comm_free(&p->pcomm);CHKERRQ(ierr); 155 ierr = PetscFree(part->data);CHKERRQ(ierr); 156 PetscFunctionReturn(0); 157 } 158 159 static PetscErrorCode PetscPartitionerView_PTScotch_ASCII(PetscPartitioner part, PetscViewer viewer) 160 { 161 PetscPartitioner_PTScotch *p = (PetscPartitioner_PTScotch *) part->data; 162 PetscErrorCode ierr; 163 164 PetscFunctionBegin; 165 ierr = PetscViewerASCIIPushTab(viewer);CHKERRQ(ierr); 166 ierr = PetscViewerASCIIPrintf(viewer,"using partitioning strategy %s\n",PTScotchStrategyList[p->strategy]);CHKERRQ(ierr); 167 ierr = PetscViewerASCIIPrintf(viewer,"using load imbalance ratio %g\n",(double)p->imbalance);CHKERRQ(ierr); 168 ierr = PetscViewerASCIIPopTab(viewer);CHKERRQ(ierr); 169 PetscFunctionReturn(0); 170 } 171 172 static PetscErrorCode PetscPartitionerView_PTScotch(PetscPartitioner part, PetscViewer viewer) 173 { 174 PetscBool iascii; 175 PetscErrorCode ierr; 176 177 PetscFunctionBegin; 178 PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1); 179 PetscValidHeaderSpecific(viewer, PETSC_VIEWER_CLASSID, 2); 180 ierr = PetscObjectTypeCompare((PetscObject) viewer, PETSCVIEWERASCII, &iascii);CHKERRQ(ierr); 181 if (iascii) {ierr = PetscPartitionerView_PTScotch_ASCII(part, viewer);CHKERRQ(ierr);} 182 PetscFunctionReturn(0); 183 } 184 185 static PetscErrorCode PetscPartitionerSetFromOptions_PTScotch(PetscOptionItems *PetscOptionsObject, PetscPartitioner part) 186 { 187 PetscPartitioner_PTScotch *p = (PetscPartitioner_PTScotch *) part->data; 188 const char *const *slist = PTScotchStrategyList; 189 PetscInt nlist = (PetscInt)(sizeof(PTScotchStrategyList)/sizeof(PTScotchStrategyList[0])); 190 PetscBool flag; 191 PetscErrorCode ierr; 192 193 PetscFunctionBegin; 194 ierr = PetscOptionsHead(PetscOptionsObject, "PetscPartitioner PTScotch Options");CHKERRQ(ierr); 195 ierr = PetscOptionsEList("-petscpartitioner_ptscotch_strategy","Partitioning strategy","",slist,nlist,slist[p->strategy],&p->strategy,&flag);CHKERRQ(ierr); 196 ierr = PetscOptionsReal("-petscpartitioner_ptscotch_imbalance","Load imbalance ratio","",p->imbalance,&p->imbalance,&flag);CHKERRQ(ierr); 197 ierr = PetscOptionsTail();CHKERRQ(ierr); 198 PetscFunctionReturn(0); 199 } 200 201 static PetscErrorCode PetscPartitionerPartition_PTScotch(PetscPartitioner part, PetscInt nparts, PetscInt numVertices, PetscInt start[], PetscInt adjacency[], PetscSection vertSection, PetscSection targetSection, PetscSection partSection, IS *partition) 202 { 203 #if defined(PETSC_HAVE_PTSCOTCH) 204 MPI_Comm comm; 205 PetscInt nvtxs = numVertices; /* The number of vertices in full graph */ 206 PetscInt *vtxdist; /* Distribution of vertices across processes */ 207 PetscInt *xadj = start; /* Start of edge list for each vertex */ 208 PetscInt *adjncy = adjacency; /* Edge lists for all vertices */ 209 PetscInt *vwgt = NULL; /* Vertex weights */ 210 PetscInt *adjwgt = NULL; /* Edge weights */ 211 PetscInt v, i, *assignment, *points; 212 PetscMPIInt size, rank, p; 213 PetscBool hasempty = PETSC_FALSE; 214 PetscInt *tpwgts = NULL; 215 PetscErrorCode ierr; 216 217 PetscFunctionBegin; 218 ierr = PetscObjectGetComm((PetscObject)part,&comm);CHKERRQ(ierr); 219 ierr = MPI_Comm_size(comm, &size);CHKERRQ(ierr); 220 ierr = MPI_Comm_rank(comm, &rank);CHKERRQ(ierr); 221 ierr = PetscMalloc2(size+1,&vtxdist,PetscMax(nvtxs,1),&assignment);CHKERRQ(ierr); 222 /* Calculate vertex distribution */ 223 vtxdist[0] = 0; 224 ierr = MPI_Allgather(&nvtxs, 1, MPIU_INT, &vtxdist[1], 1, MPIU_INT, comm);CHKERRQ(ierr); 225 for (p = 2; p <= size; ++p) { 226 hasempty = (PetscBool)(hasempty || !vtxdist[p-1] || !vtxdist[p]); 227 vtxdist[p] += vtxdist[p-1]; 228 } 229 /* null graph */ 230 if (vtxdist[size] == 0) { 231 ierr = PetscFree2(vtxdist, assignment);CHKERRQ(ierr); 232 ierr = ISCreateGeneral(comm, 0, NULL, PETSC_OWN_POINTER, partition);CHKERRQ(ierr); 233 PetscFunctionReturn(0); 234 } 235 236 /* Calculate vertex weights */ 237 if (vertSection) { 238 ierr = PetscMalloc1(nvtxs,&vwgt);CHKERRQ(ierr); 239 for (v = 0; v < nvtxs; ++v) { 240 ierr = PetscSectionGetDof(vertSection, v, &vwgt[v]);CHKERRQ(ierr); 241 } 242 } 243 244 /* Calculate partition weights */ 245 if (targetSection) { 246 PetscInt sumw; 247 248 ierr = PetscCalloc1(nparts,&tpwgts);CHKERRQ(ierr); 249 for (p = 0, sumw = 0; p < nparts; ++p) { 250 ierr = PetscSectionGetDof(targetSection,p,&tpwgts[p]);CHKERRQ(ierr); 251 sumw += tpwgts[p]; 252 } 253 if (!sumw) { 254 ierr = PetscFree(tpwgts);CHKERRQ(ierr); 255 } 256 } 257 258 { 259 PetscPartitioner_PTScotch *pts = (PetscPartitioner_PTScotch *) part->data; 260 int strat = PTScotch_Strategy(pts->strategy); 261 double imbal = (double)pts->imbalance; 262 263 for (p = 0; !vtxdist[p+1] && p < size; ++p); 264 if (vtxdist[p+1] == vtxdist[size]) { 265 if (rank == p) { 266 ierr = PTScotch_PartGraph_Seq(strat, imbal, nvtxs, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, assignment);CHKERRQ(ierr); 267 } 268 } else { 269 MPI_Comm pcomm = pts->pcomm; 270 271 if (hasempty) { 272 PetscInt cnt; 273 274 ierr = MPI_Comm_split(pts->pcomm,!!nvtxs,rank,&pcomm);CHKERRQ(ierr); 275 for (p=0,cnt=0;p<size;p++) { 276 if (vtxdist[p+1] != vtxdist[p]) { 277 vtxdist[cnt+1] = vtxdist[p+1]; 278 cnt++; 279 } 280 } 281 }; 282 if (nvtxs) { 283 ierr = PTScotch_PartGraph_MPI(strat, imbal, vtxdist, xadj, adjncy, vwgt, adjwgt, nparts, tpwgts, assignment, pcomm);CHKERRQ(ierr); 284 } 285 if (hasempty) { 286 ierr = MPI_Comm_free(&pcomm);CHKERRQ(ierr); 287 } 288 } 289 } 290 ierr = PetscFree(vwgt);CHKERRQ(ierr); 291 ierr = PetscFree(tpwgts);CHKERRQ(ierr); 292 293 /* Convert to PetscSection+IS */ 294 for (v = 0; v < nvtxs; ++v) {ierr = PetscSectionAddDof(partSection, assignment[v], 1);CHKERRQ(ierr);} 295 ierr = PetscMalloc1(nvtxs, &points);CHKERRQ(ierr); 296 for (p = 0, i = 0; p < nparts; ++p) { 297 for (v = 0; v < nvtxs; ++v) { 298 if (assignment[v] == p) points[i++] = v; 299 } 300 } 301 if (i != nvtxs) SETERRQ2(comm, PETSC_ERR_PLIB, "Number of points %D should be %D", i, nvtxs); 302 ierr = ISCreateGeneral(comm, nvtxs, points, PETSC_OWN_POINTER, partition);CHKERRQ(ierr); 303 304 ierr = PetscFree2(vtxdist,assignment);CHKERRQ(ierr); 305 PetscFunctionReturn(0); 306 #else 307 SETERRQ(PetscObjectComm((PetscObject) part), PETSC_ERR_SUP, "Mesh partitioning needs external package support.\nPlease reconfigure with --download-ptscotch."); 308 #endif 309 } 310 311 static PetscErrorCode PetscPartitionerInitialize_PTScotch(PetscPartitioner part) 312 { 313 PetscFunctionBegin; 314 part->noGraph = PETSC_FALSE; 315 part->ops->view = PetscPartitionerView_PTScotch; 316 part->ops->destroy = PetscPartitionerDestroy_PTScotch; 317 part->ops->partition = PetscPartitionerPartition_PTScotch; 318 part->ops->setfromoptions = PetscPartitionerSetFromOptions_PTScotch; 319 PetscFunctionReturn(0); 320 } 321 322 /*MC 323 PETSCPARTITIONERPTSCOTCH = "ptscotch" - A PetscPartitioner object using the PT-Scotch library 324 325 Level: intermediate 326 327 Options Database Keys: 328 + -petscpartitioner_ptscotch_strategy <string> - PT-Scotch strategy. Choose one of default quality speed balance safety scalability recursive remap 329 - -petscpartitioner_ptscotch_imbalance <val> - Load imbalance ratio 330 331 Notes: when the graph is on a single process, this partitioner actually uses Scotch and not PT-Scotch 332 333 .seealso: PetscPartitionerType, PetscPartitionerCreate(), PetscPartitionerSetType() 334 M*/ 335 336 PETSC_EXTERN PetscErrorCode PetscPartitionerCreate_PTScotch(PetscPartitioner part) 337 { 338 PetscPartitioner_PTScotch *p; 339 PetscErrorCode ierr; 340 341 PetscFunctionBegin; 342 PetscValidHeaderSpecific(part, PETSCPARTITIONER_CLASSID, 1); 343 ierr = PetscNewLog(part, &p);CHKERRQ(ierr); 344 part->data = p; 345 346 ierr = MPI_Comm_dup(PetscObjectComm((PetscObject)part),&p->pcomm);CHKERRQ(ierr); 347 p->strategy = 0; 348 p->imbalance = 0.01; 349 350 ierr = PetscPartitionerInitialize_PTScotch(part);CHKERRQ(ierr); 351 ierr = PetscCitationsRegister(PTScotchPartitionerCitation, &PTScotchPartitionerCite);CHKERRQ(ierr); 352 PetscFunctionReturn(0); 353 } 354