Migrating the Odd-Even Merge Sort from CUDA* to SYCL*

Overview:

The Odd-Even Merge Sort sample demonstrates how to use the odd-even merge sort algorithm (also known as "Batcher's odd–even merge sort"). It belongs to the class of sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number of items to be sorted. Generally, this algorithm is not efficient for large sequences compared to algorithms with better asymptotic algorithmic complexity (merge sort or radix sort). However, this sort method may be the preferred algorithm for sorting batches of short-sized to mid-sized (key, value) array pairs. The original CUDA* source code is migrated to SYCL for portability across GPUs from multiple vendors.

Key Implementation Details

This sample demonstrates the migration of the following prominent CUDA features:

• Cooperative Groups
• Shared Memory

In this implementation, a random sequence of power of 2 elements is given as input, and the algorithm sorts the sequence in parallel. The algorithm sorts the first half of the list and second half of the list separately. The algorithm then sorts the odd-indexed entries and the even-indexed entries separately. You need make only one more comparison-switch per pair of keys to sort the list completely.

In this sample, the array length of 1048576 is the input size for the algorithm. The code checks for all the input sizes in the intervals of 2nd power of array lengths from 64 to 1048576 calculated for one iteration. The comparator swaps the value if top value is greater or equal to the bottom value.

Original CUDA source files: oddEvenMergeSort.

Migrated SYCL source files including step by step instructions: guided_oddEvenMergeSort_SYCLmigration.

References

• Data Parallel C++, by James Reinders et al
• oneAPI GPU Optimization Guide
• CUDA Toolkit documentation
• Install oneAPI for NVIDIA GPUs