Sorting and Permuting without Bank Conflicts on GPUs

DOI10.1007/978-3-662-48350-3_2MaRDI QIDQ3452764zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Nodari Sitchinava

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.01391

Mathematics Subject Classification ID

Searching and sorting (68P10) Distributed algorithms (68W15) Randomized algorithms (68W20) Analysis of algorithms (68W40)

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(fracnwlogn)$ time. When $nge{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(fracnwlo{g}_{n/w}^{3}w)$ time. Finally, we solve the permutation problem using a randomized algorithm in $O(fracnwlogloglo{g}_{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.

Recommendations

• Parallel sorting for GPUs
• Fast parallel GPU-sorting using a hybrid algorithm
• Parallel bucket sorting on graphics processing units based on convex optimization

Cites work

• Cache-oblivious algorithms
• scientific article; zbMATH DE number 5764815 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Some Computer Organizations and Their Effectiveness
• Sorting and Permuting without Bank Conflicts on GPUs
• Uniform Hashing in Constant Time and Optimal Space

Cited in

(3)

• Sorting and Permuting without Bank Conflicts on GPUs
• Fast parallel GPU-sorting using a hybrid algorithm
• Algorithm design for tensor units

Describes a project that uses

Uses Software

• CUDA

This page was built for publication: Sorting and Permuting without Bank Conflicts on GPUs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452764)