1/*
2 * DistParMetisDistribution.hpp
3 *
4 * Created on: Nov 19, 2015
5 * Author: Antonio Leo
6 */
7
8#ifndef SRC_DECOMPOSITION_DISTPARMETISDISTRIBUTION_HPP_
9#define SRC_DECOMPOSITION_DISTPARMETISDISTRIBUTION_HPP_
10
11#include "SubdomainGraphNodes.hpp"
12#include "parmetis_dist_util.hpp"
13#include "Graph/dist_map_graph.hpp"
14#include "Graph/DistGraphFactory.hpp"
15
16template<unsigned int dim, typename T>
17class DistParMetisDistribution
18{
19 //! Vcluster
20 Vcluster<> & v_cl;
21
22 //! Structure that store the cartesian grid information
23 grid_sm<dim, void> gr;
24
25 //! rectangular domain to decompose
26 Box<dim, T> domain;
27
28 //! Processor sub-sub-domain graph
29 DistGraph_CSR<nm_v<dim>, nm_e> g;
30
31 //! Convert the graph to parmetis format
32 DistParmetis<DistGraph_CSR<nm_v<dim>, nm_e>> parmetis_graph;
33
34 //! Init vtxdist needed for Parmetis
35 openfpm::vector<idx_t> vtxdist;
36
37 //! partitions
38 openfpm::vector<openfpm::vector<idx_t>> partitions;
39
40 //! Init data structure to keep trace of new vertices distribution in processors (needed to update main graph)
41 openfpm::vector<openfpm::vector<size_t>> v_per_proc;
42
43 //! Number of moved vertices in all iterations
44 size_t g_moved = 0;
45
46 //! Max number of moved vertices in all iterations
47 size_t m_moved = 0;
48
49 //! Flag to check if weights are used on vertices
50 bool verticesGotWeights = false;
51
52 /*! \brief Callback of the sendrecv to set the size of the array received
53 *
54 * \param msg_i Index of the message
55 * \param total_msg Total numeber of messages
56 * \param total_p Total number of processors to comunicate with
57 * \param i Processor id
58 * \param ri Request id
59 * \param ptr Void pointer parameter for additional data to pass to the call-back
60 */
61 static void * message_receive(size_t msg_i, size_t total_msg, size_t total_p, size_t i, size_t ri, void * ptr)
62 {
63 openfpm::vector < openfpm::vector < idx_t >> *v = static_cast<openfpm::vector<openfpm::vector<idx_t>> *>(ptr);
64
65 v->get(i).resize(msg_i / sizeof(idx_t));
66
67 return &(v->get(i).get(0));
68 }
69
70public:
71
72 /*! Constructor for the ParMetis class
73 *
74 * @param v_cl Vcluster to use as communication object in this class
75 */
76 DistParMetisDistribution(Vcluster<> & v_cl) :
77 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())
78
79 {
80 }
81
82 /*! \brief Initialize the distribution graph
83 *
84 * /param grid Grid
85 * /param dom Domain
86 */
87 void createCartGraph(grid_sm<dim, void> & grid, Box<dim, T> dom)
88 {
89 //! Set grid and domain
90 gr = grid;
91 domain = dom;
92
93 //! Create sub graph
94 DistGraphFactory<dim, DistGraph_CSR<nm_v<dim>, 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 for (size_t i = 0; i < g.getNVertex(); i++)
100 g.vertex(i).template get<nm_v_x>()[2] = 0;
101
102 }
103
104 /*! \brief Get the current graph (main)
105 *
106 */
107 DistGraph_CSR<nm_v<dim>, nm_e> & getGraph()
108 {
109 return g;
110 }
111
112 /*! \brief Create first decomposition, it divides the graph in slices and give each slice to a processor
113 *
114 */
115 void decompose()
116 {
117 //! Init sub graph in parmetis format
118 parmetis_graph.initSubGraph(g);
119
120 //! Decompose
121 parmetis_graph.template decompose<nm_v_proc_id>(g);
122
123 //! Get result partition for this processors
124 idx_t *partition = parmetis_graph.getPartition();
125
126 for (size_t i = 0, j = g.firstId(); i < g.getNVertex() && j <= g.lastId(); i++, j++)
127 {
128 if ((size_t)partition[i] != v_cl.getProcessUnitID())
129 g.q_move(g.nodeById(j), partition[i]);
130 }
131 g.redistribute();
132 }
133
134 /*! \brief Refine current decomposition
135 *
136 * It makes a refinement of the current decomposition using Parmetis function RefineKWay
137 * After that it also does the remapping of the graph
138 *
139 */
140 void refine()
141 {
142 //! Reset parmetis graph and reconstruct it
143 parmetis_graph.reset(g);
144
145 //! Refine
146 parmetis_graph.template refine<nm_v_proc_id>(g);
147
148 //! Get result partition for this processors
149 idx_t *partition = parmetis_graph.getPartition();
150
151 for (size_t i = 0, j = g.firstId(); i < g.getNVertex() && j <= g.lastId(); i++, j++)
152 {
153 if ((size_t)partition[i] != v_cl.getProcessUnitID())
154 g.q_move(g.nodeById(j), partition[i]);
155 }
156 g.redistribute();
157 }
158
159 /*! \brief Compute the unbalance value
160 *
161 * \return the unbalance value
162 */
163 float getUnbalance()
164 {
165 long t_cost = getProcessorLoad();
166
167 long min, max, sum;
168 float unbalance;
169
170 min = t_cost;
171 max = t_cost;
172 sum = t_cost;
173
174 v_cl.min(min);
175 v_cl.max(max);
176 v_cl.sum(sum);
177 v_cl.execute();
178
179 unbalance = ((float) (max - min)) / (float) (sum / v_cl.getProcessingUnits());
180
181 return unbalance * 100;
182 }
183
184 /*! \brief function that return the position of the vertex in the space
185 *
186 * \param id vertex id
187 * \param pos vector that will contain x, y, z
188 *
189 */
190 void getSubSubDomainPosition(size_t id, T (&pos)[dim])
191 {
192#ifdef SE_CLASS1
193 if (id >= g.getNVertex())
194 std::cerr << __FILE__ << ":" << __LINE__ << " Position - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
195#endif
196
197 pos[0] = g.vertex(id).template get<nm_v_x>()[0];
198 pos[1] = g.vertex(id).template get<nm_v_x>()[1];
199 if (dim == 3)
200 pos[2] = g.vertex(id).template get<nm_v_x>()[2];
201 }
202
203 /*! \brief Function that set the weight of the vertex
204 *
205 * \param id vertex id
206 * \param weight to give to the vertex
207 *
208 */
209 inline void setComputationCost(size_t id, size_t weight)
210 {
211 verticesGotWeights = true;
212#ifdef SE_CLASS1
213 if (id >= g.getNVertex())
214 std::cerr << __FILE__ << ":" << __LINE__ << "Weight - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
215#endif
216
217 // If the vertex is inside this processor update the value
218 g.vertex(id).template get<nm_v_computation>() = weight;
219
220 }
221
222 /*! \brief Checks if weights are used on the vertices
223 *
224 * \return true if weights are used in the decomposition
225 */
226 bool weightsAreUsed()
227 {
228 return verticesGotWeights;
229 }
230
231 /*! \brief function that get the weight of the vertex
232 *
233 * \param id vertex id
234 *
235 * \return the weight of the vertex
236 *
237 */
238 size_t getVertexWeight(size_t id)
239 {
240#ifdef SE_CLASS1
241 if (id >= g.getNVertex())
242 std::cerr << __FILE__ << ":" << __LINE__ << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getTotNVertex() << ")\n";
243#endif
244
245 return g.vertex(id).template get<nm_v_computation>();
246 }
247
248 /*! \brief Compute the processor load counting the total weights of its vertices
249 *
250 * \return the computational load of the processor graph
251 */
252 size_t getProcessorLoad()
253 {
254 size_t load = 0;
255
256 for (size_t i = 0; i < g.getNVertex(); i++)
257 {
258 load += g.vertex(i).template get<nm_v_computation>();
259 }
260 return load;
261 }
262
263 /*! \brief return number of moved vertices in all iterations so far
264 *
265 * \return number of moved vertices
266 *
267 */
268 size_t getTotalMovedV()
269 {
270 return g_moved;
271 }
272
273 /*! \brief return number of moved vertices in all iterations so far
274 *
275 * \return number of moved vertices
276 *
277 */
278 size_t getMaxMovedV()
279 {
280 return m_moved;
281 }
282
283 /*! \brief Set migration cost of the vertex id
284 *
285 * \param id of the vertex to update
286 * \param migration cost of the migration
287 */
288 void setMigrationCost(size_t id, size_t migration)
289 {
290#ifdef SE_CLASS1
291 if (id >= g.getNVertex())
292 std::cerr << __FILE__ << ":" << __LINE__ << "Migration - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
293#endif
294
295 g.vertex(id).template get<nm_v_migration>() = migration;
296 }
297
298 /*! \brief Set communication cost of the edge id
299 *
300 * \param v_id Id of the source vertex of the edge
301 * \param e i child of the vertex
302 * \param communication Communication value
303 */
304 void setCommunicationCost(size_t v_id, size_t e, size_t communication)
305 {
306 g.getChildEdge(v_id, e).template get<nm_e::communication>() = communication;
307 }
308
309 /*! \brief Returns total number of sub-sub-domains in the distribution graph
310 *
311 * \return number od sub-sub-domain
312 *
313 */
314 size_t getNSubSubDomains()
315 {
316 return g.getNVertex();
317 }
318
319 /*! \brief Returns total number of neighbors of the sub-sub-domain id
320 *
321 * \param id id of the sub-sub-domain
322 *
323 * \return the number of neighborhood sub-sub-domain
324 *
325 */
326 size_t getNSubSubDomainNeighbors(size_t id)
327 {
328 if (id >= g.getNVertex())
329 std::cerr << "Neighbors - Such vertex doesn't exist (id = " << id << ", " << "total size = " << g.getNVertex() << ")\n";
330
331 return g.getNChilds(id);
332 }
333
334 /*! \brief Print current graph and save it to file
335 *
336 * \param file file
337 *
338 */
339 void write(const std::string & file)
340 {
341 VTKWriter<DistGraph_CSR<nm_v<dim>, nm_e>, DIST_GRAPH> gv2(g);
342 gv2.write(std::to_string(file + ".vtk"));
343 }
344
345 /*! \brief copy operator
346 *
347 * \param dist object to copy
348 *
349 * \return itself
350 *
351 */
352 const DistParMetisDistribution<dim, T> & operator=(const DistParMetisDistribution<dim, T> & dist)
353 {
354 gr = dist.gr;
355 domain = dist.domain;
356 g = dist.g;
357 vtxdist = dist.vtxdist;
358 partitions = dist.partitions;
359 v_per_proc = dist.v_per_proc;
360 verticesGotWeights = dist.verticesGotWeights;
361
362 return *this;
363 }
364
365 /*! \brief copy operator
366 *
367 * \param dist object to copy
368 *
369 * \return itself
370 *
371 */
372 const DistParMetisDistribution<dim, T> & operator=(DistParMetisDistribution<dim, T> && dist)
373 {
374 gr = dist.gr;
375 domain = dist.domain;
376 g.swap(dist.g);
377 vtxdist.swap(dist.vtxdist);
378 partitions.swap(dist.partitions);
379 v_per_proc.swap(dist.v_per_proc);
380 verticesGotWeights = dist.verticesGotWeights;
381
382 return *this;
383 }
384}
385;
386
387#endif /* SRC_DECOMPOSITION_PARMETISDISTRIBUTION_HPP_ */
388