Presentation
A Data-Centric Hardware Accelerator for Efficient Adaptive Radix Tree
DescriptionThe Adaptive Radix Tree (ART) is a widely used tree index structure prevalent in various domains such as databases and key-value stores. Despite many solutions have been proposed to improve the performance of ART, they still suffer from significant redundant tree traversals and serious synchronization costs when concurrently performing the operations (e.g., read/write) over ART. In this work, we observe that most operations of real-world workloads tend to target a small subset of ART nodes frequently, exhibiting strong temporal and spatial similarities among the operations. Based on this observation, we propose a data-centric hardware accelerator, called DCART, to support the operations over ART efficiently. Specifically, DCART proposes a novel data-centric processing model into the accelerator design to coalesce the operations associated with the same ART nodes and adaptively cache the frequently traversed ART nodes and their search results, thereby fully exploiting the similarities among the operations for lower tree traversal and synchronization overhead. We implemented DCART on the Xilinx Alveo U280 FPGA card and compared it with the cutting-edge solutions, DCART achieves 21.1×-44.2× speedups and 71.1×-148.9× energy savings.
Event Type
Research Manuscript
TimeTuesday, June 244:15pm - 4:30pm PDT
Location3002, Level 3