26888

Onesweep: A Faster Least Significant Digit Radix Sort for GPUs

Andy Adinets, Duane Merrill
NVIDIA Corporation
arXiv:2206.01784 [cs.DC], (3 Jun 2022)

@misc{https://doi.org/10.48550/arxiv.2206.01784,

   doi={10.48550/ARXIV.2206.01784},

   url={https://arxiv.org/abs/2206.01784},

   author={Adinets, Andy and Merrill, Duane},

   keywords={Distributed, Parallel, and Cluster Computing (cs.DC), Data Structures and Algorithms (cs.DS), FOS: Computer and information sciences, FOS: Computer and information sciences, F.2.2; D.1.3},

   title={Onesweep: A Faster Least Significant Digit Radix Sort for GPUs},

   publisher={arXiv},

   year={2022},

   copyright={Creative Commons Attribution Non Commercial No Derivatives 4.0 International}

}

We present Onesweep, a least-significant digit (LSD) radix sorting algorithm for large GPU sorting problems residing in global memory. Our parallel algorithm employs a method of single-pass prefix sum that only requires ~2n global read/write operations for each digit-binning iteration. This exhibits a significant reduction in last-level memory traffic versus contemporary GPU radix sorting implementations, where each iteration of digit binning requires two passes through the dataset totaling ~3n global memory operations. On the NVIDIA A100 GPU, our approach achieves 29.4 GKey/s when sorting 256M random 32-bit keys. Compared to CUB, the current state-of-the-art GPU LSD radix sort, our approach provides a speedup of ~1.5x. For 32-bit keys with varied distributions, our approach provides more consistent performance compared to HRS, the current state-of-the-art GPU MSD radix sort, and outperforms it in almost all cases.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: