Liebe Gitlab-Nutzer, lieber Gitlab-Nutzer,
es ist nun möglich sich mittels des ZIH-Logins/LDAP an unserem Dienst anzumelden. Die Konten der externen Nutzer:innen sind über den Reiter "Standard" erreichbar.
Die Administratoren


Dear Gitlab user,
it is now possible to log in to our service using the ZIH login/LDAP. The accounts of external users can be accessed via the "Standard" tab.
The administrators

ParMetisPartitioner.cc 15 KB
Newer Older
1
#include <queue>
2 3 4 5 6 7 8 9 10 11 12 13
#include "ParMetisPartitioner.h"
#include "Mesh.h"
#include "Traverse.h"
#include "ElInfo.h"
#include "Element.h"
#include "FixVec.h"
#include "PartitionElementData.h"
#include "DOFVector.h"
#include "mpi.h"

namespace AMDiS {

14
  ParMetisMesh::ParMetisMesh(Mesh *mesh, MPI::Intracomm *comm)
Thomas Witkowski's avatar
Thomas Witkowski committed
15 16
    : dim(mesh->getDim()),
      nElements(0),
17
      mpiComm(comm)
18 19
  {
    FUNCNAME("ParMetisMesh::ParMetisMesh()");
20 21

    int mpiSize = mpiComm->Get_size();
22 23 24 25 26
    int nodeCounter = 0;
    int elementCounter = 0;
    int dow = Global::getGeo(WORLD);

    TraverseStack stack;
27
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
28
    while (elInfo) {
29 30
      // get partition data
      PartitionElementData *partitionData = dynamic_cast<PartitionElementData*>
Thomas Witkowski's avatar
Thomas Witkowski committed
31
	(elInfo->getElement()->getElementData(PARTITION_ED));
32

33 34
      if (partitionData && 
	  partitionData->getPartitionStatus() == IN &&
35 36
	  partitionData->getLevel() == 0)
	elementCounter++;      
37 38 39 40

      elInfo = stack.traverseNext(elInfo);
    }

41
    nElements = elementCounter;
42

43
    TEST_EXIT(nElements > 0)("no elements in ParMETIS mesh\n");
44 45

    // allocate memory
Thomas Witkowski's avatar
Thomas Witkowski committed
46
    eptr = new int[nElements + 1];
Thomas Witkowski's avatar
huh  
Thomas Witkowski committed
47
    eind = new int[nElements * (dim + 1)];
Thomas Witkowski's avatar
Thomas Witkowski committed
48 49
    elmdist = new int[mpiSize + 1];
    elem_p2a = new int[nElements];
50

51
    if (dim == dow)
Thomas Witkowski's avatar
Thomas Witkowski committed
52
      xyz = new float[nElements * dim];
53 54
    else
      xyz = NULL;    
55

Thomas Witkowski's avatar
Thomas Witkowski committed
56
    eptr[0] = 0;
57

Thomas Witkowski's avatar
Thomas Witkowski committed
58 59 60
    int *ptr_eptr = eptr + 1;
    int *ptr_eind = eind;
    float *ptr_xyz = xyz;
61 62
    
    // gather element numbers and create elmdist
63
    mpiComm->Allgather(&nElements, 1, MPI_INT, elmdist + 1, 1, MPI_INT);
64

65
    elmdist[0] = 0;
66
    for (int i = 2; i < mpiSize + 1; i++)
67
      elmdist[i] += elmdist[i - 1];
68 69

    // traverse mesh and fill distributed ParMETIS data
Thomas Witkowski's avatar
Thomas Witkowski committed
70
    DimVec<double> bary(dim, DEFAULT_VALUE, 1.0 / (dim + 1));
71 72 73 74 75
    WorldVector<double> world;

    elementCounter = 0;

    elInfo = stack.traverseFirst(mesh, -1, 
76
				 Mesh::CALL_EVERY_EL_PREORDER | Mesh::FILL_COORDS);
77
    while (elInfo) {
78 79 80 81 82 83 84 85
      Element *element = elInfo->getElement();
      int index = element->getIndex();

      // get partition data
      PartitionElementData *partitionData = dynamic_cast<PartitionElementData*>
	(element->getElementData(PARTITION_ED));

      // if element in partition
86 87 88
      if (partitionData && 
	  partitionData->getPartitionStatus() == IN &&
	  partitionData->getLevel() == 0) {
89 90 91 92 93
	// remember index
	setParMetisIndex(index, elementCounter);
	setAMDiSIndex(elementCounter, index);

	// write eptr entry
Thomas Witkowski's avatar
Thomas Witkowski committed
94
	nodeCounter += dim + 1;
95 96 97 98
	*ptr_eptr = nodeCounter;
	ptr_eptr++;

	// write eind entries (element nodes)
Thomas Witkowski's avatar
Thomas Witkowski committed
99
	for (int i = 0; i < dim + 1; i++) {
100 101 102 103 104
	  *ptr_eind = element->getDOF(i, 0);
	  ptr_eind++;
	}

	// write xyz element coordinates
105
	if (ptr_xyz) {
106
	  elInfo->coordToWorld(bary, world);
Thomas Witkowski's avatar
Thomas Witkowski committed
107
	  for (int i = 0; i < dim; i++) {
108 109 110 111 112 113 114 115 116 117 118 119 120
	    *ptr_xyz = static_cast<float>(world[i]); 
	    ptr_xyz++;
	  }
	}

	elementCounter++;
      }
      elInfo = stack.traverseNext(elInfo);
    }
  }

  ParMetisMesh::~ParMetisMesh()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
121
    if (eptr)
Thomas Witkowski's avatar
Thomas Witkowski committed
122
      delete [] eptr;
123
    
Thomas Witkowski's avatar
Thomas Witkowski committed
124
    if (eind)     
Thomas Witkowski's avatar
Thomas Witkowski committed
125
      delete [] eind;
126
    
127
    if (elmdist)
Thomas Witkowski's avatar
Thomas Witkowski committed
128
      delete [] elmdist;
129
    
Thomas Witkowski's avatar
Thomas Witkowski committed
130
    if (xyz)
Thomas Witkowski's avatar
Thomas Witkowski committed
131
      delete [] xyz;
132
    
Thomas Witkowski's avatar
Thomas Witkowski committed
133
    if (elem_p2a) 
Thomas Witkowski's avatar
Thomas Witkowski committed
134
      delete [] elem_p2a;
135 136
  }

137
  ParMetisGraph::ParMetisGraph(ParMetisMesh *parMesh,
138
			       MPI::Intracomm *comm,
139
			       int ncommonnodes)
140
    : parMetisMesh(parMesh)
141 142 143
  {
    int numflag = 0;

144 145
    if (ncommonnodes == -1) 
      ncommonnodes = parMetisMesh->getDim();
146

147
    MPI_Comm tmpComm = MPI_Comm(*comm);
148

149 150 151
    ParMETIS_V3_Mesh2Dual(parMetisMesh->getElementDist(),
			  parMetisMesh->getElementPtr(),
			  parMetisMesh->getElementInd(),
152 153
			  &numflag,
			  &ncommonnodes,
Thomas Witkowski's avatar
Thomas Witkowski committed
154 155
			  &xadj,
			  &adjncy,
156
			  &tmpComm);
157 158 159 160
  }

  ParMetisGraph::~ParMetisGraph()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
161 162
    free(xadj);
    free(adjncy);
163 164
  }

165

166 167 168
  void ParMetisPartitioner::deletePartitionData() 
  {
    TraverseStack stack;
169
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
170
    while (elInfo) {
171 172 173 174 175 176
      Element *element = elInfo->getElement();
      element->deleteElementData(PARTITION_ED);
      elInfo = stack.traverseNext(elInfo);
    }
  }

177 178
  void ParMetisPartitioner::createPartitionData() 
  {
179 180
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
181 182
    int nLeaves = mesh->getNumberOfLeaves();
    int elPerRank = nLeaves / mpiSize;
183

184
    // === Create initial partitioning of the AMDiS mesh. ===
185

186 187
    TraverseStack stack;
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_LEAF_EL);
188
    while (elInfo) {
189 190 191 192 193 194
      Element *element = elInfo->getElement();

      TEST_EXIT(element->getElementData(PARTITION_ED) == NULL)
	("mesh already partitioned\n");

      PartitionElementData *elData = 
Thomas Witkowski's avatar
Thomas Witkowski committed
195
	new PartitionElementData(element->getElementData());
196 197
      element->setElementData(elData);

198 199
      if (element->getIndex() >= mpiRank * elPerRank &&
	  element->getIndex() < (mpiRank + 1) * elPerRank)
200
	elData->setPartitionStatus(IN);
201
      else
202
	elData->setPartitionStatus(UNDEFINED);
203
      
204 205 206 207 208 209 210 211
      elInfo = stack.traverseNext(elInfo);
    }
  }

  void ParMetisPartitioner::partition(std::map<int, double> *elemWeights,
				      PartitionMode mode,
				      float itr) 
  {
212
    FUNCNAME("ParMetisPartitioner::partition()");
213

214
    int mpiSize = mpiComm->Get_size();
215 216

    // === create parmetis mesh ===
217
    if (parMetisMesh) 
Thomas Witkowski's avatar
Thomas Witkowski committed
218
      delete parMetisMesh;
219 220

    parMetisMesh = new ParMetisMesh(mesh, mpiComm);
221

222
    int nElements = parMetisMesh->getNumElements();
223 224

    // === create weight array ===
Thomas Witkowski's avatar
Thomas Witkowski committed
225 226
    int *wgts = elemWeights ? new int[nElements] : NULL;
    float *floatWgts = elemWeights ? new float[nElements] : NULL;
227 228 229
    float maxWgt = 0.0;
    float *ptr_floatWgts = floatWgts;

230 231
    TraverseStack stack;
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
232
    while (elInfo) {
233 234 235 236 237 238
      Element *element = elInfo->getElement();

      // get partition data
      PartitionElementData *partitionData = dynamic_cast<PartitionElementData*>
	(element->getElementData(PARTITION_ED));

239 240 241
      if (partitionData &&
	  partitionData->getPartitionStatus() == IN &&
	  partitionData->getLevel() == 0) {
242

243 244 245 246 247 248 249 250 251 252 253 254 255 256
	int index = element->getIndex();

	// get weight 
	float wgt = static_cast<float>((*elemWeights)[index]);
	maxWgt = max(wgt, maxWgt);

	// write float weight
	*ptr_floatWgts = wgt;
	ptr_floatWgts++;
      }
      elInfo = stack.traverseNext(elInfo);
    }

    float tmp;
257
    mpiComm->Allreduce(&maxWgt, &tmp, 1, MPI_FLOAT, MPI_MAX);
258 259 260
    maxWgt = tmp;

    // === create dual graph ===
261
    ParMetisGraph parMetisGraph(parMetisMesh, mpiComm);
262 263 264 265 266 267

    // === partitioning of dual graph ===
    int wgtflag = elemWeights ? 2 : 0; // weights at vertices only!
    int numflag = 0; // c numbering style!
    int ncon = elemWeights ? 1 : 0; // one weight at each vertex!
    int nparts = mpiSize; // number of partitions
268

Thomas Witkowski's avatar
Thomas Witkowski committed
269
    float *tpwgts = elemWeights ? new float[mpiSize] : NULL;
270 271 272
    float ubvec = 1.05;
    int options[3] = {0, 0, 0}; // default options
    int edgecut = -1;
Thomas Witkowski's avatar
Thomas Witkowski committed
273
    int *part = new int[nElements];
274
    
275
    if (elemWeights) {
Thomas Witkowski's avatar
Thomas Witkowski committed
276 277
      // set tpwgts
      for (int i = 0; i < mpiSize; i++)
278
	tpwgts[i] = 1.0 / nparts;
279

280
      float scale = 10000.0 / maxWgt;
Thomas Witkowski's avatar
Thomas Witkowski committed
281 282
      // scale wgts
      for (int i = 0; i < nElements; i++)
283 284 285
	wgts[i] = static_cast<int>(floatWgts[i] * scale);
    }

286 287
    MPI_Comm tmpComm = MPI_Comm(*mpiComm);

288 289
    switch(mode) {
    case INITIAL:
290
      ParMETIS_V3_PartKway(parMetisMesh->getElementDist(),
291 292
			   parMetisGraph.getXAdj(),
			   parMetisGraph.getAdjncy(),
293
			   wgts,
294
			   NULL,
295
			   &wgtflag,
296 297 298 299 300 301 302 303
			   &numflag,
			   &ncon,
			   &nparts,
			   tpwgts,
			   &ubvec,
			   options,
			   &edgecut,
			   part,
304
			   &tmpComm);
305 306 307
      break;
    case ADAPTIVE_REPART:
      {
Thomas Witkowski's avatar
Thomas Witkowski committed
308 309
	int *vsize = new int[nElements];
	for (int i = 0; i < nElements; i++)
310
	  vsize[i] = 1;
311
	ParMETIS_V3_AdaptiveRepart(parMetisMesh->getElementDist(),
312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
				   parMetisGraph.getXAdj(),
				   parMetisGraph.getAdjncy(),
				   wgts,
				   NULL,
				   vsize,
				   &wgtflag,
				   &numflag,
				   &ncon,
				   &nparts,
				   tpwgts,
				   &ubvec,
				   &itr,
				   options,
				   &edgecut,
				   part,
327
				   &tmpComm);
Thomas Witkowski's avatar
Thomas Witkowski committed
328
	delete [] vsize;
329 330 331
      }
      break;
    case REFINE_PART:
332
      ParMETIS_V3_RefineKway(parMetisMesh->getElementDist(),
333 334 335 336 337 338 339 340 341 342 343 344 345
			     parMetisGraph.getXAdj(),
			     parMetisGraph.getAdjncy(),
			     wgts,
			     NULL,
			     &wgtflag,
			     &numflag,
			     &ncon,
			     &nparts,
			     tpwgts,
			     &ubvec,
			     options,
			     &edgecut,
			     part,
346
			     &tmpComm);
347 348 349 350 351 352 353 354
      break;
    default: 
      ERROR_EXIT("unknown partitioning mode\n");
    }

    // === distribute new partition data ===
    distributePartitioning(part);

355
    if (floatWgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
356
      delete [] floatWgts;
357
    if (wgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
358
      delete [] wgts;
359
    if (tpwgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
360 361 362
      delete [] tpwgts;

    delete [] part;
363 364 365 366 367 368 369 370 371
  }

  void ParMetisPartitioner::fillCoarsePartitionVec(std::map<int, int> *partitionVec)
  {
    TEST_EXIT(partitionVec)("no partition vector\n");

    partitionVec->clear();

    // update ParMETIS mesh to new partitioning
372 373
    if (!parMetisMesh)
      parMetisMesh = new ParMetisMesh(mesh, mpiComm);    
374

375 376
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
Thomas Witkowski's avatar
Thomas Witkowski committed
377
    int *nPartitionElements = new int[mpiSize];
378
    int *elmdist = parMetisMesh->getElementDist();
Thomas Witkowski's avatar
Thomas Witkowski committed
379

Thomas Witkowski's avatar
Thomas Witkowski committed
380
    for (int i = 0;  i < mpiSize; i++)
381
      nPartitionElements[i] = elmdist[i + 1] - elmdist[i];
382 383

    // === count number of elements ===
384 385 386
    int nElements = 0;
    int localElements = parMetisMesh->getNumElements();
    mpiComm->Allreduce(&localElements, &nElements, 1, MPI_INT, MPI_SUM);
387

Thomas Witkowski's avatar
Thomas Witkowski committed
388
    int *partitionElements = new int[nElements];
389 390

    // distribute partition elements
391 392
    mpiComm->Allgatherv(parMetisMesh->getAMDiSIndices(),
			nPartitionElements[mpiRank], 
393 394
			MPI_INT, 
			partitionElements, 
395
			nPartitionElements, 
396 397
			elmdist, 
			MPI_INT);
398 399

    // fill partitionVec
Thomas Witkowski's avatar
Thomas Witkowski committed
400 401
    for (int i = 0; i < mpiSize; i++)
      for (int j = 0; j < nPartitionElements[i]; j++)
402 403
	(*partitionVec)[partitionElements[elmdist[i] + j]] = i;

Thomas Witkowski's avatar
Thomas Witkowski committed
404 405
    delete [] partitionElements;
    delete [] nPartitionElements;
406 407 408 409
  }

  void ParMetisPartitioner::distributePartitioning(int *part) 
  {
410 411
    FUNCNAME("ParMetisPartitioner::distributePartitioning()");

412 413
    int mpiSize = mpiComm->Get_size();
    int mpiRank = mpiComm->Get_rank();
414
    int nElements = parMetisMesh->getNumElements();
415

416
    // nPartitionElements[i] is the number of elements for the i-th partition
Thomas Witkowski's avatar
Thomas Witkowski committed
417
    int *nPartitionElements = new int[mpiSize];
418
    for (int i = 0; i < mpiSize; i++) 
419
      nPartitionElements[i] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
420
    for (int i = 0; i < nElements; i++)
421
      nPartitionElements[part[i]]++;
422 423

    // collect number of partition elements from all ranks for this rank
Thomas Witkowski's avatar
Thomas Witkowski committed
424
    int *nRankElements = new int[mpiSize];
425
    mpiComm->Alltoall(nPartitionElements, 1, MPI_INT, nRankElements, 1, MPI_INT);
426 427

    // sum up partition elements over all ranks
Thomas Witkowski's avatar
Thomas Witkowski committed
428
    int *sumPartitionElements = new int[mpiSize];
429
    mpiComm->Allreduce(nPartitionElements, sumPartitionElements, mpiSize,
430
		       MPI_INT, MPI_SUM);
431 432
    
    // prepare distribution (fill partitionElements with AMDiS indices)
Thomas Witkowski's avatar
Thomas Witkowski committed
433
    int *bufferOffset = new int[mpiSize];
434
    bufferOffset[0] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
435
    for (int i = 1; i < mpiSize; i++)
436
      bufferOffset[i] = bufferOffset[i - 1] + nPartitionElements[i - 1];
437

Thomas Witkowski's avatar
Thomas Witkowski committed
438 439
    int *partitionElements = new int[nElements];
    int **partitionPtr = new int*[mpiSize];
440

Thomas Witkowski's avatar
Thomas Witkowski committed
441
    for (int i = 0; i < mpiSize; i++)
442 443
      partitionPtr[i] = partitionElements + bufferOffset[i];

444
    for (int i = 0; i < nElements; i++) {
445
      int partition = part[i];
446
      int amdisIndex = parMetisMesh->getAMDiSIndex(i);
447 448 449 450 451
      *(partitionPtr[partition]) = amdisIndex;
      ++(partitionPtr[partition]);
    }

    // all to all: partition elements to rank elements
Thomas Witkowski's avatar
Thomas Witkowski committed
452 453
    int *rankElements = new int[sumPartitionElements[mpiRank]];
    int *recvBufferOffset = new int[mpiSize];
454
    recvBufferOffset[0] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
455
    for (int i = 1; i < mpiSize; i++)
456
      recvBufferOffset[i] = recvBufferOffset[i - 1] + nRankElements[i - 1];
457

458
    mpiComm->Alltoallv(partitionElements, 
459
		       nPartitionElements,
460 461 462
		       bufferOffset,
		       MPI_INT,
		       rankElements,
463
		       nRankElements,
464 465
		       recvBufferOffset,
		       MPI_INT);
466 467
    

468 469
    // Create map which stores for each element index on ther partitioning level
    // if the element is in the partition of this rank.
470
    std::map<int, bool> elementInPartition;
471
    for (int i = 0; i < mpiSize; i++) {
472
      int *rankStart = rankElements + recvBufferOffset[i];
473
      int *rankEnd = rankStart + nRankElements[i];
474
      for (int *rankPtr = rankStart; rankPtr < rankEnd; ++rankPtr)
475 476 477 478
	elementInPartition[*rankPtr] = true;
    }

    TraverseStack stack;
479
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
480
    while (elInfo) {
481 482 483 484 485 486
      Element *element = elInfo->getElement();

      // get partition data
      PartitionElementData *partitionData = dynamic_cast<PartitionElementData*>
	(element->getElementData(PARTITION_ED));

487
      if (partitionData && partitionData->getLevel() == 0) {
488
	int amdisIndex = element->getIndex();
489
	if (elementInPartition[amdisIndex])
490
	  partitionData->setPartitionStatus(IN);
491
	else
492
	  partitionData->setPartitionStatus(OUT);
493
	
494 495 496 497 498 499
	descendPartitionData(element);
      }

      elInfo = stack.traverseNext(elInfo);
    }

Thomas Witkowski's avatar
Thomas Witkowski committed
500
    delete parMetisMesh;
501
    parMetisMesh = NULL;
502

Thomas Witkowski's avatar
Thomas Witkowski committed
503 504 505 506 507 508 509
    delete [] rankElements;
    delete [] nPartitionElements;
    delete [] nRankElements;
    delete [] sumPartitionElements;
    delete [] partitionElements;
    delete [] partitionPtr;
    delete [] bufferOffset;
Thomas Witkowski's avatar
huh  
Thomas Witkowski committed
510
    delete [] recvBufferOffset;
511 512 513 514
  }

  void ParMetisPartitioner::descendPartitionData(Element *element) 
  {
515 516
    FUNCNAME("ParMetisPartitioner::descendPartitionData()");

517
    if (!element->isLeaf()) {
518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
      Element *child0 = element->getChild(0);
      Element *child1 = element->getChild(1);

      // get partition data
      PartitionElementData *parentData = dynamic_cast<PartitionElementData*>
	(element->getElementData(PARTITION_ED));
      PartitionElementData *child0Data = dynamic_cast<PartitionElementData*>
	(child0->getElementData(PARTITION_ED));
      PartitionElementData *child1Data = dynamic_cast<PartitionElementData*>
	(child1->getElementData(PARTITION_ED));
      
      TEST_EXIT(parentData && child0Data && child1Data)("no partition data\n");

      child0Data->setPartitionStatus(parentData->getPartitionStatus());
      child1Data->setPartitionStatus(parentData->getPartitionStatus());

      descendPartitionData(child0);
      descendPartitionData(child1);
    }
  }


  void ParMetisPartitioner::fillLeafPartitionVec(std::map<int, int> *coarseVec,
						 std::map<int, int> *fineVec)
  {
    int partition = -1;
    TraverseStack stack;
545
    ElInfo *elInfo = stack.traverseFirst(mesh, -1, Mesh::CALL_EVERY_EL_PREORDER);
546
    while (elInfo) {
547 548 549
      Element *element = elInfo->getElement();
      PartitionElementData *partitionData = dynamic_cast<PartitionElementData*>
	(element->getElementData(PARTITION_ED));
550
      if (partitionData) {
551
	if (partitionData->getLevel() == 0)
552
	  partition = (*(coarseVec))[element->getIndex()];
553
	if (element->isLeaf())
554 555 556 557 558 559
	  (*(fineVec))[element->getIndex()] = partition;
      }
      elInfo = stack.traverseNext(elInfo);
    }
  }
}