Provably Efficient GPU Algorithms

Nodari Sitchinava, Volker Weichert
Karlsruhe Institute of Technology, Karlsruhe, Germany
arXiv:1306.5076 [cs.DS], (21 Jun 2013)


   author={Sitchinava}, N. and {Weichert}, V.},

   title={"{Provably Efficient GPU Algorithms}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Data Structures and Algorithms, Computer Science – Distributed, Parallel, and Cluster Computing},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



In this paper we present an abstract model for algorithm design on GPUs by extending the parallel external memory (PEM) model with computations in internal memory (commonly known as shared memory in GPU literature) defined in the presence of memory banks and bank conflicts. We also present a framework for designing bank conflict free algorithms on GPUs. Using our framework we develop the first shared memory sorting algorithm that incurs no bank conflicts. Our sorting algorithm can be used as a subroutine for comparison-based GPU sorting algorithms to replace current use of sorting networks in shared memory. We show experimentally that such substitution improves the runtime of the mergesort implementation of the THRUST library.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: