  This paper proposes Capstan: a scalable, parallel-patterns-based,
reconfigurable-dataflow accelerator (RDA) for sparse and dense tensor
applications. Instead of designing for one application, we start with common
sparse data formats, each of which supports multiple applications. Using a
declarative programming model, Capstan supports application-independent sparse
iteration and memory primitives that can be mapped to vectorized,
high-performance hardware. We optimize random-access sparse memories with
configurable out-of-order execution to increase SRAM random-access throughput
from 32% to 80%.
  For a variety of sparse applications, Capstan with DDR4 memory is 22x faster
than a multi-core CPU baseline, while Capstan with HBM2 memory is 17x faster
than an Nvidia V100 GPU. For sparse applications that can be mapped to
Plasticine, a recent dense RDA, Capstan is 7.6x to 365x faster and only 13%
larger.
