With slowing technology scaling, specialized accelerators are increasingly attractive solutions to continue expected generational scaling of performance. However, many advanced algorithms from challenging domains are “irregular” in terms of their control flow or memory patterns. These forms of irregularity inherently couple compute with memory, and also preclude efficient vectorization – defeating the traditional parallelization mechanisms put into programmable accelerators (eg. GPUs).

In this work we develop a programmable accelerator which is broadly applicable across algorithms, including those with irregularity. To this end we first identify forms of irregularity (ie. data-dependence) which are both common and simple-enough to exploit with specialized hardware: specifically stream-join (eg. join two lists) and alias-free indirection (eg. hashtable access). Then, we create an accelerator with a hardware/software interface to support these, called the Sparse Processing Unit (SPU). SPU couples a systolic compute-fabric for high efficiency on regular workloads, with a novel dataflow model to support fast join, and a scratchpad architecture supporting high-bandwidth indirection using aggressive reordering and embedded compute. SPU achieves 20x, 30x, and 14x speedup over a 24-core SKL CPU on ML, database, and graph algorithms respectively, and up to 20x against a similarly provisioned GPGPU, at 15% the area and 24% of the power.