1/*
2 * grid_dist_util.hpp
3 *
4 * Created on: Jan 28, 2016
5 * Author: i-bird
6 */
7
8#ifndef SRC_GRID_GRID_DIST_UTIL_HPP_
9#define SRC_GRID_GRID_DIST_UTIL_HPP_
10
11#include "NN/CellList/CellDecomposer.hpp"
12#include "Decomposition/common.hpp"
13
14/*! \brief get cellDecomposer parameters
15 *
16 * \tparam dim dimensionality
17 *
18 * \param c_g get the parameters of the cell decomposer
19 * \param g_sz global grid parameters
20 *
21 */
22template<unsigned int dim> void getCellDecomposerPar(size_t (& c_g)[dim], const size_t (& g_sz)[dim], const size_t (& bc)[dim])
23{
24 for (size_t i = 0 ; i < dim ; i++)
25 {
26 if (bc[i] == NON_PERIODIC)
27 c_g[i] = (g_sz[i]-1 > 0)?(g_sz[i]-1):1;
28 else
29 c_g[i] = g_sz[i];
30 }
31}
32
33
34/*! \brief Create NON_PERIODIC data structure
35 *
36 * \tparam dim Dimensionality
37 *
38 * \return structure that define the non periodicity of the grid
39 *
40 */
41template<unsigned int dim> periodicity<dim> create_non_periodic()
42{
43 periodicity<dim> p;
44
45 for(size_t i = 0 ; i < dim ; i++)
46 p.bc[i] = NON_PERIODIC;
47
48 return p;
49}
50
51template<unsigned int dim>
52size_t get_gdb_ext(const openfpm::vector<GBoxes<dim>> & gdb_ext, size_t start , size_t stop, size_t k)
53{
54 for (size_t i = start ; i < stop ; i++)
55 {
56 if (gdb_ext.get(i).k == k)
57 {return i;}
58 }
59
60 // not found
61 return (size_t)-1;
62}
63
64/*! \brief Add a box to gdb_ext
65 *
66 * \param on which gdb_ext array add the box
67 * \param k from which definition box it come from
68 * This parameter make sense only when the grid is not defined everywhere
69 * \param grid of the sub-domain
70 * \param grid of the sub-domain inclusive of ghost
71 *
72 */
73template<unsigned int dim>
74void add_to_gdb_ext(openfpm::vector<GBoxes<dim>> & gdb_ext, size_t k, Box<dim,long int> & sp_t, Box<dim,long int> & sp_tg)
75{
76 // Add gdb_ext
77 gdb_ext.add();
78
79 //! Save the origin of the sub-domain of the local grid
80 gdb_ext.last().origin = sp_tg.getP1();
81
82 // save information about the local grid: domain box seen inside the domain + ghost box (see GDBoxes for a visual meaning)
83 // and where the GDBox start, or the origin of the local grid (+ghost) in global coordinate
84 gdb_ext.last().Dbox = sp_t;
85 gdb_ext.last().Dbox -= sp_tg.getP1();
86
87 gdb_ext.last().GDbox = sp_tg;
88 gdb_ext.last().GDbox -= sp_tg.getP1();
89
90 gdb_ext.last().k = k;
91}
92
93/*! \brief Create the gdb_ext
94 *
95 * It is a fundamental function, because it create the structure that store the information of the local grids. In
96 * particular from the continuous decomposed domain it calculate the grid that each sub-domain store
97 *
98 * \param gdb_ext output Vector of Boxes that define the local grids extension
99 * \param dec Decomposition
100 * \param cd_sm CellDecomposer the size of cell is equal to the distance between grid points
101 *
102 */
103template<int dim, typename Decomposition>
104inline void create_gdb_ext(openfpm::vector<GBoxes<Decomposition::dims>> & gdb_ext,
105 openfpm::vector<size_t> & gdb_ext_markers,
106 Decomposition & dec,
107 CellDecomposer_sm<Decomposition::dims,typename Decomposition::stype,shift<dim,typename Decomposition::stype>> & cd_sm,
108 openfpm::vector<Box<Decomposition::dims,long int>> & bx_create,
109 const Ghost<Decomposition::dims,long int> & exp,
110 bool use_bx_def)
111{
112 gdb_ext.clear();
113 gdb_ext_markers.clear();
114
115 // Get the number of local grid needed
116 size_t n_grid = dec.getNSubDomain();
117
118 // Allocate the grids
119 for (size_t i = 0 ; i < n_grid ; i++)
120 {
121 gdb_ext_markers.add(gdb_ext.size());
122
123 // Get the local sub-domain (Grid conversion must be done with the domain P1 equivalent to 0.0)
124 // consider that the sub-domain with point P1 equivalent to the domain P1 is a (0,0,0) in grid unit
125 SpaceBox<Decomposition::dims, typename Decomposition::stype> sp = dec.getSubDomain(i);
126 SpaceBox<Decomposition::dims, typename Decomposition::stype> sp_g = dec.getSubDomainWithGhost(i);
127
128 // Because of round off we expand for safety the ghost area
129 // std::nextafter return the next bigger or smaller representable floating
130 // point number
131 for (size_t i = 0 ; i < Decomposition::dims ; i++)
132 {
133 sp_g.setLow(i,std::nextafter(sp_g.getLow(i),sp_g.getLow(i) - 1.0));
134 sp_g.setHigh(i,std::nextafter(sp_g.getHigh(i),sp_g.getHigh(i) + 1.0));
135 }
136
137 // Convert from SpaceBox<dim,St> to SpaceBox<dim,long int>
138 SpaceBox<Decomposition::dims,long int> sp_t = cd_sm.convertDomainSpaceIntoGridUnits(sp,dec.periodicity());
139 SpaceBox<Decomposition::dims,long int> sp_tg = cd_sm.convertDomainSpaceIntoGridUnits(sp_g,dec.periodicity());
140
141 for (size_t i = 0 ; i < Decomposition::dims ; i++)
142 {
143 if (sp_t.getLow(i) < sp_tg.getLow(i))
144 {sp_tg.setLow(i,sp_t.getLow(i));}
145 if (sp_t.getHigh(i) > sp_tg.getHigh(i))
146 {sp_tg.setHigh(i,sp_t.getHigh(i));}
147 }
148
149 if (use_bx_def == true)
150 {
151 // intersect the sub-domain with all the boxes
152
153 for (size_t k = 0 ; k < bx_create.size() ; k++)
154 {
155 Box<Decomposition::dims, long int> inte;
156
157 if (sp_t.Intersect(bx_create.get(k),inte) == true)
158 {
159 // Ok we have a sub-domain now we have to create the ghost part.
160 // The ghost part is created converting the bx_def into a continuous
161 // box expanding this box by the ghost and intersecting this box
162 // with the sub-domain. This is one way to get a ghost area consistent
163 // with the construction of the external and internal ghost boxes,
164 // always calculated in continuous from the decomposition.
165 //
166
167 Box<Decomposition::dims,typename Decomposition::stype> output;
168 Box<Decomposition::dims,typename Decomposition::stype> bx_wg = cd_sm.convertCellUnitsIntoDomainSpaceMiddle(bx_create.get(k));
169 bx_wg.enlarge(dec.getGhost());
170 bx_wg.Intersect(sp_g,output);
171
172 SpaceBox<Decomposition::dims,long int> sp_t2 = inte;
173 SpaceBox<Decomposition::dims,long int> sp_tg2 = cd_sm.convertDomainSpaceIntoGridUnits(output,dec.periodicity());
174
175 add_to_gdb_ext(gdb_ext,k,sp_t2,sp_tg2);
176 }
177 }
178 }
179 else
180 {
181 add_to_gdb_ext(gdb_ext,0,sp_t,sp_tg);
182 }
183 }
184
185 gdb_ext_markers.add(gdb_ext.size());
186}
187
188/*! \brief Create the gdb_ext
189 *
190 * \param gdb_ext Vector of Boxes that define the local grids extension
191 * \param gdb_ext_markers filled with sub-domain markers
192 * see gdb_ext_markers in grid_dist_id for an explanation
193 * \param dec Decomposition
194 * \param sz Global grid grid size
195 * \param domain Domain where the grid is defined
196 * \param spacing Define the spacing of the grid
197 * \param bc boundary conditions
198 *
199 */
200template<int dim, typename Decomposition>
201inline void create_gdb_ext(openfpm::vector<GBoxes<dim>> & gdb_ext,
202 Decomposition & dec,
203 const size_t (& sz)[dim],
204 const Box<Decomposition::dims,typename Decomposition::stype> & domain,
205 typename Decomposition::stype (& spacing)[dim])
206{
207 // Create the cell decomposer
208 CellDecomposer_sm<Decomposition::dims,typename Decomposition::stype, shift<Decomposition::dims,typename Decomposition::stype>> cd_sm;
209
210 size_t cdp[dim];
211
212 // Get the parameters to create a Cell-decomposer
213 getCellDecomposerPar<Decomposition::dims>(cdp,sz,dec.periodicity());
214
215 // Careful cd_sm require the number of cell
216 cd_sm.setDimensions(domain,cdp,0);
217
218 // create an empty vector of boxes
219 openfpm::vector<Box<Decomposition::dims,long int>> empty;
220 Ghost<Decomposition::dims,long int> zero(0);
221
222 //! We are not interested on the markers
223 openfpm::vector<size_t> unused;
224 create_gdb_ext<dim,Decomposition>(gdb_ext,unused,dec,cd_sm,empty,zero,false);
225
226 // fill the spacing
227 for (size_t i = 0 ; i < dim ; i++)
228 {spacing[i] = cd_sm.getCellBox().getP2()[i];}
229}
230
231/*! \brief It store the information about the external ghost box
232 *
233 *
234 */
235template <unsigned int dim> struct e_box_id
236{
237 //! Box defining the external ghost box in global coordinates
238 ::Box<dim,long int> g_e_box;
239
240 //! Box defining the external ghost box in local coordinates for gdb_ext
241 ::Box<dim,long int> l_e_box;
242
243 //! Box defining the external box in local coordinates for received box
244 ::Box<dim,long int> lr_e_box;
245
246 //! Sector position of the external ghost
247 comb<dim> cmb;
248
249 //! Id
250 size_t g_id;
251
252 //! sub_id in which sub-domain this box live
253 size_t sub;
254};
255
256/*! \brief flip box just convert and internal ghost box into an external ghost box and the other way around
257 *
258 * \param box to convert
259 * \param cmb sector position of the box
260 *
261 * \return the converted box
262 *
263 */
264template<unsigned int dim, typename T, typename idT>
265Box<dim,long int> flip_box(const Box<dim,idT> & box, const comb<dim> & cmb, const grid_sm<dim,T> & ginfo)
266{
267 Box<dim,long int> flp;
268
269 for (size_t i = 0 ; i < dim; i++)
270 {
271 if (cmb[i] == 0)
272 {
273 flp.setLow(i,box.getLow(i));
274 flp.setHigh(i,box.getHigh(i));
275 }
276 else if (cmb[i] == 1)
277 {
278 flp.setLow(i,box.getLow(i) + ginfo.size(i));
279 flp.setHigh(i,box.getHigh(i) + ginfo.size(i));
280 }
281 else if (cmb[i] == -1)
282 {
283 flp.setLow(i,box.getLow(i) - ginfo.size(i));
284 flp.setHigh(i,box.getHigh(i) - ginfo.size(i));
285 }
286 }
287
288 return flp;
289}
290
291/*! \brief convert to sub-domain id
292 *
293 * In case the grid is not defined everywhere the ids returned by getProcessorIGhostSub
294 * or any function that return a sub-domain id does not match the ids in gdb_ext. This
295 * function convert it to the correct one
296 *
297 * \param k sub-domain id to convert
298 * \param def_id id of the box that define the real allocated grid
299 * \param gdb_ext_markers markers for sub-domain id gdb_ext
300 *
301 */
302template<unsigned int dim>
303inline size_t convert_to_gdb_ext(size_t sub_id,
304 size_t def_id,
305 openfpm::vector<GBoxes<dim>> & gdb_ext,
306 openfpm::vector<size_t> & gdb_ext_markers)
307{
308 size_t start = gdb_ext_markers.get(sub_id);
309 size_t stop = gdb_ext_markers.get(sub_id+1);
310 return get_gdb_ext(gdb_ext,start,stop,def_id);
311}
312
313/*! \brief It store the information about the local external ghost box
314 *
315 *
316 */
317template <unsigned int dim> struct e_lbox_id
318{
319 //! Box defining the external ghost box in local coordinates
320 ::Box<dim,long int> ebox;
321
322 //! Has this external ghost box initialized
323 bool initialized = false;
324
325 //! sub-domain id of the non-extended sub-domain
326 size_t sub;
327
328 //! to which gdb_ext this external ghost box is linked with
329 //! (in case of grid defined everywhere these two number match)
330 size_t sub_gdb_ext;
331
332 //! external ghost box linked to this internal ghost box
333 size_t k;
334
335 //! Sector position of the local external ghost box
336 comb<dim> cmb;
337};
338
339
340/*! \brief Add a local external ghost box
341 *
342 * \param le_sub sub-domain id
343 * \param s id of the external ghost box
344 * \param j id of the domain not expanded
345 * \param k id of the grid (gdb_ext) this external ghost box is linked with
346 * \param bid where to add the local external ghost box
347 * \param box the box to add
348 * \param cmb quadrant in which the external ghost box live
349 *
350 */
351template<unsigned int dim> inline void add_loc_eg_box(size_t le_sub,
352 size_t se,
353 size_t j,
354 size_t k,
355 openfpm::vector<e_lbox_id<dim>> & bid,
356 const Box<dim,long int> & ebox,
357 comb<dim> & cmb)
358{
359 bid.add();
360
361 bid.last().ebox = ebox;
362
363 bid.last().sub = se;
364 bid.last().sub_gdb_ext = k;
365
366 bid.last().cmb = cmb;
367 bid.last().k = j;
368 bid.last().initialized = true;
369}
370
371/*! Add an entry of for an external ghost box
372 *
373 * \param k sub-domain id to which this external ghost box is linked
374 * \param cmb quadrant where the received linked internal ghost box live
375 * \param output external ghost box
376 * \param g_id global id of the external ghost box, in general this id is communicated
377 * by the processor that has the linked internal ghost-box
378 * \param origin domain where this external ghost box is linked
379 * \param p1 origin of the received internal ghost box
380 *
381 */
382template<unsigned int dim> inline void add_eg_box(size_t k,
383 const comb<dim> & cmb,
384 const Box<dim,long int> & output,
385 size_t g_id,
386 const Point<dim,long int> & origin,
387 const Point<dim,long int> & p1,
388 openfpm::vector<e_box_id<dim>> & bid)
389{
390 // link
391
392 size_t sub_id = k;
393
394 e_box_id<dim> bid_t;
395 bid_t.sub = sub_id;
396 bid_t.cmb = cmb;
397 bid_t.cmb.sign_flip();
398 ::Box<dim,long int> ib = output;
399 bid_t.g_e_box = ib;
400 bid_t.g_id = g_id;
401
402 // Translate in local coordinate for gdb_ext
403 Box<dim,long int> tb = ib;
404 tb -= origin;
405 bid_t.l_e_box = tb;
406
407 // Translate in local coordinates for the received box
408 Box<dim,long int> tbr = ib;
409 bid_t.lr_e_box = tbr;
410
411 bid.add(bid_t);
412}
413
414/*! \brief Result of the itersection of a box with an array of boxes
415 *
416 *
417 */
418template<unsigned int dim>
419struct result_box
420{
421 //! id of the box in the array that produced an non-empty intersection
422 size_t id;
423
424 //! valid result of the itersection
425 Box<dim,long int> bx;
426};
427
428/*! \brief Intersect a box with an array of boxes
429 *
430 * \param bx_def array of boxes
431 * \param bx box to intersect with
432 * \param use_bx_def in case of false the box bx is added to the result array
433 * and nothing is performed
434 * \param result results of the intersections
435 *
436 */
437template<unsigned int dim>
438void bx_intersect(openfpm::vector<Box<dim,long int>> & bx_def,
439 bool use_bx_def,
440 Box<dim,long int> & bx,
441 openfpm::vector_std<result_box<dim>> & result)
442{
443 result.clear();
444
445 if (use_bx_def == false)
446 {
447 result_box<dim> tmp;
448 tmp.bx = bx;
449 tmp.id = 0;
450
451 result.add(tmp);
452 return;
453 }
454
455 for (size_t i = 0 ; i < bx_def.size() ; i++)
456 {
457 result_box<dim> inte;
458 if (bx.Intersect(bx_def.get(i),inte.bx))
459 {
460 inte.id = i;
461 result.add(inte);
462 }
463 }
464}
465
466/*! \brief it store a box, its unique id and the sub-domain from where it come from
467 *
468 */
469template<unsigned int dim> struct i_box_id
470{
471 //! Box
472 ::Box<dim,long int> box;
473
474 //! id
475 size_t g_id;
476
477 //! r_sub id of the sub-domain in the sent list
478 size_t r_sub;
479
480 //! Sector where it live the linked external ghost box
481 comb<dim> cmb;
482
483
484
485 //! sub
486 size_t sub;
487};
488
489/*! \brief set of internal ghost box to send
490 *
491 *
492 */
493template<unsigned int dim>
494struct ibox_send
495{
496 //! global id
497 size_t gid;
498
499 //! internal ghost box
500 Box<dim,long int> ibox;
501};
502
503
504
505/*! \brief it store an internal ghost box, the linked external ghost box and the sub-domain from where
506 * it come from as internal ghost box
507 *
508 */
509template<unsigned int dim> struct i_lbox_id
510{
511 //! Box
512 ::Box<dim,long int> box;
513
514 //! sub-domain id (of the extended sub-domain).
515 //! sub and sub_gdb_ext match if use_bx_def is not used in the
516 //! distributed grid
517 size_t sub;
518
519 //! to which gdb_ext this internal ghost box is linked with
520 size_t sub_gdb_ext;
521
522 //! external ghost box linked to this internal ghost box
523 openfpm::vector<size_t> k;
524
525 //! combination
526 comb<dim> cmb;
527};
528
529
530/*! \brief For each external ghost id, it contain a set of sub-domain at which this
531 * external box is linked
532 *
533 *
534 */
535template<unsigned int dim>
536struct e_box_multi
537{
538 //! set sub-domain at which with external ghost is linked
539 //! The eb_list are id for the eb_box list
540 openfpm::vector<size_t> eb_list;
541
542 //! This is the id in eb_list that contain an external ghost box
543 //! able to store the full received box
544 size_t full_match;
545
546 //! It store the id of linked eg_box (eg_box.get(e_id) is valid, this mean that e_id store processor id information)
547 //! \see ProctoID function
548 size_t e_id;
549};
550
551
552/*! \brief Per-processor Internal ghost box
553 *
554 */
555template <unsigned int dim> struct ip_box_grid
556{
557 // ghost in grid units
558 openfpm::vector<i_box_id<dim>> bid;
559
560 //! processor id
561 size_t prc;
562};
563
564/*! \brief local Internal ghost box
565 *
566 */
567template <unsigned int dim> struct i_lbox_grid
568{
569 // ghost in grid units
570 openfpm::vector<i_lbox_id<dim>> bid;
571};
572
573/*! \brief Per-processor external ghost box
574 *
575 */
576template <unsigned int dim>struct ep_box_grid
577{
578 // ghost in grid units
579 openfpm::vector<e_box_id<dim>> bid;
580
581 //! processor id
582 size_t prc;
583
584 //! total number of received points
585 size_t recv_pnt;
586
587 //! Number of received boxes
588 size_t n_r_box;
589};
590
591/*! \brief Per-processor external ghost box
592 *
593 */
594template <unsigned int dim> struct e_lbox_grid
595{
596 // ghost in grid units
597 openfpm::vector<e_lbox_id<dim>> bid;
598};
599
600
601#endif /* SRC_GRID_GRID_DIST_UTIL_HPP_ */
602