Two Algorithms for Sorting On Heterogeneous Clusters

Kyle Spafford, Jeremy Meredith, Jeffrey Vetter, Aparna Chandramowlishwaran, David Noble, Richard Vuduc
Future Technologies Group, Oak Ridge National Laboratory
Future Technologies Group, 2012


   title={Two Algorithms for Sorting On Heterogeneous Clusters},

   author={Spafford, K. and Meredith, J. and Vetter, J. and Chandramowlishwaran, A. and Noble, D. and Vuduc, R.},



Download Download (PDF)   View View   Source Source   



In the past few years, performance improvements in CPUs and memory technologies have outpaced those of storage systems. When extrapolated to the exascale, this trend places strict limits on the amount of data that can be written to disk for full analysis, resulting in an increased reliance on characterizing in-memory data. Many of these characterizations are simple, but require sorted data. This paper explores variations on two classic algorithms for distributed sorting-radix and sample sort – under two novel constraints imposed by the projected requirements of an exascale machine, heterogeneity and limited external storage. The two approaches are evaluated on the GPU-based NSF Keeneland system, including an analysis of data movement and the effects of GPUs on performance and scalability. Results from Keeneland indicate a substantial performance advantage for sample-based approaches on some data distributions, but this advantage comes at the cost of randomized behavior and load imbalance.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: