ParMetisPartitioner.cc 14.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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"

#include <queue>

namespace AMDiS {

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

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

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

35
36
37
      if (partitionData && 
	  partitionData->getPartitionStatus() == IN &&
	  partitionData->getLevel() == 0) {
38
39
40
41
42
43
	elementCounter++;
      }

      elInfo = stack.traverseNext(elInfo);
    }

44
    nElements = elementCounter;
45

46
    TEST_EXIT(nElements > 0)("no elements in ParMETIS mesh\n");
47
48

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

Thomas Witkowski's avatar
Thomas Witkowski committed
54
    if (dim == dow) {
Thomas Witkowski's avatar
Thomas Witkowski committed
55
      xyz = new float[nElements * dim];
56
    } else {
Thomas Witkowski's avatar
Thomas Witkowski committed
57
      xyz = NULL;
58
59
    }

Thomas Witkowski's avatar
Thomas Witkowski committed
60
    eptr[0] = 0;
61

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

69
    elmdist[0] = 0;
70
    for (int i = 2; i < mpiSize + 1; i++) {
71
      elmdist[i] += elmdist[i - 1];
72
73
74
    }

    // traverse mesh and fill distributed ParMETIS data
Thomas Witkowski's avatar
Thomas Witkowski committed
75
    DimVec<double> bary(dim, DEFAULT_VALUE, 1.0 / (dim + 1));
76
77
78
79
80
81
82
    WorldVector<double> world;

    elementCounter = 0;

    elInfo = stack.traverseFirst(mesh, -1, 
				 Mesh::CALL_EVERY_EL_PREORDER | 
				 Mesh::FILL_COORDS);
83
    while (elInfo) {
84
85
86
87
88
89
90
91
      Element *element = elInfo->getElement();
      int index = element->getIndex();

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

      // if element in partition
92
93
94
      if (partitionData && 
	  partitionData->getPartitionStatus() == IN &&
	  partitionData->getLevel() == 0) {
95
96
97
98
99
	// remember index
	setParMetisIndex(index, elementCounter);
	setAMDiSIndex(elementCounter, index);

	// write eptr entry
Thomas Witkowski's avatar
Thomas Witkowski committed
100
	nodeCounter += dim + 1;
101
102
103
104
	*ptr_eptr = nodeCounter;
	ptr_eptr++;

	// write eind entries (element nodes)
Thomas Witkowski's avatar
Thomas Witkowski committed
105
	for (int i = 0; i < dim + 1; i++) {
106
107
108
109
110
	  *ptr_eind = element->getDOF(i, 0);
	  ptr_eind++;
	}

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

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

  ParMetisMesh::~ParMetisMesh()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
127
    if (eptr)
Thomas Witkowski's avatar
Thomas Witkowski committed
128
      delete [] eptr;
129
    
Thomas Witkowski's avatar
Thomas Witkowski committed
130
    if (eind)     
Thomas Witkowski's avatar
Thomas Witkowski committed
131
      delete [] eind;
132
    
133
    if (elmdist)
Thomas Witkowski's avatar
Thomas Witkowski committed
134
      delete [] elmdist;
135
    
Thomas Witkowski's avatar
Thomas Witkowski committed
136
    if (xyz)
Thomas Witkowski's avatar
Thomas Witkowski committed
137
      delete [] xyz;
138
    
Thomas Witkowski's avatar
Thomas Witkowski committed
139
    if (elem_p2a) 
Thomas Witkowski's avatar
Thomas Witkowski committed
140
      delete [] elem_p2a;
141
142
  }

143
  ParMetisGraph::ParMetisGraph(ParMetisMesh *parMesh,
144
			       MPI::Comm *comm,
145
			       int ncommonnodes)
146
    : parMetisMesh(parMesh)
147
148
149
  {
    int numflag = 0;

150
151
    if (ncommonnodes == -1) 
      ncommonnodes = parMetisMesh->getDim();
152

153
    MPI_Comm tmpComm = MPI_Comm(*comm);
154

155
156
157
    ParMETIS_V3_Mesh2Dual(parMetisMesh->getElementDist(),
			  parMetisMesh->getElementPtr(),
			  parMetisMesh->getElementInd(),
158
159
			  &numflag,
			  &ncommonnodes,
Thomas Witkowski's avatar
Thomas Witkowski committed
160
161
			  &xadj,
			  &adjncy,
162
			  &tmpComm);
163
164
165
166
  }

  ParMetisGraph::~ParMetisGraph()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
167
168
    free(xadj);
    free(adjncy);
169
170
  }

171

172
173
174
175
176
  void ParMetisPartitioner::deletePartitionData() 
  {
    TraverseStack stack;
    ElInfo *elInfo;
    elInfo = stack.traverseFirst(mesh_, -1, Mesh::CALL_EVERY_EL_PREORDER);
177
    while (elInfo) {
178
179
180
181
182
183
184
      Element *element = elInfo->getElement();
      element->deleteElementData(PARTITION_ED);
      elInfo = stack.traverseNext(elInfo);
    }
  }

  void ParMetisPartitioner::createPartitionData() {
185
186
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
187
188
189
190
191
192
193

    TraverseStack stack;
    ElInfo *elInfo;

    // === create initial partitioning on AMDiS mesh ===
    int totalElementCounter = 0;
    elInfo = stack.traverseFirst(mesh_, -1, Mesh::CALL_LEAF_EL);
194
    while (elInfo) {
195
196
197
198
199
200
      Element *element = elInfo->getElement();

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

      PartitionElementData *elData = 
Thomas Witkowski's avatar
Thomas Witkowski committed
201
	new PartitionElementData(element->getElementData());
202
203
      element->setElementData(elData);

204
      if (totalElementCounter % mpiSize == mpiRank) {
205
206
207
208
209
210
211
212
213
214
215
216
217
218
	elData->setPartitionStatus(IN);
      } else {
	elData->setPartitionStatus(UNDEFINED);
      }
      totalElementCounter++;

      elInfo = stack.traverseNext(elInfo);
    }
  }

  void ParMetisPartitioner::partition(std::map<int, double> *elemWeights,
				      PartitionMode mode,
				      float itr) 
  {
219
    int mpiSize = mpiComm->Get_size();
220
221
222
223
224

    TraverseStack stack;
    ElInfo *elInfo;

    // === create parmetis mesh ===
225
    if (parMetisMesh) 
Thomas Witkowski's avatar
Thomas Witkowski committed
226
227
      delete parMetisMesh;
    parMetisMesh = new ParMetisMesh(mesh_, mpiComm);
228

229
    int nElements = parMetisMesh->getNumElements();
230
231

    // === create weight array ===
Thomas Witkowski's avatar
Thomas Witkowski committed
232
233
    int *wgts = elemWeights ? new int[nElements] : NULL;
    float *floatWgts = elemWeights ? new float[nElements] : NULL;
234
235
236
237
    float maxWgt = 0.0;
    float *ptr_floatWgts = floatWgts;

    elInfo = stack.traverseFirst(mesh_, -1, Mesh::CALL_EVERY_EL_PREORDER);
238
    while (elInfo) {
239
240
241
242
243
244
      Element *element = elInfo->getElement();

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

245
246
247
      if (partitionData &&
	  partitionData->getPartitionStatus() == IN &&
	  partitionData->getLevel() == 0) {
248
249
250
251
252
253
254
255
256
257
258
259
260
261
	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;
262
    mpiComm->Allreduce(&maxWgt, &tmp, 1, MPI_FLOAT, MPI_MAX);
263
264
265
    maxWgt = tmp;

    // === create dual graph ===
266
    ParMetisGraph parMetisGraph(parMetisMesh, mpiComm);
267
268
269
270
271
272

    // === 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
Thomas Witkowski's avatar
Thomas Witkowski committed
273
    float *tpwgts = elemWeights ? new float[mpiSize] : NULL;
274
275
276
    float ubvec = 1.05;
    int options[3] = {0, 0, 0}; // default options
    int edgecut = -1;
Thomas Witkowski's avatar
Thomas Witkowski committed
277
    int *part = new int[nElements];
278
    
279
    if (elemWeights) {
Thomas Witkowski's avatar
Thomas Witkowski committed
280
281
      // set tpwgts
      for (int i = 0; i < mpiSize; i++)
282
	tpwgts[i] = 1.0 / nparts;
283
284

      float scale = 10000 / maxWgt;
Thomas Witkowski's avatar
Thomas Witkowski committed
285
286
      // scale wgts
      for (int i = 0; i < nElements; i++)
287
288
289
	wgts[i] = static_cast<int>(floatWgts[i] * scale);
    }

290
291
    MPI_Comm tmpComm = MPI_Comm(*mpiComm);

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

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

359
    if (floatWgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
360
      delete [] floatWgts;
361
    if (wgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
362
      delete [] wgts;
363
    if (tpwgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
364
365
366
      delete [] tpwgts;

    delete [] part;
367
368
369
370
371
372
373
374
375
  }

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

    partitionVec->clear();

    // update ParMETIS mesh to new partitioning
376
    if (!parMetisMesh) 
Thomas Witkowski's avatar
Thomas Witkowski committed
377
      parMetisMesh = new ParMetisMesh(mesh_, mpiComm);
378

379
380
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
Thomas Witkowski's avatar
Thomas Witkowski committed
381
    int *nPartitionElements = new int[mpiSize];
382
    int *elmdist = parMetisMesh->getElementDist();
Thomas Witkowski's avatar
Thomas Witkowski committed
383

Thomas Witkowski's avatar
Thomas Witkowski committed
384
    for (int i = 0;  i < mpiSize; i++)
385
      nPartitionElements[i] = elmdist[i + 1] - elmdist[i];
386
387

    // === count number of elements ===
388
389
390
    int nElements = 0;
    int localElements = parMetisMesh->getNumElements();
    mpiComm->Allreduce(&localElements, &nElements, 1, MPI_INT, MPI_SUM);
391

Thomas Witkowski's avatar
Thomas Witkowski committed
392
    int *partitionElements = new int[nElements];
393
394

    // distribute partition elements
395
396
    mpiComm->Allgatherv(parMetisMesh->getAMDiSIndices(),
			nPartitionElements[mpiRank], 
397
398
			MPI_INT, 
			partitionElements, 
399
			nPartitionElements, 
400
401
			elmdist, 
			MPI_INT);
402
403

    // fill partitionVec
Thomas Witkowski's avatar
Thomas Witkowski committed
404
405
    for (int i = 0; i < mpiSize; i++)
      for (int j = 0; j < nPartitionElements[i]; j++)
406
407
	(*partitionVec)[partitionElements[elmdist[i] + j]] = i;

Thomas Witkowski's avatar
Thomas Witkowski committed
408
409
    delete [] partitionElements;
    delete [] nPartitionElements;
410
411
412
413
  }

  void ParMetisPartitioner::distributePartitioning(int *part) 
  {
414
415
    int mpiSize = mpiComm->Get_size();
    int mpiRank = mpiComm->Get_rank();
416
    int nElements = parMetisMesh->getNumElements();
417

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

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

    // sum up partition elements over all ranks
Thomas Witkowski's avatar
Thomas Witkowski committed
431
    int *sumPartitionElements = new int[mpiSize];
432
    mpiComm->Allreduce(nPartitionElements, sumPartitionElements, mpiSize,
433
		       MPI_INT, MPI_SUM);
434
435
436

    
    // prepare distribution (fill partitionElements with AMDiS indices)
Thomas Witkowski's avatar
Thomas Witkowski committed
437
    int *bufferOffset = new int[mpiSize];
438
    bufferOffset[0] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
439
    for (int i = 1; i < mpiSize; i++)
440
      bufferOffset[i] = bufferOffset[i - 1] + nPartitionElements[i - 1];
441

Thomas Witkowski's avatar
Thomas Witkowski committed
442
443
    int *partitionElements = new int[nElements];
    int **partitionPtr = new int*[mpiSize];
444

Thomas Witkowski's avatar
Thomas Witkowski committed
445
    for (int i = 0; i < mpiSize; i++)
446
447
      partitionPtr[i] = partitionElements + bufferOffset[i];

448
    for (int i = 0; i < nElements; i++) {
449
      int partition = part[i];
450
      int amdisIndex = parMetisMesh->getAMDiSIndex(i);
451
452
453
454
455
      *(partitionPtr[partition]) = amdisIndex;
      ++(partitionPtr[partition]);
    }

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

462
    mpiComm->Alltoallv(partitionElements, 
463
		       nPartitionElements,
464
465
466
		       bufferOffset,
		       MPI_INT,
		       rankElements,
467
		       nRankElements,
468
469
		       recvBufferOffset,
		       MPI_INT);
470
471
    

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

    TraverseStack stack;
    ElInfo *elInfo = stack.traverseFirst(mesh_, -1, Mesh::CALL_EVERY_EL_PREORDER);
485
    while (elInfo) {
486
487
488
489
490
491
      Element *element = elInfo->getElement();

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

492
      if (partitionData && partitionData->getLevel() == 0) {
493
	int amdisIndex = element->getIndex();
494
	if (elementInPartition[amdisIndex]) {
495
496
497
498
499
500
501
502
503
504
	  partitionData->setPartitionStatus(IN);
	} else {
	  partitionData->setPartitionStatus(OUT);
	}
	descendPartitionData(element);
      }

      elInfo = stack.traverseNext(elInfo);
    }

Thomas Witkowski's avatar
Thomas Witkowski committed
505
    delete parMetisMesh;
506
    parMetisMesh = NULL;
507

Thomas Witkowski's avatar
Thomas Witkowski committed
508
509
510
511
512
513
514
    delete [] rankElements;
    delete [] nPartitionElements;
    delete [] nRankElements;
    delete [] sumPartitionElements;
    delete [] partitionElements;
    delete [] partitionPtr;
    delete [] bufferOffset;
Thomas Witkowski's avatar
huh    
Thomas Witkowski committed
515
    delete [] recvBufferOffset;
516
517
518
519
  }

  void ParMetisPartitioner::descendPartitionData(Element *element) 
  {
520
    if (!element->isLeaf()) {
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
      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;
    ElInfo *elInfo = stack.traverseFirst(mesh_, -1, Mesh::CALL_EVERY_EL_PREORDER);
549
    while (elInfo) {
550
551
552
      Element *element = elInfo->getElement();
      PartitionElementData *partitionData = dynamic_cast<PartitionElementData*>
	(element->getElementData(PARTITION_ED));
553
554
      if (partitionData) {
	if (partitionData->getLevel() == 0) {
555
556
557
558
559
560
561
562
563
564
	  partition = (*(coarseVec))[element->getIndex()];
	}
	if(element->isLeaf()) {
	  (*(fineVec))[element->getIndex()] = partition;
	}
      }
      elInfo = stack.traverseNext(elInfo);
    }
  }
}