Sorts¶
RAJA provides portable parallel sort operations, which are basic parallel algorithm building blocks. They are described in this section.
A few important notes:
Note
- All RAJA sort operations are in the namespace
RAJA
. - Each RAJA sort operation is a template on an execution policy
parameter. The same policy types used for
RAJA::forall
methods may be used for RAJA sorts. - RAJA sort operations accept an optional comparator argument so users can perform different types of sort operations. If no operator is given, the default is a less than operation and the result is non-decreasing.
Also:
Note
- For sorts using the CUDA back-end, RAJA uses the implementations provided by the NVIDIA CUB library. For information please see build-external-tpl.
- For sorts using the HIP back-end, RAJA uses the implementations provided by the AMD rocPRIM library. For information please see build-external-tpl.
- The RAJA CUDA and HIP back-ends only support sorting arithmetic types using RAJA operators ‘less than’ and ‘greater than’.
Please see the Parallel Sort Operations tutorial section for usage examples of RAJA sort operations.
Sort Operations¶
In general, a sort operation takes a sequence of numbers x
and a binary
comparison operator op
that forms a strict weak ordering of elements in
input sequence x
and produces a sequence of numbers y
as output. The
output sequence is a permutation of the input sequence where each pair of
elements a
and b
, where a
is before b
in the output sequence,
satisfies !(b op a)
. Sorts are stable if they always preserve the order of
equivalent elements, where equivalent elements satisfy !(a op b) && !(b op a)
.
A stable sort takes an input sequence x
where ai appears
before aj if i < j when ai and aj are equivalent for
any i != j.
x = { a0, b0, a1, … }
and calculates the stably sorted output sequence y
that preserves the
order of equivalent elements. That is, the sorted sequence where element
ai appears before the equivalent element aj if i < j:
y = { a0, a1, b0, … }
An unstable sort may not preserve the order of equivalent elements and may produce either of the following output sequences:
y = { a0, a1, b0, … }
or
y = { a1, a0, b0, … }
RAJA Unstable Sorts¶
RAJA unstable sort operations look like the following:
RAJA::sort< exec_policy >(container)
RAJA::sort< exec_policy >(container, comparator)
For example, sorting an array with this sequence of values:
6 7 2 1 0 9 4 8 5 3 4 9 6 3 7 0 1 8 2 5
with a sequential unstable sort operation:
RAJA::sort<RAJA::seq_exec>(RAJA::make_span(out, N));
produces the out
array with this sequence of values:
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
Note that the syntax is essentially the same as Parallel Scan Operations.
Here, container
is a random access range of elements. container
provides
access to the input sequence and contains the output sequence at the end of
sort. The first sort operation listed above will be a non-decreasing sort
since there is no comparator argument given; i.e., the sequences will be
reordered in-place using operator::less. The second sort will apply the
comparator that is passed into the function. Note that the container argument
can be generated from iterators using RAJA::make_span(begin, len)
.
RAJA also provides sort operations that operate on key-value pairs stored separately:
RAJA::sort_pairs< exec_policy >(keys_container, vals_container)
RAJA::sort_pairs< exec_policy >(keys_container, vals_container, comparator)
RAJA::sort_pairs
methods generate the same output sequence of keys in
keys_container
as RAJA::sort
does in container
and reorders the
sequence of values in vals_container
by permuting the sequence of values in
the same manner as the sequence of keys; i.e. the sequence of pairs is sorted
based on comparing their keys.
Note
The comparator used in RAJA::sort_pairs
only compares keys.
RAJA Stable Sorts¶
RAJA stable sorts are essentially the same as unstable sorts:
RAJA::stable_sort< exec_policy >(container)
RAJA::stable_sort< exec_policy >(container, comparator)
RAJA also provides stable sort pairs that operate on key-value pairs stored separately:
RAJA::stable_sort_pairs< exec_policy >(keys_container, vals_container)
RAJA::stable_sort_pairs< exec_policy >(keys_container, vals_container, comparator)
RAJA Comparison Operators¶
RAJA provides two operators that can be used to produce different ordered sorts:
RAJA::operators::less<T>
RAJA::operators::greater<T>
Note
All RAJA comparison operators are in the namespace RAJA::operators
.