Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
SerialPatchTree.cpp
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
15
18
19/*
20 * This file implements a faster version of the following algorithm (commit 3ff163a25), which
21 * builds the serial tree with a serial iterative pre-order traversal, run once per root, where each
22 * node is converted as soon as it is visited and its id written back in the childs_id of its
23 * parent.
24 *
25 * struct TraversalItem {
26 * u64 key; // key of the node in ptree.tree
27 * u64 parent_id; // id of its parent in the serial tree (u64_max for a root)
28 * u32 child_slot; // which child of the parent it is
29 * };
30 *
31 * std::vector<TraversalItem> stack{{root_key, u64_max, 0}};
32 * while (!stack.empty()) {
33 * TraversalItem cur = stack.back();
34 * stack.pop_back();
35 *
36 * const PatchTree::Node &ptn = ptree.tree.at(cur.key);
37 *
38 * u64 id = counter++;
39 * if (cur.parent_id != u64_max) {
40 * serial_tree[cur.parent_id].childs_id[cur.child_slot] = id;
41 * }
42 *
43 * max_level = sycl::max(ptn.tree_node.level, max_level);
44 * serial_tree.push_back(ptn.convert(box_transform));
45 * linked_patch_ids.push_back(ptn.linked_patchid);
46 *
47 * if (!ptn.tree_node.is_leaf) {
48 * for (u32 i = 8; i-- > 0;) { // reversed so that child 0 is visited first
49 * stack.push_back({ptn.tree_node.childs_nid[i], id, i});
50 * }
51 * }
52 * }
53 *
54 * The two pass version implemented here is equivalent up to the numbering of the nodes : it
55 * produces the same nodes (boxes, linked patch ids, leafs), the same childs in the same order, the
56 * same roots in the same order and the same level count, but numbers the nodes in breadth-first
57 * order instead of pre-order. Every user of the serial tree goes through roots_ids and childs_id,
58 * so the numbering does not matter. The test "shamrock/scheduler/SerialPatchTree:build" checks this
59 * equivalence on random patch trees.
60 */
61
62namespace {
63
64 using PatchTree = shamrock::scheduler::PatchTree;
65 using Node = PatchTree::Node;
66
67 // Below these sizes the OpenMP startup cost outweighs the gain (SerialPatchTree benchmark:
68 // serial is faster at ~40k nodes, parallel is ~3x faster at ~300k nodes)
69 constexpr u64 omp_min_lookups = 1U << 16;
70 constexpr u64 omp_min_nodes = 1U << 17;
71
73 struct SerialTreeLayout {
75 std::vector<const Node *> nodes;
77 std::vector<u64> first_child_ids;
79 std::vector<u64> roots_ids;
80 };
81
89 SerialTreeLayout make_breadth_first_layout(const PatchTree &ptree) {
90 SerialTreeLayout layout;
91 auto &nodes = layout.nodes;
92 auto &first_child_ids = layout.first_child_ids;
93
94 // is_leaf[i] mirrors nodes[i]->tree_node.is_leaf, filled when the node is looked up, so
95 // that the serial loop below reads a compact array instead of following the pointers.
96 // (u8 rather than bool since std::vector<bool> can not be written concurrently)
97 std::vector<u8> is_leaf;
98
99 nodes.reserve(ptree.tree.size());
100 first_child_ids.reserve(ptree.tree.size());
101 is_leaf.reserve(ptree.tree.size());
102
103 for (u64 root_key : ptree.roots_id) {
104 const Node &root = ptree.tree.at(root_key);
105 layout.roots_ids.push_back(nodes.size());
106 nodes.push_back(&root);
107 is_leaf.push_back(root.tree_node.is_leaf);
108 }
109
110 // nodes[level_begin, level_end) is the current level
111 u64 level_begin = 0;
112 u64 level_end = nodes.size();
113 while (level_begin < level_end) {
114
115 // give their ids to the childs of the current level
116 u64 next_level_end = level_end;
117 for (u64 i = level_begin; i < level_end; i++) {
118 if (is_leaf[i]) {
119 first_child_ids.push_back(u64_max);
120 } else {
121 first_child_ids.push_back(next_level_end);
122 next_level_end += 8;
123 }
124 }
125 nodes.resize(next_level_end);
126 is_leaf.resize(next_level_end);
127
128 // look the childs up in the patch tree
129 bool missing_child = false;
130#pragma omp parallel for if (next_level_end - level_end > omp_min_lookups) \
131 reduction(|| : missing_child)
132 for (u64 i = level_begin; i < level_end; i++) {
133 if (first_child_ids[i] == u64_max) {
134 continue;
135 }
136 for (u32 c = 0; c < 8; c++) {
137 auto it = ptree.tree.find(nodes[i]->tree_node.childs_nid[c]);
138 if (it == ptree.tree.end()) {
139 missing_child = true;
140 continue;
141 }
142 nodes[first_child_ids[i] + c] = &it->second;
143 is_leaf[first_child_ids[i] + c] = it->second.tree_node.is_leaf;
144 }
145 }
146 if (missing_child) {
148 "a child referenced in the patch tree is not in the tree");
149 }
150
151 level_begin = level_end;
152 level_end = next_level_end;
153 }
154
155 return layout;
156 }
157
158} // namespace
159
160template<class vec>
161void SerialPatchTree<vec>::build_from_patch_tree(
162 PatchTree &ptree, const shamrock::patch::PatchCoordTransform<vec> box_transform) {
163
164 // pass 1 : choose where each node goes in the serial tree
165 SerialTreeLayout layout = make_breadth_first_layout(ptree);
166
167 roots_ids = std::move(layout.roots_ids);
168 root_count = roots_ids.size();
169
170 // pass 2 : convert the nodes, in parallel since this writes the whole serial tree
171 u64 node_count = layout.nodes.size();
172 serial_tree.resize(node_count);
173 linked_patch_ids.resize(node_count);
174
175 u32 max_level = 0;
176#pragma omp parallel for if (node_count > omp_min_nodes) reduction(max : max_level)
177 for (u64 i = 0; i < node_count; i++) {
178 const Node &node = *layout.nodes[i];
179
180 PtNode snode = node.convert(box_transform);
181 if (layout.first_child_ids[i] != u64_max) {
182 for (u32 c = 0; c < 8; c++) {
183 snode.childs_id[c] = layout.first_child_ids[i] + c;
184 }
185 }
186
187 serial_tree[i] = snode;
188 linked_patch_ids[i] = node.linked_patchid;
189 max_level = sycl::max(max_level, node.tree_node.level);
190 }
191 level_count = max_level;
192
193 shamlog_debug_ln("Serial Patch Tree", "tree cell count = ", serial_tree.size());
194 shamlog_debug_ln("Serial Patch Tree", "level_count =", level_count);
195}
196
197template void SerialPatchTree<f32_3>::build_from_patch_tree(
198 PatchTree &ptree, const shamrock::patch::PatchCoordTransform<f32_3> box_transform);
199template void SerialPatchTree<f64_3>::build_from_patch_tree(
200 PatchTree &ptree, const shamrock::patch::PatchCoordTransform<f64_3> box_transform);
201template void SerialPatchTree<i64_3>::build_from_patch_tree(
202 PatchTree &ptree, const shamrock::patch::PatchCoordTransform<i64_3> box_transform);
std::uint32_t u32
32 bit unsigned integer
std::uint64_t u64
64 bit unsigned integer
Patch Tree : Tree structure organisation for an abstract list of patches Nb : this tree is compatible...
Definition PatchTree.hpp:29
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
constexpr u64 u64_max
u64 max value