## Sorting and Permuting without Bank Conflicts on GPUs

MADALGO, Aarhus University, Denmark

arXiv:1507.01391 [cs.DS], (6 Jul 2015)

@article{afshani2015sorting,

title={Sorting and Permuting without Bank Conflicts on GPUs},

author={Afshani, Peyman and Sitchinava, Nodari},

year={2015},

month={jul},

archivePrefix={"arXiv"},

primaryClass={cs.DS}

}

In this paper, we look at the complexity of designing algorithms without any bank conflicts in the shared memory of Graphical Processing Units (GPUs). Given input of size $n$, $w$ processors and $w$ memory banks, we study three fundamental problems: sorting, permuting and $w$-way partitioning (defined as sorting an input containing exactly $n/w$ copies of every integer in $[w]$). We solve sorting in optimal $O(frac{n}{w} log n)$ time. When $n ge w^2$, we solve the partitioning problem optimally in $O(n/w)$ time. We also present a general solution for the partitioning problem which takes $O(frac{n}{w} log^3_{n/w} w)$ time. Finally, we solve the permutation problem using a randomized algorithm in $O(frac{n}{w} logloglog_{n/w} n)$ time. Our results show evidence that when working with banked memory architectures, there is a separation between these problems and the permutation and partitioning problems are not as easy as simple parallel scanning.

July 8, 2015 by hgpu