ParMetisPartitioner.cc 12.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
//
// Software License for AMDiS
//
// Copyright (c) 2010 Dresden University of Technology 
// All rights reserved.
// Authors: Simon Vey, Thomas Witkowski et al.
//
// This file is part of AMDiS
//
// See also license.opensource.txt in the distribution.


13
#include <queue>
14
15
16
17
18
19
20
21
22
23
24
#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 {

25
  ParMetisMesh::ParMetisMesh(Mesh *mesh, MPI::Intracomm *comm, 
26
			     std::map<int, bool>& elementInRank,
27
			     std::map<DegreeOfFreedom, DegreeOfFreedom> *mapLocalGlobal)
Thomas Witkowski's avatar
Thomas Witkowski committed
28
29
    : dim(mesh->getDim()),
      nElements(0),
30
      mpiComm(comm)
31
32
  {
    FUNCNAME("ParMetisMesh::ParMetisMesh()");
33
34

    int mpiSize = mpiComm->Get_size();
35
36
37
38
39
    int nodeCounter = 0;
    int elementCounter = 0;
    int dow = Global::getGeo(WORLD);

    TraverseStack stack;
40
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
41
    while (elInfo) {
42
      if (elementInRank[elInfo->getElement()->getIndex()])
43
	elementCounter++;      
44
45
46
47

      elInfo = stack.traverseNext(elInfo);
    }

48
    nElements = elementCounter;
49

50
    TEST_EXIT(nElements > 0)("No elements in ParMETIS mesh!\n");
51
52

    // allocate memory
Thomas Witkowski's avatar
Thomas Witkowski committed
53
    eptr = new int[nElements + 1];
Thomas Witkowski's avatar
huh    
Thomas Witkowski committed
54
    eind = new int[nElements * (dim + 1)];
Thomas Witkowski's avatar
Thomas Witkowski committed
55
56
    elmdist = new int[mpiSize + 1];
    elem_p2a = new int[nElements];
57

58
    if (dim == dow)
Thomas Witkowski's avatar
Thomas Witkowski committed
59
      xyz = new float[nElements * dim];
60
61
    else
      xyz = NULL;    
62

Thomas Witkowski's avatar
Thomas Witkowski committed
63
    eptr[0] = 0;
64

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

72
    elmdist[0] = 0;
73
    for (int i = 2; i < mpiSize + 1; i++)
74
      elmdist[i] += elmdist[i - 1];
75
76

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

    elementCounter = 0;

82
    elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL | Mesh::FILL_COORDS);
83
    while (elInfo) {
84
85
86
87
      Element *element = elInfo->getElement();
      int index = element->getIndex();

      // if element in partition
88
      if (elementInRank[index]) {
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
	  if (mapLocalGlobal) {
	    TEST_EXIT_DBG(mapLocalGlobal->count(element->getDof(i, 0)))
	      ("Should not happen!\n");
103
	    *ptr_eind = (*mapLocalGlobal)[element->getDof(i, 0)];
104
	  } else {
105
	    *ptr_eind = element->getDof(i, 0);
106
	  }
107

108
109
110
111
	  ptr_eind++;
	}

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

	elementCounter++;
      }
122

123
124
125
126
      elInfo = stack.traverseNext(elInfo);
    }
  }

127

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

146

147
  ParMetisGraph::ParMetisGraph(ParMetisMesh *parMesh,
148
			       MPI::Intracomm *comm,
149
			       int ncommonnodes)
150
    : parMetisMesh(parMesh)
151
  {
152
153
154
155
156
    FUNCNAME("ParMetisGraph::ParMetisGraph()");

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

157
158
    int numflag = 0;

159
160
    if (ncommonnodes == -1) 
      ncommonnodes = parMetisMesh->getDim();
161

162
    MPI_Comm tmpComm = MPI_Comm(*comm);
163

164
165
166
    ParMETIS_V3_Mesh2Dual(parMetisMesh->getElementDist(),
			  parMetisMesh->getElementPtr(),
			  parMetisMesh->getElementInd(),
167
168
			  &numflag,
			  &ncommonnodes,
Thomas Witkowski's avatar
Thomas Witkowski committed
169
170
			  &xadj,
			  &adjncy,
171
			  &tmpComm);
172
173
  }

174

175
176
  ParMetisGraph::~ParMetisGraph()
  {
Thomas Witkowski's avatar
Thomas Witkowski committed
177
178
    free(xadj);
    free(adjncy);
179
180
  }

181

182
183
  void ParMetisPartitioner::createPartitionData() 
  {
184
185
    FUNCNAME("ParMetrisPartitioner::createPartitionData()");

186
187
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
188
189
    int nLeaves = mesh->getNumberOfLeaves();
    int elPerRank = nLeaves / mpiSize;
190

191
    // === Create initial partitioning of the AMDiS mesh. ===
192

193
194
    elementInRank.clear();

195
    TraverseStack stack;
196
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
197
    while (elInfo) {
198
199
      Element *element = elInfo->getElement();

200
201
202
203
      if ((element->getIndex() >= mpiRank * elPerRank &&
	   element->getIndex() < (mpiRank + 1) * elPerRank) ||
	  (element->getIndex() >= mpiSize * elPerRank &&
	   mpiRank == mpiSize - 1))
204
	elementInRank[element->getIndex()] = true;
205
      else
206
	elementInRank[element->getIndex()] = false;
207
      
208
209
210
211
      elInfo = stack.traverseNext(elInfo);
    }
  }

212

213
  void ParMetisPartitioner::partition(std::map<int, double> &elemWeights,
214
215
216
				      PartitionMode mode,
				      float itr) 
  {
217
    FUNCNAME("ParMetisPartitioner::partition()");
218

219
    int mpiSize = mpiComm->Get_size();
220
221

    // === create parmetis mesh ===
222
    if (parMetisMesh) 
Thomas Witkowski's avatar
Thomas Witkowski committed
223
      delete parMetisMesh;
224

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

227
    parMetisMesh = new ParMetisMesh(mesh, mpiComm, elementInRank, mapLocalGlobal);
228

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

    // === create weight array ===
232
233
234
    std::vector<int> wgts(nElements);
    std::vector<float> floatWgts(nElements);
    unsigned int floatWgtsPos = 0;
235
236
    float maxWgt = 0.0;

237
    TraverseStack stack;
238
    ElInfo *elInfo = stack.traverseFirst(mesh, 0, Mesh::CALL_EL_LEVEL);
239
    while (elInfo) {
240
      int index = elInfo->getElement()->getIndex();
241

242
      if (elementInRank[index]) {
243
	// get weight 
244
	float wgt = static_cast<float>(elemWeights[index]);
245
246
247
	maxWgt = max(wgt, maxWgt);

	// write float weight
248
249
	TEST_EXIT_DBG(floatWgtsPos < floatWgts.size())("Should not happen!\n");
	floatWgts[floatWgtsPos++] = wgt;
250
251
252
253
      }
      elInfo = stack.traverseNext(elInfo);
    }

254
255
    TEST_EXIT_DBG(floatWgtsPos == floatWgts.size())("Should not happen!\n");

256
    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

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

269
    std::vector<float> tpwgts(mpiSize);
270
    float ubvec = 1.05;
271
    int options[4] = {0, 0, 15, 1}; // default options
272
    int edgecut = -1;
273
    std::vector<int> part(nElements);
274

275
276
277
278
279
280
281
282
    // set tpwgts
    for (int i = 0; i < mpiSize; i++)
      tpwgts[i] = 1.0 / nparts;
    
    float scale = 10000.0 / maxWgt;
    // scale wgts
    for (int i = 0; i < nElements; i++)
      wgts[i] = static_cast<int>(floatWgts[i] * scale);
283

284
285
    MPI_Comm tmpComm = MPI_Comm(*mpiComm);

286
    switch (mode) {
287
    case INITIAL:
288
      ParMETIS_V3_PartKway(parMetisMesh->getElementDist(),
289
290
			   parMetisGraph.getXAdj(),
			   parMetisGraph.getAdjncy(),
291
			   &(wgts[0]),
292
			   NULL,
293
			   &wgtflag,
294
295
296
			   &numflag,
			   &ncon,
			   &nparts,
297
			   &(tpwgts[0]),
298
299
300
			   &ubvec,
			   options,
			   &edgecut,
301
			   &(part[0]),
302
			   &tmpComm);
303
304
305
      break;
    case ADAPTIVE_REPART:
      {
306
	std::vector<int> vsize(nElements);
Thomas Witkowski's avatar
Thomas Witkowski committed
307
	for (int i = 0; i < nElements; i++)
308
309
	  vsize[i] = static_cast<int>(floatWgts[i]);

310
	ParMETIS_V3_AdaptiveRepart(parMetisMesh->getElementDist(),
311
312
				   parMetisGraph.getXAdj(),
				   parMetisGraph.getAdjncy(),
313
				   &(wgts[0]),
314
				   NULL,
315
				   &(vsize[0]),
316
317
318
319
				   &wgtflag,
				   &numflag,
				   &ncon,
				   &nparts,
320
				   &(tpwgts[0]),
321
322
323
324
				   &ubvec,
				   &itr,
				   options,
				   &edgecut,
325
				   &(part[0]),
326
				   &tmpComm);
327
328
329
      }
      break;
    case REFINE_PART:
330
      ParMETIS_V3_RefineKway(parMetisMesh->getElementDist(),
331
332
			     parMetisGraph.getXAdj(),
			     parMetisGraph.getAdjncy(),
333
			     &(wgts[0]),
334
335
336
337
338
			     NULL,
			     &wgtflag,
			     &numflag,
			     &ncon,
			     &nparts,
339
			     &(tpwgts[0]),
340
341
342
			     &ubvec,
			     options,
			     &edgecut,
343
			     &(part[0]),
344
			     &tmpComm);
345

346
347
348
349
350
351
      break;
    default: 
      ERROR_EXIT("unknown partitioning mode\n");
    }

    // === distribute new partition data ===
352
    distributePartitioning(&(part[0]));
353
354
  }

355

356
357
  void ParMetisPartitioner::fillCoarsePartitionVec(std::map<int, int> *partitionVec)
  {
358
359
360
    FUNCNAME("ParMetisPartitioner::fillCoarsePartitionVec()");

    TEST_EXIT_DBG(partitionVec)("no partition vector\n");
361
362
363
364

    partitionVec->clear();

    // update ParMETIS mesh to new partitioning
365
    if (!parMetisMesh)
366
      parMetisMesh = new ParMetisMesh(mesh, mpiComm, elementInRank, mapLocalGlobal);
367

368
369
    int mpiRank = mpiComm->Get_rank();
    int mpiSize = mpiComm->Get_size();
370
    std::vector<int> nPartitionElements(mpiSize);
371
    int *elmdist = parMetisMesh->getElementDist();
Thomas Witkowski's avatar
Thomas Witkowski committed
372

373
    for (int i = 0; i < mpiSize; i++)
374
      nPartitionElements[i] = elmdist[i + 1] - elmdist[i];
375
376

    // === count number of elements ===
377
378
379
    int nElements = 0;
    int localElements = parMetisMesh->getNumElements();
    mpiComm->Allreduce(&localElements, &nElements, 1, MPI_INT, MPI_SUM);
380

381
    std::vector<int> partitionElements(nElements);
382
383

    // distribute partition elements
384
385
    mpiComm->Allgatherv(parMetisMesh->getAMDiSIndices(),
			nPartitionElements[mpiRank], 
386
			MPI_INT, 
387
388
			&(partitionElements[0]), 
			&(nPartitionElements[0]), 
389
390
			elmdist, 
			MPI_INT);
391
392

    // fill partitionVec
Thomas Witkowski's avatar
Thomas Witkowski committed
393
394
    for (int i = 0; i < mpiSize; i++)
      for (int j = 0; j < nPartitionElements[i]; j++)
395
396
397
	(*partitionVec)[partitionElements[elmdist[i] + j]] = i;
  }

398

399
400
  void ParMetisPartitioner::distributePartitioning(int *part) 
  {
401
402
    FUNCNAME("ParMetisPartitioner::distributePartitioning()");

403
404
    int mpiSize = mpiComm->Get_size();
    int mpiRank = mpiComm->Get_rank();
405
    int nElements = parMetisMesh->getNumElements();
406

407
    // nPartitionElements[i] is the number of elements for the i-th partition
Thomas Witkowski's avatar
Thomas Witkowski committed
408
    int *nPartitionElements = new int[mpiSize];
409
    for (int i = 0; i < mpiSize; i++) 
410
      nPartitionElements[i] = 0;
Thomas Witkowski's avatar
Thomas Witkowski committed
411
    for (int i = 0; i < nElements; i++)
412
      nPartitionElements[part[i]]++;    
413
414

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

418

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

Thomas Witkowski's avatar
Thomas Witkowski committed
430
431
    int *partitionElements = new int[nElements];
    int **partitionPtr = new int*[mpiSize];
432

433
    for (int i = 0; i < mpiSize; i++)
434
435
      partitionPtr[i] = partitionElements + bufferOffset[i];

436
    sendElements.clear();
437
    for (int i = 0; i < nElements; i++) {
438
      int partition = part[i];
439
      int amdisIndex = parMetisMesh->getAMDiSIndex(i);
440

441
442
443
      if (partition != mpiRank)
	sendElements[partition].push_back(amdisIndex);

444
445
446
447
448
      *(partitionPtr[partition]) = amdisIndex;
      ++(partitionPtr[partition]);
    }

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

455
    mpiComm->Alltoallv(partitionElements, 
456
		       nPartitionElements,
457
458
459
		       bufferOffset,
		       MPI_INT,
		       rankElements,
460
		       nRankElements,
461
462
		       recvBufferOffset,
		       MPI_INT);
463
    
464
465
466
467
    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;
468

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

Thomas Witkowski's avatar
Thomas Witkowski committed
482
    delete parMetisMesh;
483
    parMetisMesh = NULL;
484

Thomas Witkowski's avatar
Thomas Witkowski committed
485
486
487
488
489
490
491
    delete [] rankElements;
    delete [] nPartitionElements;
    delete [] nRankElements;
    delete [] sumPartitionElements;
    delete [] partitionElements;
    delete [] partitionPtr;
    delete [] bufferOffset;
Thomas Witkowski's avatar
huh    
Thomas Witkowski committed
492
    delete [] recvBufferOffset;
493
494
495
  }

}