Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
RadixTree.hpp
Go to the documentation of this file.
1// -------------------------------------------------------//
2//
3// SHAMROCK code for hydrodynamics
4// Copyright (c) 2021-2026 Timothée David--Cléris <tim.shamrock@proton.me>
5// SPDX-License-Identifier: CeCILL Free Software License Agreement v2.1
6// Shamrock is licensed under the CeCILL 2.1 License, see LICENSE for more information
7//
8// -------------------------------------------------------//
9
10#pragma once
11
17
18#include "shamalgs/memory.hpp"
36#include <array>
37#include <memory>
38#include <set>
39#include <stdexcept>
40#include <tuple>
41#include <vector>
42
49template<class Umorton, class Tvec>
50class RadixTree {
51
52 static constexpr u32 dim = shambase::VectorProperties<Tvec>::dimension;
53
55
56 static constexpr bool pos_is_int
57 = std::is_same<Tvec, u16_3>::value || std::is_same<Tvec, u32_3>::value
58 || std::is_same<Tvec, u64_3>::value || std::is_same<Tvec, i16_3>::value
59 || std::is_same<Tvec, i32_3>::value || std::is_same<Tvec, i64_3>::value;
60
61 static constexpr bool pos_is_float
62 = std::is_same<Tvec, f32_3>::value || std::is_same<Tvec, f64_3>::value;
63
64 RadixTree() = default;
65
66 public:
68 using coord_t = typename shambase::VectorProperties<Tvec>::component_type;
69
70 static constexpr u32 tree_depth = Morton::significant_bits + 1;
71
72 std::tuple<Tvec, Tvec> bounding_box;
73
74 // build by the RadixTreeMortonBuilder
77
78 // Karras alg
80
82
83 inline bool is_tree_built() { return tree_struct.is_built(); }
84
85 inline bool are_range_int_built() { return tree_cell_ranges.are_range_int_built(); }
86
87 inline bool are_range_float_built() { return tree_cell_ranges.are_range_float_built(); }
88
89 void serialize(shamalgs::SerializeHelper &serializer);
90
91 shamalgs::SerializeSize serialize_byte_size();
92
93 static RadixTree deserialize(shamalgs::SerializeHelper &serializer);
94
95 inline friend bool operator==(const RadixTree &t1, const RadixTree &t2) {
96 bool cmp = true;
97 cmp = cmp && sham::equals(std::get<0>(t1.bounding_box), std::get<0>(t2.bounding_box));
98 cmp = cmp && sham::equals(std::get<1>(t1.bounding_box), std::get<1>(t2.bounding_box));
99 cmp = cmp && t1.tree_morton_codes == t2.tree_morton_codes;
100 cmp = cmp && t1.tree_reduced_morton_codes == t2.tree_reduced_morton_codes;
101 cmp = cmp && t1.tree_struct == t2.tree_struct;
102 cmp = cmp && t1.tree_cell_ranges == t2.tree_cell_ranges;
103 return cmp;
104 }
105
106 RadixTreeField<coord_t> compute_int_boxes(
107 sycl::queue &queue, sham::DeviceBuffer<coord_t> &int_rad_buf, coord_t tolerance);
108
109 void compute_cell_ibounding_box(sycl::queue &queue);
110 void convert_bounding_box(sycl::queue &queue);
111
112 RadixTree(
113 sycl::queue &queue,
114 std::tuple<Tvec, Tvec> treebox,
115 const std::unique_ptr<sycl::buffer<Tvec>> &pos_buf,
116 u32 cnt_obj,
117 u32 reduc_level);
118
119 RadixTree(
120 sycl::queue &queue,
121 std::tuple<Tvec, Tvec> treebox,
122 sycl::buffer<Tvec> &pos_buf,
123 u32 cnt_obj,
124 u32 reduc_level);
125
126 RadixTree(
127 sham::DeviceScheduler_ptr dev_sched,
128 std::tuple<Tvec, Tvec> treebox,
130 u32 cnt_obj,
131 u32 reduc_level);
132
133 inline RadixTree(const RadixTree &other)
134 : bounding_box(other.bounding_box), tree_morton_codes{other.tree_morton_codes},
135 tree_reduced_morton_codes(other.tree_reduced_morton_codes), // size = leaf cnt
136 tree_struct{other.tree_struct}, tree_cell_ranges(other.tree_cell_ranges) {}
137
138 [[nodiscard]] inline u64 memsize() const {
139 u64 sum = 0;
140
141 sum += sizeof(bounding_box);
142
143 auto add_ptr = [&](auto &a) {
144 if (a) {
145 sum += a->byte_size();
146 }
147 };
148
149 sum += tree_morton_codes.memsize();
150 sum += tree_reduced_morton_codes.memsize();
151 sum += tree_struct.memsize();
152 sum += tree_cell_ranges.memsize();
153
154 return sum;
155 }
156
157 inline RadixTree duplicate() {
158 const auto &cur = *this;
159 return RadixTree(cur);
160 }
161
162 inline std::unique_ptr<RadixTree> duplicate_to_ptr() {
163 const auto &cur = *this;
164 return std::make_unique<RadixTree>(cur);
165 }
166
167 bool is_same(RadixTree &other) {
168 bool cmp = true;
169
170 cmp = cmp && (sham::equals(std::get<0>(bounding_box), std::get<0>(other.bounding_box)));
171 cmp = cmp && (sham::equals(std::get<1>(bounding_box), std::get<1>(other.bounding_box)));
172 cmp = cmp && (tree_cell_ranges == other.tree_cell_ranges);
173 cmp = cmp
174 && (tree_reduced_morton_codes.tree_leaf_count
175 == other.tree_reduced_morton_codes.tree_leaf_count);
176 cmp = cmp && (tree_struct == other.tree_struct);
177
178 return cmp;
179 }
180
181 template<class T>
182 using RadixTreeField = RadixTreeField<T>;
183
184 template<class T, class LambdaComputeLeaf, class LambdaCombinator>
185 RadixTreeField<T> compute_field(
186 sycl::queue &queue,
187 u32 nvar,
188 LambdaComputeLeaf &&compute_leaf,
189 LambdaCombinator &&combine) const;
190
191 template<class LambdaForEachCell>
192 std::pair<std::set<u32>, std::set<u32>> get_walk_res_set(LambdaForEachCell &&interact_cd) const;
193
194 template<class LambdaForEachCell>
195 void for_each_leaf(sycl::queue &queue, LambdaForEachCell &&par_for_each_cell) const;
196
197 std::tuple<coord_t, coord_t> get_min_max_cell_side_length();
198
199 struct CuttedTree {
200 RadixTree<Umorton, Tvec> rtree;
201 std::unique_ptr<sycl::buffer<u32>> new_node_id_to_old;
202
203 std::unique_ptr<sycl::buffer<u32>> pdat_extract_id;
204 };
205
206 CuttedTree cut_tree(sycl::queue &queue, sycl::buffer<u8> &valid_node);
207
208 template<class T>
209 void print_tree_field(sycl::buffer<T> &buf_field);
210
211 static RadixTree make_empty() { return RadixTree(); }
212
213 class LeafIterator {
214
215 sycl::accessor<u32, 1, sycl::access::mode::read, sycl::target::device> particle_index_map;
216 sycl::accessor<u32, 1, sycl::access::mode::read, sycl::target::device> reduc_index_map;
217
218 public:
219 LeafIterator(RadixTree &rtree, sycl::handler &cgh)
220 : particle_index_map(rtree.tree_morton_codes.buf_particle_index_map
221 ->template get_access<sycl::access::mode::read>(cgh)),
222 reduc_index_map(rtree.tree_reduced_morton_codes.buf_reduc_index_map
223 ->template get_access<sycl::access::mode::read>(cgh)) {}
224
225 template<class Func>
226 inline void iter_object_in_leaf(u32 leaf_id, Func &&func_it) const noexcept {
227 // loop on particle indexes
228 uint min_ids = reduc_index_map[leaf_id];
229 uint max_ids = reduc_index_map[leaf_id + 1];
230
231 for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
232
233 // recover old index before morton sort
234 uint id_b = particle_index_map[id_s];
235
236 // iteration function
237 func_it(id_b);
238 }
239 }
240 };
241
242 inline LeafIterator get_leaf_access(sycl::handler &device_handler) {
243 return LeafIterator(*this, device_handler);
244 }
245};
246
247template<class u_morton, class vec3>
248template<class T, class LambdaComputeLeaf, class LambdaCombinator>
251 sycl::queue &queue,
252 u32 nvar,
253
254 LambdaComputeLeaf &&compute_leaf,
255 LambdaCombinator &&combine) const {
256
258 ret.nvar = nvar;
259
260 shamlog_debug_sycl_ln("RadixTree", "compute_field");
261
262 ret.radix_tree_field_buf = std::make_unique<sycl::buffer<T>>(
263 tree_struct.internal_cell_count + tree_reduced_morton_codes.tree_leaf_count);
264 sycl::range<1> range_leaf_cell{tree_reduced_morton_codes.tree_leaf_count};
265
266 queue.submit([&](sycl::handler &cgh) {
267 u32 offset_leaf = tree_struct.internal_cell_count;
268
269 auto tree_field
270 = sycl::accessor{*ret.radix_tree_field_buf, cgh, sycl::write_only, sycl::no_init};
271
272 auto cell_particle_ids = tree_reduced_morton_codes.buf_reduc_index_map
273 ->template get_access<sycl::access::mode::read>(cgh);
274 auto particle_index_map = tree_morton_codes.buf_particle_index_map
275 ->template get_access<sycl::access::mode::read>(cgh);
276
277 compute_leaf(cgh, [&](auto &&lambda_loop) {
278 cgh.parallel_for(range_leaf_cell, [=](sycl::item<1> item) {
279 u32 gid = (u32) item.get_id(0);
280
281 u32 min_ids = cell_particle_ids[gid];
282 u32 max_ids = cell_particle_ids[gid + 1];
283
284 lambda_loop(
285 [&](auto &&particle_it) {
286 for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
287 particle_it(particle_index_map[id_s]);
288 }
289 },
290 tree_field,
291 [&]() {
292 return nvar * (offset_leaf + gid);
293 });
294 });
295 });
296 });
297
298 sycl::range<1> range_tree{tree_struct.internal_cell_count};
299 auto ker_reduc_hmax = [&](sycl::handler &cgh) {
300 u32 offset_leaf = tree_struct.internal_cell_count;
301
302 auto tree_field
303 = ret.radix_tree_field_buf->template get_access<sycl::access::mode::read_write>(cgh);
304
305 auto rchild_id = tree_struct.buf_rchild_id->get_access<sycl::access::mode::read>(cgh);
306 auto lchild_id = tree_struct.buf_lchild_id->get_access<sycl::access::mode::read>(cgh);
307 auto rchild_flag = tree_struct.buf_rchild_flag->get_access<sycl::access::mode::read>(cgh);
308 auto lchild_flag = tree_struct.buf_lchild_flag->get_access<sycl::access::mode::read>(cgh);
309
310 cgh.parallel_for(range_tree, [=](sycl::item<1> item) {
311 u32 gid = (u32) item.get_id(0);
312
313 u32 lid = lchild_id[gid] + offset_leaf * lchild_flag[gid];
314 u32 rid = rchild_id[gid] + offset_leaf * rchild_flag[gid];
315
316 combine(
317 [&](u32 nvar_id) -> T {
318 return tree_field[nvar * lid + nvar_id];
319 },
320 [&](u32 nvar_id) -> T {
321 return tree_field[nvar * rid + nvar_id];
322 },
323 tree_field,
324 [&]() {
325 return nvar * (gid);
326 });
327 });
328 };
329
330 for (u32 i = 0; i < tree_depth; i++) {
331 queue.submit(ker_reduc_hmax);
332 }
333
334 return std::move(ret);
335}
336
337template<class u_morton, class vec3>
338template<class LambdaForEachCell>
339inline std::pair<std::set<u32>, std::set<u32>> RadixTree<u_morton, vec3>::get_walk_res_set(
340 LambdaForEachCell &&interact_cd) const {
341
342 std::set<u32> leaf_list;
343 std::set<u32> rejected_list;
344
345 auto particle_index_map = sycl::host_accessor{*tree_morton_codes.buf_particle_index_map};
346 auto cell_index_map = sycl::host_accessor{*tree_reduced_morton_codes.buf_reduc_index_map};
347 auto rchild_id = sycl::host_accessor{*tree_struct.buf_rchild_id};
348 auto lchild_id = sycl::host_accessor{*tree_struct.buf_lchild_id};
349 auto rchild_flag = sycl::host_accessor{*tree_struct.buf_rchild_flag};
350 auto lchild_flag = sycl::host_accessor{*tree_struct.buf_lchild_flag};
351
352 // sycl::range<1> range_leaf = sycl::range<1>{tree_leaf_count};
353
354 u32 leaf_offset = tree_struct.internal_cell_count;
355
356 u32 stack_cursor = tree_depth - 1;
357 std::array<u32, tree_depth> id_stack;
358 id_stack[stack_cursor] = 0;
359
360 while (stack_cursor < tree_depth) {
361
362 u32 current_node_id = id_stack[stack_cursor];
363 id_stack[stack_cursor] = tree_depth;
364 stack_cursor++;
365
366 if (interact_cd(current_node_id)) {
367
368 // leaf and can interact => force
369 if (current_node_id >= leaf_offset) {
370
371 leaf_list.insert(current_node_id);
372
373 // can interact not leaf => stack
374 } else {
375
376 u32 lid = lchild_id[current_node_id] + leaf_offset * lchild_flag[current_node_id];
377 u32 rid = rchild_id[current_node_id] + leaf_offset * rchild_flag[current_node_id];
378
379 id_stack[stack_cursor - 1] = rid;
380 stack_cursor--;
381
382 id_stack[stack_cursor - 1] = lid;
383 stack_cursor--;
384 }
385 } else {
386 // grav
387
388 rejected_list.insert(current_node_id);
389 }
390 }
391
392 return std::pair<std::set<u32>, std::set<u32>>{std::move(leaf_list), std::move(rejected_list)};
393}
394
395template<class u_morton, class vec3>
396template<class LambdaForEachCell>
397inline void RadixTree<u_morton, vec3>::for_each_leaf(
398 sycl::queue &queue, LambdaForEachCell &&par_for_each_cell) const {
399
400 queue.submit([&](sycl::handler &cgh) {
401 auto particle_index_map = tree_morton_codes.buf_particle_index_map
402 ->template get_access<sycl::access::mode::read>(cgh);
403 auto cell_index_map = tree_reduced_morton_codes.buf_reduc_index_map
404 ->template get_access<sycl::access::mode::read>(cgh);
405 auto rchild_id
406 = tree_struct.buf_rchild_id->template get_access<sycl::access::mode::read>(cgh);
407 auto lchild_id
408 = tree_struct.buf_lchild_id->template get_access<sycl::access::mode::read>(cgh);
409 auto rchild_flag
410 = tree_struct.buf_rchild_flag->template get_access<sycl::access::mode::read>(cgh);
411 auto lchild_flag
412 = tree_struct.buf_lchild_flag->template get_access<sycl::access::mode::read>(cgh);
413
414 sycl::range<1> range_leaf = sycl::range<1>{tree_reduced_morton_codes.tree_leaf_count};
415
416 u32 leaf_offset = tree_struct.internal_cell_count;
417
418 auto par_for = [&](auto &&for_each_leaf) {
419 cgh.parallel_for(range_leaf, [=](sycl::item<1> item) {
420 u32 id_cell_a = (u32) item.get_id(0) + leaf_offset;
421
422 auto iter_obj_cell = [&](u32 cell_id, auto &&func_it) {
423 uint min_ids = cell_index_map[cell_id - leaf_offset];
424 uint max_ids = cell_index_map[cell_id + 1 - leaf_offset];
425
426 for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
427
428 // recover old index before morton sort
429 uint id_b = particle_index_map[id_s];
430
431 // iteration function
432 func_it(id_b);
433 }
434 };
435
436 auto walk_loop = [&](u32 id_cell_a, auto &&for_other_cell) {
437 u32 stack_cursor = tree_depth - 1;
438 std::array<u32, tree_depth> id_stack;
439 id_stack[stack_cursor] = 0;
440
441 while (stack_cursor < tree_depth) {
442
443 u32 current_node_id = id_stack[stack_cursor];
444 id_stack[stack_cursor] = tree_depth;
445 stack_cursor++;
446
447 auto walk_logic = [&](const bool &cur_id_valid,
448 auto &&func_leaf_found,
449 auto &&func_node_rejected) {
450 if (cur_id_valid) {
451
452 // leaf and can interact => force
453 if (current_node_id >= leaf_offset) {
454
455 func_leaf_found();
456
457 // can interact not leaf => stack
458 } else {
459
460 u32 lid = lchild_id[current_node_id]
461 + leaf_offset * lchild_flag[current_node_id];
462 u32 rid = rchild_id[current_node_id]
463 + leaf_offset * rchild_flag[current_node_id];
464
465 id_stack[stack_cursor - 1] = rid;
466 stack_cursor--;
467
468 id_stack[stack_cursor - 1] = lid;
469 stack_cursor--;
470 }
471 } else {
472 // grav
473
474 func_node_rejected();
475 }
476 };
477
478 for_other_cell(current_node_id, walk_logic);
479 }
480 };
481
482 for_each_leaf(id_cell_a, walk_loop, iter_obj_cell);
483 });
484 };
485
486 par_for_each_cell(cgh, par_for);
487 });
488}
489
490template<class u_morton, class vec3>
491inline auto RadixTree<u_morton, vec3>::get_min_max_cell_side_length()
492 -> std::tuple<coord_t, coord_t> {
493
494 u32 len = tree_reduced_morton_codes.tree_leaf_count;
495
496 sycl::buffer<coord_t> min_side_length{len};
497 sycl::buffer<coord_t> max_side_length{len};
498
500
501 q.submit([&](sycl::handler &cgh) {
502 u32 offset_leaf = tree_struct.internal_cell_count;
503
504 sycl::accessor pos_min_cell{*tree_cell_ranges.buf_pos_min_cell_flt, cgh, sycl::read_only};
505 sycl::accessor pos_max_cell{*tree_cell_ranges.buf_pos_max_cell_flt, cgh, sycl::read_only};
506
507 sycl::accessor s_lengh_min{min_side_length, cgh, sycl::write_only, sycl::no_init};
508 sycl::accessor s_lengh_max{max_side_length, cgh, sycl::write_only, sycl::no_init};
509
510 sycl::range<1> range_tree{tree_reduced_morton_codes.tree_leaf_count};
511
512 cgh.parallel_for(range_tree, [=](sycl::item<1> item) {
513 u32 gid = (u32) item.get_id(0);
514
515 vec3 min = pos_min_cell[gid + offset_leaf];
516 vec3 max = pos_max_cell[gid + offset_leaf];
517
518 vec3 sz = max - min;
519
520 if constexpr (pos_is_float) {
521 s_lengh_min[gid] = sycl::fmin(sycl::fmin(sz.x(), sz.y()), sz.z());
522 s_lengh_max[gid] = sycl::fmax(sycl::fmax(sz.x(), sz.y()), sz.z());
523 }
524
525 if constexpr (pos_is_int) {
526 s_lengh_min[gid] = sycl::min(sycl::min(sz.x(), sz.y()), sz.z());
527 s_lengh_max[gid] = sycl::max(sycl::max(sz.x(), sz.y()), sz.z());
528 }
529 });
530 });
531
532 auto dev_sched = shamsys::instance::get_compute_scheduler_ptr();
533
534 sham::DeviceBuffer<coord_t> tmp_min_side_length(len, dev_sched);
535 sham::DeviceBuffer<coord_t> tmp_max_side_length(len, dev_sched);
536
537 tmp_min_side_length.copy_from_sycl_buffer(min_side_length);
538 tmp_max_side_length.copy_from_sycl_buffer(max_side_length);
539
540 coord_t min = shamalgs::primitives::min(dev_sched, tmp_min_side_length, 0, len);
541 coord_t max = shamalgs::primitives::max(dev_sched, tmp_max_side_length, 0, len);
542
543 return {min, max};
544}
545
546namespace tree_comm {
547
548 template<class u_morton, class vec3>
549 class RadixTreeMPIRequest {
550 public:
551 template<class T>
553 using RTree = RadixTree<u_morton, vec3>;
554
555 mpi_sycl_interop::comm_type comm_mode;
556 mpi_sycl_interop::op_type comm_op;
557
558 RTree &rtree;
559
560 std::vector<Request<u_morton>> rq_u_morton;
561 std::vector<Request<u32>> rq_u32;
562 std::vector<Request<u8>> rq_u8;
563 std::vector<Request<vec3>> rq_vec;
564
565 std::vector<Request<typename RTree::ipos_t>> rq_vec3i;
566
567 inline RadixTreeMPIRequest(RTree &rtree, mpi_sycl_interop::op_type comm_op)
568 : rtree(rtree), comm_mode(mpi_sycl_interop::current_mode), comm_op(comm_op) {}
569
570 inline void finalize() {
571 mpi_sycl_interop::waitall(rq_u_morton);
572 mpi_sycl_interop::waitall(rq_u32);
573 mpi_sycl_interop::waitall(rq_u8);
574 mpi_sycl_interop::waitall(rq_vec3i);
575 mpi_sycl_interop::waitall(rq_vec);
576
577 if (comm_op == mpi_sycl_interop::Recv_Probe) {
578 rtree.tree_morton_codes.obj_cnt = rtree.tree_morton_codes.buf_morton->size();
579 rtree.tree_reduced_morton_codes.tree_leaf_count
580 = rtree.tree_reduced_morton_codes.buf_tree_morton->size();
581 rtree.tree_struct.internal_cell_count = rtree.tree_struct.buf_lchild_id->size();
582
583 {
584 sycl::host_accessor bmin{*rtree.tree_cell_ranges.buf_pos_min_cell_flt};
585 sycl::host_accessor bmax{*rtree.tree_cell_ranges.buf_pos_max_cell_flt};
586
587 rtree.bounding_box = {bmin[0], bmax[0]};
588 }
589
590 // One cell mode check
591
592 {
593 sycl::host_accessor indmap{
594 *rtree.tree_reduced_morton_codes.buf_reduc_index_map};
595 rtree.tree_struct.one_cell_mode
596 = (indmap[rtree.tree_reduced_morton_codes.buf_reduc_index_map->size() - 1]
597 == 0);
598 }
599 }
600 }
601 };
602
603 template<class u_morton, class vec3>
604 inline void wait_all(std::vector<RadixTreeMPIRequest<u_morton, vec3>> &rqs) {
605 for (auto &rq : rqs) {
606 rq.finalize();
607 }
608 }
609
610 template<class u_morton, class vec3>
611 inline u64 comm_isend(
612 RadixTree<u_morton, vec3> &rtree,
613 std::vector<RadixTreeMPIRequest<u_morton, vec3>> &rqs,
614 i32 rank_dest,
615 i32 tag,
616 MPI_Comm comm) {
617
618 u64 ret_len = 0;
619
620 rqs.push_back(RadixTreeMPIRequest<u_morton, vec3>(rtree, mpi_sycl_interop::op_type::Send));
621
622 auto &rq = rqs.back();
623
624 ret_len += mpi_sycl_interop::isend(
625 rq.rtree.tree_morton_codes.buf_morton,
626 rq.rtree.tree_morton_codes.obj_cnt,
627 rq.rq_u_morton,
628 rank_dest,
629 tag,
630 comm);
631 ret_len += mpi_sycl_interop::isend(
632 rq.rtree.tree_morton_codes.buf_particle_index_map,
633 rq.rtree.tree_morton_codes.obj_cnt,
634 rq.rq_u32,
635 rank_dest,
636 tag,
637 comm);
638
639 ret_len += mpi_sycl_interop::isend(
640 rq.rtree.tree_reduced_morton_codes.buf_reduc_index_map,
641 rq.rtree.tree_reduced_morton_codes.tree_leaf_count + 1,
642 rq.rq_u32,
643 rank_dest,
644 tag,
645 comm);
646
647 ret_len += mpi_sycl_interop::isend(
648 rq.rtree.tree_reduced_morton_codes.buf_tree_morton,
649 rq.rtree.tree_reduced_morton_codes.tree_leaf_count,
650 rq.rq_u_morton,
651 rank_dest,
652 tag,
653 comm);
654 ret_len += mpi_sycl_interop::isend(
655 rq.rtree.tree_struct.buf_lchild_id,
656 rq.rtree.tree_struct.internal_cell_count,
657 rq.rq_u32,
658 rank_dest,
659 tag,
660 comm);
661 ret_len += mpi_sycl_interop::isend(
662 rq.rtree.tree_struct.buf_rchild_id,
663 rq.rtree.tree_struct.internal_cell_count,
664 rq.rq_u32,
665 rank_dest,
666 tag,
667 comm);
668 ret_len += mpi_sycl_interop::isend(
669 rq.rtree.tree_struct.buf_lchild_flag,
670 rq.rtree.tree_struct.internal_cell_count,
671 rq.rq_u8,
672 rank_dest,
673 tag,
674 comm);
675 ret_len += mpi_sycl_interop::isend(
676 rq.rtree.tree_struct.buf_rchild_flag,
677 rq.rtree.tree_struct.internal_cell_count,
678 rq.rq_u8,
679 rank_dest,
680 tag,
681 comm);
682 ret_len += mpi_sycl_interop::isend(
683 rq.rtree.tree_struct.buf_endrange,
684 rq.rtree.tree_struct.internal_cell_count,
685 rq.rq_u32,
686 rank_dest,
687 tag,
688 comm);
689
690 ret_len += mpi_sycl_interop::isend(
691 rq.rtree.tree_cell_ranges.buf_pos_min_cell,
692 rq.rtree.tree_struct.internal_cell_count
693 + rq.rtree.tree_reduced_morton_codes.tree_leaf_count,
694 rq.rq_vec3i,
695 rank_dest,
696 tag,
697 comm);
698 ret_len += mpi_sycl_interop::isend(
699 rq.rtree.tree_cell_ranges.buf_pos_max_cell,
700 rq.rtree.tree_struct.internal_cell_count
701 + rq.rtree.tree_reduced_morton_codes.tree_leaf_count,
702 rq.rq_vec3i,
703 rank_dest,
704 tag,
705 comm);
706
707 ret_len += mpi_sycl_interop::isend(
708 rq.rtree.tree_cell_ranges.buf_pos_min_cell_flt,
709 rq.rtree.tree_struct.internal_cell_count
710 + rq.rtree.tree_reduced_morton_codes.tree_leaf_count,
711 rq.rq_vec,
712 rank_dest,
713 tag,
714 comm);
715 ret_len += mpi_sycl_interop::isend(
716 rq.rtree.tree_cell_ranges.buf_pos_max_cell_flt,
717 rq.rtree.tree_struct.internal_cell_count
718 + rq.rtree.tree_reduced_morton_codes.tree_leaf_count,
719 rq.rq_vec,
720 rank_dest,
721 tag,
722 comm);
723
724 return ret_len;
725 }
726
727 template<class u_morton, class vec3>
728 inline u64 comm_irecv_probe(
729 RadixTree<u_morton, vec3> &rtree,
730 std::vector<RadixTreeMPIRequest<u_morton, vec3>> &rqs,
731 i32 rank_source,
732 i32 tag,
733 MPI_Comm comm) {
734
735 rqs.push_back(
736 RadixTreeMPIRequest<u_morton, vec3>(rtree, mpi_sycl_interop::op_type::Recv_Probe));
737
738 auto &rq = rqs.back();
739
740 u64 ret_len = 0;
741
742 ret_len += mpi_sycl_interop::irecv_probe(
743 rq.rtree.tree_morton_codes.buf_morton, rq.rq_u_morton, rank_source, tag, comm);
744 ret_len += mpi_sycl_interop::irecv_probe(
745 rq.rtree.tree_morton_codes.buf_particle_index_map, rq.rq_u32, rank_source, tag, comm);
746
747 ret_len += mpi_sycl_interop::irecv_probe(
748 rq.rtree.tree_reduced_morton_codes.buf_reduc_index_map,
749 rq.rq_u32,
750 rank_source,
751 tag,
752 comm);
753
754 ret_len += mpi_sycl_interop::irecv_probe(
755 rq.rtree.tree_reduced_morton_codes.buf_tree_morton,
756 rq.rq_u_morton,
757 rank_source,
758 tag,
759 comm);
760 ret_len += mpi_sycl_interop::irecv_probe(
761 rq.rtree.tree_struct.buf_lchild_id, rq.rq_u32, rank_source, tag, comm);
762 ret_len += mpi_sycl_interop::irecv_probe(
763 rq.rtree.tree_struct.buf_rchild_id, rq.rq_u32, rank_source, tag, comm);
764 ret_len += mpi_sycl_interop::irecv_probe(
765 rq.rtree.tree_struct.buf_lchild_flag, rq.rq_u8, rank_source, tag, comm);
766 ret_len += mpi_sycl_interop::irecv_probe(
767 rq.rtree.tree_struct.buf_rchild_flag, rq.rq_u8, rank_source, tag, comm);
768 ret_len += mpi_sycl_interop::irecv_probe(
769 rq.rtree.tree_struct.buf_endrange, rq.rq_u32, rank_source, tag, comm);
770
771 ret_len += mpi_sycl_interop::irecv_probe(
772 rq.rtree.tree_cell_ranges.buf_pos_min_cell, rq.rq_vec3i, rank_source, tag, comm);
773 ret_len += mpi_sycl_interop::irecv_probe(
774 rq.rtree.tree_cell_ranges.buf_pos_max_cell, rq.rq_vec3i, rank_source, tag, comm);
775
776 ret_len += mpi_sycl_interop::irecv_probe(
777 rq.rtree.tree_cell_ranges.buf_pos_min_cell_flt, rq.rq_vec, rank_source, tag, comm);
778 ret_len += mpi_sycl_interop::irecv_probe(
779 rq.rtree.tree_cell_ranges.buf_pos_max_cell_flt, rq.rq_vec, rank_source, tag, comm);
780
781 return ret_len;
782 }
783
784} // namespace tree_comm
785
786// TODO move h iter thing + multipoles to a tree field class
787
788namespace walker {
789
790 namespace interaction_crit {
791 template<class vec3, class flt>
792 inline bool sph_radix_cell_crit(
793 vec3 xyz_a,
794 vec3 part_a_box_min,
795 vec3 part_a_box_max,
796 vec3 cur_cell_box_min,
797 vec3 cur_cell_box_max,
798 flt box_int_sz) {
799
800 vec3 inter_box_b_min = cur_cell_box_min - box_int_sz;
801 vec3 inter_box_b_max = cur_cell_box_max + box_int_sz;
802
803 return BBAA::cella_neigh_b(
804 part_a_box_min, part_a_box_max, cur_cell_box_min, cur_cell_box_max)
805 || BBAA::cella_neigh_b(xyz_a, xyz_a, inter_box_b_min, inter_box_b_max);
806 }
807
808 template<class vec3, class flt>
809 inline bool sph_cell_cell_crit(
810 vec3 cella_min,
811 vec3 cella_max,
812 vec3 cellb_min,
813 vec3 cellb_max,
814 flt rint_a,
815 flt rint_b) {
816
817 vec3 inter_box_a_min = cella_min - rint_a;
818 vec3 inter_box_a_max = cella_max + rint_a;
819
820 vec3 inter_box_b_min = cellb_min - rint_b;
821 vec3 inter_box_b_max = cellb_max + rint_b;
822
823 return BBAA::cella_neigh_b(inter_box_a_min, inter_box_a_max, cellb_min, cellb_max)
824 || BBAA::cella_neigh_b(inter_box_b_min, inter_box_b_max, cella_min, cella_max);
825 }
826 } // namespace interaction_crit
827
828 template<class u_morton, class vec3>
829 class Radix_tree_accessor {
830 public:
831 sycl::accessor<u32, 1, sycl::access::mode::read, sycl::target::device> particle_index_map;
832 sycl::accessor<u32, 1, sycl::access::mode::read, sycl::target::device> cell_index_map;
833 sycl::accessor<u32, 1, sycl::access::mode::read, sycl::target::device> rchild_id;
834 sycl::accessor<u32, 1, sycl::access::mode::read, sycl::target::device> lchild_id;
835 sycl::accessor<u8, 1, sycl::access::mode::read, sycl::target::device> rchild_flag;
836 sycl::accessor<u8, 1, sycl::access::mode::read, sycl::target::device> lchild_flag;
837 sycl::accessor<vec3, 1, sycl::access::mode::read, sycl::target::device> pos_min_cell;
838 sycl::accessor<vec3, 1, sycl::access::mode::read, sycl::target::device> pos_max_cell;
839
840 static constexpr u32 tree_depth = RadixTree<u_morton, vec3>::tree_depth;
841 static constexpr u32 _nindex = 4294967295;
842
843 u32 leaf_offset;
844
845 Radix_tree_accessor(RadixTree<u_morton, vec3> &rtree, sycl::handler &cgh)
846 : particle_index_map(rtree.tree_morton_codes.buf_particle_index_map
847 ->template get_access<sycl::access::mode::read>(cgh)),
848 cell_index_map(rtree.tree_reduced_morton_codes.buf_reduc_index_map
849 ->template get_access<sycl::access::mode::read>(cgh)),
850 rchild_id(
851 rtree.tree_struct.buf_rchild_id->template get_access<sycl::access::mode::read>(
852 cgh)),
853 lchild_id(
854 rtree.tree_struct.buf_lchild_id->template get_access<sycl::access::mode::read>(
855 cgh)),
856 rchild_flag(
857 rtree.tree_struct.buf_rchild_flag->template get_access<sycl::access::mode::read>(
858 cgh)),
859 lchild_flag(
860 rtree.tree_struct.buf_lchild_flag->template get_access<sycl::access::mode::read>(
861 cgh)),
862 pos_min_cell(rtree.tree_cell_ranges.buf_pos_min_cell_flt
863 ->template get_access<sycl::access::mode::read>(cgh)),
864 pos_max_cell(rtree.tree_cell_ranges.buf_pos_max_cell_flt
865 ->template get_access<sycl::access::mode::read>(cgh)),
866 leaf_offset(rtree.tree_struct.internal_cell_count) {}
867 };
868
869 template<class Rta, class Functor_iter>
870 inline void iter_object_in_cell(const Rta &acc, const u32 &cell_id, Functor_iter &&func_it) {
871 // loop on particle indexes
872 uint min_ids = acc.cell_index_map[cell_id - acc.leaf_offset];
873 uint max_ids = acc.cell_index_map[cell_id + 1 - acc.leaf_offset];
874
875 for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
876
877 // recover old index before morton sort
878 uint id_b = acc.particle_index_map[id_s];
879
880 // iteration function
881 func_it(id_b);
882 }
883
884 /*
885 std::array<u32, 16> stack_run;
886
887 u32 run_cursor = 16;
888
889 auto is_stack_full = [&]() -> bool{
890 return run_cursor == 0;
891 };
892
893 auto is_stack_not_empty = [&]() -> bool{
894 return run_cursor < 16;
895 };
896
897 auto push_stack = [&](u32 val){
898 run_cursor --;
899 stack_run[run_cursor] = val;
900 };
901
902 auto pop_stack = [&]() -> u32 {
903 u32 v = stack_run[run_cursor];
904 run_cursor ++;
905 return v;
906 };
907
908 auto empty_stack = [&](){
909 while (is_stack_not_empty()) {
910 func_it(pop_stack());
911 }
912 };
913
914 for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
915 uint id_b = acc.particle_index_map[id_s];
916
917 if(is_stack_full()){
918 empty_stack();
919 }
920
921 push_stack(id_b);
922
923 }
924
925 empty_stack();
926 */
927 }
928
929 template<class Rta, class Functor_int_cd, class Functor_iter, class Functor_iter_excl>
930 inline void rtree_for_cell(
931 const Rta &acc,
932 Functor_int_cd &&func_int_cd,
933 Functor_iter &&func_it,
934 Functor_iter_excl &&func_excl) {
935 u32 stack_cursor = Rta::tree_depth - 1;
936 std::array<u32, Rta::tree_depth> id_stack;
937 id_stack[stack_cursor] = 0;
938
939 while (stack_cursor < Rta::tree_depth) {
940
941 u32 current_node_id = id_stack[stack_cursor];
942 id_stack[stack_cursor] = Rta::_nindex;
943 stack_cursor++;
944
945 bool cur_id_valid = func_int_cd(current_node_id);
946
947 if (cur_id_valid) {
948
949 // leaf and cell can interact
950 if (current_node_id >= acc.leaf_offset) {
951
952 func_it(current_node_id);
953
954 // can interact not leaf => stack
955 } else {
956
957 u32 lid = acc.lchild_id[current_node_id]
958 + acc.leaf_offset * acc.lchild_flag[current_node_id];
959 u32 rid = acc.rchild_id[current_node_id]
960 + acc.leaf_offset * acc.rchild_flag[current_node_id];
961
962 id_stack[stack_cursor - 1] = rid;
963 stack_cursor--;
964
965 id_stack[stack_cursor - 1] = lid;
966 stack_cursor--;
967 }
968 } else {
969 // grav
970 func_excl(current_node_id);
971 }
972 }
973 }
974
975 template<class Rta, class Functor_int_cd, class Functor_iter, class Functor_iter_excl>
976 inline void rtree_for(
977 const Rta &acc,
978 Functor_int_cd &&func_int_cd,
979 Functor_iter &&func_it,
980 Functor_iter_excl &&func_excl) {
981 u32 stack_cursor = Rta::tree_depth - 1;
982 std::array<u32, Rta::tree_depth> id_stack;
983 id_stack[stack_cursor] = 0;
984
985 while (stack_cursor < Rta::tree_depth) {
986
987 u32 current_node_id = id_stack[stack_cursor];
988 id_stack[stack_cursor] = Rta::_nindex;
989 stack_cursor++;
990
991 bool cur_id_valid = func_int_cd(current_node_id);
992
993 if (cur_id_valid) {
994
995 // leaf and can interact => force
996 if (current_node_id >= acc.leaf_offset) {
997
998 // loop on particle indexes
999 // uint min_ids = acc.cell_index_map[current_node_id -acc.leaf_offset];
1000 // uint max_ids = acc.cell_index_map[current_node_id + 1 -acc.leaf_offset];
1001 //
1002 // for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
1003 //
1004 // //recover old index before morton sort
1005 // uint id_b = acc.particle_index_map[id_s];
1006 //
1007 // //iteration function
1008 // func_it(id_b);
1009 //}
1010
1011 iter_object_in_cell(acc, current_node_id, func_it);
1012
1013 // can interact not leaf => stack
1014 } else {
1015
1016 u32 lid = acc.lchild_id[current_node_id]
1017 + acc.leaf_offset * acc.lchild_flag[current_node_id];
1018 u32 rid = acc.rchild_id[current_node_id]
1019 + acc.leaf_offset * acc.rchild_flag[current_node_id];
1020
1021 id_stack[stack_cursor - 1] = rid;
1022 stack_cursor--;
1023
1024 id_stack[stack_cursor - 1] = lid;
1025 stack_cursor--;
1026 }
1027 } else {
1028 // grav
1029 func_excl(current_node_id);
1030 }
1031 }
1032 }
1033
1034 template<
1035 class Rta,
1036 class Functor_int_cd,
1037 class Functor_iter,
1038 class Functor_iter_excl,
1039 class arr_type>
1040 inline void rtree_for_fill_cache(Rta &acc, arr_type &cell_cache, Functor_int_cd &&func_int_cd) {
1041
1042 constexpr u32 cache_sz = cell_cache.size();
1043 u32 cache_pos = 0;
1044
1045 auto push_in_cache = [&cell_cache, &cache_pos](u32 id) {
1046 cell_cache[cache_pos] = id;
1047 cache_pos++;
1048 };
1049
1050 u32 stack_cursor = Rta::tree_depth - 1;
1051 std::array<u32, Rta::tree_depth> id_stack;
1052 id_stack[stack_cursor] = 0;
1053
1054 auto get_el_cnt_in_stack = [&]() -> u32 {
1055 return Rta::tree_depth - stack_cursor;
1056 };
1057
1058 while ((stack_cursor < Rta::tree_depth) && (cache_pos + get_el_cnt_in_stack < cache_sz)) {
1059
1060 u32 current_node_id = id_stack[stack_cursor];
1061 id_stack[stack_cursor] = Rta::_nindex;
1062 stack_cursor++;
1063
1064 bool cur_id_valid = func_int_cd(current_node_id);
1065
1066 if (cur_id_valid) {
1067
1068 // leaf and can interact => force
1069 if (current_node_id >= acc.leaf_offset) {
1070
1071 // can interact => add to cache
1072 push_in_cache(current_node_id);
1073
1074 // can interact not leaf => stack
1075 } else {
1076
1077 u32 lid = acc.lchild_id[current_node_id]
1078 + acc.leaf_offset * acc.lchild_flag[current_node_id];
1079 u32 rid = acc.rchild_id[current_node_id]
1080 + acc.leaf_offset * acc.rchild_flag[current_node_id];
1081
1082 id_stack[stack_cursor - 1] = rid;
1083 stack_cursor--;
1084
1085 id_stack[stack_cursor - 1] = lid;
1086 stack_cursor--;
1087 }
1088 } else {
1089 // grav
1090 //.....
1091 }
1092 }
1093
1094 while (stack_cursor < Rta::tree_depth) {
1095 u32 current_node_id = id_stack[stack_cursor];
1096 id_stack[stack_cursor] = Rta::_nindex;
1097 stack_cursor++;
1098 push_in_cache(current_node_id);
1099 }
1100
1101 if (cache_pos < cache_sz) {
1102 push_in_cache(u32_max);
1103 }
1104 }
1105
1106 template<
1107 class Rta,
1108 class Functor_int_cd,
1109 class Functor_iter,
1110 class Functor_iter_excl,
1111 class arr_type>
1112 inline void rtree_for(
1113 Rta &acc, arr_type &cell_cache, Functor_int_cd &&func_int_cd, Functor_iter &&func_it) {
1114
1115 constexpr u32 cache_sz = cell_cache.size();
1116
1117 std::array<u32, Rta::tree_depth> id_stack;
1118
1119 auto walk_step = [&](u32 start_id) {
1120 u32 stack_cursor = Rta::tree_depth - 1;
1121 id_stack[stack_cursor] = start_id;
1122
1123 while (stack_cursor < Rta::tree_depth) {
1124
1125 u32 current_node_id = id_stack[stack_cursor];
1126 id_stack[stack_cursor] = Rta::_nindex;
1127 stack_cursor++;
1128
1129 bool cur_id_valid = func_int_cd(current_node_id);
1130
1131 if (cur_id_valid) {
1132
1133 // leaf and can interact => force
1134 if (current_node_id >= acc.leaf_offset) {
1135
1136 // loop on particle indexes
1137 uint min_ids = acc.cell_index_map[current_node_id - acc.leaf_offset];
1138 uint max_ids = acc.cell_index_map[current_node_id + 1 - acc.leaf_offset];
1139
1140 for (unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
1141
1142 // recover old index before morton sort
1143 uint id_b = acc.particle_index_map[id_s];
1144
1145 // iteration function
1146 func_it(id_b);
1147 }
1148
1149 // can interact not leaf => stack
1150 } else {
1151
1152 u32 lid = acc.lchild_id[current_node_id]
1153 + acc.leaf_offset * acc.lchild_flag[current_node_id];
1154 u32 rid = acc.rchild_id[current_node_id]
1155 + acc.leaf_offset * acc.rchild_flag[current_node_id];
1156
1157 id_stack[stack_cursor - 1] = rid;
1158 stack_cursor--;
1159
1160 id_stack[stack_cursor - 1] = lid;
1161 stack_cursor--;
1162 }
1163 } else {
1164 // grav
1165 //...
1166 }
1167 }
1168 };
1169
1170 for (u32 cache_pos = 0; cache_pos < cache_sz && cell_cache[cache_pos] != u32_max;
1171 cache_pos++) {
1172 walk_step(cache_pos);
1173 }
1174 }
1175
1176} // namespace walker
constexpr const char * uint
Specific internal energy u.
Header file describing a Node Instance.
sycl::queue & get_compute_queue(u32 id=0)
std::uint32_t u32
32 bit unsigned integer
std::uint64_t u64
64 bit unsigned integer
std::int32_t i32
32 bit integer
The radix tree.
Definition RadixTree.hpp:50
A buffer allocated in USM (Unified Shared Memory).
Morton curve implementation.
T min(const sham::DeviceScheduler_ptr &sched, const sham::DeviceBuffer< T > &buf1, u32 start_id, u32 end_id)
Find the minimum element in a device buffer within a specified range.
T max(const sham::DeviceScheduler_ptr &sched, const sham::DeviceBuffer< T > &buf1, u32 start_id, u32 end_id)
Find the maximum element in a device buffer within a specified range.
constexpr u32 u32_max
u32 max value
main include file for memory algorithms