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’ 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.
  • The RAJA CUDA back-end implementation only supports sorting arithmetic types using RAJA operators less and greater.

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 equivalent elements ai and aj for any i != j where ai appears before aj if i < j

x = { a0, b0, a1, … }

and calculates the stably sorted output sequence y which preserves the order of equivalent elements, in other words 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)
  • RAJA::sort< exec_policy >(iter, iter + N)
  • RAJA::sort< exec_policy >(iter, iter + N, comparator)

For example sorting the in array filled 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

by performing a sequential unstable sort operation using the following code:

  RAJA::sort<RAJA::seq_exec>(out, out + N);

fills 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 range of elements and iter is a random access iterator to a range of elements. container and iter provide access to the input sequence and contain the output sequence at the end of sort. The first and third sort operations above will be non-decreasing sorts since there is no comparator argument given; i.e., the sequences will be reordered in-place using operator::less. The second and fourth sorts will apply the comparator that is passed into the function.

RAJA also provides sort pairs 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< exec_policy >(keys_iter, keys_iter + N, vals_iter)
  • RAJA::sort_pairs< exec_policy >(keys_iter, keys_iter + N, vals_iter, comparator)

Sort pairs generates the same output sequence of keys in keys_container or keys_iter as sort does in container or iter and also reorders the sequence of values in vals_container or vals_iter by permuting the sequence of values in the same manner as the sequence of keys; i.e. sorting the sequence of pairs based on their keys. Note that the comparator used in sort_pairs only compares keys.

RAJA Stable Sorts

Using RAJA stable sorts is essentially the same as unstable sorts:

  • RAJA::stable_sort< exec_policy >(container)
  • RAJA::stable_sort< exec_policy >(container, comparator)
  • RAJA::stable_sort< exec_policy >(iter, iter + N)
  • RAJA::stable_sort< exec_policy >(iter, iter + N, 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::stable_sort_pairs< exec_policy >(keys_iter, keys_iter + N, vals_iter)
  • RAJA::stable_sort_pairs< exec_policy >(keys_iter, keys_iter + N, vals_iter, 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.

Sort Policies

For information about RAJA execution policies to use with sort operations, please see Policies.