metis_util.hpp 9.44 KB
Newer Older
incardon's avatar
incardon committed
1
2
3
4
5
6
7
8
9
10
11
12
/*
 * metis_util.hpp
 *
 *  Created on: Nov 21, 2014
 *      Author: Pietro Incardona
 */

#ifndef METIS_UTIL_HPP
#define METIS_UTIL_HPP

#include <iostream>
#include "metis.h"
13
#include "SubdomainGraphNodes.hpp"
14
#include "VTKWriter/VTKWriter.hpp"
incardon's avatar
incardon committed
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*! \brief Metis graph structure
 *
 * Metis graph structure
 *
 */
struct Metis_graph
{
	//! The number of vertices in the graph
	idx_t * nvtxs;

	//! number of balancing constrains
	//! more practical, are the number of weights for each vertex
	//! PS even we you specify vwgt == NULL ncon must be set at leat to
	//! one
	idx_t * ncon;

	//! For each vertex it store the adjacency lost start for the vertex i
	idx_t * xadj;

	//! For each vertex it store a list of all neighborhood vertex
	idx_t * adjncy;

	//! Array that store the weight for each vertex
	idx_t * vwgt;

	//! Array of the vertex size, basically is the total communication amount
	idx_t * vsize;
	//! The weight of the edge
	idx_t * adjwgt;
	//! number of part to partition the graph
	idx_t * nparts;
	//! Desired weight for each partition (one for each constrain)
	real_t * tpwgts;
	//! For each partition load imbalance tollerated
	real_t * ubvec;
	//! Additional option for the graph partitioning
	idx_t * options;
	//! return the total comunication cost for each partition
	idx_t * objval;
	//! Is a output vector containing the partition for each vertex
	idx_t * part;
};

//! Balance communication and computation
#define BALANCE_CC 1
//! Balance communication computation and memory
#define BALANCE_CCM 2
//! Balance computation and comunication and others
#define BALANCE_CC_O(c) c+1

/*! \brief Helper class to define Metis graph
 *
 * \tparam graph structure that store the graph
 *
 */

template<typename Graph>
class Metis
{
incardon's avatar
incardon committed
75
	//! Graph in metis reppresentation
incardon's avatar
incardon committed
76
77
	Metis_graph Mg;

incardon's avatar
incardon committed
78
	//! Original graph
incardon's avatar
incardon committed
79
80
	Graph & g;

incardon's avatar
incardon committed
81
82
	//! indicate how many time decompose/refine/re-decompose has been called
	size_t n_dec;
incardon's avatar
incardon committed
83
84
85

	//! Distribution tolerance
	real_t dist_tol = 1.05;
86

incardon's avatar
incardon committed
87
88
89
90
91
92
93
94
95
	/*! \brief Construct Adjacency list
	 *
	 * \param g Graph
	 *
	 */
	void constructAdjList(Graph & g)
	{
		// create xadj and adjlist

96
97
		// create xadj, adjlist, vwgt, adjwgt and vsize
		Mg.xadj = new idx_t[g.getNVertex() + 1];
incardon's avatar
incardon committed
98
99
		Mg.adjncy = new idx_t[g.getNEdge()];

100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
		//! starting point in the adjacency list
		size_t prev = 0;

		// actual position
		size_t id = 0;

		// for each vertex calculate the position of the starting point in the adjacency list
		for (size_t i = 0; i < g.getNVertex(); i++)
		{
			// Calculate the starting point in the adjacency list
			Mg.xadj[id] = prev;

			// Create the adjacency list
			for (size_t s = 0; s < g.getNChilds(i); s++)
			{
				Mg.adjncy[prev + s] = g.getChild(i, s);
			}

			// update the position for the next vertex
			prev += g.getNChilds(i);

			id++;
		}

		// Fill the last point
		Mg.xadj[id] = prev;
	}

	/*! \brief Construct Adjacency list
	 *
	 * \param g Graph
	 *
	 */
	void constructAdjListWithWeights(Graph & g)
	{
		// create xadj, adjlist, vwgt, adjwgt and vsize
		Mg.xadj = new idx_t[g.getNVertex() + 1];
		Mg.adjncy = new idx_t[g.getNEdge()];
		Mg.vwgt = new idx_t[g.getNVertex()];
		Mg.adjwgt = new idx_t[g.getNEdge()];
		Mg.vsize = new idx_t[g.getNVertex()];
incardon's avatar
incardon committed
141
142
143
144
145
146
147
148

		//! starting point in the adjacency list
		size_t prev = 0;

		// actual position
		size_t id = 0;

		// for each vertex calculate the position of the starting point in the adjacency list
149
		for (size_t i = 0; i < g.getNVertex(); i++)
incardon's avatar
incardon committed
150
		{
151
152
			// Add weight to vertex and migration cost
			Mg.vwgt[i] = g.vertex(i).template get<nm_v::computation>();
incardon's avatar
incardon committed
153
			Mg.vwgt[i] = (Mg.vwgt[i] == 0)?1:Mg.vwgt[i];
154
			Mg.vsize[i] = g.vertex(i).template get<nm_v::migration>();
155
			Mg.vsize[i] = (Mg.vsize[i] == 0)?1:Mg.vsize[i];
156

incardon's avatar
incardon committed
157
158
159
160
			// Calculate the starting point in the adjacency list
			Mg.xadj[id] = prev;

			// Create the adjacency list
161
162
163
164
			for (size_t s = 0; s < g.getNChilds(i); s++)
			{
				Mg.adjncy[prev + s] = g.getChild(i, s);

165
				// zero values on Metis are dangerous
tonynsyde's avatar
tonynsyde committed
166
				Mg.adjwgt[prev + s] = g.getChildEdge(i, s).template get<nm_e::communication>();
167
				Mg.adjwgt[prev + s] = (Mg.adjwgt[prev + s] == 0)?1:Mg.adjwgt[prev + s];
168
			}
incardon's avatar
incardon committed
169
170

			// update the position for the next vertex
171
			prev += g.getNChilds(i);
incardon's avatar
incardon committed
172
173
174
175
176
177
178
179
180
181

			id++;
		}

		// Fill the last point
		Mg.xadj[id] = prev;
	}

public:

182
183
184
185
186
187
188
189
190
	/*! \brief Constructor
	 *
	 * Construct a metis graph from Graph_CSR
	 *
	 * \param g Graph we want to convert to decompose
	 * \param nc number of partitions
	 * \param useWeights tells if weights are used or not
	 *
	 */
incardon's avatar
incardon committed
191
	Metis(Graph & g, size_t nc, bool useWeights)
incardon's avatar
incardon committed
192
	:g(g),n_dec(0)
193
	{
incardon's avatar
incardon committed
194
		initMetisGraph(nc,useWeights);
195
196
	}

incardon's avatar
incardon committed
197
198
199
200
201
202
203
204
	/*! \brief Constructor
	 *
	 * Construct a metis graph from Graph_CSR
	 *
	 * \param g Graph we want to convert to decompose
	 * \param nc number of partitions
	 *
	 */
incardon's avatar
incardon committed
205
206
	Metis(Graph & g, size_t nc)
	:g(g),n_dec(0)
incardon's avatar
incardon committed
207
	{
incardon's avatar
incardon committed
208
209
210
211
212
213
214
215
216
217
218
219
		initMetisGraph(nc,false);
	}

	/*! \brief Constructor
	 *
	 * This constructor does not initialize the internal metis graph
	 * you have to use initMetisGraph to initialize
	 *
	 * \param g Graph we want to convert to decompose
	 *
	 */
	Metis(Graph & g)
incardon's avatar
incardon committed
220
	:g(g),n_dec(0)
incardon's avatar
incardon committed
221
222
223
224
225
226
227
228
229
230
231
232
233
	{
		Mg.nvtxs = NULL;
		Mg.ncon = NULL;
		Mg.xadj = NULL;
		Mg.adjncy = NULL;
		Mg.vwgt = NULL;
		Mg.adjwgt = NULL;
		Mg.nparts = NULL;
		Mg.tpwgts = NULL;
		Mg.ubvec = NULL;
		Mg.options = NULL;
		Mg.objval = NULL;
		Mg.part = NULL;
incardon's avatar
incardon committed
234
		Mg.vsize = NULL;
235
236
	}

incardon's avatar
incardon committed
237
238
239
240
241
242
243
244

	/*! \brief Initialize the METIS graph
	 *
	 * \param nc number of partitions
	 * \param useWeights use the weights on the graph
	 *
	 */
	void initMetisGraph(int nc, bool useWeights)
245
246
	{

incardon's avatar
incardon committed
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
		// Get the number of vertex

		Mg.nvtxs = new idx_t[1];
		Mg.nvtxs[0] = g.getNVertex();

		// Set the number of constrains

		Mg.ncon = new idx_t[1];
		Mg.ncon[0] = 1;

		// Set to null the weight of the vertex

		Mg.vwgt = NULL;

		// Put the total communication size to NULL

		Mg.vsize = NULL;

		// Set to null the weight of the edge

		Mg.adjwgt = NULL;

269
270
271
272
273
274
		// construct the adjacency list
		if (useWeights)
			constructAdjListWithWeights(g);
		else
			constructAdjList(g);

incardon's avatar
incardon committed
275
276
277
278
279
280
281
282
283
		// Set the total number of partitions

		Mg.nparts = new idx_t[1];
		Mg.nparts[0] = nc;

		// Set to null the desired weight for each partition (one for each constrain)

		Mg.tpwgts = NULL;

284
		//! Set to null the partition load imbalance tolerance
incardon's avatar
incardon committed
285
286
287
288
289
290
291
292
293
294
295
296

		Mg.ubvec = NULL;

		//! Set tp null additional option for the graph partitioning

		Mg.options = NULL;

		//! set the objective value
		Mg.objval = new idx_t[1];

		//! Is an output vector containing the partition for each vertex
		Mg.part = new idx_t[g.getNVertex()];
tonynsyde's avatar
tonynsyde committed
297

298
		for (size_t i = 0; i < g.getNVertex(); i++)
tonynsyde's avatar
tonynsyde committed
299
			Mg.part[i] = 0;
incardon's avatar
incardon committed
300
301
302
303
304
305
306
307
308
309
310
311
	}

	/*! \brief destructor
	 *
	 * Destructor, It destroy all the memory allocated
	 *
	 */
	~Metis()
	{
		// Deallocate the Mg structure
		if (Mg.nvtxs != NULL)
		{
312
			delete[] Mg.nvtxs;
incardon's avatar
incardon committed
313
314
315
316
		}

		if (Mg.ncon != NULL)
		{
317
			delete[] Mg.ncon;
incardon's avatar
incardon committed
318
319
320
321
		}

		if (Mg.xadj != NULL)
		{
322
			delete[] Mg.xadj;
incardon's avatar
incardon committed
323
324
325
326
		}

		if (Mg.adjncy != NULL)
		{
327
			delete[] Mg.adjncy;
incardon's avatar
incardon committed
328
329
330
		}
		if (Mg.vwgt != NULL)
		{
331
			delete[] Mg.vwgt;
incardon's avatar
incardon committed
332
333
334
		}
		if (Mg.adjwgt != NULL)
		{
335
			delete[] Mg.adjwgt;
incardon's avatar
incardon committed
336
337
338
		}
		if (Mg.nparts != NULL)
		{
339
			delete[] Mg.nparts;
incardon's avatar
incardon committed
340
341
342
		}
		if (Mg.tpwgts != NULL)
		{
343
			delete[] Mg.tpwgts;
incardon's avatar
incardon committed
344
345
346
		}
		if (Mg.ubvec != NULL)
		{
347
			delete[] Mg.ubvec;
incardon's avatar
incardon committed
348
349
350
		}
		if (Mg.options != NULL)
		{
351
			delete[] Mg.options;
incardon's avatar
incardon committed
352
353
354
		}
		if (Mg.objval != NULL)
		{
355
			delete[] Mg.objval;
incardon's avatar
incardon committed
356
357
358
		}
		if (Mg.part != NULL)
		{
359
			delete[] Mg.part;
incardon's avatar
incardon committed
360
361
362
363
364
365
366
367
368
369
370
371
		}
	}

	/*! \brief Decompose the graph
	 *
	 * \tparam i which property store the decomposition
	 *
	 */

	template<unsigned int i>
	void decompose()
	{
incardon's avatar
incardon committed
372
373
374
		if (Mg.nparts[0] != 1)
		{
			// Decompose
375
			METIS_PartGraphRecursive(Mg.nvtxs, Mg.ncon, Mg.xadj, Mg.adjncy, Mg.vwgt, Mg.vsize, Mg.adjwgt, Mg.nparts, Mg.tpwgts, Mg.ubvec, Mg.options, Mg.objval, Mg.part);
incardon's avatar
incardon committed
376

incardon's avatar
incardon committed
377
			// vertex id
incardon's avatar
incardon committed
378

incardon's avatar
incardon committed
379
			size_t id = 0;
incardon's avatar
incardon committed
380

incardon's avatar
incardon committed
381
			// For each vertex store the processor that contain the data
incardon's avatar
incardon committed
382

incardon's avatar
incardon committed
383
			auto it = g.getVertexIterator();
incardon's avatar
incardon committed
384

incardon's avatar
incardon committed
385
386
387
388
389
390
391
392
393
			while (it.isNext())
			{
				g.vertex(it).template get<i>() = Mg.part[id];

				++id;
				++it;
			}
		}
		else
incardon's avatar
incardon committed
394
		{
incardon's avatar
incardon committed
395
			// Trivially assign all the domains to the processor 0
incardon's avatar
incardon committed
396

incardon's avatar
incardon committed
397
398
399
400
401
402
403
404
			auto it = g.getVertexIterator();

			while (it.isNext())
			{
				g.vertex(it).template get<i>() = 0;

				++it;
			}
incardon's avatar
incardon committed
405
		}
incardon's avatar
incardon committed
406
407

		n_dec++;
incardon's avatar
incardon committed
408
409
410
411
412
413
414
415
416
417
418
419
	}

	/*! \brief Decompose the graph
	 *
	 * \tparam i which property store the decomposition
	 *
	 */

	template<unsigned int i, typename Graph_part>
	void decompose(Graph_part & gp)
	{
		// Decompose
420
		METIS_PartGraphRecursive(Mg.nvtxs, Mg.ncon, Mg.xadj, Mg.adjncy, Mg.vwgt, Mg.vsize, Mg.adjwgt, Mg.nparts, Mg.tpwgts, Mg.ubvec, Mg.options, Mg.objval, Mg.part);
incardon's avatar
incardon committed
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436

		// vertex id

		size_t id = 0;

		// For each vertex store the processor that contain the data

		auto it = gp.getVertexIterator();

		while (it.isNext())
		{
			gp.vertex(it).template get<i>() = Mg.part[id];

			++id;
			++it;
		}
incardon's avatar
incardon committed
437
438

		n_dec++;
incardon's avatar
incardon committed
439
	}
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464

	/*! \brief It set Metis on test
	 *
	 * \param testing set to true to disable the testing
	 *
	 * At the moment disable the seed randomness to keep the result
	 * reproducible
	 *
	 */
	void onTest(bool testing)
	{
		if (testing == false)
			return;

		if (Mg.options == NULL)
		{
			// allocate
			Mg.options = new idx_t[METIS_NOPTIONS];

			// set default options
			METIS_SetDefaultOptions(Mg.options);
		}

		Mg.options[METIS_OPTION_SEED] = 0;
	}
incardon's avatar
incardon committed
465
466
467
468
469
470

	/*! \brief Distribution tolerance
	 *
	 * \param tol tolerance
	 *
	 */
incardon's avatar
incardon committed
471
	void setDistTol(real_t tol)
incardon's avatar
incardon committed
472
473
474
	{
		dist_tol = tol;
	}
incardon's avatar
incardon committed
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493

	/*! \brief Get the decomposition counter
	 *
	 * \return the decomposition counter
	 *
	 */
	size_t get_ndec()
	{
		return n_dec;
	}

	/*! \brief Increment the decomposition counter
	 *
	 *
	 */
	void inc_dec()
	{
		n_dec++;
	}
incardon's avatar
incardon committed
494
495
496
};

#endif