shamalgs::algorithm::details::OddEvenOrderingPrimitive< Tkey, Tval > Struct Template Reference

Device side primitives of the odd-even merge network. More...

Static Public Member Functions
static void	compare_exchange (Tkey *__restrict__ keys, Tval *__restrict__ vals, u32 a, u32 b)
	Ascending branchless compare-exchange of the pair (a, b), with a < b.
static void	merge_step (Tkey *__restrict__ keys, Tval *__restrict__ vals, u64 len, u64 k, u64 j0, u32 log_k, u32 log_2p, u64 t)
	Work of a single thread within the (p, k) stage of the network.

Detailed Description

template<class Tkey, class Tval>
struct shamalgs::algorithm::details::OddEvenOrderingPrimitive< Tkey, Tval >

Device side primitives of the odd-even merge network.

Held as static members so that they can be called from within a device lambda.

Definition at line 33 of file batcherOddEvenSort.cpp.

Member Function Documentation

compare_exchange()

template<class Tkey, class Tval>

void shamalgs::algorithm::details::OddEvenOrderingPrimitive< Tkey, Tval >::compare_exchange ( Tkey *__restrict__ keys, Tval *__restrict__ vals, u32 a, u32 b )

inlinestatic

Ascending branchless compare-exchange of the pair (a, b), with a < b.

Definition at line 36 of file batcherOddEvenSort.cpp.

merge_step()

template<class Tkey, class Tval>

void shamalgs::algorithm::details::OddEvenOrderingPrimitive< Tkey, Tval >::merge_step ( Tkey *__restrict__ keys, Tval *__restrict__ vals, u64 len, u64 k, u64 j0, u32 log_k, u32 log_2p, u64 t )

inlinestatic

Work of a single thread within the (p, k) stage of the network.

p and k are powers of two with k dividing p, so the two innermost loops of the reference network collapse to the closed form below, made of shifts and masks only. Thread t owns the comparator whose low index is

x = (k mod p) + 2*k*(t / k) + (t mod k)

The two early returns are the guards of the reference network: x + k >= len drops the comparators that would have touched the +infinity padding of the power of two network, and the second one is the odd-even merge condition floor(x/2p) == floor((x+k)/2p).

Parameters

keys	Keys to sort by
vals	Values to reorder
len	Length of both arrays
k	Comparator distance of this stage
j0	Offset of the first comparator of this stage, k mod p
log_k	Base two logarithm of k
log_2p	Base two logarithm of 2*p
t	Index of the thread

Definition at line 75 of file batcherOddEvenSort.cpp.

Here is the call graph for this function:

---

The documentation for this struct was generated from the following file:

• shamalgs/src/details/algorithm/batcherOddEvenSort.cpp