TNL::Algorithms::Sorting::CUBRadixSort Struct Reference

CUDA radix sort using CUB's DeviceRadixSort. More...

#include <TNL/Algorithms/Sorting/CUBRadixSort.h>

Static Public Member Functions
template<typename Array>
static void	sort (Array &array)
	Sort an array of arithmetic values into ascending order.

Detailed Description

CUDA radix sort using CUB's DeviceRadixSort.

This class provides a wrapper for radix sort implementation from NVIDIA's CUB library. It uses the cub::DeviceRadixSort::SortKeys algorithm which performs a stable radix sort on device-resident data.

Stability

Radix sort is a stable sorting algorithm.

Space requirements

This implementation requires additional storage:

• An auxiliary array of the same size ( \(N\)) as the input array to temporarily hold sorted output
• Temporary storage for CUB's internal operations ( \(O(N+P)\) where P is the number of streaming multiprocessors, typically a small constant)

The total memory overhead is approximately \(2N + P\).

Example

#include <iostream>
#include <TNL/Algorithms/Sorting/CUBRadixSort.h>
#include <TNL/Algorithms/fillRandom.h>
#include <TNL/Containers/Array.h>
#include <TNL/Devices/Cuda.h>
 
int
main( int argc, char* argv[] )
{
   const int size = 20;
 
   TNL::Containers::Array< int, TNL::Devices::Cuda > arr( size );
 
   /***
    * Fill the array with random integers.
    */
   TNL::Algorithms::fillRandom< TNL::Devices::Cuda >( arr.getData(), size, 0, 2 * size );
 
   std::cout << "Random array: " << arr << "\n";
 
   /***
    * Sort in ascending order.
    */
   TNL::Algorithms::Sorting::CUBRadixSort::sort( arr );
 
   std::cout << "Array sorted in ascending order: " << arr << "\n";
 
   return EXIT_SUCCESS;
}

Output

Random array: [ 35, 1, 38, 8, 13, 19, 4, 31, 24, 14, 3, 18, 40, 16, 25, 25, 6, 0, 26, 6 ]
Array sorted in ascending order: [ 0, 1, 3, 4, 6, 6, 8, 13, 14, 16, 18, 19, 24, 25, 25, 26, 31, 35, 38, 40 ]

See also

CUBMergeSort for a general merge sort alternative (for arbitrary types and comparison functors)

https://nvidia.github.io/cccl/unstable/cub/api/structcub_1_1DeviceRadixSort.html

Member Function Documentation

sort()

template<typename Array>

void TNL::Algorithms::Sorting::CUBRadixSort::sort ( Array & array )

inlinestatic

Sort an array of arithmetic values into ascending order.

Template Parameters

Array

is a type of container to be sorted. It must be TNL::Containers::Array or TNL::Containers::ArrayView with TNL::Devices::Cuda device type.

Parameters

array

The array to sort (will be modified in-place).

---

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

• src/TNL/Algorithms/Sorting/CUBRadixSort.h