Efficient Algorithms for Sorting on GPUs

Seema M. Munavalli
University of Connecticut
University of Connecticut, 2012


   title={Efficient Algorithms for Sorting on GPUs},

   author={Munavalli, S.M.},



Download Download (PDF)   View View   Source Source   



Sorting is an important problem in computing that has a rich history of investigation by various researchers. In this thesis we focus on this vital problem. In particular, we develop a novel algorithm for sorting on Graphics Processing Units (GPUs). GPUs are multicore architectures that offer the potential of affordable parallelism. We present an efficient sorting algorithm called Fine Sample Sort (FSS). Our FSS algorithm extends and outperforms sample sort algorithm presented by Leischner[2], which is currently the fastest known comparison based algorithm on GPUs. The performance gain of FSS is mainly achieved due to the quality of the samples selected. By quantitative and empirical approach, we found out the best way to select the samples, which resulted in an efficient sorting algorithm. We carried out the experiment for different input distributions, and found out that FSS outperforms sample sort by at least 26% and on an average by 37% for data sizes ranging from 40 million and above across various input distributions.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: