%0 Journal Article %1 Afshani2015-rr %A Afshani, Peyman %A Sitchinava, Nodari %D 2015 %K To_Read_3 %T Sorting and Permuting without Bank Conflicts on GPUs %X 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(\textbackslashfrac\n\\w\ \textbackslashlog n)$ time. When $n \textbackslashge 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(\textbackslashfrac\n\\w\ \textbackslashlog^3_\n/w\ w)$ time. Finally, we solve the permutation problem using a randomized algorithm in $O(\textbackslashfrac\n\\w\ \textbackslashlog\textbackslashlog\textbackslashlog_\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.

@article{Afshani2015-rr, abstract = {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(\textbackslash{}frac\{n\}\{w\} \textbackslash{}log n)$ time. When $n \textbackslash{}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(\textbackslash{}frac\{n\}\{w\} \textbackslash{}log^3_\{n/w\} w)$ time. Finally, we solve the permutation problem using a randomized algorithm in $O(\textbackslash{}frac\{n\}\{w\} \textbackslash{}log\textbackslash{}log\textbackslash{}log_\{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.}, added-at = {2015-07-09T00:08:38.000+0200}, archiveprefix = {arXiv}, author = {Afshani, Peyman and Sitchinava, Nodari}, biburl = {https://www.bibsonomy.org/bibtex/2c996451d218e8fe94ab957d4f818b929/christophv}, eprint = {1507.01391}, interhash = {558ce3dd3cf3414cecf571589564c3c5}, intrahash = {c996451d218e8fe94ab957d4f818b929}, keywords = {To_Read_3}, primaryclass = {cs.DS}, timestamp = {2015-09-11T11:20:46.000+0200}, title = {Sorting and Permuting without Bank Conflicts on {GPUs}}, year = 2015 }