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

B+tree is one of the most important data structures and has been widely used in different fields. With the increase of concurrent queries and data-scale in storage, designing an efficient B+tree structure has become critical. Due to abundant computation resources, GPUs provide potential opportunities to achieve high query throughput for B+tree. However, prior methods cannot achieve satisfactory performance results due to low resource utilization and poor memory performance.

In this paper, we first identify the gaps between B+tree and GPUs. Concurrent B+tree queries involve many global memory accesses and different divergences, which mismatch with GPU features. Based on this observation, we propose Harmonia, a novel B+tree structure to bridge the gap. In Harmonia, a B+tree structure is divided into a key region and a child region. The key region stores the nodes with its keys in a breadth-first order. The child region is organized as a prefix-sum array, which only stores each node’s first child index in the key region. Since the prefix-sum child region is small and the children’s index can be retrieved through index computations, most of it can be stored in on-chip caches, which can achieve good cache locality. To make it more efficient, Harmonia also includes two optimizations: partially-sorted aggregation and narrowed thread-group traversal, which can mitigate memory and warp divergence and improve resource utilization. Evaluations on a TITAN V GPU show that Harmonia can achieve up to 3.6 billion queries per second, which is about 3.4X faster than that of HB+Tree, a recent state-of-the-art GPU solution.

Mon 18 Feb

16:10 - 17:00: Main Conference - Session 4: GPU B-Trees at Salon 12/13
Chair(s): Ang LiPacific Northwest National Laboratory
PPoPP-2019-papers16:10 - 16:35
Zhaofeng YanFudan University, Yuzhe LinFudan University, Lu Peng, Weihua ZhangFudan University
PPoPP-2019-papers16:35 - 17:00
Muhammad Awad, Saman AshkianiUniversity of California, Davis, Rob JohnsonVMWare Research, Martin Farach-ColtonRutgers University, John D. OwensUniversity of California, Davis