Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
sort_by_keys_lsd_radix_sort_basic.hpp File Reference

Portable LSD radix sort by keys, parallelized over chunks of the input. More...

#include "shambase/aliases_int.hpp"
#include "shambase/integer.hpp"
#include "shamalgs/primitives/scan_exclusive_sum_in_place.hpp"
#include "shambackends/DeviceBuffer.hpp"
#include "shambackends/kernel_call.hpp"
#include "shambackends/math.hpp"
#include <type_traits>
#include <algorithm>
#include <utility>
Include dependency graph for sort_by_keys_lsd_radix_sort_basic.hpp:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces

namespace  shamalgs
 namespace to contain everything implemented by shamalgs
namespace  shamalgs::primitives
 namespace for primitive algorithm (e.g. sort, scan, reductions, ...)

Functions

template<class Tkey, class Tval>
void shamalgs::primitives::device::details::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).

Detailed Description

Portable LSD radix sort by keys, parallelized over chunks of the input.

Author
Timothée David–Cléris (tim.s.nosp@m.hamr.nosp@m.ock@p.nosp@m.roto.nosp@m.n.me)

Each pass sorts on a digit of radix_bits bits :

  1. every work-item computes the digit histogram of its contiguous chunk of the input,
  2. an exclusive scan of the histograms (stored bucket major, i.e. index bucket * nchunks + chunk) gives the output offset of every (bucket, chunk) pair,
  3. every work-item scatters its chunk, in order, to those offsets.

The sort is stable. It only uses plain range kernels (no work-group primitives), so it runs on any SYCL backend. The chunking is tuned per device type (see below).

Definition in file sort_by_keys_lsd_radix_sort_basic.hpp.

Function Documentation

◆ sort_by_keys_lsd_radix_sort_basic()

template<class Tkey, class Tval>
void shamalgs::primitives::device::details::sort_by_keys_lsd_radix_sort_basic ( const sham::DeviceScheduler_ptr & sched,
sham::DeviceBuffer< Tkey > & buf_key,
sham::DeviceBuffer< Tval > & buf_values,
u32 len )
inline

Stable LSD radix sort of (keys, values) on the first len elements (unsigned keys only).

Definition at line 41 of file sort_by_keys_lsd_radix_sort_basic.hpp.

Here is the call graph for this function: