117 0

Asymptotically Optimal Merging on ManyCore GPUs

Title
Asymptotically Optimal Merging on ManyCore GPUs
Author
KUTZNER ARNE HOLGER
Keywords
parallel algorithms; GPGPU; complexity; merging; sorting
Issue Date
2012-12
Publisher
Institute of Electronics, Information and Communication Engineers
Citation
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2012, 95(12), P.2769-2777
Abstract
We propose a family of algorithms for efficiently merging on contemporary GPUs, so that each algorithm requires O(m log(n/m + 1)) element comparisons, where m and n are the sizes of the input sequences with m <= n. According to the lower bounds for merging all proposed algorithms are asymptotically optimal regarding the number of necessary comparisons. First we introduce a parallely structured algorithm that splits a merging problem of size 2(l) into 2(i) subproblems of size 2(l-i), for some arbitrary i with (0 <= i <= l). This algorithm represents a merger for i = 1 but it is rather inefficient in this case. The efficiency is boosted by moving to a two stage approach where the splitting process stops at some predetermined level and transfers control to several parallely operating block-mergers. We formally prove the asymptotic optimality of the splitting process and show that for symmetrically sized inputs our approach delivers up to 4 times faster runtimes than the thrust: :merge function that is part of the Thrust library. For assessing the value of our merging technique in the context of sorting we construct and evaluate a MergeSort on top of it. In the context of our benchmarking the resulting MergeSort clearly outperforms the MergeSort implementation provided by the Thrust library as well as Cederman's GPU optimized variant of QuickSort.
URI
https://www.jstage.jst.go.jp/article/transinf/E95.D/12/E95.D_2769/_articlehttp://hdl.handle.net/20.500.11754/48466
ISSN
0916-8532
DOI
10.1587/transinf.E95.D.2769
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > INFORMATION SYSTEMS(정보시스템학과) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE