Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
sort_by_key_pow2_len.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
16
26
28
31 enum class MaxStencilSize : u32 {
32 // Size2 = 2,
33 // Size4 = 4,
34 // Size8 = 8,
35 Size16 = 16,
36 Size32 = 32,
37 };
38
40 struct BitonicSort {
41 static constexpr std::string_view variant_type_name = "bitonic_sort";
42 MaxStencilSize stencil_size = MaxStencilSize::Size16;
43
45 static std::vector<BitonicSort> variant_custom_defaults() {
46 return {
47 // BitonicSort{MaxStencilSize::Size8},
48 BitonicSort{MaxStencilSize::Size16},
49 BitonicSort{MaxStencilSize::Size32},
50 };
51 }
52 };
53
55 struct StdSort {
56 static constexpr std::string_view variant_type_name = "std_sort";
57 };
58
62 static constexpr std::string_view variant_type_name = "lsd_radix_sort_basic";
63 };
64
65} // namespace shamalgs::primitives::impl
66
67template<>
69 static nlohmann::json to_json(const shamalgs::primitives::impl::BitonicSort &p) {
70 return {{"stencil_size", static_cast<u32>(p.stencil_size)}};
71 }
72 static shamalgs::primitives::impl::BitonicSort from_json(const nlohmann::json &j) {
74 if (j.contains("stencil_size")) {
75 p.stencil_size = static_cast<shamalgs::primitives::impl::MaxStencilSize>(
76 j.at("stencil_size").get<u32>());
77 }
78 return p;
79 }
80};
81
82namespace shamalgs::primitives {
83
84 template<class Tkey, class Tval>
86 sycl::queue &q, sycl::buffer<Tkey> &buf_key, sycl::buffer<Tval> &buf_values, u32 len) {
87
88 if (!shambase::is_pow_of_two(len)) {
90 "Length must be a power of 2");
91 }
92
93 if (len < 5e3) {
94 shamalgs::algorithm::details::sort_by_key_bitonic_fallback(q, buf_key, buf_values, len);
95 } else {
96 shamalgs::algorithm::details::sort_by_key_bitonic_updated<Tkey, Tval, 16>(
97 q, buf_key, buf_values, len);
98 }
99 }
100
102 namespace impl {
103
105 constexpr std::string_view sort_by_key_pow2_len_impl_name = "sort_by_key_pow2_len";
106
108 sort_by_key_pow2_len_impl{[](const sham::DeviceScheduler_ptr &dev_sched, auto &self) {
109 if (dev_sched->ctx->device->prop.type == sham::DeviceType::GPU) {
110 self.set(BitonicSort{});
111 } else {
112 self.set(LsdRadixSortBasic{});
113 }
114 }};
115
116 // Must come after the global it registers: same TU, so it is initialized after it
117 SHAMALGS_REGISTER_IMPL(sort_by_key_pow2_len_impl_name, sort_by_key_pow2_len_impl);
118
121 template<class Tkey, class Tval>
123 const sham::DeviceScheduler_ptr &sched,
125 sham::DeviceBuffer<Tval> &buf_values,
126 u32 len,
127 MaxStencilSize stencil_size) {
128
129 switch (stencil_size) {
130 // case MaxStencilSize::Size2:
131 // shamalgs::algorithm::details::sort_by_key_bitonic_updated_usm<Tkey, Tval, 2>(
132 // sched, buf_key, buf_values, len);
133 // return;
134 // case MaxStencilSize::Size4:
135 // shamalgs::algorithm::details::sort_by_key_bitonic_updated_usm<Tkey, Tval, 4>(
136 // sched, buf_key, buf_values, len);
137 // return;
138 // case MaxStencilSize::Size8:
139 // shamalgs::algorithm::details::sort_by_key_bitonic_updated_usm<Tkey, Tval, 8>(
140 // sched, buf_key, buf_values, len);
141 // return;
142 case MaxStencilSize::Size16:
143 shamalgs::algorithm::details::sort_by_key_bitonic_updated_usm<Tkey, Tval, 16>(
144 sched, buf_key, buf_values, len);
145 return;
146 case MaxStencilSize::Size32:
147 shamalgs::algorithm::details::sort_by_key_bitonic_updated_usm<Tkey, Tval, 32>(
148 sched, buf_key, buf_values, len);
149 return;
150 }
151
152 throw shambase::make_except_with_loc<std::invalid_argument>("invalid MaxStencilSize");
153 }
154
155 } // namespace impl
156
157 template<class Tkey, class Tval>
159 const sham::DeviceScheduler_ptr &sched,
161 sham::DeviceBuffer<Tval> &buf_values,
162 u32 len) {
163
164 if (!shambase::is_pow_of_two(len)) {
166 "Length must be a power of 2");
167 }
168
169 if (!impl::sort_by_key_pow2_len_impl.is_set()) {
171 }
172
173 std::visit(
175 [&](impl::BitonicSort cfg) {
177 sched, buf_key, buf_values, len, cfg.stencil_size);
178 },
179 [&](impl::StdSort) {
180 device::details::sort_by_keys_std_sort(buf_key, buf_values, len);
181 },
183 if constexpr (std::is_unsigned_v<Tkey>) {
185 sched, buf_key, buf_values, len);
186 } else {
188 sched, buf_key, buf_values, len, impl::MaxStencilSize::Size16);
189 }
190 },
191 },
192 impl::sort_by_key_pow2_len_impl.get());
193 }
194
195 template void sort_by_key_pow2_len(
196 sycl::queue &q, sycl::buffer<u32> &buf_key, sycl::buffer<u32> &buf_values, u32 len);
197
198 template void sort_by_key_pow2_len(
199 sycl::queue &q, sycl::buffer<u64> &buf_key, sycl::buffer<u32> &buf_values, u32 len);
200
201 template void sort_by_key_pow2_len(
202 const sham::DeviceScheduler_ptr &sched,
204 sham::DeviceBuffer<u32> &buf_values,
205 u32 len);
206
207 template void sort_by_key_pow2_len(
208 const sham::DeviceScheduler_ptr &sched,
210 sham::DeviceBuffer<u32> &buf_values,
211 u32 len);
212
213 template void sort_by_key_pow2_len(
214 const sham::DeviceScheduler_ptr &sched,
216 sham::DeviceBuffer<f64> &buf_values,
217 u32 len);
218
219 template void sort_by_key_pow2_len(
220 const sham::DeviceScheduler_ptr &sched,
222 sham::DeviceBuffer<f32> &buf_values,
223 u32 len);
224
225} // namespace shamalgs::primitives
Generic std::variant-based implementation selector.
std::uint32_t u32
32 bit unsigned integer
main include file for the shamalgs algorithms
A buffer allocated in USM (Unified Shared Memory).
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.
#define SHAMALGS_REGISTER_IMPL(name, impl)
Register the implementation selector impl under name at static initialization.
void autoselect_impl(std::string_view alg, const sham::DeviceScheduler_ptr &sched)
Select the default implementation of alg for the device behind sched.
namespace to control implementation behavior
void sort_by_key_pow2_len_bitonic_dispatch(const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len, MaxStencilSize stencil_size)
constexpr std::string_view sort_by_key_pow2_len_impl_name
Registry name, shared by its registration and the dispatch site(s).
namespace for primitive algorithm (e.g. sort, scan, reductions, ...)
void sort_by_key_pow2_len(sycl::queue &q, sycl::buffer< Tkey > &buf_key, sycl::buffer< Tval > &buf_values, u32 len)
Sort key-value pairs using sycl::buffers (power-of-2 optimized).
namespace to contain everything implemented by shamalgs
Definition algorithm.hpp:21
constexpr bool is_pow_of_two(T v) noexcept
determine if v is a power of two and check if v==0 Source : https://graphics.stanford....
Definition integer.hpp:49
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
Sort by keys algorithms.
Portable LSD radix sort by keys, parallelized over chunks of the input.
void sort_by_keys_lsd_radix_sort_basic(const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Stable LSD radix sort of (keys, values) on the first len elements (unsigned keys only).
std::sort based sort by keys implementation, shared by the sort by keys primitives
void sort_by_keys_std_sort(sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Copy both buffers to host, std::sort the zipped key/value pairs, and copy back.
Customization point controlling how an alternative's fields (if any) are serialized to / parsed from ...
static Alt from_json(const nlohmann::json &)
Parse the alternative's fields back (default: no fields, ignored).
static nlohmann::json to_json(const Alt &)
Serialize the alternative's fields (default: no fields, empty object).
Bitonic sort, updated USM kernel (see bitonicSort_updated_usm.hpp).
static std::vector< BitonicSort > variant_custom_defaults()
Expose the stencil sizes worth benchmarking as separate default implementations.
Copy the buffers to host, std::sort the zipped key/value pairs, and copy back.
Build an overload set out of several callables, for use with std::visit.