Source-linked AI summary
Shared-Memory Range-Tiled CDF Sort for Small-Range Integer Keys on GPUs
Kento Ando, Kaito Takase, Noriyuki Fujimoto, Koichi Wada
TL;DR
GPU sorting of integers in a known range motivates specialized unstable methods beyond general-purpose sorting. RT-CDF partitions the range into shared-memory tiles, builds local CDFs, and directly generates output; it outperforms baselines broadly for small to medium ranges, but larger ranges expose histogram-construction limits.
Problem
The paper studies how to sort integers from a known range on GPUs without preserving the relative order of equal values.
Method
RT-CDF partitions the value range into shared-memory tiles, constructs a histogram and local CDF for each tile, and directly generates the output array.
Results
RT-CDF outperforms the baselines over a broad set of conditions for small to medium ranges, with a maximum speedup of 4.39 over the fastest baseline.
Takeaways & Limitations
RT-CDF is effective for small to medium known integer ranges under the evaluated GPU sorting conditions.
Takeaways & Limitations
For R = 2^18, at least one baseline outperforms RT-CDF for every evaluated input size and distribution because histogram construction becomes dominant.
Abstract
from arXiv · showhide
We study unstable integer sorting on GPUs for arrays whose elements lie in a known integer range. Focusing on counting-sort-based methods that determine the output interval of each value from its frequency and the prefix sums of the frequencies, we propose and evaluate Range-Tiled CDF sort (RT-CDF), which partitions the possible value range into small intervals, called tiles, that fit in shared memory. For each tile, RT-CDF constructs a histogram, computes its prefix sum as a local CDF, and directly generates the output array from the local CDF. We compare RT-CDF against three baselines: CUB DeviceRadixSort, whose processed bit range is restricted to $[0,\lceil\log_2 R\rceil)$ to exploit the known range size $R$; Ref-H-P sort; and an implementation based on the algorithm of Kolonias et al. Experiments on an NVIDIA GeForce RTX 4090 with range sizes from $R=2^7$ to $2^{18}$, input sizes from $n=10^6$ to $10^9$, and uniformly distributed, normally distributed, and all-equal inputs show that RT-CDF outperforms the baselines over a broad set of conditions for small to medium ranges, achieving a maximum speedup of 4.39 over the fastest baseline. For $R=2^{18}$, however, at least one baseline outperforms RT-CDF for every evaluated input size and input distribution, showing that the cost of histogram construction limits the applicability of RT-CDF to larger ranges.
1 Introduction
The paper studies unstable GPU sorting for integers in a known range and proposes RT-CDF, which uses shared-memory range tiles and local CDFs to generate output intervals directly. Experiments compare RT-CDF with three GPU baselines across range sizes, input sizes, and distributions, finding broad advantages for small to medium ranges but limitations at larger ranges.
- Problem setting: Unstable sorting requires only nondecreasing output, so each value can be written across its contiguous output interval without preserving equal-value order.The intervals are determined from value frequencies and prefix sums.
- Contribution: RT-CDF partitions the possible integer range into small shared-memory tiles and constructs a histogram and CDF for each tile.The local CDF is the prefix sum of the tile histogram.
- Contribution: RT-CDF directly generates the output array from each tile’s local CDF without rescanning the input array.This distinguishes its output-generation procedure from approaches that reconstruct output using additional CDF-related processing.
- Evaluation: The evaluation compares RT-CDF with CUB DeviceRadixSort, RefHP, and an implementation based on Kolonias et al.CUB is configured to process only the bit range implied by the known range size.
- Evaluation: RT-CDF is reported as effective over identified small to medium range and input-size conditions, while its applicability is limited near R = 2^18.The paper explicitly treats the larger-range behavior as a limitation.
2 Background and Motivation
The background frames unstable range-restricted integer sorting as a counting-sort problem based on histograms and prefix sums. RT-CDF extends shared-memory histogramming with range tiling and uses local CDFs to assign output positions while addressing workload imbalance in prior output-generation strategies.
- Problem setting: The problem is to sort n integers from a known range [minVal, maxVal) into nondecreasing order without preserving equal-value order.The normalized range has size R = maxVal − minVal.
- Counting-sort foundations: Counting sort builds a histogram of value frequencies and uses prefix sums to determine each value’s output interval.For unstable sorting, writing values throughout their intervals avoids computing a separate rank for every input element.
- GPU considerations: GPU histogram updates can suffer atomic contention when many elements have identical values.The cited prior work reports that performance depends strongly on input distribution and value range.
- Prior methods: Kolonias et al. avoid synchronization by writing different values to disjoint output intervals, but assigning parallelism by value can imbalance work when counts vary.A value occurring in half the input may receive N/2 writes under that strategy.
- RT-CDF: RT-CDF partitions the range into shared-memory tiles, constructs a local CDF per tile, and determines output values from output positions.This extends shared-memory partial histograms and avoids assigning one processing unit to each value.
- Relation to H-P sort: H-P sort reconstructs sorted output from CDF boundary information, whereas RT-CDF retains only the relevant tile’s local CDF during output generation.RT-CDF therefore localizes the CDF rather than handling one CDF for the entire range.
3 Proposed Method: Range-Tiled CDF Sort
RT-CDF partitions the known value range into shared-memory tiles, builds a local CDF for each tile, and generates sorted output directly from those local CDFs. Its design avoids rescanning during output generation but incurs increasing histogram-scan overhead as the number of tiles grows.
- Algorithm overview: RT-CDF partitions the value range into tiles that fit in shared memory and constructs a local CDF for each tile.The algorithm then generates the output array from these local CDFs.
- Algorithm overview: The algorithm defines m = ⌈R/T⌉ tiles, with tile t covering [bt, bt + wt) where bt = tT and wt = min(T, R − bt).
- Histogram and CDF construction: Each tile histogram is accumulated in shared memory using atomic updates for input values belonging to that tile, then added to global memory.A block initializes S[0..w−1], scans the input, and updates S[A[i] − b] only for values in [b, b + w).
- Histogram and CDF construction: Prefix sums over each tile histogram produce local CDFs, whose final entries determine tile populations and whose prefix sums determine output offsets.Offsets are constructed in value order from the numbers of elements in preceding tiles.
- Output generation: Output generation binary-searches each local CDF to map within-tile positions to values and writes them at the tile’s global offset without rescanning the input.This replaces a prefix maximum over the entire output array with local-CDF processing in shared memory.
- Trade-offs: When the number of tiles is small, low launch and binary-search costs plus avoidance of a full-array prefix maximum provide a substantial advantage.Conversely, histogram construction scans the entire input once per tile, so data-read and scanning overhead increase with the number of tiles.
- Correctness and output organization: RT-CDF determines output intervals from local CDFs rather than computing the rank of every input element, using parallel processing over output positions.
- Correctness and output organization: The correctness argument establishes that local CDFs represent within-tile intervals, tile offsets position tiles globally, and output generation fills disjoint value-ordered intervals.
4 Experimental Evaluation
RT-CDF is fastest across broad conditions for small to medium ranges, but its advantage depends on range size and input size. At R = 2^18, baselines remain superior because histogram construction becomes costly.
- RT-CDF was fastest from R = 2^7 through 2^17 across all three input distributions.
- RT-CDF performance depended primarily on range size and only weakly on input distribution.
- At R = 2^10, RT-CDF was fastest in all 84 measured conditions across the three distributions.
- At R = 2^17, RT-CDF became fastest as input size increased, winning 53 of 84 conditions across the three distributions.
- At R = 2^18, RT-CDF was never fastest, while CUB or RefHP outperformed it throughout the measured input sizes.
- 4.39 was RT-CDF’s maximum observed speedup over the fastest baseline, occurring for all-equal inputs at R = 2^9 and n = 10^6.
5 Conclusion
RT-CDF partitions the value range into shared-memory tiles, builds a histogram and local CDF for each tile, and directly generates the sorted output. It outperformed baselines broadly for small to medium ranges, but histogram construction limited performance for larger ranges.
- Method: RT-CDF partitions the possible integer range into tiles that fit in shared memory.For each tile, it constructs a histogram and local CDF before generating output values.
- Method: RT-CDF uses each tile’s local CDF to determine values for output positions without computing a prefix maximum over the entire output array.This design directly generates the output array from the tile-local CDF.
- Results: RT-CDF outperformed the baselines over a broad set of conditions for small to medium ranges.The evaluation compared it with CUB DeviceRadixSort, RefHP, and an implementation based on Kolonias et al. across multiple ranges, input sizes, and distributions.
- Results: 4.39 was RT-CDF’s maximum speedup over the fastest baseline at R = 2^9 for all-equal input.The corresponding maxima were 3.70 for uniform inputs and 3.60 for normal inputs, both at n = 9 × 10^6.
- Results: At R = 2^17, CUB or RefHP was faster for small inputs, but RT-CDF became fastest for large inputs under all three distributions.At R = 2^18, RT-CDF was not fastest for any evaluated input size or distribution, placing the evaluated performance boundary between R = 2^17 and R = 2^18.
- Limitations: Histogram construction was the primary cause of performance degradation for large ranges.Scanning the entire input for every tile increases references as O(mn), while larger tiles increase shared-memory use, reduce resident blocks, and lower occupancy.
- Limitations: Reducing histogram-construction cost is the main challenge in extending RT-CDF to larger ranges.The paper also identifies adaptive output-generation selection and evaluation on other GPU architectures as future improvements or work.