49template<
class Umorton,
class Tvec>
52 static constexpr u32 dim = shambase::VectorProperties<Tvec>::dimension;
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;
61 static constexpr bool pos_is_float
62 = std::is_same<Tvec, f32_3>::value || std::is_same<Tvec, f64_3>::value;
64 RadixTree() =
default;
68 using coord_t =
typename shambase::VectorProperties<Tvec>::component_type;
70 static constexpr u32 tree_depth = Morton::significant_bits + 1;
72 std::tuple<Tvec, Tvec> bounding_box;
83 inline bool is_tree_built() {
return tree_struct.is_built(); }
85 inline bool are_range_int_built() {
return tree_cell_ranges.are_range_int_built(); }
87 inline bool are_range_float_built() {
return tree_cell_ranges.are_range_float_built(); }
95 inline friend bool operator==(
const RadixTree &t1,
const RadixTree &t2) {
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;
106 RadixTreeField<coord_t> compute_int_boxes(
109 void compute_cell_ibounding_box(sycl::queue &queue);
110 void convert_bounding_box(sycl::queue &queue);
114 std::tuple<Tvec, Tvec> treebox,
115 const std::unique_ptr<sycl::buffer<Tvec>> &pos_buf,
121 std::tuple<Tvec, Tvec> treebox,
122 sycl::buffer<Tvec> &pos_buf,
127 sham::DeviceScheduler_ptr dev_sched,
128 std::tuple<Tvec, Tvec> treebox,
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),
136 tree_struct{other.tree_struct}, tree_cell_ranges(other.tree_cell_ranges) {}
138 [[nodiscard]]
inline u64 memsize()
const {
141 sum +=
sizeof(bounding_box);
143 auto add_ptr = [&](
auto &a) {
145 sum += a->byte_size();
149 sum += tree_morton_codes.memsize();
150 sum += tree_reduced_morton_codes.memsize();
151 sum += tree_struct.memsize();
152 sum += tree_cell_ranges.memsize();
157 inline RadixTree duplicate() {
158 const auto &cur = *
this;
159 return RadixTree(cur);
162 inline std::unique_ptr<RadixTree> duplicate_to_ptr() {
163 const auto &cur = *
this;
164 return std::make_unique<RadixTree>(cur);
167 bool is_same(RadixTree &other) {
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);
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);
182 using RadixTreeField = RadixTreeField<T>;
184 template<
class T,
class LambdaComputeLeaf,
class LambdaCombinator>
185 RadixTreeField<T> compute_field(
188 LambdaComputeLeaf &&compute_leaf,
189 LambdaCombinator &&combine)
const;
191 template<
class LambdaForEachCell>
192 std::pair<std::set<u32>, std::set<u32>> get_walk_res_set(LambdaForEachCell &&interact_cd)
const;
194 template<
class LambdaForEachCell>
195 void for_each_leaf(sycl::queue &queue, LambdaForEachCell &&par_for_each_cell)
const;
197 std::tuple<coord_t, coord_t> get_min_max_cell_side_length();
200 RadixTree<Umorton, Tvec> rtree;
201 std::unique_ptr<sycl::buffer<u32>> new_node_id_to_old;
203 std::unique_ptr<sycl::buffer<u32>> pdat_extract_id;
206 CuttedTree cut_tree(sycl::queue &queue, sycl::buffer<u8> &valid_node);
209 void print_tree_field(sycl::buffer<T> &buf_field);
211 static RadixTree make_empty() {
return RadixTree(); }
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;
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)) {}
226 inline void iter_object_in_leaf(
u32 leaf_id, Func &&func_it)
const noexcept {
228 uint min_ids = reduc_index_map[leaf_id];
229 uint max_ids = reduc_index_map[leaf_id + 1];
231 for (
unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
234 uint id_b = particle_index_map[id_s];
242 inline LeafIterator get_leaf_access(sycl::handler &device_handler) {
247template<
class u_morton,
class vec3>
248template<
class T,
class LambdaComputeLeaf,
class LambdaCombinator>
254 LambdaComputeLeaf &&compute_leaf,
255 LambdaCombinator &&combine)
const {
260 shamlog_debug_sycl_ln(
"RadixTree",
"compute_field");
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};
266 queue.submit([&](sycl::handler &cgh) {
267 u32 offset_leaf = tree_struct.internal_cell_count;
270 = sycl::accessor{*ret.radix_tree_field_buf, cgh, sycl::write_only, sycl::no_init};
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);
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);
281 u32 min_ids = cell_particle_ids[gid];
282 u32 max_ids = cell_particle_ids[gid + 1];
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]);
292 return nvar * (offset_leaf + gid);
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;
303 = ret.radix_tree_field_buf->template get_access<sycl::access::mode::read_write>(cgh);
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);
310 cgh.parallel_for(range_tree, [=](sycl::item<1> item) {
311 u32 gid = (
u32) item.get_id(0);
313 u32 lid = lchild_id[gid] + offset_leaf * lchild_flag[gid];
314 u32 rid = rchild_id[gid] + offset_leaf * rchild_flag[gid];
317 [&](
u32 nvar_id) -> T {
318 return tree_field[nvar * lid + nvar_id];
320 [&](
u32 nvar_id) -> T {
321 return tree_field[nvar * rid + nvar_id];
330 for (
u32 i = 0; i < tree_depth; i++) {
331 queue.submit(ker_reduc_hmax);
334 return std::move(ret);
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 {
342 std::set<u32> leaf_list;
343 std::set<u32> rejected_list;
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};
354 u32 leaf_offset = tree_struct.internal_cell_count;
356 u32 stack_cursor = tree_depth - 1;
357 std::array<u32, tree_depth> id_stack;
358 id_stack[stack_cursor] = 0;
360 while (stack_cursor < tree_depth) {
362 u32 current_node_id = id_stack[stack_cursor];
363 id_stack[stack_cursor] = tree_depth;
366 if (interact_cd(current_node_id)) {
369 if (current_node_id >= leaf_offset) {
371 leaf_list.insert(current_node_id);
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];
379 id_stack[stack_cursor - 1] = rid;
382 id_stack[stack_cursor - 1] = lid;
388 rejected_list.insert(current_node_id);
392 return std::pair<std::set<u32>, std::set<u32>>{std::move(leaf_list), std::move(rejected_list)};
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 {
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);
406 = tree_struct.buf_rchild_id->template get_access<sycl::access::mode::read>(cgh);
408 = tree_struct.buf_lchild_id->template get_access<sycl::access::mode::read>(cgh);
410 = tree_struct.buf_rchild_flag->template get_access<sycl::access::mode::read>(cgh);
412 = tree_struct.buf_lchild_flag->template get_access<sycl::access::mode::read>(cgh);
414 sycl::range<1> range_leaf = sycl::range<1>{tree_reduced_morton_codes.tree_leaf_count};
416 u32 leaf_offset = tree_struct.internal_cell_count;
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;
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];
426 for (
unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
429 uint id_b = particle_index_map[id_s];
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;
441 while (stack_cursor < tree_depth) {
443 u32 current_node_id = id_stack[stack_cursor];
444 id_stack[stack_cursor] = tree_depth;
447 auto walk_logic = [&](
const bool &cur_id_valid,
448 auto &&func_leaf_found,
449 auto &&func_node_rejected) {
453 if (current_node_id >= leaf_offset) {
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];
465 id_stack[stack_cursor - 1] = rid;
468 id_stack[stack_cursor - 1] = lid;
474 func_node_rejected();
478 for_other_cell(current_node_id, walk_logic);
482 for_each_leaf(id_cell_a, walk_loop, iter_obj_cell);
486 par_for_each_cell(cgh, par_for);
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> {
494 u32 len = tree_reduced_morton_codes.tree_leaf_count;
496 sycl::buffer<coord_t> min_side_length{len};
497 sycl::buffer<coord_t> max_side_length{len};
501 q.submit([&](sycl::handler &cgh) {
502 u32 offset_leaf = tree_struct.internal_cell_count;
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};
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};
510 sycl::range<1> range_tree{tree_reduced_morton_codes.tree_leaf_count};
512 cgh.parallel_for(range_tree, [=](sycl::item<1> item) {
513 u32 gid = (
u32) item.get_id(0);
515 vec3 min = pos_min_cell[gid + offset_leaf];
516 vec3 max = pos_max_cell[gid + offset_leaf];
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());
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());
532 auto dev_sched = shamsys::instance::get_compute_scheduler_ptr();
537 tmp_min_side_length.copy_from_sycl_buffer(min_side_length);
538 tmp_max_side_length.copy_from_sycl_buffer(max_side_length);
548 template<
class u_morton,
class vec3>
549 class RadixTreeMPIRequest {
555 mpi_sycl_interop::comm_type comm_mode;
556 mpi_sycl_interop::op_type comm_op;
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;
565 std::vector<Request<typename RTree::ipos_t>> rq_vec3i;
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) {}
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);
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();
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};
587 rtree.bounding_box = {bmin[0], bmax[0]};
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]
603 template<
class u_morton,
class vec3>
605 for (
auto &rq : rqs) {
610 template<
class u_morton,
class vec3>
611 inline u64 comm_isend(
612 RadixTree<u_morton, vec3> &rtree,
622 auto &rq = rqs.back();
624 ret_len += mpi_sycl_interop::isend(
625 rq.rtree.tree_morton_codes.buf_morton,
626 rq.rtree.tree_morton_codes.obj_cnt,
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,
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,
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,
654 ret_len += mpi_sycl_interop::isend(
655 rq.rtree.tree_struct.buf_lchild_id,
656 rq.rtree.tree_struct.internal_cell_count,
661 ret_len += mpi_sycl_interop::isend(
662 rq.rtree.tree_struct.buf_rchild_id,
663 rq.rtree.tree_struct.internal_cell_count,
668 ret_len += mpi_sycl_interop::isend(
669 rq.rtree.tree_struct.buf_lchild_flag,
670 rq.rtree.tree_struct.internal_cell_count,
675 ret_len += mpi_sycl_interop::isend(
676 rq.rtree.tree_struct.buf_rchild_flag,
677 rq.rtree.tree_struct.internal_cell_count,
682 ret_len += mpi_sycl_interop::isend(
683 rq.rtree.tree_struct.buf_endrange,
684 rq.rtree.tree_struct.internal_cell_count,
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,
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,
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,
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,
727 template<
class u_morton,
class vec3>
728 inline u64 comm_irecv_probe(
729 RadixTree<u_morton, vec3> &rtree,
738 auto &rq = rqs.back();
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);
747 ret_len += mpi_sycl_interop::irecv_probe(
748 rq.rtree.tree_reduced_morton_codes.buf_reduc_index_map,
754 ret_len += mpi_sycl_interop::irecv_probe(
755 rq.rtree.tree_reduced_morton_codes.buf_tree_morton,
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);
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);
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);
790 namespace interaction_crit {
791 template<
class vec3,
class flt>
792 inline bool sph_radix_cell_crit(
796 vec3 cur_cell_box_min,
797 vec3 cur_cell_box_max,
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;
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);
808 template<
class vec3,
class flt>
809 inline bool sph_cell_cell_crit(
817 vec3 inter_box_a_min = cella_min - rint_a;
818 vec3 inter_box_a_max = cella_max + rint_a;
820 vec3 inter_box_b_min = cellb_min - rint_b;
821 vec3 inter_box_b_max = cellb_max + rint_b;
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);
828 template<
class u_morton,
class vec3>
829 class Radix_tree_accessor {
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;
840 static constexpr u32 tree_depth = RadixTree<u_morton, vec3>::tree_depth;
841 static constexpr u32 _nindex = 4294967295;
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)),
851 rtree.tree_struct.buf_rchild_id->template get_access<sycl::access::mode::read>(
854 rtree.tree_struct.buf_lchild_id->template get_access<sycl::access::mode::read>(
857 rtree.tree_struct.buf_rchild_flag->template get_access<sycl::access::mode::read>(
860 rtree.tree_struct.buf_lchild_flag->template get_access<sycl::access::mode::read>(
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) {}
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) {
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];
875 for (
unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
878 uint id_b = acc.particle_index_map[id_s];
929 template<
class Rta,
class Functor_
int_cd,
class Functor_iter,
class Functor_iter_excl>
930 inline void rtree_for_cell(
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;
939 while (stack_cursor < Rta::tree_depth) {
941 u32 current_node_id = id_stack[stack_cursor];
942 id_stack[stack_cursor] = Rta::_nindex;
945 bool cur_id_valid = func_int_cd(current_node_id);
950 if (current_node_id >= acc.leaf_offset) {
952 func_it(current_node_id);
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];
962 id_stack[stack_cursor - 1] = rid;
965 id_stack[stack_cursor - 1] = lid;
970 func_excl(current_node_id);
975 template<
class Rta,
class Functor_
int_cd,
class Functor_iter,
class Functor_iter_excl>
976 inline void rtree_for(
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;
985 while (stack_cursor < Rta::tree_depth) {
987 u32 current_node_id = id_stack[stack_cursor];
988 id_stack[stack_cursor] = Rta::_nindex;
991 bool cur_id_valid = func_int_cd(current_node_id);
996 if (current_node_id >= acc.leaf_offset) {
1011 iter_object_in_cell(acc, current_node_id, func_it);
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];
1021 id_stack[stack_cursor - 1] = rid;
1024 id_stack[stack_cursor - 1] = lid;
1029 func_excl(current_node_id);
1036 class Functor_int_cd,
1038 class Functor_iter_excl,
1040 inline void rtree_for_fill_cache(Rta &acc, arr_type &cell_cache, Functor_int_cd &&func_int_cd) {
1042 constexpr u32 cache_sz = cell_cache.size();
1045 auto push_in_cache = [&cell_cache, &cache_pos](
u32 id) {
1046 cell_cache[cache_pos] = id;
1050 u32 stack_cursor = Rta::tree_depth - 1;
1051 std::array<u32, Rta::tree_depth> id_stack;
1052 id_stack[stack_cursor] = 0;
1054 auto get_el_cnt_in_stack = [&]() ->
u32 {
1055 return Rta::tree_depth - stack_cursor;
1058 while ((stack_cursor < Rta::tree_depth) && (cache_pos + get_el_cnt_in_stack < cache_sz)) {
1060 u32 current_node_id = id_stack[stack_cursor];
1061 id_stack[stack_cursor] = Rta::_nindex;
1064 bool cur_id_valid = func_int_cd(current_node_id);
1069 if (current_node_id >= acc.leaf_offset) {
1072 push_in_cache(current_node_id);
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];
1082 id_stack[stack_cursor - 1] = rid;
1085 id_stack[stack_cursor - 1] = lid;
1094 while (stack_cursor < Rta::tree_depth) {
1095 u32 current_node_id = id_stack[stack_cursor];
1096 id_stack[stack_cursor] = Rta::_nindex;
1098 push_in_cache(current_node_id);
1101 if (cache_pos < cache_sz) {
1108 class Functor_int_cd,
1110 class Functor_iter_excl,
1112 inline void rtree_for(
1113 Rta &acc, arr_type &cell_cache, Functor_int_cd &&func_int_cd, Functor_iter &&func_it) {
1115 constexpr u32 cache_sz = cell_cache.size();
1117 std::array<u32, Rta::tree_depth> id_stack;
1119 auto walk_step = [&](
u32 start_id) {
1120 u32 stack_cursor = Rta::tree_depth - 1;
1121 id_stack[stack_cursor] = start_id;
1123 while (stack_cursor < Rta::tree_depth) {
1125 u32 current_node_id = id_stack[stack_cursor];
1126 id_stack[stack_cursor] = Rta::_nindex;
1129 bool cur_id_valid = func_int_cd(current_node_id);
1134 if (current_node_id >= acc.leaf_offset) {
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];
1140 for (
unsigned int id_s = min_ids; id_s < max_ids; id_s++) {
1143 uint id_b = acc.particle_index_map[id_s];
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];
1157 id_stack[stack_cursor - 1] = rid;
1160 id_stack[stack_cursor - 1] = lid;
1170 for (
u32 cache_pos = 0; cache_pos < cache_sz && cell_cache[cache_pos] !=
u32_max;
1172 walk_step(cache_pos);
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
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