Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
compute_histogram.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
18
21#include "shambase/string.hpp"
28#include <shambackends/sycl.hpp>
29#include <optional>
30#include <stdexcept>
31#include <tuple>
32#include <utility>
33#include <vector>
34
35namespace shamalgs::primitives {
36
37 namespace impl {
38
40 struct Reference {
41 static constexpr std::string_view variant_type_name = "reference";
42 };
43
44 struct NaiveGpu {
45 static constexpr std::string_view variant_type_name = "naive_gpu";
46 };
47
49 static constexpr std::string_view variant_type_name = "gpu_team_fetching";
50 };
51
53 static constexpr std::string_view variant_type_name = "gpu_oversubscribe";
54 };
55
59
62
64 constexpr std::string_view compute_histogram_impl_name = "compute_histogram";
65
66 template<class T, class Tbins, class... Targs, class Tfunctor>
67 inline void compute_histogram_reference(
68 const sham::DeviceBuffer<Tbins> &bin_edge_inf,
69 const sham::DeviceBuffer<Tbins> &bin_edge_sup,
70 size_t nbins,
71 size_t element_count,
72 Tfunctor &&functor,
74 const sham::DeviceBuffer<Targs> &...input_data) {
75
76 auto result_vec = result.copy_to_stdvec();
77
78 auto cpu_basic_impl = [&](const std::vector<Tbins> &bin_edge_inf,
79 const std::vector<Tbins> &bin_edge_sup,
80 const std::vector<Targs> &...in_data,
81 std::vector<T> &result) {
82 for (size_t ibin = 0; ibin < nbins; ibin++) {
83 Tbins edge_inf = bin_edge_inf[ibin];
84 Tbins edge_sup = bin_edge_sup[ibin];
85
86 T accumulator = 0;
87
88 for (size_t i = 0; i < element_count; i++) {
89 bool has_value = false;
90 auto tmp = functor(edge_inf, edge_sup, in_data[i]..., has_value);
91 if (has_value) {
92 accumulator += tmp;
93 }
94 }
95
96 result[ibin] = accumulator;
97 }
98 };
99
100 cpu_basic_impl(
101 bin_edge_inf.copy_to_stdvec(),
102 bin_edge_sup.copy_to_stdvec(),
103 input_data.copy_to_stdvec()...,
104 result_vec);
105
106 result.copy_from_stdvec(result_vec);
107 }
108
109 template<class T, class Tbins, class... Targs, class Tfunctor>
110 inline void compute_histogram_naive_gpu(
111 const sham::DeviceScheduler_ptr &dev_sched,
112 const sham::DeviceBuffer<Tbins> &bin_edge_inf,
113 const sham::DeviceBuffer<Tbins> &bin_edge_sup,
114 size_t nbins,
115 size_t element_count,
116 Tfunctor &&functor,
117 sham::DeviceBuffer<T> &result,
118 const sham::DeviceBuffer<Targs> &...input_data) {
119
121 dev_sched->get_queue(),
122 sham::MultiRef{bin_edge_inf, bin_edge_sup, input_data...},
123 sham::MultiRef{result},
124 nbins,
125 [element_count, functor](
126 u32 ibin,
127 const Tbins *__restrict bin_edge_inf,
128 const Tbins *__restrict bin_edge_sup,
129 const Targs *__restrict... in_data,
130 T *__restrict result) {
131 Tbins edge_inf = bin_edge_inf[ibin];
132 Tbins edge_sup = bin_edge_sup[ibin];
133
134 T accumulator = 0;
135
136 for (size_t i = 0; i < element_count; i++) {
137 bool has_value = false;
138 T tmp = functor(edge_inf, edge_sup, in_data[i]..., has_value);
139 if (has_value) {
140 accumulator += tmp;
141 }
142 }
143
144 result[ibin] = accumulator;
145 });
146 }
147
148 template<class T, class Tbins, class... Targs, class Tfunctor>
149 inline void compute_histogram_gpu_team_fetching(
150 const sham::DeviceScheduler_ptr &dev_sched,
151 const sham::DeviceBuffer<Tbins> &bin_edge_inf,
152 const sham::DeviceBuffer<Tbins> &bin_edge_sup,
153 size_t nbins,
154 size_t element_count,
155 Tfunctor &&functor,
156 sham::DeviceBuffer<T> &result,
157 const sham::DeviceBuffer<Targs> &...input_data) {
158
159 sham::kernel_call_hndl(
160 dev_sched->get_queue(),
161 sham::MultiRef{bin_edge_inf, bin_edge_sup, input_data...},
162 sham::MultiRef{result},
163 nbins,
164 [element_count, functor](
165 u32 nbins,
166 const Tbins *__restrict bin_edge_inf,
167 const Tbins *__restrict bin_edge_sup,
168 const Targs *__restrict... in_data,
169 T *__restrict result) {
170 return [=, in_data = std::tuple{in_data...}](sycl::handler &cgh) {
171 u32 group_size = 128;
172 u32 group_cnt = shambase::group_count(nbins, group_size);
173
174 // roundup to next multiple of 4
175 group_cnt = (group_cnt + 3) / 4 * 4;
176 u32 corrected_len = group_cnt * group_size;
177
178 auto locals
179 = sycl::local_accessor<std::tuple<Targs...>, 1>(group_size, cgh);
180
181 cgh.parallel_for(
182 sycl::nd_range<1>{corrected_len, group_size},
183 [=](sycl::nd_item<1> item) {
184 u32 local_id = item.get_local_id(0);
185 u32 group_tile_id = item.get_group_linear_id();
186 u32 ibin = group_tile_id * group_size + local_id;
187
188 bool is_valid_point = (ibin < nbins);
189 Tbins edge_inf = is_valid_point ? bin_edge_inf[ibin] : Tbins{};
190 Tbins edge_sup = is_valid_point ? bin_edge_sup[ibin] : Tbins{};
191
192 T local_sum = 0;
193
194 for (size_t i = 0; i < element_count; i += group_size) {
195
196 item.barrier(sycl::access::fence_space::local_space);
197
198 if (i + local_id < element_count) {
199 std::apply(
200 [&](auto &...in_data) {
201 locals[local_id]
202 = std::tuple{in_data[i + local_id]...};
203 },
204 in_data);
205 }
206
207 item.barrier(sycl::access::fence_space::local_space);
208
209 if (is_valid_point) {
210 for (size_t lane = 0; lane < group_size; lane++) {
211 if (i + lane >= element_count) {
212 continue;
213 }
214 bool has_value = false;
215 T tmp = std::apply(
216 [&](auto &...local_accs) {
217 return functor(
218 edge_inf,
219 edge_sup,
220 local_accs...,
221 has_value);
222 },
223 locals[lane]);
224 if (has_value) {
225 local_sum += tmp;
226 }
227 }
228 }
229
230 item.barrier(sycl::access::fence_space::local_space);
231 }
232
233 if (is_valid_point) {
234 result[ibin] = local_sum;
235 }
236 });
237 };
238 });
239 }
240
241 template<class T, class Tbins, class... Targs, class Tfunctor>
242 inline void compute_histogram_gpu_oversubscribe(
243 const sham::DeviceScheduler_ptr &dev_sched,
244 u32 group_size,
245 const sham::DeviceBuffer<Tbins> &bin_edge_inf,
246 const sham::DeviceBuffer<Tbins> &bin_edge_sup,
247 size_t nbins,
248 size_t element_count,
249 Tfunctor &&functor,
250 sham::DeviceBuffer<T> &result,
251 const sham::DeviceBuffer<Targs> &...input_data) {
252
253 sham::kernel_call_hndl(
254 dev_sched->get_queue(),
255 sham::MultiRef{bin_edge_inf, bin_edge_sup, input_data...},
256 sham::MultiRef{result},
257 nbins * group_size,
258 [element_count, functor, group_size, nbins](
259 u32 nbins_oversubscribed,
260 const Tbins *__restrict bin_edge_inf,
261 const Tbins *__restrict bin_edge_sup,
262 const Targs *__restrict... in_data,
263 T *__restrict result) {
264 return [=, in_data = std::tuple{in_data...}](sycl::handler &cgh) {
265 u32 group_cnt = shambase::group_count(nbins_oversubscribed, group_size);
266
267 // roundup to next multiple of 4
268 group_cnt = (group_cnt + 3) / 4 * 4;
269
270 u32 corrected_len = group_cnt * group_size;
271
272 cgh.parallel_for(
273 sycl::nd_range<1>{corrected_len, group_size},
274 [=](sycl::nd_item<1> item) {
275 u32 local_id = item.get_local_id(0);
276 u32 ibin = item.get_group_linear_id();
277
278 bool is_valid_point = (ibin < nbins);
279 Tbins edge_inf = is_valid_point ? bin_edge_inf[ibin] : Tbins{};
280 Tbins edge_sup = is_valid_point ? bin_edge_sup[ibin] : Tbins{};
281
282 // for each thread this will the sum of all the
283 // "func(in_data[group_size*i + local_id]) for all i"
284 T local_sum = 0;
285
286 for (size_t i = 0; i < element_count; i += group_size) {
287
288 if (i + local_id < element_count) {
289
290 bool has_value = false;
291
292 // coalesced read of the data and then
293 // compute the value to accumulate
294 T tmp = std::apply(
295 [&](auto &...in_data) {
296 return functor(
297 edge_inf,
298 edge_sup,
299 in_data[i + local_id]...,
300 has_value);
301 },
302 in_data);
303
304 if (has_value) {
305 // add it to the local sum of this thread
306 local_sum += tmp;
307 }
308 }
309 }
310
311 // we have all the terms scattered across the threads of the group,
312 // we can just accumulate the result
313 auto group_sum = sycl::reduce_over_group(
314 item.get_group(), local_sum, sycl::plus<T>{});
315
316 if (is_valid_point && local_id == 0) {
317 result[ibin] = group_sum;
318 }
319 });
320 };
321 });
322 }
323
324 } // namespace impl
325
326 template<class T, class Tbins, class... Targs, class Tfunctor>
327 inline sham::DeviceBuffer<T> compute_histogram(
328 const sham::DeviceScheduler_ptr &dev_sched,
329 const sham::DeviceBuffer<Tbins> &bin_edge_inf,
330 const sham::DeviceBuffer<Tbins> &bin_edge_sup,
331 size_t element_count,
332 Tfunctor &&functor,
333 const sham::DeviceBuffer<Targs> &...input_data) {
334
335 using namespace impl;
336
337 size_t nbins = bin_edge_inf.get_size();
338
339 if (nbins != bin_edge_sup.get_size()) {
341 "bin_edge_inf and bin_edge_sup must have the same size");
342 }
343
344 sham::DeviceBuffer<T> result(nbins, dev_sched);
345
346 if (!impl::compute_histogram_impl.is_set()) {
347 shamalgs::impl_registry::autoselect_impl(impl::compute_histogram_impl_name, dev_sched);
348 }
349
350 std::visit(
352 [&](impl::Reference) {
353 compute_histogram_reference(
354 bin_edge_inf,
355 bin_edge_sup,
356 nbins,
357 element_count,
358 std::forward<Tfunctor>(functor),
359 result,
360 input_data...);
361 },
362 [&](impl::NaiveGpu) {
363 compute_histogram_naive_gpu(
364 dev_sched,
365 bin_edge_inf,
366 bin_edge_sup,
367 nbins,
368 element_count,
369 std::forward<Tfunctor>(functor),
370 result,
371 input_data...);
372 },
373 [&](impl::GpuTeamFetching) {
374 compute_histogram_gpu_team_fetching(
375 dev_sched,
376 bin_edge_inf,
377 bin_edge_sup,
378 nbins,
379 element_count,
380 std::forward<Tfunctor>(functor),
381 result,
382 input_data...);
383 },
384 [&](impl::GpuOversubscribe) {
385 compute_histogram_gpu_oversubscribe(
386 dev_sched,
387 256,
388 bin_edge_inf,
389 bin_edge_sup,
390 nbins,
391 element_count,
392 std::forward<Tfunctor>(functor),
393 result,
394 input_data...);
395 },
396 },
397 impl::compute_histogram_impl.get());
398
399 return result;
400 }
401
402 template<class T>
403 inline sham::DeviceBuffer<T> compute_histogram_basic(
404 const sham::DeviceScheduler_ptr &dev_sched,
405 const sham::DeviceBuffer<T> &bin_edge_inf,
406 const sham::DeviceBuffer<T> &bin_edge_sup,
407 const sham::DeviceBuffer<T> &positions) {
408
409 size_t element_count = positions.get_size();
410
411 return compute_histogram<T>(
412 dev_sched,
413 bin_edge_inf,
414 bin_edge_sup,
415 element_count,
416 [](const T &bin_edge_inf, const T &bin_edge_sup, const T &position, bool &has_value) {
417 has_value = position >= bin_edge_inf && position < bin_edge_sup;
418 return has_value ? 1 : 0;
419 },
420 positions);
421 }
422
423} // namespace shamalgs::primitives
Generic std::variant-based implementation selector.
std::uint32_t u32
32 bit unsigned integer
A buffer allocated in USM (Unified Shared Memory).
void copy_from_stdvec(const std::vector< T > &vec)
Copy the content of a std::vector into the buffer.
std::vector< T > copy_to_stdvec() const
Copy the content of the buffer to a std::vector.
size_t get_size() const
Gets the number of elements in the buffer.
Drop-in replacement for the hand-rolled "global variable + enum + name mapping.
This header file contains utility functions related to exception handling in the code.
Name-keyed registry of the implementation selectors (IImplVariant) of every algorithm.
void autoselect_impl(std::string_view alg, const sham::DeviceScheduler_ptr &sched)
Select the default implementation of alg for the device behind sched.
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.
namespace to control implementation behavior
shamalgs::ImplVariantGlobal< Reference, NaiveGpu, GpuTeamFetching, GpuOversubscribe > ComputeHistogramImpl
Implementation selector type for compute_histogram.
constexpr std::string_view compute_histogram_impl_name
Registry name, shared by its registration and the dispatch site(s).
ComputeHistogramImpl compute_histogram_impl
Implementation selector for compute_histogram (defined in compute_histogram.cpp).
namespace for primitive algorithm (e.g. sort, scan, reductions, ...)
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
A class that references multiple buffers or similar objects.
Definition MultiRef.hpp:33
GPU kernel oversubscribing a work-group per bin, reducing locally.
GPU kernel using a team-local cache to coalesce input reads.
Portable GPU kernel, one work-item per bin.
CPU reference implementation, computed on a host copy of the buffers.
Build an overload set out of several callables, for use with std::visit.