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

作者：Qijing Huang, Po-An Tsai, Joel Emer, Angshuman Parashar · 年份：2024 · DOI：10.1109/isca59077.2024.00021 · 被引用次数：10 · 研究领域：Tensor decomposition and applications、Computational Physics and Python Applications、Parallel Computing and Optimization Techniques

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 mul...