Terminus: A Programmable Accelerator for Read and Update Operations on Sparse Data Structures

Sparse data structures like hash tables, trees, or compressed tensors are ubiquitous, but operations on these structures are expensive and inefficient on current systems. Prior work has proposed hardware acceleration for these operations, but these techniques have two key shortcomings: they limit the types of data structures they support, and they focus on reads but do not support fine-grained updates to these structures. We present Terminus, a programmable accelerator for read and update operations on sparse data structures. Terminus extends each general-purpose core with a programmable dataflow engine capable of accelerating a wide range of structures and operations. Terminus engines are flexible yet simple, as they focus on common operations and defer rare, complex ones to cores. Terminus features a simple concurrency control mechanism based on address ranges that enables safe updates while preserving parallelism. We evaluate Terminus on serial and parallel benchmarks on a wide range of sparse data structures. Terminus improves performance by gmean <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$7.4\times$</tex> over a CPU baseline, showing that Terminus can accelerate fine-grained reads and writes that were previously not possible in prior accelerators for sparse structures.