1 | /* |
2 | * DistGraphFactory.hpp |
3 | * |
4 | * Created on: Dec 03, 2015 |
5 | * Author: Antonio Leo |
6 | */ |
7 | |
8 | #ifndef DISTGRAPHFACTORYOLD_HPP_ |
9 | #define DISTGRAPHFACTORYOLD_HPP_ |
10 | |
11 | #include "VCluster/VCluster.hpp" |
12 | #include "Vector/map_vector.hpp" |
13 | #include "Graph/map_graph.hpp" |
14 | #include "Grid/grid_sm.hpp" |
15 | #include "Space/Shape/Box.hpp" |
16 | #include "Space/Shape/HyperCube.hpp" |
17 | #include "parmetis.h" |
18 | |
19 | /*! \brief This class work as a functor |
20 | * |
21 | * For each number in the boost::mpl::vector (for example 3 6) set the properties of the vertex at the |
22 | * specified id (3 6) with pos[d] * spacing[d] with d running from 0 to 1, pos[d] the position id of the vertex |
23 | * spacing the grid spacing |
24 | * |
25 | * Example |
26 | * |
27 | * if we give a grid_key of dimension 2 4x4 the expression "pos[d] * spacing[d]" |
28 | * will assume the value |
29 | * |
30 | * (0.0 0.0) (0.25 0.0) ...... (1.0 0.0) |
31 | * (0.0 0.25)................. (1.0 0.25) |
32 | * .................................... |
33 | * (0.0 1.0).................. (1.0 1.0) |
34 | * |
35 | * and the properties 3 6 will be filled with the numbers 0.0 0.0 ....... 1.0 1.0 |
36 | * progressively |
37 | * |
38 | * \tparam dim Dimensionality of the cartesian grid |
39 | * \tparam dT type of the domain |
40 | * \tparam G_v vertex type object |
41 | * \tparam v boost::mpl::vector containing all the index to fill |
42 | * \tparam is_stub when is true, produce a trivial operator(), |
43 | * to use when v is an empty vector to avoid compilation error |
44 | * |
45 | */ |
46 | |
47 | template<unsigned int dim, typename dT, typename G_v, typename v, int impl> |
48 | class fill_prop_v |
49 | { |
50 | //! Reference to an array containing the spacing |
51 | const dT (&szd)[dim]; |
52 | |
53 | //! grid_key_dx Reference containing the actual position |
54 | grid_key_dx<dim> & gk; |
55 | |
56 | //! Vertex object to fill |
57 | G_v & g_v; |
58 | |
59 | //! grid info |
60 | const grid_sm<dim, void> & gs; |
61 | |
62 | public: |
63 | |
64 | //! Fill the object from where to take the properties |
65 | fill_prop_v(G_v & g_v, const dT (&szd)[dim], grid_key_dx<dim> & gk, const grid_sm<dim, void> & gs) : |
66 | szd(szd), gk(gk), g_v(g_v), gs(gs) |
67 | { |
68 | } |
69 | |
70 | //! It call the function for each property we want to copy |
71 | template<typename T> |
72 | void operator()(T& t) const |
73 | { |
74 | typedef typename boost::fusion::result_of::at<v, boost::mpl::int_<T::value>>::type t_val; |
75 | |
76 | g_v.template get<t_val::value>() = gk.get(T::value) * szd[T::value]; |
77 | } |
78 | }; |
79 | |
80 | |
81 | /*! \brief This class work as a functor |
82 | * |
83 | * For each number in the boost::mpl::vector (for example 3 6) set the properties of the vertex at the |
84 | * specified id (3 6) with pos[d] * spacing[d] with d running from 0 to 1, pos[d] the position id of the vertex |
85 | * spacing the grid spacing |
86 | * |
87 | * Example |
88 | * |
89 | * if we give a grid_key of dimension 2 4x4 the expression "pos[d] * spacing[d]" |
90 | * will assume the value |
91 | * |
92 | * (0.0 0.0) (0.25 0.0) ...... (1.0 0.0) |
93 | * (0.0 0.25)................. (1.0 0.25) |
94 | * .................................... |
95 | * (0.0 1.0).................. (1.0 1.0) |
96 | * |
97 | * and the properties 3 6 will be filled with the numbers 0.0 0.0 ....... 1.0 1.0 |
98 | * progressively |
99 | * |
100 | * \tparam dim Dimensionality of the cartesian grid |
101 | * \tparam dT type of the domain |
102 | * \tparam G_v vertex type object |
103 | * \tparam v boost::mpl::vector containing all the index to fill |
104 | * |
105 | */ |
106 | |
107 | template<unsigned int dim, typename dT, typename G_v, typename v> |
108 | class fill_prop_v<dim, dT, G_v, v, 0> |
109 | { |
110 | |
111 | public: |
112 | |
113 | //! Fill the object from where to take the properties |
114 | fill_prop_v(G_v & g_v, const dT (&szd)[dim], grid_key_dx<dim> & gk, const grid_sm<dim, void> & gs) |
115 | { |
116 | } |
117 | |
118 | //! It call the function for each property we want to copy |
119 | template<typename T> |
120 | void operator()(T& t) const |
121 | { |
122 | } |
123 | }; |
124 | |
125 | /*! \brief This class work as a functor |
126 | * |
127 | * For each number in the boost::mpl::vector (for example 3 6) set the properties of the vertex at the |
128 | * specified id (3 6) with pos[d] * spacing[d] with d running from 0 to 1, pos[d] the position id of the vertex |
129 | * spacing the grid spacing |
130 | * |
131 | * Example |
132 | * |
133 | * if we give a grid_key of dimension 2 4x4 the expression "pos[d] * spacing[d]" |
134 | * will assume the value |
135 | * |
136 | * (0.0 0.0) (0.25 0.0) ...... (1.0 0.0) |
137 | * (0.0 0.25)................. (1.0 0.25) |
138 | * .................................... |
139 | * (0.0 1.0).................. (1.0 1.0) |
140 | * |
141 | * and the properties 3 6 will be filled with the numbers 0.0 0.0 ....... 1.0 1.0 |
142 | * progressively |
143 | * |
144 | * \tparam dim Dimensionality of the cartesian grid |
145 | * \tparam dT type of the domain |
146 | * \tparam G_v vertex type object |
147 | * \tparam v boost::mpl::vector containing all the index to fill |
148 | * |
149 | */ |
150 | |
151 | template<unsigned int dim, typename dT, typename G_v, typename v> |
152 | class fill_prop_v<dim, dT, G_v, v, 2> |
153 | { |
154 | |
155 | //! Reference to an array containing the spacing |
156 | const dT (&szd)[dim]; |
157 | |
158 | //! grid_key_dx Reference containing the actual position |
159 | grid_key_dx<dim> & gk; |
160 | |
161 | //! Vertex object to fill |
162 | G_v & g_v; |
163 | |
164 | //! grid info |
165 | const grid_sm<dim, void> & gs; |
166 | |
167 | public: |
168 | |
169 | //! Fill the object from where to take the properties |
170 | fill_prop_v(G_v & g_v, const dT (&szd)[dim], grid_key_dx<dim> & gk, const grid_sm<dim, void> & gs) |
171 | :szd(szd), gk(gk), g_v(g_v), gs(gs) |
172 | { |
173 | } |
174 | |
175 | //! It call the function for each property we want to copy |
176 | template<typename T> |
177 | void operator()(T& t) const |
178 | { |
179 | typedef typename boost::fusion::result_of::at<v, boost::mpl::int_<0>>::type t_val; |
180 | typedef typename boost::mpl::at<typename G_v::T_type::type,t_val>::type s_type; |
181 | |
182 | for (size_t i = 0 ; i < std::extent<s_type>::value ; i++) |
183 | g_v.template get<t_val::value>()[i] = 0.0; |
184 | |
185 | for (size_t i = 0 ; i < dim ; i++) |
186 | g_v.template get<t_val::value>()[i] = gk.get(i) * static_cast<float>(szd[i]); |
187 | } |
188 | }; |
189 | |
190 | /*! \brief Operator for vector and scalar property |
191 | * |
192 | * \tparam i Size of the property |
193 | * \tparam p Type of the property |
194 | * \tparam Graph Graph |
195 | * \tparam pos Array of properties |
196 | */ |
197 | template<int i, typename p, typename Graph, int ... pos> |
198 | struct fill_prop_v_by_type |
199 | { |
200 | |
201 | typedef typename boost::mpl::at<p, boost::mpl::int_<0>>::type v_element; |
202 | typedef typename boost::mpl::at<typename Graph::V_type::type, v_element>::type pos_prop_type; |
203 | |
204 | enum |
205 | { |
206 | value = ((sizeof...(pos) != 0) * (std::is_array<pos_prop_type>::value + 1)) |
207 | }; |
208 | |
209 | }; |
210 | |
211 | /*! \brief Operator for vector and scalar property in the case there are no properties |
212 | * |
213 | * \tparam i Size of the property |
214 | * \tparam p Type of the property |
215 | * \tparam Graph Graph |
216 | * \tparam pos Array of properties |
217 | */ |
218 | template<typename p, typename Graph, int ... pos> |
219 | struct fill_prop_v_by_type<0, p, Graph, pos...> |
220 | { |
221 | enum |
222 | { |
223 | value = 0 |
224 | }; |
225 | |
226 | }; |
227 | |
228 | /*! \brief Graph constructor function specialization |
229 | * |
230 | * On C++ partial function specialization is not allowed, so we need a class to do it |
231 | * |
232 | * \see CartesianGraphFactory method construct |
233 | * |
234 | */ |
235 | |
236 | template<unsigned int dim, typename Graph, int se, typename T, unsigned int dim_c, int ... pos> |
237 | class DistGraph_constr_impl |
238 | { |
239 | public: |
240 | //! Construct Cartesian graph |
241 | static Graph construct(const size_t (&sz)[dim], Box<dim, T> dom) |
242 | { |
243 | Vcluster<> &v_cl = create_vcluster(); |
244 | |
245 | // Calculate the size of the hyper-cubes on each dimension |
246 | T szd[dim]; |
247 | |
248 | for (size_t i = 0; i < dim; i++) |
249 | { |
250 | szd[i] = (dom.getHigh(i) - dom.getLow(i)) / sz[i]; |
251 | } |
252 | |
253 | //! Construct an hyper-cube of dimension dim |
254 | |
255 | HyperCube<dim> hc; |
256 | |
257 | // Construct a grid info |
258 | |
259 | grid_sm<dim, void> g(sz); |
260 | |
261 | //! Get the processor id |
262 | size_t p_id = v_cl.getProcessUnitID(); |
263 | |
264 | //! Get the number of processing units |
265 | size_t Np = v_cl.getProcessingUnits(); |
266 | |
267 | //! Division of vertices in Np graphs |
268 | //! Put (div+1) vertices in mod graphs |
269 | //! Put div vertices in the rest of the graphs |
270 | size_t mod_v = g.size() % Np; |
271 | size_t div_v = g.size() / Np; |
272 | |
273 | //! Distribution vector |
274 | openfpm::vector<idx_t> vtxdist(v_cl.getProcessingUnits() + 1); |
275 | |
276 | for (int i = 0; i <= Np; i++) |
277 | { |
278 | if (i < mod_v) |
279 | vtxdist.get(i) = (div_v + 1) * (i); |
280 | else |
281 | vtxdist.get(i) = (div_v) * (i) + mod_v; |
282 | } |
283 | |
284 | //! Get size of this processor graph |
285 | size_t gp_size = vtxdist.get(p_id + 1) - vtxdist.get(p_id); |
286 | |
287 | //! Graph to construct |
288 | Graph gp(gp_size); |
289 | |
290 | //! Store the decomposition vector inside the distributed graph |
291 | gp.initDistributionVector(vtxdist); |
292 | |
293 | /****************** |
294 | * |
295 | * Create the edges and fill spatial |
296 | * information properties |
297 | * |
298 | ******************/ |
299 | |
300 | //! Construct a key iterator |
301 | grid_key_dx_iterator<dim> k_it(g); |
302 | |
303 | //! Local iterator of the graph |
304 | size_t local_it = 0; |
305 | |
306 | //! Iterate through all the elements |
307 | |
308 | while (k_it.isNext()) |
309 | { |
310 | size_t v_id = g.LinId(k_it.get()); |
311 | |
312 | if (v_id < vtxdist.get(p_id + 1) && v_id >= vtxdist.get(p_id)) |
313 | { |
314 | |
315 | grid_key_dx<dim> key = k_it.get(); |
316 | |
317 | // Vertex object |
318 | |
319 | auto obj = gp.vertex(local_it); |
320 | |
321 | typedef typename to_boost_vmpl<pos...>::type p; |
322 | |
323 | // vertex spatial properties functor |
324 | |
325 | fill_prop_v<dim, T, decltype(gp.vertex(local_it)), typename to_boost_vmpl<pos...>::type, fill_prop_v_by_type<sizeof...(pos), p, Graph, pos...>::value> flp(obj, szd, key, g); |
326 | |
327 | // fill properties |
328 | |
329 | boost::mpl::for_each<boost::mpl::range_c<int, 0, sizeof...(pos)> >(flp); |
330 | |
331 | // set map global to local in the graph, needed because vertex is already created without addVertex method |
332 | |
333 | gp.setGlobalMap(v_id, local_it, v_id); |
334 | |
335 | // Get the combinations of dimension d |
336 | |
337 | for (size_t d = dim - 1; d >= dim_c; d--) |
338 | { |
339 | // create the edges for that dimension |
340 | |
341 | std::vector<comb<dim>> c = hc.getCombinations_R(d); |
342 | |
343 | // for each combination calculate a safe linearization and create an edge |
344 | |
345 | for (size_t j = 0; j < c.size(); j++) |
346 | { |
347 | // Calculate the element size |
348 | |
349 | T ele_sz = 0; |
350 | |
351 | // for each dimension multiply and reduce |
352 | |
353 | for (size_t s = 0; s < dim; s++) |
354 | { |
355 | ele_sz += szd[s] * abs(c[j][s]); |
356 | } |
357 | |
358 | // Calculate the end point vertex id |
359 | // Calculate the start point id |
360 | |
361 | size_t start_v = local_it; |
362 | size_t end_v = g.template LinId<CheckExistence>(key, c[j].getComb()); |
363 | |
364 | // check if the end_v is valid globally |
365 | if (end_v < g.size()) |
366 | { |
367 | // Add an edge and set the the edge property to the size of the face (communication weight) |
368 | gp.template addEdge<NoCheck>(start_v, end_v).template get<se>() = ele_sz; |
369 | } |
370 | } |
371 | } |
372 | ++local_it; |
373 | } |
374 | ++k_it; |
375 | } |
376 | |
377 | return gp; |
378 | } |
379 | }; |
380 | |
381 | /*! \brief Graph constructor function specialization |
382 | * |
383 | * On C++ partial function specialization is not allowed, so we need a class to do it |
384 | * This specialization handle the case when we have NO_EDGE option active |
385 | * |
386 | * \see CartesianGraphFactory method construct |
387 | * |
388 | */ |
389 | |
390 | template<unsigned int dim, typename Graph, typename T, unsigned int dim_c, int ... pos> |
391 | class DistGraph_constr_impl<dim, Graph, NO_EDGE, T, dim_c, pos...> |
392 | { |
393 | public: |
394 | //! Construct Cartesian graph |
395 | static Graph construct(const size_t (&sz)[dim], Box<dim, T> dom) |
396 | { |
397 | Vcluster<> &v_cl = create_vcluster(); |
398 | |
399 | // Calculate the size of the hyper-cubes on each dimension |
400 | |
401 | T szd[dim]; |
402 | |
403 | for (size_t i = 0; i < dim; i++) |
404 | { |
405 | szd[i] = (dom.getHigh(i) - dom.getLow(i)) / sz[i]; |
406 | } |
407 | |
408 | //! Construct an hyper-cube of dimension dim |
409 | |
410 | HyperCube<dim> hc; |
411 | |
412 | // Construct a grid info |
413 | |
414 | grid_sm<dim, void> g(sz); |
415 | |
416 | //! Get the processor id |
417 | size_t p_id = v_cl.getProcessUnitID(); |
418 | |
419 | //! Get the number of processing units |
420 | size_t Np = v_cl.getProcessingUnits(); |
421 | |
422 | //! Division of vertices in Np graphs |
423 | //! Put (div+1) vertices in mod graphs |
424 | //! Put div vertices in the rest of the graphs |
425 | size_t mod_v = g.size() % Np; |
426 | size_t div_v = g.size() / Np; |
427 | |
428 | //! Distribution vector |
429 | openfpm::vector<idx_t> vtxdist(v_cl.getProcessingUnits() + 1); |
430 | |
431 | for (size_t i = 0; i <= Np; i++) |
432 | { |
433 | if (i < mod_v) |
434 | vtxdist.get(i) = (div_v + 1) * (i); |
435 | else |
436 | vtxdist.get(i) = (div_v) * (i) + mod_v; |
437 | } |
438 | |
439 | size_t gp_size = vtxdist.get(p_id + 1) - vtxdist.get(p_id); |
440 | |
441 | //! Graph to construct |
442 | Graph gp(gp_size); |
443 | |
444 | //! Store the decomposition vector inside the distributed graph |
445 | gp.initDistributionVector(vtxdist); |
446 | |
447 | /****************** |
448 | * |
449 | * Create the edges and fill spatial |
450 | * information properties |
451 | * |
452 | ******************/ |
453 | |
454 | //! Construct a key iterator |
455 | grid_key_dx_iterator<dim> k_it(g); |
456 | |
457 | //! Local iterator of the graph |
458 | size_t local_it = 0; |
459 | |
460 | //! Iterate through all the elements |
461 | |
462 | while (k_it.isNext()) |
463 | { |
464 | size_t v_id = g.LinId(k_it.get()); |
465 | |
466 | if (v_id < (size_t)vtxdist.get(p_id + 1) && v_id >= (size_t)vtxdist.get(p_id)) |
467 | { |
468 | grid_key_dx<dim> key = k_it.get(); |
469 | |
470 | // Vertex object |
471 | auto obj = gp.vertex(local_it); |
472 | |
473 | typedef typename to_boost_vmpl<pos...>::type p; |
474 | |
475 | // vertex spatial properties functor |
476 | |
477 | fill_prop_v<dim, T, decltype(gp.vertex(local_it)), typename to_boost_vmpl<pos...>::type, fill_prop_v_by_type<sizeof...(pos), p, Graph, pos...>::value> flp(obj, szd, key, g); |
478 | |
479 | // fill properties |
480 | |
481 | boost::mpl::for_each<boost::mpl::range_c<int, 0, sizeof...(pos)> >(flp); |
482 | |
483 | // set map global to local in the graph, needed because vertex is already created without addVertex method |
484 | |
485 | gp.setGlobalMap(v_id, local_it, v_id); |
486 | |
487 | // Get the combinations of dimension d |
488 | |
489 | for (size_t d = dim - 1; d >= dim_c; d--) |
490 | { |
491 | // create the edges for that dimension |
492 | |
493 | std::vector<comb<dim>> c = hc.getCombinations_R(d); |
494 | |
495 | // for each combination calculate a safe linearization and create an edge |
496 | |
497 | for (size_t j = 0; j < c.size(); j++) |
498 | { |
499 | // Calculate the element size |
500 | |
501 | T ele_sz = 0; |
502 | |
503 | // for each dimension multiply and reduce |
504 | |
505 | for (size_t s = 0; s < dim; s++) |
506 | { |
507 | ele_sz += szd[s] * abs(c[j][s]); |
508 | } |
509 | |
510 | // Calculate the end point vertex id |
511 | // Calculate the start point id |
512 | |
513 | size_t start_v = local_it; |
514 | size_t end_v = g.template LinId<CheckExistence>(key, c[j].getComb()); |
515 | |
516 | // check if the end_v is valid globally |
517 | if (end_v < g.size()) |
518 | { |
519 | // Add an edge and set the the edge property to the size of the face (communication weight) |
520 | gp.addEdge(start_v, end_v, v_id, end_v); |
521 | } |
522 | } |
523 | } |
524 | ++local_it; |
525 | } |
526 | ++k_it; |
527 | } |
528 | return gp; |
529 | } |
530 | }; |
531 | |
532 | /*! \brief This class construct a cartesian graph |
533 | * |
534 | * This class construct a cartesian graph |
535 | * |
536 | * \param dim dimensionality of the cartesian grid |
537 | * |
538 | */ |
539 | |
540 | template<unsigned int dim, typename Graph> |
541 | class DistGraphFactory |
542 | { |
543 | |
544 | public: |
545 | |
546 | /*! \brief Construct a cartesian graph, with V and E edge properties |
547 | * |
548 | * Each vertex is a subspace (Hyper-cube) of dimension dim, each vertex is |
549 | * connected with an edge if two vertex (Hyper-cube) share a element of dimension grater than |
550 | * dim_c. One property can be used to store the contact size or the d-dimensional |
551 | * surface in common between two connected hyper-cube. |
552 | * |
553 | * \param sz Vector that store the size of the grid on each dimension |
554 | * \param dom Box enclosing the physical domain |
555 | * |
556 | * \tparam se Indicate which properties fill with the contact size. The |
557 | * contact size is the point, line , surface, d-dimensional object size |
558 | * in contact (in common) between two hyper-cube. NO_EDGE indicate |
559 | * no property will store this information |
560 | * \tparam T type of the domain like (int real complex ... ) |
561 | * \tparam dim_c Connectivity dimension |
562 | * \tparam pos... (optional)one or more integer indicating the spatial properties |
563 | * |
564 | */ |
565 | template<int se, typename T, unsigned int dim_c, int ... pos> |
566 | static Graph construct(const size_t (&sz)[dim], Box<dim, T> dom) |
567 | { |
568 | return DistGraph_constr_impl<dim, Graph, se, T, dim_c, pos...>::construct(sz, dom); |
569 | } |
570 | }; |
571 | |
572 | #endif /* DISTGRAPHFACTORY_HPP_ */ |
573 | |