TY - GEN

T1 - Fast radix sort for sparse linear algebra on GPU

AU - Polok, Lukas

AU - Ila, Viorela

AU - Smrz, Pavel

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Matrix-matrix multiplication

KW - Parallel sorting

KW - Radix sort

KW - Sparse matrix

UR - http://www.scopus.com/inward/record.url?scp=84901836445&partnerID=8YFLogxK

M3 - Conference contribution

SN - 9781632662163

T3 - Simulation Series

SP - 79

EP - 86

BT - Proceedings of the 2014 Spring Simulation Multiconference, SpringSim 2014 - High Performance Computing Symposium, HPC 2014

PB - The Society for Modeling and Simulation International

T2 - 22nd High Performance Computing Symposium, HPC 2014, Part of the 2014 Summer Simulation Multiconference, SummerSim 2014

Y2 - 13 April 2014 through 16 April 2014

ER -