DistParMetisDistribution.hpp 9.47 KB
Newer Older
tonynsyde's avatar
tonynsyde committed
1
2
3
4
5
6
7
/*
 * DistParMetisDistribution.hpp
 *
 *  Created on: Nov 19, 2015
 *      Author: Antonio Leo
 */

8
9
10
#ifndef SRC_DECOMPOSITION_DISTPARMETISDISTRIBUTION_HPP_
#define SRC_DECOMPOSITION_DISTPARMETISDISTRIBUTION_HPP_

tonynsyde's avatar
tonynsyde committed
11
12
13
14
15
#include "SubdomainGraphNodes.hpp"
#include "parmetis_dist_util.hpp"
#include "Graph/dist_map_graph.hpp"
#include "Graph/DistGraphFactory.hpp"

16
template<unsigned int dim, typename T>
tonynsyde's avatar
tonynsyde committed
17
18
19
class DistParMetisDistribution
{
	//! Vcluster
20
	Vcluster<> & v_cl;
tonynsyde's avatar
tonynsyde committed
21
22
23
24
25

	//! Structure that store the cartesian grid information
	grid_sm<dim, void> gr;

	//! rectangular domain to decompose
26
	Box<dim, T> domain;
tonynsyde's avatar
tonynsyde committed
27
28

	//! Processor sub-sub-domain graph
29
	DistGraph_CSR<nm_v, nm_e> g;
tonynsyde's avatar
tonynsyde committed
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
75

	//! Convert the graph to parmetis format
	DistParmetis<DistGraph_CSR<nm_v, nm_e>> parmetis_graph;

	//! Init vtxdist needed for Parmetis
	openfpm::vector<idx_t> vtxdist;

	//! partitions
	openfpm::vector<openfpm::vector<idx_t>> partitions;

	//! Init data structure to keep trace of new vertices distribution in processors (needed to update main graph)
	openfpm::vector<openfpm::vector<size_t>> v_per_proc;

	//! Number of moved vertices in all iterations
	size_t g_moved = 0;

	//! Max number of moved vertices in all iterations
	size_t m_moved = 0;

	//! Flag to check if weights are used on vertices
	bool verticesGotWeights = false;

	/*! \brief Callback of the sendrecv to set the size of the array received
	 *
	 * \param msg_i Index of the message
	 * \param total_msg Total numeber of messages
	 * \param total_p Total number of processors to comunicate with
	 * \param i Processor id
	 * \param ri Request id
	 * \param ptr Void pointer parameter for additional data to pass to the call-back
	 */
	static void * message_receive(size_t msg_i, size_t total_msg, size_t total_p, size_t i, size_t ri, void * ptr)
	{
		openfpm::vector < openfpm::vector < idx_t >> *v = static_cast<openfpm::vector<openfpm::vector<idx_t>> *>(ptr);

		v->get(i).resize(msg_i / sizeof(idx_t));

		return &(v->get(i).get(0));
	}

public:

	/*! Constructor for the ParMetis class
	 *
	 * @param v_cl Vcluster to use as communication object in this class
	 */
76
	DistParMetisDistribution(Vcluster<> & v_cl) :
tonynsyde's avatar
tonynsyde committed
77
78
79
80
81
82
83
84
85
86
			v_cl(v_cl), parmetis_graph(v_cl, v_cl.getProcessingUnits()), vtxdist(v_cl.getProcessingUnits() + 1), partitions(v_cl.getProcessingUnits()), v_per_proc(v_cl.getProcessingUnits())

	{
	}

	/*! \brief Initialize the distribution graph
	 *
	 * /param grid Grid
	 * /param dom Domain
	 */
87
	void createCartGraph(grid_sm<dim, void> & grid, Box<dim, T> dom)
tonynsyde's avatar
tonynsyde committed
88
89
90
91
92
93
94
	{
		//! Set grid and domain
		gr = grid;
		domain = dom;

		//! Create sub graph
		DistGraphFactory<dim, DistGraph_CSR<nm_v, nm_e>> dist_g_factory;
95
		g = dist_g_factory.template construct<NO_EDGE, T, dim - 1, 0>(gr.getSize(), domain);
96
		g.getDecompositionVector(vtxdist);
97
98

		if (dim == 2)
99
100
			for (size_t i = 0; i < g.getNVertex(); i++)
				g.vertex(i).template get<nm_v::x>()[2] = 0;
tonynsyde's avatar
tonynsyde committed
101
102
103
104
105
106
107
108

	}

	/*! \brief Get the current graph (main)
	 *
	 */
	DistGraph_CSR<nm_v, nm_e> & getGraph()
	{
109
		return g;
tonynsyde's avatar
tonynsyde committed
110
111
112
113
114
115
116
117
	}

	/*! \brief Create first decomposition, it divides the graph in slices and give each slice to a processor
	 *
	 */
	void decompose()
	{
		//! Init sub graph in parmetis format
118
		parmetis_graph.initSubGraph(g);
tonynsyde's avatar
tonynsyde committed
119
120

		//! Decompose
121
		parmetis_graph.decompose<nm_v::proc_id>(g);
tonynsyde's avatar
tonynsyde committed
122
123
124
125

		//! Get result partition for this processors
		idx_t *partition = parmetis_graph.getPartition();

126
		for (size_t i = 0, j = g.firstId(); i < g.getNVertex() && j <= g.lastId(); i++, j++)
tonynsyde's avatar
tonynsyde committed
127
		{
128
			if ((size_t)partition[i] != v_cl.getProcessUnitID())
129
				g.q_move(g.nodeById(j), partition[i]);
tonynsyde's avatar
tonynsyde committed
130
		}
131
		g.redistribute();
tonynsyde's avatar
tonynsyde committed
132
133
134
135
136
137
138
139
140
141
142
	}

	/*! \brief Refine current decomposition
	 *
	 * It makes a refinement of the current decomposition using Parmetis function RefineKWay
	 * After that it also does the remapping of the graph
	 *
	 */
	void refine()
	{
		//! Reset parmetis graph and reconstruct it
143
		parmetis_graph.reset(g);
tonynsyde's avatar
tonynsyde committed
144
145

		//! Refine
146
		parmetis_graph.refine<nm_v::proc_id>(g);
tonynsyde's avatar
tonynsyde committed
147
148
149
150

		//! Get result partition for this processors
		idx_t *partition = parmetis_graph.getPartition();

151
		for (size_t i = 0, j = g.firstId(); i < g.getNVertex() && j <= g.lastId(); i++, j++)
tonynsyde's avatar
tonynsyde committed
152
		{
153
			if ((size_t)partition[i] != v_cl.getProcessUnitID())
154
				g.q_move(g.nodeById(j), partition[i]);
tonynsyde's avatar
tonynsyde committed
155
		}
156
		g.redistribute();
tonynsyde's avatar
tonynsyde committed
157
158
159
160
161
162
163
164
	}

	/*! \brief Compute the unbalance value
	 *
	 * \return the unbalance value
	 */
	float getUnbalance()
	{
165
		long t_cost = getProcessorLoad();
tonynsyde's avatar
tonynsyde committed
166
167
168
169
170
171
172
173
174
175
176
177
178

		long min, max, sum;
		float unbalance;

		min = t_cost;
		max = t_cost;
		sum = t_cost;

		v_cl.min(min);
		v_cl.max(max);
		v_cl.sum(sum);
		v_cl.execute();

179
		unbalance = ((float) (max - min)) / (float) (sum / v_cl.getProcessingUnits());
tonynsyde's avatar
tonynsyde committed
180
181
182
183
184
185
186
187
188
189

		return unbalance * 100;
	}

	/*! \brief function that return the position of the vertex in the space
	 *
	 * \param id vertex id
	 * \param pos vector that will contain x, y, z
	 *
	 */
190
	void getSubSubDomainPosition(size_t id, T (&pos)[dim])
tonynsyde's avatar
tonynsyde committed
191
	{
incardon's avatar
incardon committed
192
#ifdef SE_CLASS1
193
		if (id >= g.getNVertex())
incardon's avatar
incardon committed
194
195
			std::cerr << __FILE__ << ":" << __LINE__ << " Position - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
#endif
tonynsyde's avatar
tonynsyde committed
196

197
198
		pos[0] = g.vertex(id).template get<nm_v::x>()[0];
		pos[1] = g.vertex(id).template get<nm_v::x>()[1];
tonynsyde's avatar
tonynsyde committed
199
		if (dim == 3)
200
			pos[2] = g.vertex(id).template get<nm_v::x>()[2];
tonynsyde's avatar
tonynsyde committed
201
202
203
204
205
206
207
208
	}

	/*! \brief Function that set the weight of the vertex
	 *
	 * \param id vertex id
	 * \param weight to give to the vertex
	 *
	 */
209
	inline void setComputationCost(size_t id, size_t weight)
tonynsyde's avatar
tonynsyde committed
210
	{
211
		verticesGotWeights = true;
incardon's avatar
incardon committed
212
#ifdef SE_CLASS1
213
		if (id >= g.getNVertex())
incardon's avatar
incardon committed
214
215
			std::cerr << __FILE__ << ":" << __LINE__ << "Weight - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
#endif
tonynsyde's avatar
tonynsyde committed
216
217

		// If the vertex is inside this processor update the value
218
		g.vertex(id).template get<nm_v::computation>() = weight;
tonynsyde's avatar
tonynsyde committed
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234

	}

	/*! \brief Checks if weights are used on the vertices
	 *
	 * \return true if weights are used in the decomposition
	 */
	bool weightsAreUsed()
	{
		return verticesGotWeights;
	}

	/*! \brief function that get the weight of the vertex
	 *
	 * \param id vertex id
	 *
235
236
	 * \return the weight of the vertex
	 *
tonynsyde's avatar
tonynsyde committed
237
238
239
	 */
	size_t getVertexWeight(size_t id)
	{
incardon's avatar
incardon committed
240
#ifdef SE_CLASS1
241
		if (id >= g.getNVertex())
incardon's avatar
incardon committed
242
243
			std::cerr << __FILE__ << ":" << __LINE__ << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getTotNVertex() << ")\n";
#endif
tonynsyde's avatar
tonynsyde committed
244

245
		return g.vertex(id).template get<nm_v::computation>();
tonynsyde's avatar
tonynsyde committed
246
247
248
249
250
251
252
253
254
255
	}

	/*! \brief Compute the processor load counting the total weights of its vertices
	 *
	 * \return the computational load of the processor graph
	 */
	size_t getProcessorLoad()
	{
		size_t load = 0;

256
		for (size_t i = 0; i < g.getNVertex(); i++)
tonynsyde's avatar
tonynsyde committed
257
		{
258
			load += g.vertex(i).template get<nm_v::computation>();
tonynsyde's avatar
tonynsyde committed
259
260
261
262
263
264
		}
		return load;
	}

	/*! \brief return number of moved vertices in all iterations so far
	 *
265
	 * \return number of moved vertices
tonynsyde's avatar
tonynsyde committed
266
267
268
269
270
271
272
273
274
	 *
	 */
	size_t getTotalMovedV()
	{
		return g_moved;
	}

	/*! \brief return number of moved vertices in all iterations so far
	 *
incardon's avatar
incardon committed
275
	 * \return number of moved vertices
tonynsyde's avatar
tonynsyde committed
276
277
278
279
280
281
282
283
284
285
286
287
288
289
	 *
	 */
	size_t getMaxMovedV()
	{
		return m_moved;
	}

	/*! \brief Set migration cost of the vertex id
	 *
	 * \param id of the vertex to update
	 * \param migration cost of the migration
	 */
	void setMigrationCost(size_t id, size_t migration)
	{
incardon's avatar
incardon committed
290
#ifdef SE_CLASS1
291
		if (id >= g.getNVertex())
incardon's avatar
incardon committed
292
293
			std::cerr << __FILE__ << ":" << __LINE__ << "Migration - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
#endif
tonynsyde's avatar
tonynsyde committed
294

295
		g.vertex(id).template get<nm_v::migration>() = migration;
tonynsyde's avatar
tonynsyde committed
296
297
298
299
300
301
302
303
304
305
	}

	/*! \brief Set communication cost of the edge id
	 *
	 * \param v_id Id of the source vertex of the edge
	 * \param e i child of the vertex
	 * \param communication Communication value
	 */
	void setCommunicationCost(size_t v_id, size_t e, size_t communication)
	{
306
		g.getChildEdge(v_id, e).template get<nm_e::communication>() = communication;
tonynsyde's avatar
tonynsyde committed
307
308
309
	}

	/*! \brief Returns total number of sub-sub-domains in the distribution graph
310
311
	 *
	 * \return number od sub-sub-domain
tonynsyde's avatar
tonynsyde committed
312
313
314
315
	 *
	 */
	size_t getNSubSubDomains()
	{
316
		return g.getNVertex();
tonynsyde's avatar
tonynsyde committed
317
318
319
320
	}

	/*! \brief Returns total number of neighbors of the sub-sub-domain id
	 *
incardon's avatar
incardon committed
321
	 * \param id id of the sub-sub-domain
322
323
324
	 *
	 * \return the number of neighborhood sub-sub-domain
	 *
tonynsyde's avatar
tonynsyde committed
325
326
327
	 */
	size_t getNSubSubDomainNeighbors(size_t id)
	{
328
329
		if (id >= g.getNVertex())
			std::cerr << "Neighbors - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
tonynsyde's avatar
tonynsyde committed
330

331
		return g.getNChilds(id);
tonynsyde's avatar
tonynsyde committed
332
333
	}

Pietro Incardona's avatar
Pietro Incardona committed
334
	/*! \brief Print current graph and save it to file
335
336
	 *
	 * \param file file
tonynsyde's avatar
tonynsyde committed
337
338
	 *
	 */
339
	void write(const std::string & file)
tonynsyde's avatar
tonynsyde committed
340
	{
341
		VTKWriter<DistGraph_CSR<nm_v, nm_e>, DIST_GRAPH> gv2(g);
Pietro Incardona's avatar
Pietro Incardona committed
342
		gv2.write(std::to_string(file + ".vtk"));
tonynsyde's avatar
tonynsyde committed
343
	}
344

345
346
347
348
349
350
351
	/*! \brief copy operator
	 *
	 * \param dist object to copy
	 *
	 * \return itself
	 *
	 */
352
	const DistParMetisDistribution<dim, T> & operator=(const DistParMetisDistribution<dim, T> & dist)
353
354
355
356
	{
		v_cl = dist.v_cl;
		gr = dist.gr;
		domain = dist.domain;
357
		g = dist.g;
358
359
360
361
362
363
364
365
		vtxdist = dist.vtxdist;
		partitions = dist.partitions;
		v_per_proc = dist.v_per_proc;
		verticesGotWeights = dist.verticesGotWeights;

		return *this;
	}

366
367
368
369
370
371
372
	/*! \brief copy operator
	 *
	 * \param dist object to copy
	 *
	 * \return itself
	 *
	 */
incardon's avatar
incardon committed
373
	const DistParMetisDistribution<dim, T> & operator=(DistParMetisDistribution<dim, T> && dist)
374
375
376
377
	{
		v_cl = dist.v_cl;
		gr = dist.gr;
		domain = dist.domain;
378
		g.swap(dist.g);
379
380
381
382
383
384
385
		vtxdist.swap(dist.vtxdist);
		partitions.swap(dist.partitions);
		v_per_proc.swap(dist.v_per_proc);
		verticesGotWeights = dist.verticesGotWeights;

		return *this;
	}
386
387
}
;
tonynsyde's avatar
tonynsyde committed
388
389

#endif /* SRC_DECOMPOSITION_PARMETISDISTRIBUTION_HPP_ */