Aurochs: An Architecture for Dataflow Threads

Data analytics pipelines increasingly rely on databases to select, filter, and pre-process reams of data. These databases use data structures with irregular control flow like trees and hash tables which map poorly to existing database accelerators, leaving architects with a choice between CPUS— with stagnant performance—or accelerators that handle this complexity by relying on simpler but asymptotically sub-optimal algorithms.To bridge this gap, we propose Aurochs: a reconfigurable dataflow accelerator (RDA) that matches a CPU asymptotically but outperforms it by over 100 × on constant factors. We introduce a threading model for vector dataflow accelerators that extracts massive parallelism from irregular data structures using lightweight thread contexts. To implement this model, we add only a sparse scratchpad to an existing database accelerator— increasing area by 5 %. We reformulate common data structures using dataflow threads and evaluate Aurochs on ridesharing queries—outperforming a GPU by 8 ×.