Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
SerialPatchTree.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
19
20//%Impl status : Should rewrite
21
22#include "shambase/memory.hpp"
30#include <array>
31#include <tuple>
32#include <vector>
33
34template<class fp_prec_vec>
35class SerialPatchTree {
36 public:
38
39 using PatchTree = shamrock::scheduler::PatchTree;
40
41 // TODO use unique pointer instead
42 u32 root_count = 0;
43 std::unique_ptr<sycl::buffer<PtNode>> serial_tree_buf;
44 std::unique_ptr<sycl::buffer<u64>> linked_patch_ids_buf;
45
46 inline void attach_buf() {
47 if (bool(serial_tree_buf))
49 "serial_tree_buf is already allocated");
50 if (bool(linked_patch_ids_buf))
52 "linked_patch_ids_buf is already allocated");
53
54 serial_tree_buf
55 = std::make_unique<sycl::buffer<PtNode>>(serial_tree.data(), serial_tree.size());
56 linked_patch_ids_buf
57 = std::make_unique<sycl::buffer<u64>>(linked_patch_ids.data(), linked_patch_ids.size());
58 }
59
60 inline void detach_buf() {
61 if (!bool(serial_tree_buf))
63 "serial_tree_buf wasn't allocated");
64 if (!bool(linked_patch_ids_buf))
66 "linked_patch_ids_buf wasn't allocated");
67
68 serial_tree_buf.reset();
69 linked_patch_ids_buf.reset();
70 }
71
72 private:
73 u32 level_count = 0;
74
75 std::vector<PtNode> serial_tree;
76 std::vector<u64> linked_patch_ids;
77 std::vector<u64> roots_ids;
78
79 void build_from_patch_tree(
80 PatchTree &ptree, const shamrock::patch::PatchCoordTransform<fp_prec_vec> box_transform);
81
82 public:
83 inline void print_status() {
84 if (shamcomm::world_rank() == 0) {
85 for (PtNode n : serial_tree) {
87 n.box_min,
88 n.box_max,
89 "[",
90 n.childs_id[0],
91 n.childs_id[1],
92 n.childs_id[2],
93 n.childs_id[3],
94 n.childs_id[4],
95 n.childs_id[5],
96 n.childs_id[6],
97 n.childs_id[7],
98 "]");
99 }
100 }
101 }
102
103 inline SerialPatchTree(
104 PatchTree &ptree, const shamrock::patch::PatchCoordTransform<fp_prec_vec> box_transform) {
105 StackEntry stack_loc{};
106 build_from_patch_tree(ptree, box_transform);
107 }
108
109 template<class Acc1, class Acc2>
110 inline void host_for_each_leafs_internal(
111 std::function<bool(u64, PtNode pnode)> interact_cd,
112 std::function<void(u64, PtNode)> found_case,
113 Acc1 &&tree,
114 Acc2 &&lpid) {
115
116 std::stack<u64> id_stack;
117
118 for (u64 root : roots_ids) {
119 id_stack.push(root);
120 }
121
122 while (!id_stack.empty()) {
123 u64 cur_id = id_stack.top();
124 id_stack.pop();
125 PtNode cur_p = tree[cur_id];
126
127 bool interact = interact_cd(cur_id, cur_p);
128
129 if (interact) {
130 u64 linked_id = lpid[cur_id];
131 if (linked_id != u64_max) {
132 found_case(linked_id, cur_p);
133 } else {
134 id_stack.push(cur_p.childs_id[0]);
135 id_stack.push(cur_p.childs_id[1]);
136 id_stack.push(cur_p.childs_id[2]);
137 id_stack.push(cur_p.childs_id[3]);
138 id_stack.push(cur_p.childs_id[4]);
139 id_stack.push(cur_p.childs_id[5]);
140 id_stack.push(cur_p.childs_id[6]);
141 id_stack.push(cur_p.childs_id[7]);
142 }
143 }
144 }
145 }
146
147 inline void host_for_each_leafs(
148 std::function<bool(u64, PtNode pnode)> interact_cd,
149 std::function<void(u64, PtNode)> found_case) {
150 StackEntry stack_loc{false};
151
152 sycl::host_accessor tree{shambase::get_check_ref(serial_tree_buf), sycl::read_only};
153 sycl::host_accessor lpid{shambase::get_check_ref(linked_patch_ids_buf), sycl::read_only};
154
155 host_for_each_leafs_internal(interact_cd, found_case, tree, lpid);
156 }
157
163 inline const u32 &get_level_count() { return level_count; }
164
170 inline u32 get_element_count() { return serial_tree.size(); }
171
176 inline const std::vector<u64> &get_roots_ids() const { return roots_ids; }
177
178 inline static SerialPatchTree<fp_prec_vec> build(PatchScheduler &sched) {
180 sched.patch_tree, sched.get_patch_transform<fp_prec_vec>());
181 }
182
183 template<class T, class Func>
184 inline shamrock::patch::PatchtreeField<T> make_patch_tree_field(
185 PatchScheduler &sched,
186 sycl::queue &queue,
187 const shamrock::patch::PatchField<T> &pfield,
188 Func &&reducer) {
190
191 shamrock::patch::PatchtreeField<T> ptfield;
192 ptfield.allocate(get_element_count());
193
194 {
196 sycl::host_accessor lpid{
197 shambase::get_check_ref(linked_patch_ids_buf), sycl::read_only};
198 sycl::host_accessor tree_field{
199 shambase::get_check_ref(ptfield.internal_buf), sycl::write_only, sycl::no_init};
200
201 // init reduction
202 std::unordered_map<u64, u64> &idp_to_gid = sched.patch_list.id_patch_to_global_idx;
203
204#pragma omp parallel for
205 for (u64 idx = 0; idx < get_element_count(); idx++) {
206 tree_field[idx] = (lpid[idx] != u64_max) ? pfield.get(lpid[idx]) : T();
207 }
208 }
209
210 sycl::range<1> range{get_element_count()};
211 u32 end_loop = get_level_count();
212
213 for (u32 level = 0; level < end_loop; level++) {
214 queue.submit([&](sycl::handler &cgh) {
215 sycl::accessor tree{shambase::get_check_ref(serial_tree_buf), cgh, sycl::read_only};
216 sycl::accessor f{
217 shambase::get_check_ref(ptfield.internal_buf), cgh, sycl::read_write};
218
219 cgh.parallel_for(range, [=](sycl::item<1> item) {
220 u64 i = (u64) item.get_id(0);
221
222 std::array<u64, 8> n = tree[i].childs_id;
223
224 if (n[0] != u64_max) {
225 f[i] = reducer(
226 f[n[0]], f[n[1]], f[n[2]], f[n[3]], f[n[4]], f[n[5]], f[n[6]], f[n[7]]);
227 }
228 });
229 });
230 }
231 return ptfield;
232 }
233
234 inline void dump_dat() {
235 for (u64 idx = 0; idx < get_element_count(); idx++) {
236 std::cout << idx << " (" << serial_tree[idx].childs_id[0] << ", "
237 << serial_tree[idx].childs_id[1] << ", " << serial_tree[idx].childs_id[2]
238 << ", " << serial_tree[idx].childs_id[3] << ", "
239 << serial_tree[idx].childs_id[4] << ", " << serial_tree[idx].childs_id[5]
240 << ", " << serial_tree[idx].childs_id[6] << ", "
241 << serial_tree[idx].childs_id[7] << ")";
242
243 std::cout << " (" << serial_tree[idx].box_min.x() << ", "
244 << serial_tree[idx].box_min.y() << ", " << serial_tree[idx].box_min.z()
245 << ")";
246
247 std::cout << " (" << serial_tree[idx].box_max.x() << ", "
248 << serial_tree[idx].box_max.y() << ", " << serial_tree[idx].box_max.z()
249 << ")";
250
251 std::cout << " = " << linked_patch_ids[idx];
252
253 std::cout << std::endl;
254 }
255 }
256
257 sycl::buffer<u64> compute_patch_owner(
258 sham::DeviceScheduler_ptr dev_sched,
259 sham::DeviceBuffer<fp_prec_vec> &position_buffer,
260 u32 len,
261 u64 current_patch_id = u64_max,
262 fp_prec_vec current_patch_min = {},
263 fp_prec_vec current_patch_max = {});
264};
265
266template<class vec>
267sycl::buffer<u64> SerialPatchTree<vec>::compute_patch_owner(
268 sham::DeviceScheduler_ptr dev_sched,
269 sham::DeviceBuffer<vec> &position_buffer,
270 u32 len,
271 u64 current_patch_id,
272 vec current_patch_min,
273 vec current_patch_max) {
274 sycl::buffer<u64> new_owned_id(len);
275
276 using namespace shamrock::patch;
277
278 sham::DeviceBuffer<u64> roots(roots_ids.size(), dev_sched);
279 roots.copy_from_stdvec(roots_ids);
280
281 auto &q = dev_sched->get_queue();
282
283 sham::EventList depends_list;
284 auto pos = position_buffer.get_read_access(depends_list);
285 auto roots_id = roots.get_read_access(depends_list);
286
287 auto e = q.submit(depends_list, [&](sycl::handler &cgh) {
288 sycl::accessor tnode{shambase::get_check_ref(serial_tree_buf), cgh, sycl::read_only};
289 sycl::accessor linked_node_id{
290 shambase::get_check_ref(linked_patch_ids_buf), cgh, sycl::read_only};
291 sycl::accessor new_id{new_owned_id, cgh, sycl::write_only, sycl::no_init};
292
293 u32 root_cnt = roots_ids.size();
294 auto max_lev = get_level_count();
295
296 u64 cur_pid = current_patch_id;
297 vec cur_box_min = current_patch_min;
298 vec cur_box_max = current_patch_max;
299
301
302 cgh.parallel_for(sycl::range(len), [=](sycl::item<1> item) {
303 u32 i = (u32) item.get_id(0);
304
305 auto xyz = pos[i];
306
307 // the object is still in its current patch, skip the tree traversal
308 if (cur_pid != u64_max && Patch::is_in_patch_converted(xyz, cur_box_min, cur_box_max)) {
309 new_id[i] = cur_pid;
310 return;
311 }
312
313 u64 current_node = 0;
314
315 // find the correct root to start the search
316 for (u32 iroot = 0; iroot < root_cnt; iroot++) {
317 u32 root_id = roots_id[iroot];
318 PtNode root_node = tnode[root_id];
319
320 if (Patch::is_in_patch_converted(xyz, root_node.box_min, root_node.box_max)) {
321 current_node = root_id;
322 break;
323 }
324 }
325
326 u64 result_node = u64_max;
327
328 for (u32 step = 0; step < max_lev + 1; step++) {
329 PtNode cur_node = tnode[current_node];
330
331 if (cur_node.childs_id[0] != u64_max) {
332
334 xyz,
335 tnode[cur_node.childs_id[0]].box_min,
336 tnode[cur_node.childs_id[0]].box_max)) {
337 current_node = cur_node.childs_id[0];
338 } else if (
340 xyz,
341 tnode[cur_node.childs_id[1]].box_min,
342 tnode[cur_node.childs_id[1]].box_max)) {
343 current_node = cur_node.childs_id[1];
344 } else if (
346 xyz,
347 tnode[cur_node.childs_id[2]].box_min,
348 tnode[cur_node.childs_id[2]].box_max)) {
349 current_node = cur_node.childs_id[2];
350 } else if (
352 xyz,
353 tnode[cur_node.childs_id[3]].box_min,
354 tnode[cur_node.childs_id[3]].box_max)) {
355 current_node = cur_node.childs_id[3];
356 } else if (
358 xyz,
359 tnode[cur_node.childs_id[4]].box_min,
360 tnode[cur_node.childs_id[4]].box_max)) {
361 current_node = cur_node.childs_id[4];
362 } else if (
364 xyz,
365 tnode[cur_node.childs_id[5]].box_min,
366 tnode[cur_node.childs_id[5]].box_max)) {
367 current_node = cur_node.childs_id[5];
368 } else if (
370 xyz,
371 tnode[cur_node.childs_id[6]].box_min,
372 tnode[cur_node.childs_id[6]].box_max)) {
373 current_node = cur_node.childs_id[6];
374 } else if (
376 xyz,
377 tnode[cur_node.childs_id[7]].box_min,
378 tnode[cur_node.childs_id[7]].box_max)) {
379 current_node = cur_node.childs_id[7];
380 }
381
382 } else {
383
384 result_node = linked_node_id[current_node];
385 break;
386 }
387 }
388
389 new_id[i] = result_node;
390 });
391 });
392
393 position_buffer.complete_event_state(e);
394 roots.complete_event_state(e);
395
396 return new_owned_id;
397}
constexpr const char * xyz
Position field (3D coordinates).
MPI scheduler.
std::uint32_t u32
32 bit unsigned integer
std::uint64_t u64
64 bit unsigned integer
The MPI scheduler.
PatchTree patch_tree
handle the tree structure of the patches
SchedulerPatchList patch_list
handle the list of the patches of the scheduler
std::unordered_map< u64, u64 > id_patch_to_global_idx
id_patch_to_global_idx[patch_id] = index in global patch list
const u32 & get_level_count()
accesor to the number of level in the tree
u32 get_element_count()
accesor to the number of element in the tree
const std::vector< u64 > & get_roots_ids() const
accessor to the ids of the roots in the serial tree, in the order of PatchTree::roots_id
A buffer allocated in USM (Unified Shared Memory).
void complete_event_state(sycl::event e) const
Complete the event state of the buffer.
const T * get_read_access(sham::EventList &depends_list, SourceLocation src_loc=SourceLocation{}) const
Get a read-only pointer to the buffer's data.
Class to manage a list of SYCL events.
Definition EventList.hpp:32
Patch Tree : Tree structure organisation for an abstract list of patches Nb : this tree is compatible...
Definition PatchTree.hpp:29
T & get_check_ref(const std::unique_ptr< T > &ptr, SourceLocation loc=SourceLocation())
Takes a std::unique_ptr and returns a reference to the object it holds. It throws a std::runtime_erro...
Definition memory.hpp:112
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
i32 world_rank()
Gives the rank of the current process in the MPI communicator.
Definition worldInfo.cpp:41
constexpr u64 u64_max
u64 max value
void raw_ln(Types... var2)
Prints a log message with multiple arguments followed by a newline.
Definition logs.hpp:89
This file contains the definition for the stacktrace related functionality.
#define __shamrock_stack_entry()
Macro to create a stack entry.
shambase::details::BasicStackEntry StackEntry
Alias for shambase::details::BasicStackEntry.
static bool is_in_patch_converted(sycl::vec< T, 3 > val, sycl::vec< T, 3 > min_val, sycl::vec< T, 3 > max_val)
check if particle is in the asked range, given the output of @convert_coord
Definition Patch.hpp:210
header file to manage sycl