Engineering a high-performance GPU B-Tree
Engineering a high-performance GPU B-Tree
复制标题
DOI：
10.1145/3293883.3295706
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Muhammad A. Awad;Saman Ashkiani;Rob Johnson;Martín Farach-Colton;John Douglas Owens
中科院分区：
文献类型：
--
作者：
Muhammad A. Awad;Saman Ashkiani;Rob Johnson;Martín Farach-Colton;John Douglas Owens
我们设计了一个支持并发查询(点、范围和后续)和更新(插入和删除)的B树的GPU实现。我们的B-树的性能优于最先进的GPU日志结构合并树(LSM)和GPU排序数组。特别是，点和范围查询比在GPU LSM中要快得多(GPU LSM不实现后续查询)。此外，B-Tree插入也比LSM和排序数组插入更快，除非插入是以大约100k以上的批量进行的。因为我们缓存树的较高级别，所以我们实现了超过GPU的DRAM带宽的查找吞吐量。我们论证了GPU性能的关键限制因素是争用，并描述了使我们能够实现这种高性能的设计选择。
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.