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

namespace AMDiS {

13
  ParMetisMesh::ParMetisMesh(Mesh *mesh, MPI::Intracomm *comm, 
14
			     std::map<int, bool>& elementInRank,
15
			     std::map<DegreeOfFreedom, DegreeOfFreedom> *mapLocalGlobal)
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
    int nodeCounter = 0;
    int elementCounter = 0;
    int dow = Global::getGeo(WORLD);

    TraverseStack stack;
28
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
29
    while (elInfo) {
30
      if (elementInRank[elInfo->getElement()->getIndex()])
31
	elementCounter++;      
32
33
34
35

      elInfo = stack.traverseNext(elInfo);
    }

36
    nElements = elementCounter;
37

38
    TEST_EXIT(nElements > 0)("No elements in ParMETIS mesh!\n");
39
40

    // allocate memory
Thomas Witkowski's avatar
Thomas Witkowski committed
41
    eptr = new int[nElements + 1];
Thomas Witkowski's avatar
huh    
Thomas Witkowski committed
42
    eind = new int[nElements * (dim + 1)];
Thomas Witkowski's avatar
Thomas Witkowski committed
43
44
    elmdist = new int[mpiSize + 1];
    elem_p2a = new int[nElements];
45

46
    if (dim == dow)
Thomas Witkowski's avatar
Thomas Witkowski committed
47
      xyz = new float[nElements * dim];
48
49
    else
      xyz = NULL;    
50

Thomas Witkowski's avatar
Thomas Witkowski committed
51
    eptr[0] = 0;
52

Thomas Witkowski's avatar
Thomas Witkowski committed
53
54
55
    int *ptr_eptr = eptr + 1;
    int *ptr_eind = eind;
    float *ptr_xyz = xyz;
56
57
    
    // gather element numbers and create elmdist
58
    mpiComm->Allgather(&nElements, 1, MPI_INT, elmdist + 1, 1, MPI_INT);
59

60
    elmdist[0] = 0;
61
    for (int i = 2; i < mpiSize + 1; i++)
62
      elmdist[i] += elmdist[i - 1];
63
64

    // traverse mesh and fill distributed ParMETIS data
Thomas Witkowski's avatar
Thomas Witkowski committed
65
    DimVec<double> bary(dim, DEFAULT_VALUE, 1.0 / (dim + 1));
66
67
68
69
    WorldVector<double> world;

    elementCounter = 0;

70
    elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL | Mesh::FILL_COORDS);
71
    while (elInfo) {
72
73
74
75
      Element *element = elInfo->getElement();
      int index = element->getIndex();

      // if element in partition
76
      if (elementInRank[index]) {
77
78
79
80
81
	// remember index
	setParMetisIndex(index, elementCounter);
	setAMDiSIndex(elementCounter, index);

	// write eptr entry
Thomas Witkowski's avatar
Thomas Witkowski committed
82
	nodeCounter += dim + 1;
83
84
85
86
	*ptr_eptr = nodeCounter;
	ptr_eptr++;

	// write eind entries (element nodes)
Thomas Witkowski's avatar
Thomas Witkowski committed
87
	for (int i = 0; i < dim + 1; i++) {
88
	  if (mapLocalGlobal)
89
	    *ptr_eind = (*mapLocalGlobal)[element->getDof(i, 0)];
90
	  else
91
	    *ptr_eind = element->getDof(i, 0);
92

93
94
95
96
	  ptr_eind++;
	}

	// write xyz element coordinates
97
	if (ptr_xyz) {
98
	  elInfo->coordToWorld(bary, world);
Thomas Witkowski's avatar
Thomas Witkowski committed
99
	  for (int i = 0; i < dim; i++) {
100
101
102
103
104
105
106
	    *ptr_xyz = static_cast<float>(world[i]); 
	    ptr_xyz++;
	  }
	}

	elementCounter++;
      }
107

108
109
110
111
      elInfo = stack.traverseNext(elInfo);
    }
  }

112

113
114
  ParMetisMesh::~ParMetisMesh()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
115
    if (eptr)
Thomas Witkowski's avatar
Thomas Witkowski committed
116
      delete [] eptr;
117
    
Thomas Witkowski's avatar
Thomas Witkowski committed
118
    if (eind)     
Thomas Witkowski's avatar
Thomas Witkowski committed
119
      delete [] eind;
120
    
121
    if (elmdist)
Thomas Witkowski's avatar
Thomas Witkowski committed
122
      delete [] elmdist;
123
    
Thomas Witkowski's avatar
Thomas Witkowski committed
124
    if (xyz)
Thomas Witkowski's avatar
Thomas Witkowski committed
125
      delete [] xyz;
126
    
Thomas Witkowski's avatar
Thomas Witkowski committed
127
    if (elem_p2a) 
Thomas Witkowski's avatar
Thomas Witkowski committed
128
      delete [] elem_p2a;
129
130
  }

131

132
  ParMetisGraph::ParMetisGraph(ParMetisMesh *parMesh,
133
			       MPI::Intracomm *comm,
134
			       int ncommonnodes)
135
    : parMetisMesh(parMesh)
136
  {
137
138
139
140
141
    FUNCNAME("ParMetisGraph::ParMetisGraph()");

    TEST_EXIT(parMesh)("No ParMetisMesh defined!\n");
    TEST_EXIT(comm)("No MPI communicator defined!\n");

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
161
  ParMetisGraph::~ParMetisGraph()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
162
163
    free(xadj);
    free(adjncy);
164
165
  }

166

167
168
  void ParMetisPartitioner::createPartitionData() 
  {
169
170
    FUNCNAME("ParMetrisPartitioner::createPartitionData()");

171
172
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
173
174
    int nLeaves = mesh->getNumberOfLeaves();
    int elPerRank = nLeaves / mpiSize;
175

176
    // === Create initial partitioning of the AMDiS mesh. ===
177

178
179
    elementInRank.clear();

180
    TraverseStack stack;
181
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
182
    while (elInfo) {
183
184
      Element *element = elInfo->getElement();

185
186
187
188
      if ((element->getIndex() >= mpiRank * elPerRank &&
	   element->getIndex() < (mpiRank + 1) * elPerRank) ||
	  (element->getIndex() >= mpiSize * elPerRank &&
	   mpiRank == mpiSize - 1))
189
	elementInRank[element->getIndex()] = true;
190
      else
191
	elementInRank[element->getIndex()] = false;
192
      
193
194
195
196
      elInfo = stack.traverseNext(elInfo);
    }
  }

197

198
199
200
201
  void ParMetisPartitioner::partition(std::map<int, double> *elemWeights,
				      PartitionMode mode,
				      float itr) 
  {
202
    FUNCNAME("ParMetisPartitioner::partition()");
203

204
    int mpiSize = mpiComm->Get_size();
205
206

    // === create parmetis mesh ===
207
    if (parMetisMesh) 
Thomas Witkowski's avatar
Thomas Witkowski committed
208
      delete parMetisMesh;
209

210
211
    TEST_EXIT_DBG(elementInRank.size() != 0)("Should not happen!\n");

212
    parMetisMesh = new ParMetisMesh(mesh, mpiComm, elementInRank, mapLocalGlobal);
213

214
    int nElements = parMetisMesh->getNumElements();
215
216

    // === create weight array ===
Thomas Witkowski's avatar
Thomas Witkowski committed
217
218
    int *wgts = elemWeights ? new int[nElements] : NULL;
    float *floatWgts = elemWeights ? new float[nElements] : NULL;
219
220
221
    float maxWgt = 0.0;
    float *ptr_floatWgts = floatWgts;

222
    TraverseStack stack;
223
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
224
    while (elInfo) {
225
      int index = elInfo->getElement()->getIndex();
226

227
      if (elementInRank[index]) {
228
229
230
231
232
233
234
235
236
237
238
239
	// 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;
240
    mpiComm->Allreduce(&maxWgt, &tmp, 1, MPI_FLOAT, MPI_MAX);
241
242
243
    maxWgt = tmp;

    // === create dual graph ===
244
    ParMetisGraph parMetisGraph(parMetisMesh, mpiComm);
245
246
247
248
249
250

    // === 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
251

Thomas Witkowski's avatar
Thomas Witkowski committed
252
    float *tpwgts = elemWeights ? new float[mpiSize] : NULL;
253
254
255
    float ubvec = 1.05;
    int options[3] = {0, 0, 0}; // default options
    int edgecut = -1;
Thomas Witkowski's avatar
Thomas Witkowski committed
256
    int *part = new int[nElements];
257

258
    if (elemWeights) {
Thomas Witkowski's avatar
Thomas Witkowski committed
259
260
      // set tpwgts
      for (int i = 0; i < mpiSize; i++)
261
	tpwgts[i] = 1.0 / nparts;
262

263
      float scale = 10000.0 / maxWgt;
Thomas Witkowski's avatar
Thomas Witkowski committed
264
265
      // scale wgts
      for (int i = 0; i < nElements; i++)
266
267
268
	wgts[i] = static_cast<int>(floatWgts[i] * scale);
    }

269
270
    MPI_Comm tmpComm = MPI_Comm(*mpiComm);

271
    switch (mode) {
272
    case INITIAL:
273
      ParMETIS_V3_PartKway(parMetisMesh->getElementDist(),
274
275
			   parMetisGraph.getXAdj(),
			   parMetisGraph.getAdjncy(),
276
			   wgts,
277
			   NULL,
278
			   &wgtflag,
279
280
281
282
283
284
285
286
			   &numflag,
			   &ncon,
			   &nparts,
			   tpwgts,
			   &ubvec,
			   options,
			   &edgecut,
			   part,
287
			   &tmpComm);
288
289
290
      break;
    case ADAPTIVE_REPART:
      {
Thomas Witkowski's avatar
Thomas Witkowski committed
291
292
	int *vsize = new int[nElements];
	for (int i = 0; i < nElements; i++)
293
	  vsize[i] = 1;
294
	ParMETIS_V3_AdaptiveRepart(parMetisMesh->getElementDist(),
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
				   parMetisGraph.getXAdj(),
				   parMetisGraph.getAdjncy(),
				   wgts,
				   NULL,
				   vsize,
				   &wgtflag,
				   &numflag,
				   &ncon,
				   &nparts,
				   tpwgts,
				   &ubvec,
				   &itr,
				   options,
				   &edgecut,
				   part,
310
				   &tmpComm);
311

Thomas Witkowski's avatar
Thomas Witkowski committed
312
	delete [] vsize;
313
314
315
      }
      break;
    case REFINE_PART:
316
      ParMETIS_V3_RefineKway(parMetisMesh->getElementDist(),
317
318
319
320
321
322
323
324
325
326
327
328
329
			     parMetisGraph.getXAdj(),
			     parMetisGraph.getAdjncy(),
			     wgts,
			     NULL,
			     &wgtflag,
			     &numflag,
			     &ncon,
			     &nparts,
			     tpwgts,
			     &ubvec,
			     options,
			     &edgecut,
			     part,
330
			     &tmpComm);
331

332
333
334
335
336
337
338
339
      break;
    default: 
      ERROR_EXIT("unknown partitioning mode\n");
    }

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

340
    if (floatWgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
341
      delete [] floatWgts;
342
    if (wgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
343
      delete [] wgts;
344
    if (tpwgts) 
Thomas Witkowski's avatar
Thomas Witkowski committed
345
346
347
      delete [] tpwgts;

    delete [] part;
348
349
  }

350

351
352
  void ParMetisPartitioner::fillCoarsePartitionVec(std::map<int, int> *partitionVec)
  {
353
354
355
    FUNCNAME("ParMetisPartitioner::fillCoarsePartitionVec()");

    TEST_EXIT_DBG(partitionVec)("no partition vector\n");
356
357
358
359

    partitionVec->clear();

    // update ParMETIS mesh to new partitioning
360
    if (!parMetisMesh)
361
      parMetisMesh = new ParMetisMesh(mesh, mpiComm, elementInRank, mapLocalGlobal);
362

363
364
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
365
    std::vector<int> nPartitionElements(mpiSize);
366
    int *elmdist = parMetisMesh->getElementDist();
Thomas Witkowski's avatar
Thomas Witkowski committed
367

368
    for (int i = 0; i < mpiSize; i++)
369
      nPartitionElements[i] = elmdist[i + 1] - elmdist[i];
370
371

    // === count number of elements ===
372
373
374
    int nElements = 0;
    int localElements = parMetisMesh->getNumElements();
    mpiComm->Allreduce(&localElements, &nElements, 1, MPI_INT, MPI_SUM);
375

376
    std::vector<int> partitionElements(nElements);
377
378

    // distribute partition elements
379
380
    mpiComm->Allgatherv(parMetisMesh->getAMDiSIndices(),
			nPartitionElements[mpiRank], 
381
			MPI_INT, 
382
383
			&(partitionElements[0]), 
			&(nPartitionElements[0]), 
384
385
			elmdist, 
			MPI_INT);
386
387

    // fill partitionVec
Thomas Witkowski's avatar
Thomas Witkowski committed
388
389
    for (int i = 0; i < mpiSize; i++)
      for (int j = 0; j < nPartitionElements[i]; j++)
390
391
392
	(*partitionVec)[partitionElements[elmdist[i] + j]] = i;
  }

393

394
395
  void ParMetisPartitioner::distributePartitioning(int *part) 
  {
396
397
    FUNCNAME("ParMetisPartitioner::distributePartitioning()");

398
399
    int mpiSize = mpiComm->Get_size();
    int mpiRank = mpiComm->Get_rank();
400
    int nElements = parMetisMesh->getNumElements();
401

402
    // nPartitionElements[i] is the number of elements for the i-th partition
Thomas Witkowski's avatar
Thomas Witkowski committed
403
    int *nPartitionElements = new int[mpiSize];
404
    for (int i = 0; i < mpiSize; i++) 
405
      nPartitionElements[i] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
406
    for (int i = 0; i < nElements; i++)
407
      nPartitionElements[part[i]]++;    
408
409

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

413

414
    // sum up partition elements over all ranks
Thomas Witkowski's avatar
Thomas Witkowski committed
415
    int *sumPartitionElements = new int[mpiSize];
416
    mpiComm->Allreduce(nPartitionElements, sumPartitionElements, mpiSize,
417
		       MPI_INT, MPI_SUM);
418
419
    
    // prepare distribution (fill partitionElements with AMDiS indices)
Thomas Witkowski's avatar
Thomas Witkowski committed
420
    int *bufferOffset = new int[mpiSize];
421
    bufferOffset[0] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
422
    for (int i = 1; i < mpiSize; i++)
423
      bufferOffset[i] = bufferOffset[i - 1] + nPartitionElements[i - 1];
424

Thomas Witkowski's avatar
Thomas Witkowski committed
425
426
    int *partitionElements = new int[nElements];
    int **partitionPtr = new int*[mpiSize];
427

428
    for (int i = 0; i < mpiSize; i++)
429
430
      partitionPtr[i] = partitionElements + bufferOffset[i];

431
    sendElements.clear();
432
    for (int i = 0; i < nElements; i++) {
433
      int partition = part[i];
434
      int amdisIndex = parMetisMesh->getAMDiSIndex(i);
435

436
437
438
      if (partition != mpiRank)
	sendElements[partition].push_back(amdisIndex);

439
440
441
442
443
      *(partitionPtr[partition]) = amdisIndex;
      ++(partitionPtr[partition]);
    }

    // all to all: partition elements to rank elements
Thomas Witkowski's avatar
Thomas Witkowski committed
444
445
    int *rankElements = new int[sumPartitionElements[mpiRank]];
    int *recvBufferOffset = new int[mpiSize];
446
    recvBufferOffset[0] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
447
    for (int i = 1; i < mpiSize; i++)
448
      recvBufferOffset[i] = recvBufferOffset[i - 1] + nRankElements[i - 1];
449

450
    mpiComm->Alltoallv(partitionElements, 
451
		       nPartitionElements,
452
453
454
		       bufferOffset,
		       MPI_INT,
		       rankElements,
455
		       nRankElements,
456
457
		       recvBufferOffset,
		       MPI_INT);
458
    
459
460
461
462
    TEST_EXIT(elementInRank.size() != 0)("Should not happen!\n");
    for (std::map<int, bool>::iterator it = elementInRank.begin();
	 it != elementInRank.end(); ++it)
      elementInRank[it->first] = false;
463

464
465
    // Create map which stores for each element index on ther partitioning level
    // if the element is in the partition of this rank.
466
    recvElements.clear();
467
    for (int i = 0; i < mpiSize; i++) {
468
      int *rankStart = rankElements + recvBufferOffset[i];
469
      int *rankEnd = rankStart + nRankElements[i];
470
471
      for (int *rankPtr = rankStart; rankPtr < rankEnd; ++rankPtr) {
	elementInRank[*rankPtr] = true;
472
473
	if (i != mpiRank)
	  recvElements[i].push_back(*rankPtr);
474
475
476
      }
    }

Thomas Witkowski's avatar
Thomas Witkowski committed
477
    delete parMetisMesh;
478
    parMetisMesh = NULL;
479

Thomas Witkowski's avatar
Thomas Witkowski committed
480
481
482
483
484
485
486
    delete [] rankElements;
    delete [] nPartitionElements;
    delete [] nRankElements;
    delete [] sumPartitionElements;
    delete [] partitionElements;
    delete [] partitionPtr;
    delete [] bufferOffset;
Thomas Witkowski's avatar
huh    
Thomas Witkowski committed
487
    delete [] recvBufferOffset;
488
489
490
  }

}