PPoPP 2019
Sat 16 - Wed 20 February 2019 Washington, DC, United States
Mon 18 Feb 2019 16:35 - 17:00 at Salon 12/13 - Session 4: GPU B-Trees Chair(s): Ang Li

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.

Mon 18 Feb

Displayed time zone: Guadalajara, Mexico City, Monterrey change

16:10 - 17:00
Session 4: GPU B-TreesMain Conference at Salon 12/13
Chair(s): Ang Li Pacific Northwest National Laboratory
16:10
25m
Talk
Harmonia: A High Throughput B+tree for GPUs
Main Conference
Zhaofeng Yan Fudan University, Yuzhe Lin Fudan University, Lu Peng , Weihua Zhang Fudan University
DOI
16:35
25m
Talk
Engineering a High-Performance GPU B-Tree
Main Conference
Muhammad Awad , Saman Ashkiani University of California, Davis, Rob Johnson VMWare Research, Martin Farach-Colton Rutgers University, John D. Owens University of California, Davis
DOI