DistParMetisDistribution.hpp 9.17 KB
Newer Older
tonynsyde's avatar
tonynsyde committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * DistParMetisDistribution.hpp
 *
 *  Created on: Nov 19, 2015
 *      Author: Antonio Leo
 */

#include "SubdomainGraphNodes.hpp"
#include "parmetis_dist_util.hpp"
#include "Graph/dist_map_graph.hpp"
#include "Graph/DistGraphFactory.hpp"
#ifndef SRC_DECOMPOSITION_DISTPARMETISDISTRIBUTION_HPP_
#define SRC_DECOMPOSITION_DISTPARMETISDISTRIBUTION_HPP_

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

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

	//! rectangular domain to decompose
25
	Box<dim, T> domain;
tonynsyde's avatar
tonynsyde committed
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
75
76
77
78
79
80
81
82
83
84
85

	//! Processor sub-sub-domain graph
	DistGraph_CSR<nm_v, nm_e> sub_g;

	//! 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
	 */
	DistParMetisDistribution(Vcluster & v_cl) :
			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
	 */
86
	void createCartGraph(grid_sm<dim, void> & grid, Box<dim, T> dom)
tonynsyde's avatar
tonynsyde committed
87
88
89
90
91
92
93
	{
		//! Set grid and domain
		gr = grid;
		domain = dom;

		//! Create sub graph
		DistGraphFactory<dim, DistGraph_CSR<nm_v, nm_e>> dist_g_factory;
94
		sub_g = dist_g_factory.template construct<NO_EDGE, T, dim - 1, 0, 1, 2>(gr.getSize(), domain);
tonynsyde's avatar
tonynsyde committed
95
		sub_g.getDecompositionVector(vtxdist);
96
97
98
99

		if (dim == 2)
			for (size_t i = 0; i < sub_g.getNVertex(); i++)
				sub_g.vertex(i).template get<nm_v::x>()[2] = 0;
tonynsyde's avatar
tonynsyde committed
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

	}

	/*! \brief Get the current graph (main)
	 *
	 */
	DistGraph_CSR<nm_v, nm_e> & getGraph()
	{
		return sub_g;
	}

	/*! \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
		parmetis_graph.initSubGraph(sub_g);

		//! Decompose
		parmetis_graph.decompose<nm_v::proc_id>(sub_g);

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

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

	/*! \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
		parmetis_graph.reset(sub_g);

		//! Refine
		parmetis_graph.refine<nm_v::proc_id>(sub_g);

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

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

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

		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();

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

		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
	 *
	 */
189
	void getSubSubDomainPosition(size_t id, T (&pos)[dim])
tonynsyde's avatar
tonynsyde committed
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
	{
		if (id >= sub_g.getNVertex())
			std::cerr << "Position - Such vertex doesn't exist (id = " << id << ", " << "total size = " << sub_g.getNVertex() << ")\n";

		pos[0] = sub_g.vertex(id).template get<nm_v::x>()[0];
		pos[1] = sub_g.vertex(id).template get<nm_v::x>()[1];
		if (dim == 3)
			pos[2] = sub_g.vertex(id).template get<nm_v::x>()[2];
	}

	/*! \brief Function that set the weight of the vertex
	 *
	 * \param id vertex id
	 * \param weight to give to the vertex
	 *
	 */
206
	inline void setComputationCost(size_t id, size_t weight)
tonynsyde's avatar
tonynsyde committed
207
	{
208
		verticesGotWeights = true;
tonynsyde's avatar
tonynsyde committed
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

		if (id >= sub_g.getNVertex())
			std::cerr << "Weight - Such vertex doesn't exist (id = " << id << ", " << "total size = " << sub_g.getNVertex() << ")\n";

		// If the vertex is inside this processor update the value
		sub_g.vertex(id).template get<nm_v::computation>() = weight;

	}

	/*! \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
	 *
	 */
	size_t getVertexWeight(size_t id)
	{
		if (id >= sub_g.getNVertex())
			std::cerr << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << sub_g.getTotNVertex() << ")\n";

		return sub_g.vertex(id).template get<nm_v::computation>();
	}

	/*! \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;

		for (size_t i = 0; i < sub_g.getNVertex(); i++)
		{
			load += sub_g.vertex(i).template get<nm_v::computation>();
		}
		return load;
	}

	/*! \brief return number of moved vertices in all iterations so far
	 *
	 * \param id vertex id
	 *
	 * \return vector with x, y, z
	 *
	 */
	size_t getTotalMovedV()
	{
		return g_moved;
	}

	/*! \brief return number of moved vertices in all iterations so far
	 *
	 * \param id vertex id
	 *
	 * \return vector with x, y, z
	 *
	 */
	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)
	{
		if (id >= sub_g.getNVertex())
			std::cerr << "Migration - Such vertex doesn't exist (id = " << id << ", " << "total size = " << sub_g.getNVertex() << ")\n";

		sub_g.vertex(id).template get<nm_v::migration>() = migration;
	}

	/*! \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)
	{
		sub_g.getChildEdge(v_id, e).template get<nm_e::communication>() = communication;
	}

	/*! \brief Returns total number of sub-sub-domains in the distribution graph
	 *
	 */
	size_t getNSubSubDomains()
	{
		return sub_g.getNVertex();
	}

	/*! \brief Returns total number of neighbors of the sub-sub-domain id
	 *
	 * \param i id of the sub-sub-domain
	 */
	size_t getNSubSubDomainNeighbors(size_t id)
	{
		if (id >= sub_g.getNVertex())
			std::cerr << "Neighbors - Such vertex doesn't exist (id = " << id << ", " << "total size = " << sub_g.getNVertex() << ")\n";

		return sub_g.getNChilds(id);
	}

	/*! \brief Print current graph and save it to file with name test_graph_[id]
	 *
	 * \param id to attach to the filename
	 *
	 */
328
	void write(const std::string & file)
tonynsyde's avatar
tonynsyde committed
329
	{
330
		VTKWriter<DistGraph_CSR<nm_v, nm_e>, DIST_GRAPH> gv2(sub_g);
331
		gv2.write(file);
tonynsyde's avatar
tonynsyde committed
332
	}
333

334
	const DistParMetisDistribution<dim, T> & operator=(const DistParMetisDistribution<dim, T> & dist)
335
336
337
338
339
340
341
342
343
344
345
346
347
	{
		v_cl = dist.v_cl;
		gr = dist.gr;
		domain = dist.domain;
		sub_g = dist.sub_g;
		vtxdist = dist.vtxdist;
		partitions = dist.partitions;
		v_per_proc = dist.v_per_proc;
		verticesGotWeights = dist.verticesGotWeights;

		return *this;
	}

348
	const DistParMetisDistribution<dim, T> & operator=(const DistParMetisDistribution<dim, T> && dist)
349
350
351
352
353
354
355
356
357
358
359
360
	{
		v_cl = dist.v_cl;
		gr = dist.gr;
		domain = dist.domain;
		sub_g.swap(dist.sub_g);
		vtxdist.swap(dist.vtxdist);
		partitions.swap(dist.partitions);
		v_per_proc.swap(dist.v_per_proc);
		verticesGotWeights = dist.verticesGotWeights;

		return *this;
	}
361
362
}
;
tonynsyde's avatar
tonynsyde committed
363
364

#endif /* SRC_DECOMPOSITION_PARMETISDISTRIBUTION_HPP_ */