Analysis-driven Engineering of Comparison-based Sorting Algorithms on GPUs

Ben Karsin, Volker Weichert, Henri Casanova, John Iacono, Nodari Sitchinava
University of Hawaii at Manoa, USA
The 32nd ACM International Conference on Supercomputing (ICS), 2018


   title={Analysis-driven Engineering of Comparison-based Sorting Algorithms on GPUs},

   author={Karsin, Ben and Weichert, Volker and Casanova, Henri and Iacono, John and Sitchinava, Nodari}


Download Download (PDF)   View View   Source Source   



We study the relationship between memory accesses, bank conflicts, thread multiplicity (also known as over-subscription) and instruction-level parallelism in comparison-based sorting algorithms for Graphics Processing Units (GPUs). We experimentally validate a proposed formula that relates these parameters with asymptotic analysis of the number of memory accesses by an algorithm. Using this formula we analyze and compare several GPU sorting algorithms, identifying key performance bottlenecks in each one of them. Based on this analysis we propose a GPU-efficient multiway mergesort algorithm, GPU-MMS, which minimizes or eliminates these bottlenecks and balances various limiting factors for specific hardware. We realize an implementation of GPU-MMS and compare it to sorting algorithm implementations in state-of-the-art GPU libraries on three GPU architectures. Despite these library implementations being highly optimized, we find that GPU-MMS outperforms them by an average of 21% for random integer inputs and 14% for random key-value pairs
Rating: 3.0/5. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: