Mind the Gap: Attainable Data Movement and Operational Intensity Bounds for Tensor Algorithms

The architectural design-space exploration (or DSE) process-whether manual or automated-benefits greatly from knowing the limits of the metrics of interest in advance. Data movement is rapidly emerging as a critical metric for DSE due to its increasing impact on both performance and energy efficiency. Unfortunately, the commonly used algorithmic minimum (or “compulsory misses”) limit for data movement is extremely loose, limiting its utility in design-space search. In this paper, we present Orojenesis, an approach to compute data movement limits (or bounds) for tensor algorithms. Unlike algorithmic-minimum bounds, Orojenesis comprehends reuse and the ability of a buffer (such as a cache or scratchpad) to exploit reuse to reduce data movement. Orojenesis provides a bound that no dataflow or mapping can possibly exceed under varying onchip buffer capacity constraints, including mappings that fuse a sequence of tensor operations to exploit producer-consumer reuse. Orojenesis produces a plot that shows the relationship between a buffer’s size and the lower data movement limit to/from the next level in a memory hierarchy. This plot, dubbed a ski-slope diagram, allows designers to gain critical insights into the behavior of a workload as a function of storage capacity. This analysis can inform early high-level design decisions before embarking on thorough design space searches. We use Orojenesis to analyze a set of valuable tensor algorithms including batched and grouped matrix multiplications, convolutions, and sequences of operations in Large Language Models (LLMs). Our analysis reveals a range of architectural insights, including the fact that attainable data movement can be orders-of-magnitude higher than algorithmic minimum, that there exists a sweet spot between SRAM and compute resource provisioning for optimal throughput, and that up to $5.6 \times$ data movement reduction can be achieved with fusion with a buffer capacity of 320 MB for the GPT-3-6.7b LLM.