MetisDistribution.hpp 6.08 KB
Newer Older
Pietro Incardona's avatar
Pietro Incardona committed
1
2
3
4
/*
 * MetisDistribution.hpp
 *
 *  Created on: Nov 19, 2015
5
 *      Author: Antonio Leo
Pietro Incardona's avatar
Pietro Incardona committed
6
7
8
9
10
 */

#ifndef SRC_DECOMPOSITION_METISDISTRIBUTION_HPP_
#define SRC_DECOMPOSITION_METISDISTRIBUTION_HPP_

11
12
#include "SubdomainGraphNodes.hpp"
#include "metis_util.hpp"
Pietro Incardona's avatar
Pietro Incardona committed
13

14
15
16
17
18
template<unsigned int dim, typename T, template<unsigned int, typename > class Domain = Box>
class MetisDistribution
{
	//! Vcluster
	Vcluster & v_cl;
Pietro Incardona's avatar
Pietro Incardona committed
19

20
21
	//! Structure that store the cartesian grid information
	grid_sm<dim, void> gr;
Pietro Incardona's avatar
Pietro Incardona committed
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
	//! rectangular domain to decompose
	Domain<dim, T> domain;

	//! Global sub-sub-domain graph
	Graph_CSR<nm_v, nm_e> gp;

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

public:

	//! constructor
	MetisDistribution(Vcluster & v_cl) :
			v_cl(v_cl)
	{
	}

	/*! \brief Initialize the distribution graph
	 *
	 */
	void init(grid_sm<dim, void> & grid, Domain<dim, T> dom)
	{
		// Set grid and domain
		gr = grid;
		domain = dom;

		// Create a cartesian grid graph
		CartesianGraphFactory<dim, Graph_CSR<nm_v, nm_e>> g_factory_part;
		gp = g_factory_part.template construct<NO_EDGE, nm_v::id, T, dim - 1, 0, 1, 2>(gr.getSize(), domain);

		// Init to 0.0 axis z (to fix in graphFactory)
		if (dim < 3)
		{
			for (size_t i = 0; i < gp.getNVertex(); i++)
			{
tonynsyde's avatar
tonynsyde committed
58
				gp.vertex(i).template get<nm_v::x>()[2] = 0.0;
59
60
			}
		}
tonynsyde's avatar
tonynsyde committed
61
62
63
64
65

		for (size_t i = 0; i < gp.getNVertex(); i++)
		{
			gp.vertex(i).template get<nm_v::global_id>() = i;
		}
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
	}

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

	/*! \brief Create first decomposition, it divides the graph in slices and give each slice to a processor
	 *
	 */
	void decompose()
	{
		Metis<Graph_CSR<nm_v, nm_e>> met(gp, v_cl.getProcessingUnits(), verticesGotWeights);

		// decompose
		met.decompose<nm_v::proc_id>();
	}

	/*! \brief Refine current decomposition (NOT AVAILABLE on Metis)
	 *
	 * It has no function
	 */
	void refine()
	{
	}

	/*! \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
	 *
	 */
tonynsyde's avatar
tonynsyde committed
101
	void getVertexPosition(size_t id, T (&pos)[dim])
102
103
	{
		if (id >= gp.getNVertex())
tonynsyde's avatar
tonynsyde committed
104
			std::cerr << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
105

tonynsyde's avatar
tonynsyde committed
106
107
108
		// Copy the geometrical informations inside the pos vector
		pos[0] = gp.vertex(id).template get<nm_v::x>()[0];
		pos[1] = gp.vertex(id).template get<nm_v::x>()[1];
109
		if (dim == 3)
tonynsyde's avatar
tonynsyde committed
110
			pos[2] = gp.vertex(id).template get<nm_v::x>()[2];
111
112
113
114
115
116
117
118
119
120
	}

	/*! \brief function that set the weight of the vertex
	 *
	 * \param id vertex id
	 * \param wieght to give to the vertex
	 *
	 */
	void setVertexWeight(size_t id, size_t weight)
	{
tonynsyde's avatar
tonynsyde committed
121
		if (!verticesGotWeights)
122
123
124
			verticesGotWeights = true;

		if (id >= gp.getNVertex())
tonynsyde's avatar
tonynsyde committed
125
			std::cerr << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

		gp.vertex(id).template get<nm_v::computation>() = weight;
	}

	/*! \brief Checks if weights are used on the vertices
	 *
	 */
	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 >= gp.getNVertex())
tonynsyde's avatar
tonynsyde committed
146
			std::cerr << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
147
148
149
150
151
152
153
154
155
156
157
158

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

	/*! \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 >= gp.getNVertex())
tonynsyde's avatar
tonynsyde committed
159
			std::cerr << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
160
161
162
163
164
165

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

	/*! \brief Set communication cost of the edge id
	 *
tonynsyde's avatar
tonynsyde committed
166
167
168
	 * \param v_id Id of the source vertex of the edge
	  * \param e i child of the vertex
	 * \param communication Communication value
169
	 */
tonynsyde's avatar
tonynsyde committed
170
	void setCommunicationCost(size_t v_id, size_t e, size_t communication)
171
	{
tonynsyde's avatar
tonynsyde committed
172
173
174
175
		size_t e_id = v_id + e;

		if (e_id >= gp.getNEdge())
			std::cerr << "Such edge doesn't exist (id = " << e_id << ", " << "total size = " << gp.getNEdge() << ")\n";
176

tonynsyde's avatar
tonynsyde committed
177
		gp.getChildEdge(v_id, e).template get<nm_e::communication>() = communication;
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
	}

	/*! \brief Returns total number of sub-sub-domains in the distribution graph
	 *
	 */
	size_t getNSubSubDomains()
	{
		return gp.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 >= gp.getNVertex())
tonynsyde's avatar
tonynsyde committed
195
			std::cerr << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
196
197
198
199

		return gp.getNChilds(id);
	}

tonynsyde's avatar
tonynsyde committed
200
	/*! \brief Print current graph and save it to file with name test_graph_[id]
201
202
203
204
205
206
	 *
	 * \param id to attach to the filename
	 *
	 */
	void printCurrentDecomposition(int id)
	{
207
		VTKWriter<Graph_CSR<nm_v, nm_e>, VTK_GRAPH> gv2(gp);
208
209
210
		gv2.write("test_graph_" + std::to_string(id) + ".vtk");

	}
tonynsyde's avatar
tonynsyde committed
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

	/*! \brief Compute the unbalance value
	 *
	 * \return the unbalance value
	 */
	float getUnbalance()
	{
		long min, max, sum;
		std::vector<long> loads(v_cl.getProcessingUnits());

		for (size_t i = 0; i < loads.size(); i++)
			loads[i] = 0;

		for (size_t i = 0; i < gp.getNVertex(); i++)
			loads[gp.vertex(i).template get<nm_v::proc_id>()]++;

		max = *std::max_element(loads.begin(), loads.end());
		min = *std::min_element(loads.begin(), loads.end());
		sum = std::accumulate(loads.begin(), loads.end(), 0);

		float unbalance = ((float) (max - min)) / (float) sum;

		return unbalance;
	}

	/*! \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 < gp.getNVertex(); i++)
		{
			if (gp.vertex(i).template get<nm_v::proc_id>() == v_cl.getProcessUnitID())
				load += gp.vertex(i).template get<nm_v::computation>();
		}

		return load;
	}
252
};
Pietro Incardona's avatar
Pietro Incardona committed
253
254

#endif /* SRC_DECOMPOSITION_METISDISTRIBUTION_HPP_ */