TY - GEN
T1 - Engineering a high-performance GPU B-tree
AU - Awad, Muhammad A.
AU - Ashkiani, Saman
AU - Johnson, Rob
AU - Farach-Colton, Martín
AU - Owens, John D.
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s).
PY - 2019/2/16
Y1 - 2019/2/16
N2 - We engineer a GPU implementation of a B-Tree that supports concurrent queries (point, range, and successor) and updates (insertions and deletions). Our B-tree outperforms the state of the art, a GPU log-structured merge tree (LSM) and a GPU sorted array. In particular, point and range queries are significantly faster than in a GPU LSM (the GPU LSM does not implement successor queries). Furthermore, B-Tree insertions are also faster than LSM and sorted array insertions unless insertions come in batches of more than roughly 100k. Because we cache the upper levels of the tree, we achieve lookup throughput that exceeds the DRAM bandwidth of the GPU. We demonstrate that the key limiter of performance on a GPU is contention and describe the design choices that allow us to achieve this high performance.
AB - We engineer a GPU implementation of a B-Tree that supports concurrent queries (point, range, and successor) and updates (insertions and deletions). Our B-tree outperforms the state of the art, a GPU log-structured merge tree (LSM) and a GPU sorted array. In particular, point and range queries are significantly faster than in a GPU LSM (the GPU LSM does not implement successor queries). Furthermore, B-Tree insertions are also faster than LSM and sorted array insertions unless insertions come in batches of more than roughly 100k. Because we cache the upper levels of the tree, we achieve lookup throughput that exceeds the DRAM bandwidth of the GPU. We demonstrate that the key limiter of performance on a GPU is contention and describe the design choices that allow us to achieve this high performance.
KW - B-tree
KW - Data structures
KW - Dynamic
KW - GPU
KW - Mutable
UR - http://www.scopus.com/inward/record.url?scp=85064230046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064230046&partnerID=8YFLogxK
U2 - 10.1145/3293883.3295706
DO - 10.1145/3293883.3295706
M3 - Conference contribution
AN - SCOPUS:85064230046
T3 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
SP - 145
EP - 157
BT - PPoPP 2019 - Proceedings of the 24th Principles and Practice of Parallel Programming
PB - Association for Computing Machinery
T2 - 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019
Y2 - 16 February 2019 through 20 February 2019
ER -