Efficient top-K query processing on massively parallel hardware
File(s)
Published version
Author(s)
Shanbhag, Anil
Pirk, H
Madden, Sam
Type
Conference Paper
Abstract
A common operation in many data analytics workloads is to find
the top-k items, i.e., the largest or smallest operations according to
some sort order (implemented via LIMIT or ORDER BY expressions
in SQL). A naive implementation of top-k is to sort all of the items
and then return the first k, but this does much more work than
needed. Although efficient implementations for top-k have been
explored on traditional multi-core processors, there has been no
prior systematic study of top-k implementations on GPUs, despite
open requests for such implementations in GPU-based frameworks
like TensorFlow
1
and ArrayFire
2
. In this work, we present several
top-k algorithms for GPUs, including a new algorithm based on
bitonic sort called bitonic top-k. The bitonic top-k algorithm is up
to a factor of 15x faster than sort and 4x faster than a variety of
other possible implementations for values of k up to 256. We also
develop a cost model to predict the performance of several of our
algorithms, and show that it accurately predicts actual performance
on modern GPUs.
the top-k items, i.e., the largest or smallest operations according to
some sort order (implemented via LIMIT or ORDER BY expressions
in SQL). A naive implementation of top-k is to sort all of the items
and then return the first k, but this does much more work than
needed. Although efficient implementations for top-k have been
explored on traditional multi-core processors, there has been no
prior systematic study of top-k implementations on GPUs, despite
open requests for such implementations in GPU-based frameworks
like TensorFlow
1
and ArrayFire
2
. In this work, we present several
top-k algorithms for GPUs, including a new algorithm based on
bitonic sort called bitonic top-k. The bitonic top-k algorithm is up
to a factor of 15x faster than sort and 4x faster than a variety of
other possible implementations for values of k up to 256. We also
develop a cost model to predict the performance of several of our
algorithms, and show that it accurately predicts actual performance
on modern GPUs.
Date Issued
2018-05-27
Date Acceptance
2017-11-09
Citation
Proceedings of the ACM SIGMOD International Conference on Management of Data, 2018, pp.1557-1570
ISSN
0730-8078
Publisher
Association for Computing Machinery (ACM)
Start Page
1557
End Page
1570
Journal / Book Title
Proceedings of the ACM SIGMOD International Conference on Management of Data
Copyright Statement
© 2018 Association for Computing Machinery. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data, May 2018, Pages 1557–1570, https://doi.org/10.1145/3183713.3183735
Source
SIGMOD 2018
Subjects
Science & Technology
Technology
Computer Science, Information Systems
Computer Science
Top-K Algorithms for GPU
Bitonic Top-K
Publication Status
Published
Start Date
2018-06-10
Finish Date
2018-06-15
Coverage Spatial
Houston, TX, USA
Date Publish Online
2018-05-27