1 | #ifndef DEC_OPTIMIZER_HPP |
2 | #define DEC_OPTIMIZER_HPP |
3 | |
4 | #include "Grid/iterators/grid_key_dx_iterator_sub.hpp" |
5 | #include "Grid/iterators/grid_skin_iterator.hpp" |
6 | |
7 | /*! \brief this class represent a wavefront of dimension dim |
8 | * |
9 | * \tparam dim Dimensionality of the wavefront (dimensionality of the space |
10 | * where it live so the wavefront |
11 | * is dim-1) |
12 | * |
13 | * Each wavefront is identified by one starting point and one stop point. |
14 | * More or less a wavefront is just a box defined in the integer space |
15 | * |
16 | */ |
17 | template <unsigned int dim> |
18 | class wavefront : public Box<dim,size_t> |
19 | { |
20 | public: |
21 | |
22 | //! start point is the property with id 0 (first property) |
23 | static const int start = 0; |
24 | |
25 | //! stop point is the property with id 1 (second property) |
26 | static const int stop = 1; |
27 | }; |
28 | |
29 | ///// Unfortunately it seem that nvcc it specialize incorrectly this data structure so we have to specialize for the broken cases |
30 | |
31 | template<unsigned int dim> |
32 | struct is_typedef_and_data_same<true,wavefront<dim>> |
33 | { |
34 | enum |
35 | { |
36 | value = 1 |
37 | }; |
38 | }; |
39 | |
40 | /*! \brief This class take a graph representing the space decomposition and produce a |
41 | * simplified version |
42 | * |
43 | * Given a Graph_CSR and a seed point produce an alternative decomposition in boxes with |
44 | * less sub-domain. In the following we referee with sub-domain the boxes produced by this |
45 | * algorithm and sub-sub-domain the sub-domain before reduction |
46 | * |
47 | */ |
48 | |
49 | template <unsigned int dim, typename Graph> |
50 | class dec_optimizer |
51 | { |
52 | //! Contain information about the grid size |
53 | grid_sm<dim,void> gh; |
54 | |
55 | private: |
56 | |
57 | /*! \brief Expand one wavefront |
58 | * |
59 | * \param v_w wavefronts |
60 | * \param w_comb wavefront expansion combinations |
61 | * \param d direction of expansion |
62 | * |
63 | */ |
64 | void expand_one_wf(openfpm::vector<wavefront<dim>> & v_w, std::vector<comb<dim>> & w_comb , size_t d) |
65 | { |
66 | for (size_t j = 0 ; j < dim ; j++) |
67 | { |
68 | v_w.template get<wavefront<dim>::stop>(d)[j] = v_w.template get<wavefront<dim>::stop>(d)[j] + w_comb[d].c[j]; |
69 | v_w.template get<wavefront<dim>::start>(d)[j] = v_w.template get<wavefront<dim>::start>(d)[j] + w_comb[d].c[j]; |
70 | } |
71 | } |
72 | |
73 | |
74 | /*! \brief Adjust the other wavefronts |
75 | * |
76 | * \param v_w array of wavefronts |
77 | * \param hyp Hyper cube used to adjust the wavefront |
78 | * \param w_comb for each wavefront indicate their position (normal to the face of the wavefront) |
79 | * \param d direction |
80 | * |
81 | */ |
82 | void adjust_others_wf(openfpm::vector<wavefront<dim>> & v_w, HyperCube<dim> & hyp, std::vector<comb<dim>> & w_comb, size_t d) |
83 | { |
84 | // expand the intersection of the wavefronts |
85 | |
86 | std::vector<comb<dim>> q_comb = SubHyperCube<dim,dim-1>::getCombinations_R(w_comb[d],dim-2); |
87 | |
88 | // Eliminate the w_comb[d] direction |
89 | |
90 | for (size_t k = 0 ; k < q_comb.size() ; k++) |
91 | { |
92 | for (size_t j = 0 ; j < dim ; j++) |
93 | { |
94 | if (w_comb[d].c[j] != 0) |
95 | { |
96 | q_comb[k].c[j] = 0; |
97 | } |
98 | } |
99 | } |
100 | |
101 | // for all the combinations |
102 | for (size_t j = 0 ; j < q_comb.size() ; j++) |
103 | { |
104 | size_t id = hyp.LinId(q_comb[j]); |
105 | |
106 | // get the combination of the direction d |
107 | bool is_pos = hyp.isPositive(d); |
108 | |
109 | // is positive, modify the stop point or the starting point |
110 | |
111 | for (size_t s = 0 ; s < dim ; s++) |
112 | { |
113 | if (is_pos == true) |
114 | {v_w.template get<wavefront<dim>::stop>(id)[s] = v_w.template get<wavefront<dim>::stop>(id)[s] + w_comb[d].c[s];} |
115 | else |
116 | {v_w.template get<wavefront<dim>::start>(id)[s] = v_w.template get<wavefront<dim>::start>(id)[s] + w_comb[d].c[s];} |
117 | } |
118 | } |
119 | } |
120 | |
121 | /*! \brief Fill the wavefront position |
122 | * |
123 | * \tparam prp property to set |
124 | * |
125 | * \param graph we are processing |
126 | * \param v_w array of wavefronts |
127 | * |
128 | */ |
129 | template<unsigned int prp> void write_wavefront(Graph & graph,openfpm::vector<wavefront<dim>> & v_w) |
130 | { |
131 | // fill the wall domain with 0 |
132 | |
133 | fill_domain<prp>(graph,gh.getBox(),0); |
134 | |
135 | // fill the wavefront |
136 | |
137 | for (int i = 0 ; i < v_w.size() ; i++) |
138 | { |
139 | Box<dim,size_t> box = wavefront<dim>::getBox(v_w.get(i)); |
140 | |
141 | fill_domain<prp>(graph,box,1); |
142 | } |
143 | } |
144 | |
145 | /*! \brief Fill the domain |
146 | * |
147 | * \tparam p_sub property to set with the sub-domain id |
148 | * |
149 | * \param graph we are processing |
150 | * \param box Box to fill |
151 | * \param ids value to fill with |
152 | * |
153 | */ |
154 | |
155 | template<unsigned int p_sub> void fill_domain(Graph & graph,const Box<dim,size_t> & box, long int ids) |
156 | { |
157 | // Create a subgrid iterator |
158 | grid_key_dx_iterator_sub<dim,no_stencil,grid_sm<dim,void>,do_not_print_warning_on_adjustment<dim,grid_sm<dim,void>>> g_sub(gh,box.getKP1(),box.getKP2()); |
159 | |
160 | // iterate through all grid points |
161 | |
162 | while (g_sub.isNext()) |
163 | { |
164 | // get the actual key |
165 | const grid_key_dx<dim> & gk = g_sub.get(); |
166 | |
167 | // get the vertex and set the sub id |
168 | |
169 | graph.vertex(gh.LinId(gk)).template get<p_sub>() = ids; |
170 | |
171 | // next subdomain |
172 | ++g_sub; |
173 | } |
174 | } |
175 | |
176 | /*! \brief Add the boundary domain of id p_id to the queue |
177 | * |
178 | * \tparam p_sub property id where to store the sub-domain decomposition |
179 | * \tparam p_id property id where is stored the decomposition |
180 | * |
181 | * \param domains vector with sub-sub-domains still to process |
182 | * \param v_w array of wave-fronts |
183 | * \param graph we are processing |
184 | * \param w_comb wavefront combination, it is the normal vector to the wavefront |
185 | * \param pr_id processor id for which we are optimizing the decomposition |
186 | * \param bc boundary conditions |
187 | * |
188 | */ |
189 | template<unsigned int p_sub, unsigned int p_id> void add_to_queue(openfpm::vector<size_t> & domains, openfpm::vector<wavefront<dim>> & v_w, Graph & graph, std::vector<comb<dim>> & w_comb, long int pr_id, const size_t(& bc)[dim]) |
190 | { |
191 | // create a new queue |
192 | openfpm::vector<size_t> domains_new; |
193 | |
194 | // push in the new queue, the old domains of the queue that are not assigned element |
195 | |
196 | for (size_t j = 0 ; j < domains.size() ; j++) |
197 | { |
198 | long int gs = graph.vertex(domains.get(j)).template get<p_sub>(); |
199 | if (gs < 0) |
200 | { |
201 | // not assigned push it |
202 | |
203 | domains_new.add(domains.get(j)); |
204 | } |
205 | } |
206 | |
207 | // Create an Hyper-cube |
208 | HyperCube<dim> hyp; |
209 | |
210 | for (size_t d = 0 ; d < v_w.size() ; d++) |
211 | { |
212 | expand_one_wf(v_w,w_comb,d); |
213 | adjust_others_wf(v_w,hyp,w_comb,d); |
214 | } |
215 | |
216 | // for each expanded wavefront create a sub-grid iterator and add the sub-domain |
217 | |
218 | for (size_t d = 0 ; d < v_w.size() ; d++) |
219 | { |
220 | // Create a sub-grid iterator |
221 | grid_key_dx_iterator_sub_bc<dim,no_stencil,grid_sm<dim,void>,do_not_print_warning_on_adjustment<dim,grid_sm<dim,void>>> g_sub(gh,v_w.template get<wavefront<dim>::start>(d),v_w.template get<wavefront<dim>::stop>(d),bc); |
222 | |
223 | // iterate through all grid points |
224 | |
225 | while (g_sub.isNext()) |
226 | { |
227 | // get the actual key |
228 | const grid_key_dx<dim> & gk = g_sub.get(); |
229 | |
230 | // get the vertex and if does not have a sub-id and is assigned ... |
231 | long int pid = graph.vertex(gh.LinId(gk)).template get<p_sub>(); |
232 | |
233 | // Get the processor id of the sub-sub-domain |
234 | long int pp_id = graph.vertex(gh.LinId(gk)).template get<p_id>(); |
235 | |
236 | // if the sub-sub-domain is not assigned |
237 | if (pid < 0) |
238 | { |
239 | // ... and we are not processing the full graph |
240 | if (pr_id != -1) |
241 | { |
242 | // ... and the processor id of the sub-sub-domain match the part we are processing, add to the queue |
243 | |
244 | if ( pr_id == pp_id) |
245 | domains_new.add(gh.LinId(gk)); |
246 | } |
247 | else |
248 | domains_new.add(gh.LinId(gk)); |
249 | } |
250 | |
251 | ++g_sub; |
252 | } |
253 | } |
254 | |
255 | // copy the new queue to the old one (it not copied, C++11 move semantic) |
256 | domains.swap(domains_new); |
257 | } |
258 | |
259 | /*! \brief Find the biggest hyper-cube |
260 | * |
261 | * starting from one initial sub-domain find the biggest hyper-cube |
262 | * output the box, and fill a list of neighborhood processor |
263 | * |
264 | * \tparam p_sub id of the property storing the sub-decomposition |
265 | * \tparam p_id id of the property containing the decomposition |
266 | * |
267 | * \param start_p initial domain |
268 | * \param graph representing the grid of sub-sub-domain |
269 | * \param box produced box |
270 | * \param v_w Wavefronts |
271 | * \param w_comb wavefronts directions (0,0,1) (0,0,-1) (0,1,0) (0,-1,0) ... |
272 | * |
273 | */ |
274 | template <unsigned int p_sub, unsigned int p_id> void expand_from_point(size_t start_p, Graph & graph, Box<dim,size_t> & box, openfpm::vector<wavefront<dim>> & v_w , std::vector<comb<dim>> & w_comb) |
275 | { |
276 | // We assume that Graph is the rapresentation of a cartesian graph |
277 | // this mean that the direction d is at the child d |
278 | |
279 | // Get the number of wavefronts |
280 | size_t n_wf = w_comb.size(); |
281 | |
282 | // Create an Hyper-cube |
283 | HyperCube<dim> hyp; |
284 | |
285 | // direction of expansion |
286 | |
287 | size_t domain_id = graph.vertex(start_p).template get<p_id>(); |
288 | bool can_expand = true; |
289 | |
290 | // while is possible to expand |
291 | |
292 | while (can_expand) |
293 | { |
294 | // reset can expand |
295 | can_expand = false; |
296 | |
297 | // for each direction of expansion expand the wavefront |
298 | |
299 | for (size_t d = 0 ; d < n_wf ; d++) |
300 | { |
301 | // number of processed sub-domain |
302 | size_t n_proc_sub = 0; |
303 | |
304 | // flag to indicate if the wavefront can expand |
305 | bool w_can_expand = true; |
306 | |
307 | // Create an iterator of the expanded wavefront |
308 | grid_key_dx<dim> start = grid_key_dx<dim>(v_w.template get<wavefront<dim>::start>(d)) + w_comb[d]; |
309 | grid_key_dx<dim> stop = grid_key_dx<dim>(v_w.template get<wavefront<dim>::stop>(d)) + w_comb[d]; |
310 | grid_key_dx_iterator_sub<dim,no_stencil,grid_sm<dim,void>,do_not_print_warning_on_adjustment<dim,grid_sm<dim,void>>> it(gh,start,stop); |
311 | |
312 | // for each sub-domain in the expanded wavefront |
313 | while (it.isNext()) |
314 | { |
315 | // get the wavefront sub-domain id |
316 | size_t sub_w_e = gh.LinId(it.get()); |
317 | |
318 | // we get the processor id of the neighborhood sub-domain on direction d |
319 | // (expanded wavefront) |
320 | size_t exp_p = graph.vertex(sub_w_e).template get<p_id>(); |
321 | |
322 | // Check if already assigned |
323 | long int ass = graph.vertex(sub_w_e).template get<p_sub>(); |
324 | |
325 | // we check if it is the same processor id and is not assigned |
326 | w_can_expand &= ((exp_p == domain_id) & (ass < 0)); |
327 | |
328 | // next domain |
329 | ++it; |
330 | |
331 | // increase the number of processed sub-domain |
332 | n_proc_sub++; |
333 | } |
334 | |
335 | // if we did not processed sub-domain, we cannot expand |
336 | w_can_expand &= (n_proc_sub != 0); |
337 | |
338 | // if you can expand one wavefront we did not reach the end |
339 | can_expand |= w_can_expand; |
340 | |
341 | // if we can expand the wavefront expand it |
342 | if (w_can_expand == true) |
343 | { |
344 | // expand the wavefront |
345 | for (size_t j = 0 ; j < dim ; j++) |
346 | { |
347 | v_w.template get<wavefront<dim>::stop>(d)[j] = v_w.template get<wavefront<dim>::stop>(d)[j] + w_comb[d].c[j]; |
348 | v_w.template get<wavefront<dim>::start>(d)[j] = v_w.template get<wavefront<dim>::start>(d)[j] + w_comb[d].c[j]; |
349 | } |
350 | |
351 | // expand the intersection of the wavefronts |
352 | |
353 | if (dim >= 2) |
354 | { |
355 | std::vector<comb<dim>> q_comb = SubHyperCube<dim,dim-1>::getCombinations_R(w_comb[d],dim-2); |
356 | |
357 | // Eliminate the w_comb[d] direction |
358 | |
359 | for (size_t k = 0 ; k < q_comb.size() ; k++) |
360 | { |
361 | for (size_t j = 0 ; j < dim ; j++) |
362 | { |
363 | if (w_comb[d].c[j] != 0) |
364 | { |
365 | q_comb[k].c[j] = 0; |
366 | } |
367 | } |
368 | } |
369 | |
370 | // for all the combinations |
371 | for (size_t j = 0 ; j < q_comb.size() ; j++) |
372 | { |
373 | size_t id = hyp.LinId(q_comb[j]); |
374 | |
375 | // get the combination of the direction d |
376 | |
377 | bool is_pos = hyp.isPositive(d); |
378 | |
379 | // is positive, modify the stop point or the starting point |
380 | |
381 | for (size_t s = 0 ; s < dim ; s++) |
382 | { |
383 | if (is_pos == true) |
384 | {v_w.template get<wavefront<dim>::stop>(id)[s] = v_w.template get<wavefront<dim>::stop>(id)[s] + w_comb[d].c[s];} |
385 | else |
386 | {v_w.template get<wavefront<dim>::start>(id)[s] = v_w.template get<wavefront<dim>::start>(id)[s] + w_comb[d].c[s];} |
387 | } |
388 | } |
389 | } |
390 | } |
391 | } |
392 | } |
393 | |
394 | // get back the hyper-cube produced |
395 | |
396 | for (size_t i = 0 ; i < dim ; i++) |
397 | { |
398 | // get the index of the wavefront direction |
399 | size_t p_f = hyp.positiveFace(i); |
400 | size_t n_f = hyp.negativeFace(i); |
401 | |
402 | // set the box |
403 | box.setHigh(i,v_w.template get<wavefront<dim>::stop>(p_f)[i]); |
404 | box.setLow(i,v_w.template get<wavefront<dim>::start>(n_f)[i]); |
405 | } |
406 | } |
407 | |
408 | /*! \brief Initialize the wavefronts |
409 | * |
410 | * \param start_p starting point for the wavefront set |
411 | * \param v_w Wavefront array |
412 | * |
413 | */ |
414 | void InitializeWavefront(grid_key_dx<dim> & start_p, openfpm::vector<wavefront<dim>> & v_w) |
415 | { |
416 | // Wavefront to initialize |
417 | |
418 | for (size_t i = 0 ; i < v_w.size() ; i++) |
419 | { |
420 | for (size_t j = 0 ; j < dim ; j++) |
421 | { |
422 | v_w.template get<wavefront<dim>::start>(i)[j] = start_p.get(j); |
423 | v_w.template get<wavefront<dim>::stop>(i)[j] = start_p.get(j); |
424 | } |
425 | } |
426 | } |
427 | |
428 | /*! \brief Get the first seed |
429 | * |
430 | * search in the graph for one sub-domain labelled with processor id |
431 | * to use as seed |
432 | * |
433 | * \tparam p_id property id containing the decomposition |
434 | * \tparam p_sub property id that will contain the sub-domain decomposition |
435 | * |
436 | * \param graph Graph |
437 | * \param id processor id |
438 | * |
439 | * \return a valid seed key |
440 | * |
441 | */ |
442 | template<unsigned int p_id, unsigned int p_sub> grid_key_dx<dim> search_seed(Graph & graph, long int id) |
443 | { |
444 | // if no processor is selected return the first point |
445 | if (id < -1) |
446 | { |
447 | grid_key_dx<dim> key; |
448 | key.zero(); |
449 | |
450 | return key; |
451 | } |
452 | |
453 | // Create a grid iterator |
454 | grid_key_dx_iterator<dim> g_sub(gh); |
455 | |
456 | // iterate through all grid points |
457 | |
458 | while (g_sub.isNext()) |
459 | { |
460 | // get the actual key |
461 | const grid_key_dx<dim> & gk = g_sub.get(); |
462 | |
463 | // if the subdomain has the id we are searching stop |
464 | if ((long int)graph.vertex(gh.LinId(gk)).template get<p_id>() == id && graph.vertex(gh.LinId(gk)).template get<p_sub>() == -1) |
465 | { |
466 | return gk; |
467 | } |
468 | |
469 | ++g_sub; |
470 | } |
471 | |
472 | // If not found return an invalid key |
473 | grid_key_dx<dim> key; |
474 | key.invalid(); |
475 | |
476 | return key; |
477 | } |
478 | |
479 | |
480 | /*! \brief optimize the graph |
481 | * |
482 | * Starting from a domain (hyper-cubic), it create wavefront at the boundary and expand |
483 | * the boundary until the wavefronts cannot expand any more. |
484 | * To the domains inside the hyper-cube one sub-id is assigned. This procedure continue until |
485 | * all the domain of one p_id has a sub-id |
486 | * |
487 | * \tparam p_id property containing the decomposition |
488 | * \tparam p_sub property to fill with the sub-domain decomposition |
489 | * |
490 | * \param start_p seed point |
491 | * \param graph we are processing |
492 | * \param pr_id Processor id (if p_id == -1 the optimization is done for all the processors) |
493 | * \param lb list of sub-domain boxes produced by the algorithm |
494 | * \param box_nn_processor for each sub-domain it list all the neighborhood processors |
495 | * \param ghe Ghost extension in sub-sub-domain units in each direction |
496 | * \param init_sub_id when true p_sub property is initially set to -1 [default true] |
497 | * \param sub_id starting sub_id to enumerate them [default 0] |
498 | * \param bc boundary conditions |
499 | * |
500 | * \return last assigned sub-id |
501 | * |
502 | */ |
503 | template <unsigned int p_sub, unsigned int p_id> size_t optimize(grid_key_dx<dim> & start_p, Graph & graph, long int pr_id, openfpm::vector<Box<dim,size_t>> & lb, openfpm::vector< openfpm::vector<size_t> > & box_nn_processor , const Ghost<dim,long int> & ghe ,const size_t (& bc)[dim], bool init_sub_id = true, size_t sub_id = 0) |
504 | { |
505 | // queue |
506 | openfpm::vector<size_t> v_q; |
507 | |
508 | // box list 2 |
509 | openfpm::vector< openfpm::vector<size_t> > box_nn_processor2; |
510 | |
511 | // Create an hyper-cube |
512 | HyperCube<dim> hyp; |
513 | |
514 | // Get the wavefront combinations |
515 | std::vector<comb<dim>> w_comb = hyp.getCombinations_R(dim-1); |
516 | |
517 | // wavefronts |
518 | openfpm::vector<wavefront<dim>> v_w(w_comb.size()); |
519 | |
520 | // fill the sub decomposition with negative number |
521 | |
522 | if (init_sub_id == true) |
523 | fill_domain<p_sub>(graph,gh.getBox(),-1); |
524 | |
525 | // push the first domain |
526 | v_q.add(gh.LinId(start_p)); |
527 | |
528 | while (v_q.size() != 0) |
529 | { |
530 | // Box |
531 | Box<dim,size_t> box; |
532 | |
533 | // Get the grid_key position from the linearized id |
534 | start_p = gh.InvLinId(v_q.get(0)); |
535 | |
536 | // Initialize the wavefronts from the domain start_p |
537 | InitializeWavefront(start_p,v_w); |
538 | |
539 | // Create the biggest box containing the domain |
540 | expand_from_point<p_sub,p_id>(v_q.get(0),graph,box,v_w,w_comb); |
541 | |
542 | // Add the created box to the list of boxes |
543 | lb.add(box); |
544 | |
545 | // fill the domain |
546 | fill_domain<p_sub>(graph,box,sub_id); |
547 | |
548 | // add the surrounding sub-domain to the queue |
549 | add_to_queue<p_sub,p_id>(v_q,v_w,graph,w_comb,pr_id,bc); |
550 | |
551 | // increment the sub_id |
552 | sub_id++; |
553 | } |
554 | |
555 | return sub_id; |
556 | } |
557 | |
558 | /*! \brief Construct the sub-domain processor list |
559 | * |
560 | * \tparam p_id property that contain the decomposition |
561 | * |
562 | * Each entry is a sub-domain, the list of numbers indicate the neighborhood processors |
563 | * |
564 | * \param graph graph to process |
565 | * \param box_nn_processor for each sub-domain it list all the neighborhood processors |
566 | * \param subs vector of sub-domains |
567 | * \param ghe ghost extensions |
568 | * \param bc boundary conditions |
569 | * \param pr_id processor that we are processing |
570 | * |
571 | */ |
572 | template<unsigned int p_id> void construct_box_nn_processor(Graph & graph, openfpm::vector< openfpm::vector<size_t> > & box_nn_processor, const openfpm::vector<Box<dim,size_t>> & subs, const Ghost<dim,long int> & ghe, const size_t (& bc)[dim], long int pr_id) |
573 | { |
574 | std::unordered_map<size_t,size_t> map; |
575 | |
576 | for (size_t i = 0 ; i < subs.size() ; i++) |
577 | { |
578 | map.clear(); |
579 | Box<dim,size_t> sub = subs.get(i); |
580 | sub.enlarge(ghe); |
581 | |
582 | grid_skin_iterator_bc<dim> gsi(gh,subs.get(i),sub,bc); |
583 | |
584 | while (gsi.isNext()) |
585 | { |
586 | auto key = gsi.get(); |
587 | |
588 | size_t pp_id = graph.vertex(gh.LinId(key)).template get<p_id>(); |
589 | if (pr_id != (long int)pp_id) |
590 | map[pp_id] = pp_id; |
591 | |
592 | ++gsi; |
593 | } |
594 | |
595 | // Add the keys to box_nn_processors |
596 | |
597 | box_nn_processor.add(); |
598 | for ( auto it = map.begin(); it != map.end(); ++it ) |
599 | { |
600 | box_nn_processor.last().add(it->first); |
601 | } |
602 | } |
603 | } |
604 | |
605 | public: |
606 | |
607 | /*! \brief Constructor |
608 | * |
609 | * \param g Graph to simplify |
610 | * \param sz size of the grid on each dimension |
611 | * |
612 | */ |
613 | |
614 | dec_optimizer(Graph & g, const size_t (& sz)[dim]) |
615 | :gh(sz) |
616 | { |
617 | // The graph g is suppose to represent a cartesian grid |
618 | // No check is performed on g |
619 | } |
620 | |
621 | /*! \brief optimize the graph |
622 | * |
623 | * Starting from a sub-sub-domain, it create wavefronts at the boundary and expand |
624 | * the boundary until the wavefronts cannot expand any more, creating a sub-domain covering more sub-sub-domain. |
625 | * This procedure continue until all the domain is covered by a sub-domains |
626 | * |
627 | * \tparam p_id property containing the processor decomposition |
628 | * \tparam p_sub property to fill with the sub-domain decomposition |
629 | * |
630 | * \param start_p seed point |
631 | * \param graph we are processing |
632 | * \param ghe ghost size |
633 | * \param bc boundary conditions |
634 | * |
635 | */ |
636 | template <unsigned int p_sub, unsigned int p_id> void optimize(grid_key_dx<dim> & start_p, Graph & graph, const Ghost<dim,long int> & ghe , const size_t (& bc)[dim]) |
637 | { |
638 | // temporal vector |
639 | openfpm::vector<Box<dim,size_t>> tmp; |
640 | |
641 | // temporal vector |
642 | openfpm::vector< openfpm::vector<size_t> > box_nn_processor; |
643 | |
644 | // optimize |
645 | optimize<p_sub,p_id>(start_p,graph,-1,tmp, box_nn_processor,ghe,bc); |
646 | } |
647 | |
648 | /*! \brief optimize the graph |
649 | * |
650 | * Starting from a sub-sub-domain, it create wavefronts at the boundary and expand |
651 | * the boundary until the wavefronts cannot expand any more, creating a sub-domain covering more sub-sub-domain. |
652 | * This procedure continue until all the sub-domain of the processor p_id are covered by a sub-domains |
653 | * |
654 | * \tparam p_id property containing the decomposition |
655 | * \tparam p_sub property to fill with the sub-domain decomposition |
656 | * |
657 | * \param graph we are processing |
658 | * \param pr_id Processor id (if p_id == -1 the optimization is done for all the processors) |
659 | * \param lb list of sub-domain boxes |
660 | * \param box_nn_processor for each sub-domain it list all the neighborhood processors |
661 | * \param ghe ghost size |
662 | * |
663 | */ |
664 | template <unsigned int p_sub, unsigned int p_id> void optimize(Graph & graph, long int pr_id, openfpm::vector<Box<dim,size_t>> & lb, openfpm::vector< openfpm::vector<size_t> > & box_nn_processor, const Ghost<dim,long int> & ghe, const size_t (& bc)[dim]) |
665 | { |
666 | grid_key_dx<dim> key_seed; |
667 | key_seed.zero(); |
668 | |
669 | // if processor is -1 call optimize with -1 to do on all processors and exit |
670 | if (pr_id == -1) |
671 | { |
672 | optimize<p_sub,p_id>(key_seed,graph,pr_id,lb,box_nn_processor,ghe,bc); |
673 | |
674 | // Construct box box_nn_processor from the constructed domain |
675 | construct_box_nn_processor<p_id>(graph,box_nn_processor,lb,ghe,bc,pr_id); |
676 | |
677 | return; |
678 | } |
679 | |
680 | size_t sub_id = 0; |
681 | |
682 | // fill the sub decomposition with negative number |
683 | fill_domain<p_sub>(graph,gh.getBox(),-1); |
684 | |
685 | key_seed = search_seed<p_id,p_sub>(graph,pr_id); |
686 | |
687 | while (key_seed.isValid()) |
688 | { |
689 | // optimize |
690 | sub_id = optimize<p_sub,p_id>(key_seed,graph,pr_id,lb,box_nn_processor,ghe,bc,false,sub_id); |
691 | |
692 | // new seed |
693 | key_seed = search_seed<p_id,p_sub>(graph,pr_id); |
694 | } |
695 | |
696 | // Construct box box_nn_processor from the constructed domain |
697 | construct_box_nn_processor<p_id>(graph,box_nn_processor,lb,ghe,bc,pr_id); |
698 | } |
699 | }; |
700 | |
701 | #endif |
702 | |