Fast Radix Sort for Sparse Linear Algebra on GPU

Lukas Polok, Viorela Ila, Pavel Smrz
Brno University of Technology, Faculty of Information Technology, Bozetechova 2, 612 66 Brno, Czech Republic
22nd High Performance Computing Symposia (HPC’14), 2014


   title={Fast radix sort for sparse linear algebra on GPU},

   author={Polok, Lukas and Ila, Viorela and Smrz, Pavel},

   booktitle={Proceedings of the High Performance Computing Symposium},



   organization={Society for Computer Simulation International}


Download Download (PDF)   View View   Source Source   



Fast sorting is an important step in many parallel algorithms, which require data ranking, ordering or partitioning. Parallel sorting is a widely researched subject, and many algorithms were developed in the past. In this paper, the focus is on implementing highly efficient sorting routines for the sparse linear algebra operations, such as parallel sparse matrix – matrix multiplication, or factorization. We propose a fast and simple to implement variant of parallel radix sort algorithm, suitable for GPU architecture. Extensive testing on both synthetic and real-world data shows, that our method outperforms other similar state-of-the-art implementations. Our implementation is bandwidth-efficient, as it achieves sorting rates comparable to the theoretical upper bound of memory bandwidth. We also present several interesting code optimizations relevant to GPU programming.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: