Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
digit_histogram.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#include "shambase/integer.hpp"
21#include "shambackends/sycl.hpp"
22#include <type_traits>
23#include <algorithm>
24
25namespace shamalgs::primitives {
26
27 template<class Tkey, u32 radix_bits>
29 const sham::DeviceScheduler_ptr &sched,
30 const sham::DeviceBuffer<Tkey> &buf_key,
32 u32 len) {
33
34 static_assert(std::is_unsigned_v<Tkey>, "the digit histogram requires unsigned keys");
35 static_assert(radix_bits >= 1 && radix_bits <= 8, "radix_bits must be in [1, 8]");
36 static_assert(
37 (sizeof(Tkey) * 8) % radix_bits == 0, "radix_bits must divide the bit size of Tkey");
38
39 constexpr u32 nbuckets = 1u << radix_bits;
40 constexpr u32 digit_mask = nbuckets - 1;
41 constexpr u32 npasses = (sizeof(Tkey) * 8) / radix_bits;
42 constexpr u32 hist_size = npasses * nbuckets;
43
44 constexpr u32 group_size = 256;
45 constexpr u32 items_per_thread = 8;
46 constexpr u32 chunk_size = group_size * items_per_thread;
47
48 using atomic_ref_local = sycl::atomic_ref<
49 u32,
50 sycl::memory_order_relaxed,
51 sycl::memory_scope_work_group,
52 sycl::access::address_space::local_space>;
53
54 using atomic_ref_global = sycl::atomic_ref<
55 u32,
56 sycl::memory_order_relaxed,
57 sycl::memory_scope_device,
58 sycl::access::address_space::global_space>;
59
60 if (len > buf_key.get_size()) {
62 "the key buffer is smaller than the length of the histogram\n"
63 "len = {}, buf_key.get_size() = {}",
64 len,
65 buf_key.get_size()));
66 }
67
68 buf_hist.resize(hist_size, false);
69 buf_hist.fill(0);
70
71 if (len == 0) {
72 return;
73 }
74
75 u32 nchunks = shambase::group_count(len, chunk_size);
76
77 // enough groups to fill the device, while bounding the number of global atomics
78 u32 hist_groups = std::min<u32>(nchunks, 1024);
79
80 sham::kernel_call_hndl(
81 sched->get_queue(),
82 sham::MultiRef{buf_key},
83 sham::MultiRef{buf_hist},
84 hist_groups * group_size,
85 [=](u32 nthreads, const Tkey *__restrict keys, u32 *__restrict hist) {
86 return [=](sycl::handler &cgh) {
87 sycl::local_accessor<u32, 1> l_hist{hist_size, cgh};
88
89 cgh.parallel_for(
90 sycl::nd_range<1>{nthreads, group_size}, [=](sycl::nd_item<1> item) {
91 u32 lid = item.get_local_id(0);
92 u32 group = item.get_group_linear_id();
93
94 for (u32 b = lid; b < hist_size; b += group_size) {
95 l_hist[b] = 0;
96 }
97 item.barrier(sycl::access::fence_space::local_space);
98
99 // grid-stride over the chunks, coalesced reads within a chunk
100 for (u32 c = group; c < nchunks; c += hist_groups) {
101 for (u32 j = 0; j < items_per_thread; j++) {
102 u32 i = c * chunk_size + j * group_size + lid;
103 if (i < len) {
104 Tkey k = keys[i];
105 for (u32 p = 0; p < npasses; p++) {
106 u32 digit = u32(k >> (p * radix_bits)) & digit_mask;
107 atomic_ref_local(l_hist[p * nbuckets + digit])
108 .fetch_add(1U);
109 }
110 }
111 }
112 }
113 item.barrier(sycl::access::fence_space::local_space);
114
115 for (u32 b = lid; b < hist_size; b += group_size) {
116 u32 cnt = l_hist[b];
117 if (cnt > 0) {
118 atomic_ref_global(hist[b]).fetch_add(cnt);
119 }
120 }
121 });
122 };
123 });
124 }
125
126 template<class Tkey, u32 radix_bits>
128 const sham::DeviceScheduler_ptr &sched,
129 const sham::DeviceBuffer<Tkey> &buf_key,
130 sham::DeviceBuffer<u32> &buf_hist) {
132 sched, buf_key, buf_hist, shambase::narrow_or_throw<u32>(buf_key.get_size()));
133 }
134
135#define X(Tkey, radix_bits) \
136 template void digit_histogram<Tkey, radix_bits>( \
137 const sham::DeviceScheduler_ptr &sched, \
138 const sham::DeviceBuffer<Tkey> &buf_key, \
139 sham::DeviceBuffer<u32> &buf_hist, \
140 u32 len); \
141 template void digit_histogram<Tkey, radix_bits>( \
142 const sham::DeviceScheduler_ptr &sched, \
143 const sham::DeviceBuffer<Tkey> &buf_key, \
144 sham::DeviceBuffer<u32> &buf_hist);
145
146 X(u32, 1)
147 X(u32, 2)
148 X(u32, 4)
149 X(u32, 8)
150 X(u64, 1)
151 X(u64, 2)
152 X(u64, 4)
153 X(u64, 8)
154
155#undef X
156
157} // namespace shamalgs::primitives
std::uint32_t u32
32 bit unsigned integer
std::uint64_t u64
64 bit unsigned integer
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.
size_t get_size() const
Gets the number of elements in the buffer.
Histograms of every radix digit place of a key buffer, in a single read of the keys.
This header file contains utility functions related to exception handling in the code.
namespace for primitive algorithm (e.g. sort, scan, reductions, ...)
void digit_histogram(const sham::DeviceScheduler_ptr &sched, const sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< u32 > &buf_hist, u32 len)
Compute the histograms of all the digit places of the first len keys.
constexpr u32 group_count(u32 len, u32 group_size)
Calculates the number of groups based on the length and group size.
Definition integer.hpp:125
void throw_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Throw an exception and append the source location to it.
Utilities for safe type narrowing conversions.
#define X
Temp definition for the X macro call to define the log levels.
Definition logs.hpp:131
A class that references multiple buffers or similar objects.
Definition MultiRef.hpp:33