Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
segmented_sort_in_place.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/assert.hpp"
24
25namespace shamalgs::primitives::details {
26
27 template<class T, class Comp>
28 inline void segmented_sort_in_place_local_insertion_sort(
29 sham::DeviceBuffer<T> &buf, const sham::DeviceBuffer<u32> &offsets, Comp &&comp) {
30
31 auto &q = buf.get_dev_scheduler().get_queue();
32
33 size_t interact_count = buf.get_size();
34 size_t offsets_count = offsets.get_size();
35 size_t N = offsets_count - 1;
36
38 q,
39 sham::MultiRef{offsets},
40 sham::MultiRef{buf},
41 N,
42 [interact_count,
43 comp](u32 gid, const u32 *__restrict__ offsets, T *__restrict__ in_out_sorted) {
44 u32 start_index = offsets[gid];
45 u32 end_index = offsets[gid + 1];
46
47 // can be equal if there is no interaction for this sender
48 SHAM_ASSERT(start_index <= end_index);
49
50 // skip empty ranges to avoid unnecessary work
51 if (start_index == end_index) {
52 return;
53 }
54
55 // if there is no interactions at the end of the offset list
56 // offsets[gid] can be equal to interact_count
57 // but we check that start_index != end_index, so here the correct assertions
58 // is indeed start_index < interact_count
59 SHAM_ASSERT(start_index < interact_count);
60 SHAM_ASSERT(end_index <= interact_count); // see the for loop for this one
61
62 shambase::ptr_insert_sort(in_out_sorted, start_index, end_index, comp);
63 });
64 }
65
66 template<class T, class Comp>
67 inline void segmented_sort_in_place_multi_std_sort(
68 sham::DeviceBuffer<T> &buf, const sham::DeviceBuffer<u32> &offsets, Comp &&comp) {
69
70 auto &q = buf.get_dev_scheduler().get_queue();
71
72 size_t interact_count = buf.get_size();
73 size_t offsets_count = offsets.get_size();
74 size_t N = offsets_count - 1;
75
76 std::vector<T> buf_stdvec = buf.copy_to_stdvec();
77 std::vector<u32> offsets_stdvec = offsets.copy_to_stdvec();
78
79#pragma omp parallel for
80 for (u32 i = 0; i < N; ++i) {
81 u32 start_index = offsets_stdvec[i];
82 u32 end_index = offsets_stdvec[i + 1];
83
84 // can be equal if there is no interaction for this sender
85 SHAM_ASSERT(start_index <= end_index);
86
87 // skip empty ranges to avoid unnecessary work
88 if (start_index == end_index) {
89 continue;
90 }
91
92 // if there is no interactions at the end of the offset list
93 // offsets[gid] can be equal to interact_count
94 // but we check that start_index != end_index, so here the correct assertions
95 // is indeed start_index < interact_count
96 SHAM_ASSERT(start_index < interact_count);
97 SHAM_ASSERT(end_index <= interact_count); // see the for loop for this one
98
99 std::sort(buf_stdvec.begin() + start_index, buf_stdvec.begin() + end_index, comp);
100 }
101
102 buf.copy_from_stdvec(buf_stdvec);
103 }
104
105} // namespace shamalgs::primitives::details
106
107namespace shamalgs::primitives {
108
110 namespace impl {
111
114 static constexpr std::string_view variant_type_name = "local_insertion_sort";
115 };
116
119 static constexpr std::string_view variant_type_name = "multi_std_sort";
120 };
121
123 constexpr std::string_view segmented_sort_in_place_impl_name = "segmented_sort_in_place";
124
126 [](const sham::DeviceScheduler_ptr &, auto &self) {
127 self.set(MultiStdSort{});
128 }};
129
130 // Must come after the global it registers: same TU, so it is initialized after it
131 SHAMALGS_REGISTER_IMPL(segmented_sort_in_place_impl_name, segmented_sort_in_place_impl);
132
133 } // namespace impl
134
135 template<class T, class Comp>
136 void internal_segmented_sort_in_place(
137 sham::DeviceBuffer<T> &buf, const sham::DeviceBuffer<u32> &offsets, Comp &&comp) {
138
139 if (buf.get_size() == 0) {
140 return;
141 }
142
143 if (offsets.get_size() == 0) {
144 throw shambase::make_except_with_loc<std::invalid_argument>("offsets buffer is empty");
145 }
146
147 if (!impl::segmented_sort_in_place_impl.is_set()) {
150 }
151
152 std::visit(
155 details::segmented_sort_in_place_local_insertion_sort(buf, offsets, comp);
156 },
157 [&](impl::MultiStdSort) {
158 details::segmented_sort_in_place_multi_std_sort(buf, offsets, comp);
159 },
160 },
161 impl::segmented_sort_in_place_impl.get());
162 }
163
164 template<>
165 void segmented_sort_in_place<u32_2>(
166 sham::DeviceBuffer<u32_2> &buf, const sham::DeviceBuffer<u32> &offsets) {
167
168 internal_segmented_sort_in_place(buf, offsets, [](u32_2 a, u32_2 b) {
169 return (a.x() == b.x()) ? (a.y() < b.y()) : (a.x() < b.x());
170 });
171 }
172
173 template<>
174 void segmented_sort_in_place<u32>(
175 sham::DeviceBuffer<u32> &buf, const sham::DeviceBuffer<u32> &offsets) {
176 internal_segmented_sort_in_place(buf, offsets, [](u32 a, u32 b) {
177 return a < b;
178 });
179 }
180
181} // namespace shamalgs::primitives
Generic std::variant-based implementation selector.
std::uint32_t u32
32 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 copy_from_stdvec(const std::vector< T > &vec)
Copy the content of a std::vector into the buffer.
std::shared_ptr< DeviceScheduler > & get_dev_scheduler_ptr()
Gets the Device scheduler pointer corresponding to the held allocation.
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.
DeviceScheduler & get_dev_scheduler() const
Gets the Device scheduler corresponding to the held allocation.
DeviceQueue & get_queue(u32 id=0)
Get a reference to a DeviceQueue.
Drop-in replacement for the hand-rolled "global variable + enum + name mapping.
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.
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
constexpr std::string_view segmented_sort_in_place_impl_name
Registry name, shared by its registration and the dispatch site(s).
namespace for primitive algorithm (e.g. sort, scan, reductions, ...)
void ptr_insert_sort(T *data, u32 start, u32 end, Comp &&comp)
Simple insertion sort on pointer range.
overloaded(Ts...) -> overloaded< Ts... >
Deduction guide so overloaded{lambda1, lambda2, ...} deduces Ts... from the lambdas.
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
Sort each segment locally with an insertion sort, one kernel work-item per segment.
Copy back to host and sort each segment with std::sort, parallelized over OpenMP.