Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Sorting and Permuting without Bank Conflicts on GPUs
verfasst von : Peyman Afshani, Nodari Sitchinava
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
≥
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} \log\log\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.