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.
%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
}