OpenFPM_pdata  4.1.0
Project that contain the implementation of distributed structures
 
Loading...
Searching...
No Matches
MetisDistribution.hpp
1/*
2 * MetisDistribution.hpp
3 *
4 * Created on: Nov 19, 2015
5 * Author: Antonio Leo
6 */
7
8#ifndef SRC_DECOMPOSITION_METISDISTRIBUTION_HPP_
9#define SRC_DECOMPOSITION_METISDISTRIBUTION_HPP_
10
11#include "SubdomainGraphNodes.hpp"
12#include "metis_util.hpp"
13
14#define METIS_DISTRIBUTION_ERROR_OBJECT std::runtime_error("Metis runtime error");
15
20{
22 size_t id;
23
25 size_t w;
26
27 static bool noPointers() {return true;}
28};
29
43template<unsigned int dim, typename T>
45{
48
51
54
57
59 bool testing = false;
60
63
65 std::unordered_map<size_t,size_t> owner_scs;
66
69
72
78 inline void check_overflow(size_t id)
79 {
80#ifdef SE_CLASS1
81 if (id >= gp.getNVertex())
82 {
83 std::cerr << "Error " << __FILE__ ":" << __LINE__ << " such sub-sub-domain doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
84 ACTION_ON_ERROR(METIS_DISTRIBUTION_ERROR_OBJECT)
85 }
86#endif
87 }
88
94 inline void check_overflowe(size_t id, size_t e)
95 {
96#ifdef SE_CLASS1
97 if (e >= gp.getNChilds(id))
98 {
99 std::cerr << "Error " << __FILE__ ":" << __LINE__ << " for the sub-sub-domain " << id << " such neighborhood doesn't exist (e = " << e << ", " << "total size = " << gp.getNChilds(id) << ")\n";
100 ACTION_ON_ERROR(METIS_DISTRIBUTION_ERROR_OBJECT)
101 }
102#endif
103 }
104
105public:
106
107 static constexpr unsigned int computation = nm_v_computation;
108
116 {
117#ifdef SE_CLASS2
118 check_new(this,8,VECTOR_EVENT,1);
119#endif
120 }
121
128 :v_cl(mt.v_cl)
129 {
130#ifdef SE_CLASS2
131 check_valid(mt);
132 check_new(this,8,VECTOR_EVENT,1);
133#endif
134 this->operator=(mt);
135 }
136
143 {
144#ifdef SE_CLASS2
145 check_valid(mt);
146 check_new(this,8,VECTOR_EVENT,1);
147#endif
148 this->operator=(mt);
149 }
150
156 {
157#ifdef SE_CLASS2
158 check_delete(this);
159#endif
160 }
161
162
170 {
171#ifdef SE_CLASS2
172 check_valid(this,8);
173#endif
174 // NON periodic boundary conditions
175 size_t bc[dim];
176
177 for (size_t i = 0 ; i < dim ; i++)
178 bc[i] = NON_PERIODIC;
179
180 // Set grid and domain
181 gr = grid;
182 domain = dom;
183
184 // Create a cartesian grid graph
186 gp = g_factory_part.template construct<NO_EDGE, nm_v_id, T, dim - 1, 0>(gr.getSize(), domain, bc);
187
188 // Init to 0.0 axis z (to fix in graphFactory)
189 if (dim < 3)
190 {
191 for (size_t i = 0; i < gp.getNVertex(); i++)
192 {
193 gp.vertex(i).template get<nm_v_x>()[2] = 0.0;
194 }
195 }
196
197 for (size_t i = 0; i < gp.getNVertex(); i++)
198 gp.vertex(i).template get<nm_v_global_id>() = i;
199 }
200
207 {
208#ifdef SE_CLASS2
209 check_valid(this,8);
210#endif
211 return gp;
212 }
213
218 {
219#ifdef SE_CLASS2
220 check_valid(this,8);
221#endif
222
223 // Gather the sub-domain weight in one processor
224 recv_ass.clear();
226
227 if (v_cl.getProcessUnitID() == 0)
228 {
229 if (recv_ass.size() != 0)
230 {
231 // we fill the assignment
232 for (size_t i = 0 ; i < recv_ass.size() ; i++)
233 gp.template vertex_p<nm_v_computation>(recv_ass.get(i).id) = recv_ass.get(i).w;
234
236 }
237 else
240
241 // decompose
242 metis_graph.template decompose<nm_v_proc_id>();
243
244 if (recv_ass.size() != 0)
245 {
246 // we fill the assignment
247 for (size_t i = 0 ; i < recv_ass.size() ; i++)
248 recv_ass.get(i).w = gp.template vertex_p<nm_v_proc_id>(recv_ass.get(i).id);
249 }
250 else
251 {
252 recv_ass.resize(gp.getNVertex());
253
254 // we fill the assignment
255 for (size_t i = 0 ; i < gp.getNVertex() ; i++)
256 {
257 recv_ass.get(i).id = i;
258 recv_ass.get(i).w = gp.template vertex_p<nm_v_proc_id>(i);
259 }
260 }
261 }
262 else
263 {
265 }
266
267 recv_ass.resize(gp.getNVertex());
268
269 // broad cast the result
271 v_cl.execute();
272 owner_scs.clear();
273 owner_cost_sub.clear();
274
275 size_t j = 0;
276
277 // Fill the metis graph
278 for (size_t i = 0 ; i < recv_ass.size() ; i++)
279 {
280 gp.template vertex_p<nm_v_proc_id>(recv_ass.get(i).id) = recv_ass.get(i).w;
281
282 if (recv_ass.get(i).w == v_cl.getProcessUnitID())
283 {
284 owner_scs[recv_ass.get(i).id] = j;
285 j++;
286 owner_cost_sub.add();
287 owner_cost_sub.last().id = recv_ass.get(i).id;
288 owner_cost_sub.last().w = 1;
289 }
290 }
291 }
292
298 void refine()
299 {
300#ifdef SE_CLASS2
301 check_valid(this,8);
302#endif
303
304 decompose();
305 }
306
311 {
312#ifdef SE_CLASS2
313 check_valid(this,8);
314#endif
315 decompose();
316 }
317
318
325 void getSSDomainPos(size_t id, T (&pos)[dim])
326 {
327#ifdef SE_CLASS2
328 check_valid(this,8);
329#endif
330 check_overflow(id);
331
332 // Copy the geometrical informations inside the pos vector
333 pos[0] = gp.vertex(id).template get<nm_v_x>()[0];
334 pos[1] = gp.vertex(id).template get<nm_v_x>()[1];
335 if (dim == 3)
336 {pos[2] = gp.vertex(id).template get<nm_v_x>()[2];}
337 }
338
346 size_t getComputationalCost(size_t id)
347 {
348#ifdef SE_CLASS2
349 check_valid(this,8);
350#endif
351 check_overflow(id);
352 return gp.vertex(id).template get<nm_v_computation>();
353 }
354
355
362 void setComputationCost(size_t id, size_t cost)
363 {
364#ifdef SE_CLASS2
365 check_valid(this,8);
366#endif
367#ifdef SE_CLASS1
368 check_overflow(id);
369#endif
370
371 auto fnd = owner_scs.find(id);
372 if (fnd == owner_scs.end())
373 {
374 std::cerr << __FILE__ << ":" << __LINE__ << " Error you are setting a sub-sub-domain the processor does not own" << std::endl;
375 }
376 else
377 {
378 size_t id = fnd->second;
379 owner_cost_sub.get(id).w = cost;
380 }
381 }
382
388 void setMigrationCost(size_t id, size_t cost)
389 {
390#ifdef SE_CLASS2
391 check_valid(this,8);
392#endif
393#ifdef SE_CLASS1
394 check_overflow(id);
395#endif
396
397 gp.vertex(id).template get<nm_v_migration>() = cost;
398 }
399
406 void setCommunicationCost(size_t id, size_t e, size_t cost)
407 {
408#ifdef SE_CLASS2
409 check_valid(this,8);
410#endif
411#ifdef SE_CLASS1
412 check_overflow(id);
413 check_overflowe(id,e);
414#endif
415
416 gp.getChildEdge(id, e).template get<nm_e::communication>() = cost;
417 }
418
425 {
426#ifdef SE_CLASS2
427 check_valid(this,8);
428#endif
429 return gp.getNVertex();
430 }
431
437 {
438#ifdef SE_CLASS2
439 check_valid(this,8);
440#endif
441#ifdef SE_CLASS1
442 check_overflow(id);
443#endif
444
445 return gp.getNChilds(id);
446 }
447
455 {
456#ifdef SE_CLASS2
457 check_valid(this,8);
458#endif
459 size_t load_p = getProcessorLoad();
460
461 float load_avg = load_p;
462 v_cl.sum(load_avg);
463 v_cl.execute();
464
465 if (load_avg == 0)
466 {
467 // count the number if sub-sub-domain assigned
468 load_avg = owner_cost_sub.size();
469
470 v_cl.sum(load_avg);
471 v_cl.execute();
472 }
473
474 load_avg /= v_cl.getProcessingUnits();
475
476 return ((float)load_p - load_avg) / load_avg;
477 }
478
485 {
486 return owner_cost_sub.size();
487 }
488
496 size_t getOwnerSubSubDomain(size_t id) const
497 {
498 return owner_cost_sub.get(id).id;
499 }
500
506 void onTest()
507 {
508#ifdef SE_CLASS2
509 check_valid(this,8);
510#endif
511 testing = true;
512 }
513
519 void write(std::string out)
520 {
521#ifdef SE_CLASS2
522 check_valid(this,8);
523#endif
524
525 VTKWriter<Graph_CSR<nm_v<dim>, nm_e>, VTK_GRAPH> gv2(gp);
526 gv2.write(std::to_string(v_cl.getProcessUnitID()) + "_" + out + ".vtk");
527
528 }
529
537 {
538#ifdef SE_CLASS2
539 check_valid(this,8);
540#endif
542
543 size_t load = 0;
544
545 if (v_cl.getProcessUnitID() == 0)
546 {
547 for (size_t i = 0; i < gp.getNVertex(); i++)
548 {loads.get(gp.template vertex_p<nm_v_proc_id>(i)) += gp.template vertex_p<nm_v_computation>(i);}
549
550 for (size_t i = 0 ; i < v_cl.getProcessingUnits() ; i++)
551 {
552 v_cl.send(i,1234,&loads.get(i),sizeof(size_t));
553 }
554 }
555 v_cl.recv(0,1234,&load,sizeof(size_t));
556 v_cl.execute();
557
558 return load;
559 }
560
569 {
570#ifdef SE_CLASS2
571 check_valid(&mt,8);
572 check_valid(this,8);
573#endif
574 this->gr = mt.gr;
575 this->domain = mt.domain;
576 this->gp = mt.gp;
577 this->owner_cost_sub = mt.owner_cost_sub;
578 this->owner_scs = mt.owner_scs;
579 return *this;
580 }
581
590 {
591#ifdef SE_CLASS2
592 check_valid(mt);
593 check_valid(this,8);
594#endif
595 this->gr = mt.gr;
596 this->domain = mt.domain;
597 this->gp.swap(mt.gp);
598 this->owner_cost_sub.swap(mt.owner_cost_sub);
599 this->owner_scs.swap(mt.owner_scs);
600 return *this;
601 }
602
610 inline bool operator==(const MetisDistribution & mt)
611 {
612#ifdef SE_CLASS2
613 check_valid(&mt,8);
614 check_valid(this,8);
615#endif
616 bool ret = true;
617
618 ret &= (this->gr == mt.gr);
619 ret &= (this->domain == mt.domain);
620 ret &= (this->gp == mt.gp);
621
622 return ret;
623 }
624
630 void setDistTol(double tol)
631 {
633 }
634
635
636
643 {
644#ifdef SE_CLASS1
645 if (id >= gp.getNVertex())
646 std::cerr << __FILE__ << ":" << __LINE__ << "Such vertex doesn't exist (id = " << id << ", " << "total size = " << gp.getNVertex() << ")\n";
647#endif
648
649 auto fnd = owner_scs.find(id);
650 if (fnd == owner_scs.end())
651 {
652 std::cerr << __FILE__ << ":" << __LINE__ << " Error you are setting a sub-sub-domain that the processor does not own" << std::endl;
653 return 0;
654 }
655
656 size_t ids = fnd->second;
657 return owner_cost_sub.get(ids).w;
658 }
659
665 size_t get_ndec()
666 {
667 return metis_graph.get_ndec();
668 }
669};
670
671#endif /* SRC_DECOMPOSITION_METISDISTRIBUTION_HPP_ */
This class represent an N-dimensional box.
Definition Box.hpp:61
This class construct a cartesian graph.
Structure that store a graph in CSR format or basically in compressed adjacency matrix format.
auto vertex(size_t id) -> decltype(v.get(id))
Function to access the vertex.
auto getChildEdge(size_t v, size_t v_e) -> decltype(e.get(0))
Get the vertex edge.
size_t getNChilds(size_t c) const
Return the number of childs of a vertex.
void swap(Graph_CSR< V, E > &g)
swap the memory of g with this graph
size_t getNVertex() const
Return the number of the vertex.
Class that distribute sub-sub-domains across processors using Metis Library.
MetisDistribution & operator=(MetisDistribution &&mt)
operator=
size_t getSubSubDomainComputationCost(size_t id)
function that get the weight of the vertex
void setDistTol(double tol)
Set the tolerance for each partition.
void write(std::string out)
Write the distribution graph into file.
size_t getProcessorLoad()
Compute the processor load.
size_t getOwnerSubSubDomain(size_t id) const
Return the id of the set sub-sub-domain.
Box< dim, T > domain
rectangular domain to decompose
size_t getNSubSubDomains()
Returns total number of sub-sub-domains.
size_t get_ndec()
Get the decomposition counter.
std::unordered_map< size_t, size_t > owner_scs
unordered map that map global sub-sub-domain to owned_cost_sub id
size_t getComputationalCost(size_t id)
function that get the computational cost of the sub-sub-domain
void refine()
Refine current decomposition.
Graph_CSR< nm_v< dim >, nm_e > & getGraph()
Get the current graph (main)
~MetisDistribution()
Destructor.
openfpm::vector< met_sub_w > owner_cost_sub
list owned sub-sub-domains set for computation cost
MetisDistribution & operator=(const MetisDistribution &mt)
operator=
void createCartGraph(grid_sm< dim, void > &grid, Box< dim, T > dom)
create a Cartesian distribution graph
Graph_CSR< nm_v< dim >, nm_e > gp
Global sub-sub-domain graph.
void setMigrationCost(size_t id, size_t cost)
Set migration cost on a sub-sub domain.
openfpm::vector< met_sub_w > recv_ass
received assignment
void setCommunicationCost(size_t id, size_t e, size_t cost)
Set communication cost between neighborhood sub-sub-domains (weight on the edge)
void getSSDomainPos(size_t id, T(&pos)[dim])
Function that return the position (point P1) of the sub-sub domain box in the space.
size_t getNOwnerSubSubDomains() const
Return the total number of sub-sub-domains in the distribution graph.
bool testing
Flag that indicate if we are doing a test (In general it fix the seed)
Metis< Graph_CSR< nm_v< dim >, nm_e > > metis_graph
Metis decomposer utility.
void redecompose()
Redecompose current decomposition.
grid_sm< dim, void > gr
Structure that store the cartesian grid information.
void check_overflow(size_t id)
Check that the sub-sub-domain id exist.
void setComputationCost(size_t id, size_t cost)
Set computation cost on a sub-sub domain.
size_t getNSubSubDomainNeighbors(size_t id)
Returns total number of neighbors of one sub-sub-domain.
bool operator==(const MetisDistribution &mt)
operator==
MetisDistribution(const MetisDistribution &mt)
Copy constructor.
void check_overflowe(size_t id, size_t e)
Check that the sub-sub-domain id exist.
Vcluster & v_cl
Vcluster.
MetisDistribution(Vcluster<> &v_cl)
constructor
void onTest()
It set the Classs on test mode.
void decompose()
Distribute the sub-sub-domains.
MetisDistribution(MetisDistribution &&mt)
Copy constructor.
float getUnbalance()
Compute the unbalance of the processor compared to the optimal balance.
Helper class to define Metis graph.
size_t get_ndec()
Get the decomposition counter.
void onTest(bool testing)
It set Metis on test.
void inc_dec()
Increment the decomposition counter.
void setDistTol(real_t tol)
Distribution tolerance.
void initMetisGraph(int nc, bool useWeights)
Initialize the METIS graph.
void execute()
Execute all the requests.
void sum(T &num)
Sum the numbers across all processors and get the result.
bool Bcast(openfpm::vector< T, Mem, layout_base > &v, size_t root)
Broadcast the data to all processors.
size_t getProcessUnitID()
Get the process unit id.
size_t getProcessingUnits()
Get the total number of processors.
bool recv(size_t proc, size_t tag, void *v, size_t sz)
Recv data from a processor.
bool send(size_t proc, size_t tag, const void *mem, size_t sz)
Send data to a processor.
Implementation of VCluster class.
Definition VCluster.hpp:59
bool SGather(T &send, S &recv, size_t root)
Semantic Gather, gather the data from all processors into one node.
Definition VCluster.hpp:450
Declaration grid_sm.
Definition grid_sm.hpp:167
__device__ __host__ const size_t(& getSize() const)[N]
Return the size of the grid as an array.
Definition grid_sm.hpp:760
Implementation of 1-D std::vector like structure.
size_t size()
Stub size.
sub-domain list and weight
size_t id
sub-domain id
size_t w
sub-domain weight / assignment (it depend in which context is used)
sub-domain edge graph node