batcherOddEvenSort.hpp File Reference

Batcher odd-even mergesort, native for any length. More...

#include "shambackends/DeviceBuffer.hpp"
#include "shambackends/DeviceQueue.hpp"
#include "shambackends/sycl.hpp"
#include "shambackends/typeAliasVec.hpp"
#include <vector>

Include dependency graph for batcherOddEvenSort.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::algorithm
	namespace to store algorithms implemented by shamalgs
namespace	shamalgs::algorithm::details
	namespace to store algorithms implemented by shamalgs

Functions
template<class Tkey, class Tval>
void	shamalgs::algorithm::details::sort_by_key_batcher_odd_even (const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
	Sort key-value pairs of any length using a Batcher odd-even merge network.
template<class Tkey, class Tval>
void	shamalgs::algorithm::details::sort_by_key_batcher_odd_even_host_reference (std::vector< Tkey > &keys, std::vector< Tval > &values)
	Host reference of sort_by_key_batcher_odd_even.

Detailed Description

Batcher odd-even mergesort, native for any length.

Author

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

The bitonic sorting networks of bitonicSort*.hpp only exist for lengths that are powers of two, which forces every caller to round its arrays up to roundup_pow2(len) and to pad the tail with a sentinel greater than every key.

Batcher's odd-even mergesort has no such restriction: all of its comparators are ascending (there is no bitonic direction flag), so truncating the network to the comparators that stay inside [0, len) is exactly equivalent to running the power of two network on an array padded with +infinity, every dropped comparator being a no-op on such an array. The implementations here therefore sort any length in place, with no padding and no scratch allocation.

The network is

for p = 1, 2, 4, ... while p < n
  for k = p, p/2, ... while k >= 1
    for j = k mod p to n-1-k step 2k
      for i = 0 to min(k-1, n-j-k-1)
        if floor((i+j)/2p) == floor((i+j+k)/2p)
          compare_exchange(a[i+j], a[i+j+k])

Definition in file batcherOddEvenSort.hpp.