Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
numeric.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
17
19#include "shambase/assert.hpp"
20#include "shambase/integer.hpp"
30#include <utility>
31
32namespace shamalgs::numeric {
33
34 template<class T>
35 sycl::buffer<T> scan_exclusive(sycl::queue &q, sycl::buffer<T> &buf1, u32 len) {
36#ifdef __MACH__ // decoupled lookback perf on mac os is awful
37 return details::exclusive_sum_fallback(q, buf1, len);
38#else
39 #ifdef SYCL2020_FEATURE_GROUP_REDUCTION
40 return details::exclusive_sum_atomic_decoupled_v5<T, 512>(q, buf1, len);
41 #else
42 return details::exclusive_sum_fallback(q, buf1, len);
43 #endif
44#endif
45 }
46
47 template<class T>
49 sham::DeviceScheduler_ptr sched, sham::DeviceBuffer<T> &buf1, u32 len) {
50#ifdef __MACH__ // decoupled lookback perf on mac os is awful
51 return details::exclusive_sum_fallback_usm(sched, buf1, len);
52#else
53 #ifdef SYCL2020_FEATURE_GROUP_REDUCTION
54 return details::exclusive_sum_atomic_decoupled_v5_usm<T, 512>(sched, buf1, len);
55 #else
56 return details::exclusive_sum_fallback_usm(sched, buf1, len);
57 #endif
58#endif
59 }
60
61 template sycl::buffer<u32> scan_exclusive(sycl::queue &q, sycl::buffer<u32> &buf1, u32 len);
63 sham::DeviceScheduler_ptr sched, sham::DeviceBuffer<u32> &buf1, u32 len);
64
65 std::tuple<std::optional<sycl::buffer<u32>>, u32> stream_compact(
66 sycl::queue &q, sycl::buffer<u32> &buf_flags, u32 len) {
67 return details::stream_compact_excl_scan(q, buf_flags, len);
68 };
69
71 const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer<u32> &buf_flags, u32 len) {
72 return details::stream_compact_excl_scan(sched, buf_flags, len);
73 }
74
75 template<class Tret, class T>
77 const sham::DeviceScheduler_ptr &sched,
78 const sham::DeviceBuffer<T> &bin_edges,
79 u64 nbins,
80 const sham::DeviceBuffer<T> &values,
81 u32 len) {
82
83 SHAM_ASSERT(nbins > 1); // at least a sup and a inf
84 SHAM_ASSERT(bin_edges.get_size() == nbins + 1);
85
87 counts.fill(0);
88
89 if (len == 0) {
90 return counts;
91 }
92
93 auto &q = shambase::get_check_ref(sched).get_queue();
94
96 q,
97 sham::MultiRef{values, bin_edges},
98 sham::MultiRef{counts},
99 len,
100 [nbins](
101 u32 i,
102 const T *__restrict values,
103 const T *__restrict bin_edges,
104 Tret *__restrict counts) {
105 // Only count values within [bin_edges[0], bin_edges[nbins])
106 if (values[i] < bin_edges[0] || values[i] >= bin_edges[nbins]) {
107 return;
108 }
109
110 u32 start_range = 0;
111 u32 end_range = nbins + 1;
112
113 while (end_range - start_range > 1) {
114 u32 mid_range = (start_range + end_range) / 2;
115
116 if (values[i] < bin_edges[mid_range]) { // mid_range is a sup
117 end_range = mid_range;
118 } else { // mid_range is an inf
119 start_range = mid_range;
120 }
121 }
122
123 SHAM_ASSERT(end_range == start_range + 1);
124
125 sycl::atomic_ref<
126 Tret,
127 sycl::memory_order_relaxed,
128 sycl::memory_scope_device,
129 sycl::access::address_space::global_space>
130 cnt(counts[start_range]);
131
132 cnt++;
133 });
134
135 return counts;
136 }
137
139 const sham::DeviceScheduler_ptr &sched,
140 const sham::DeviceBuffer<f64> &bin_edges,
141 u64 nbins,
142 const sham::DeviceBuffer<f64> &values,
143 u32 len);
145 const sham::DeviceScheduler_ptr &sched,
146 const sham::DeviceBuffer<f32> &bin_edges,
147 u64 nbins,
148 const sham::DeviceBuffer<f32> &values,
149 u32 len);
151 const sham::DeviceScheduler_ptr &sched,
152 const sham::DeviceBuffer<f64> &bin_edges,
153 u64 nbins,
154 const sham::DeviceBuffer<f64> &values,
155 u32 len);
157 const sham::DeviceScheduler_ptr &sched,
158 const sham::DeviceBuffer<f32> &bin_edges,
159 u64 nbins,
160 const sham::DeviceBuffer<f32> &values,
161 u32 len);
162
163 template<class T>
165 const sham::DeviceScheduler_ptr &sched,
166 const sham::DeviceBuffer<T> &bin_edges,
167 u64 nbins,
168 const sham::DeviceBuffer<T> &values, // ie f(r)
169 const sham::DeviceBuffer<T> &keys, // ie r
170 u32 len) { // ie return <f(r)>_r
171
172 auto &q = shambase::get_check_ref(sched).get_queue();
173
174 auto value_filter = [&]() {
175 if (len > 0) {
176
177 // filter values
178 sham::DeviceBuffer<u32> key_filter(keys.get_size(), sched);
179
181 q,
182 sham::MultiRef{keys, bin_edges},
183 sham::MultiRef{key_filter},
184 len,
185 [nbins](
186 u32 i,
187 const T *__restrict keys,
188 const T *__restrict bin_edges,
189 u32 *__restrict key_filter) {
190 // Only count keys within [bin_edges[0], bin_edges[nbins])
191 if (keys[i] < bin_edges[0] || keys[i] >= bin_edges[nbins]) {
192 key_filter[i] = 0;
193 } else {
194 key_filter[i] = 1;
195 }
196 });
197
198 // compact
199 sham::DeviceBuffer<u32> valid_key_idxs = stream_compact(sched, key_filter, len);
200
201 return valid_key_idxs;
202 } else {
203 return sham::DeviceBuffer<u32>(0, sched);
204 }
205 };
206
207 sham::DeviceBuffer<u32> valid_key_idxs = value_filter();
208
209 u32 valid_key_count = valid_key_idxs.get_size();
210
211 // make the buffer with all the valid keys
212 sham::DeviceBuffer<T> valid_keys(valid_key_count, sched);
213 sham::DeviceBuffer<T> valid_values(valid_key_count, sched);
214
215 if (valid_key_count > 0) {
217 q,
218 sham::MultiRef{keys, values, valid_key_idxs},
219 sham::MultiRef{valid_keys, valid_values},
220 valid_key_count,
221 [](u32 i,
222 const T *__restrict keys,
223 const T *__restrict values,
224 const u32 *__restrict valid_keys_idxs,
225 T *__restrict valid_keys,
226 T *__restrict valid_values) {
227 u32 src_key = valid_keys_idxs[i];
228 valid_keys[i] = keys[src_key];
229 valid_values[i] = values[src_key];
230 });
231 }
232
233 // histogram standard
234 sham::DeviceBuffer<u32> bin_counts
235 = device_histogram<u32>(sched, bin_edges, nbins, valid_keys, valid_key_count);
236
237 bin_counts.expand(1);
238 bin_counts.set_val_at_idx(bin_counts.get_size() - 1, 0);
239
240 // exclusive scan
241 // bin_ids[i] starts at offset[i] and ends at offset[i+1]
242 sham::DeviceBuffer<u32> offsets_bins
243 = scan_exclusive(sched, bin_counts, bin_counts.get_size());
244
245 SHAM_ASSERT(offsets_bins.get_val_at_idx(offsets_bins.get_size() - 1) == valid_key_count);
246
247 if (valid_key_count > 0) {
248 // sort need 2^n as length
249 u32 pow2_len_key = shambase::roundup_pow2(valid_key_count);
250 {
251 if (pow2_len_key > valid_key_count) {
252 valid_keys.resize(pow2_len_key);
253 valid_values.resize(pow2_len_key);
254
256 q,
258 sham::MultiRef{valid_keys, valid_values},
259 pow2_len_key - valid_key_count,
260 [offset_start = valid_key_count](
261 u32 i, T *__restrict valid_keys, T *__restrict valid_values) {
262 u32 key_id = offset_start + i;
263 valid_keys[key_id] = shambase::get_max<T>();
264 valid_values[key_id] = shambase::get_max<T>();
265 });
266 }
267 }
268
269 // how to be a patate? Resize buffers to diligently become powers of 2, and don't update
270 // the variable holding their length
272 sched, valid_keys, valid_values, pow2_len_key);
273 }
274
275 return {std::move(valid_values), std::move(offsets_bins)};
276 }
277
279 const sham::DeviceScheduler_ptr &sched,
280 const sham::DeviceBuffer<f64> &bin_edges,
281 u64 nbins,
282 const sham::DeviceBuffer<f64> &values,
283 const sham::DeviceBuffer<f64> &keys,
284 u32 len);
286 const sham::DeviceScheduler_ptr &sched,
287 const sham::DeviceBuffer<f32> &bin_edges,
288 u64 nbins,
289 const sham::DeviceBuffer<f32> &values,
290 const sham::DeviceBuffer<f32> &keys,
291 u32 len);
292
293} // namespace shamalgs::numeric
std::uint32_t u32
32 bit unsigned integer
std::uint64_t u64
64 bit unsigned integer
Shamrock assertion utility.
#define SHAM_ASSERT(x)
Shorthand for SHAM_ASSERT_NAMED without a message.
Definition assert.hpp:67
A buffer allocated in USM (Unified Shared Memory).
void resize(size_t new_size, bool keep_data=true)
Resizes the buffer to a given size.
void fill(T value, std::array< size_t, 2 > idx_range)
Fill a subpart of the buffer with a given value.
T get_val_at_idx(size_t idx) const
Get the value at a given index in the buffer.
size_t get_size() const
Gets the number of elements in the buffer.
void expand(u32 add_sz)
Expand the buffer by add_sz elements.
main include file for the shamalgs algorithms
void kernel_call(sham::DeviceQueue &q, RefIn in, RefOut in_out, u32 n, Functor &&func, SourceLocation &&callsite=SourceLocation{})
Submit a kernel to a SYCL queue.
void sort_by_key_pow2_len(sycl::queue &q, sycl::buffer< Tkey > &buf_key, sycl::buffer< Tval > &buf_values, u32 len)
Sort the buffer according to the key order.
Definition algorithm.hpp:43
namespace containing the numeric algorithms of shamalgs
BinnedCompute< T > binned_init_compute(const sham::DeviceScheduler_ptr &sched, const sham::DeviceBuffer< T > &bin_edges, u64 nbins, const sham::DeviceBuffer< T > &values, const sham::DeviceBuffer< T > &keys, u32 len)
Prepare binned data for per-bin computation.
Definition numeric.cpp:164
sham::DeviceBuffer< Tret > device_histogram(const sham::DeviceScheduler_ptr &sched, const sham::DeviceBuffer< T > &bin_edges, u64 nbins, const sham::DeviceBuffer< T > &values, u32 len)
Compute the histogram of values between bin_edges.
Definition numeric.cpp:76
sycl::buffer< T > scan_exclusive(sycl::queue &q, sycl::buffer< T > &buf1, u32 len)
Computes the exclusive sum of elements in a SYCL buffer.
Definition numeric.cpp:35
std::tuple< std::optional< sycl::buffer< u32 > >, u32 > stream_compact(sycl::queue &q, sycl::buffer< u32 > &buf_flags, u32 len)
Stream compaction algorithm.
Definition numeric.cpp:65
constexpr T roundup_pow2(T v) noexcept
round up to the next power of two Source : https://graphics.stanford.edu/~seander/bithacks....
Definition integer.hpp:92
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
sham::DeviceBuffer< T > exclusive_sum_fallback_usm(const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer< T > &buf1, u32 len)
Exclusive sum fallback on USM.
sycl::buffer< T > exclusive_sum_fallback(sycl::queue &q, sycl::buffer< T > &buf1, u32 len)
Exclusive sum fallback on SYCL buffer.
std::tuple< std::optional< sycl::buffer< u32 > >, u32 > stream_compact_excl_scan(sycl::queue &q, sycl::buffer< u32 > &buf_flags, u32 len)
Stream compaction algorithm using exclusive summation.
A class that references multiple buffers or similar objects.
Definition MultiRef.hpp:33
Structure holding the result of binning values for further computation.
Definition numeric.hpp:207