29 const sham::DeviceScheduler_ptr &sched,
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]");
37 (
sizeof(Tkey) * 8) % radix_bits == 0,
"radix_bits must divide the bit size of Tkey");
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;
44 constexpr u32 group_size = 256;
45 constexpr u32 items_per_thread = 8;
46 constexpr u32 chunk_size = group_size * items_per_thread;
48 using atomic_ref_local = sycl::atomic_ref<
50 sycl::memory_order_relaxed,
51 sycl::memory_scope_work_group,
52 sycl::access::address_space::local_space>;
54 using atomic_ref_global = sycl::atomic_ref<
56 sycl::memory_order_relaxed,
57 sycl::memory_scope_device,
58 sycl::access::address_space::global_space>;
62 "the key buffer is smaller than the length of the histogram\n"
63 "len = {}, buf_key.get_size() = {}",
68 buf_hist.
resize(hist_size,
false);
78 u32 hist_groups = std::min<u32>(nchunks, 1024);
80 sham::kernel_call_hndl(
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};
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();
94 for (u32 b = lid; b < hist_size; b += group_size) {
97 item.barrier(sycl::access::fence_space::local_space);
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;
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])
113 item.barrier(sycl::access::fence_space::local_space);
115 for (u32 b = lid; b < hist_size; b += group_size) {
118 atomic_ref_global(hist[b]).fetch_add(cnt);
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.