High performance GPU concurrent B+tree
Open Access
- 28 March 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 443-444
Abstract
Concurrent B+trees have been widely used in many systems from file systems to databases. With the volume of data requests expanding exponentially, the systems are facing tremendous performance pressure. GPUs have shown their potential to accelerate the concurrent B+trees operations with their high volume of parallel computing resources and large memory bandwidth. In concurrent B+tree, the conflicts should be detected and resolved when multiple concurrent requests are traversing and operating on the tree. However, conflict detection and handling in concurrent B+tree complicates the request processing logic, increases the number of memory accesses and leads to execution path divergence. That leads to performance degradation and increased response time variance. We present a high performance GPU concurrent B+tree. To reduce the performance impact introduced by conflict detection, an optimization is proposed to detect and resolve key conflicts before concurrent requests are issued to the execution phase. Then another optimization is used to reduce structure conflicts and concurrent control overheads. Finally, an optimization is used to reduce structure conflicts and improve memory performance by exploiting the locality among requests. Evaluations on a TITAN V GPU show that our GPU concurrent B+tree is efficient with a throughput of 1.23 billion per second. Compared to a state-of-the-art GPU B+tree system, it can achieve 5.1X speedup and reduce the response time variance from 38% to 4%.Keywords
This publication has 11 references indexed in Scilit:
- A High Throughput B+tree for SIMD ArchitecturesIEEE Transactions on Parallel and Distributed Systems, 2019
- X-Engine2019
- pLock2019
- Harmonia2019
- Engineering a high-performance GPU B-Tree2019
- EunomiaACM SIGPLAN Notices, 2017
- Mega-KVProceedings of the VLDB Endowment, 2015
- Lightweight Software Transactions on GPUs2014
- Software Transactional Memory for GPU Architectures2014
- Benchmarking cloud serving systems with YCSB2010