25namespace shamalgs::primitives::details {
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) {
33 size_t interact_count = buf.
get_size();
34 size_t offsets_count = offsets.
get_size();
35 size_t N = offsets_count - 1;
39 sham::MultiRef{offsets},
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];
51 if (start_index == end_index) {
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) {
72 size_t interact_count = buf.
get_size();
73 size_t offsets_count = offsets.
get_size();
74 size_t N = offsets_count - 1;
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];
88 if (start_index == end_index) {
99 std::sort(buf_stdvec.begin() + start_index, buf_stdvec.begin() + end_index, comp);
114 static constexpr std::string_view variant_type_name =
"local_insertion_sort";
119 static constexpr std::string_view variant_type_name =
"multi_std_sort";
126 [](
const sham::DeviceScheduler_ptr &,
auto &self) {
135 template<
class T,
class Comp>
136 void internal_segmented_sort_in_place(
147 if (!impl::segmented_sort_in_place_impl.is_set()) {
155 details::segmented_sort_in_place_local_insertion_sort(buf, offsets, comp);
158 details::segmented_sort_in_place_multi_std_sort(buf, offsets, comp);
161 impl::segmented_sort_in_place_impl.get());
165 void segmented_sort_in_place<u32_2>(
166 sham::DeviceBuffer<u32_2> &buf,
const sham::DeviceBuffer<u32> &offsets) {
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());
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) {
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.
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.