  As its core computation, a self-attention mechanism gauges pairwise
correlations across the entire input sequence. Despite favorable performance,
calculating pairwise correlations is prohibitively costly. While recent work
has shown the benefits of runtime pruning of elements with low attention
scores, the quadratic complexity of self-attention mechanisms and their on-chip
memory capacity demands are overlooked. This work addresses these constraints
by architecting an accelerator, called SPRINT, which leverages the inherent
parallelism of ReRAM crossbar arrays to compute attention scores in an
approximate manner. Our design prunes the low attention scores using a
lightweight analog thresholding circuitry within ReRAM, enabling SPRINT to
fetch only a small subset of relevant data to on-chip memory. To mitigate
potential negative repercussions for model accuracy, SPRINT re-computes the
attention scores for the few fetched data in digital. The combined in-memory
pruning and on-chip recompute of the relevant attention scores enables SPRINT
to transform quadratic complexity to a merely linear one. In addition, we
identify and leverage a dynamic spatial locality between the adjacent attention
operations even after pruning, which eliminates costly yet redundant data
fetches. We evaluate our proposed technique on a wide range of state-of-the-art
transformer models. On average, SPRINT yields 7.5x speedup and 19.6x energy
reduction when total 16KB on-chip memory is used, while virtually on par with
iso-accuracy of the baseline models (on average 0.36% degradation).
