Analytical Modeling of Set-Associative Caches for Optimizing Tensor Operations

Optimizing for data cache memories is a difficult problem for a compiler, and an important performance bottleneck. Indeed, the behavior of a cache is complex to model statically, due to the cache policies (associativity, eviction policy), and the complex interplay with the mechanisms of a superscalar microarchitecture. Many analytical cache models exist that predict the number of cache misses at compile time, which is pertinent information for optimization. However, there is a compromise between the precision of the model, coverage of input programs, and the model’s analysis time. For example, using a fully-associative analytical cache model is one such compromise: precision is sacrificed by assuming full associativity, but the model is fast and applicable to any affine program. This paper introduces a new cache model, called SARCASM (Set-Associative Rotating Cache Analytical/Simulating Model), representing a new and useful compromise, which is pertinent in the context of sampling over optimization choices (called configurations ). This was previously limited to fully-associative cache models. SARCASM is a set-associative cache model and can thus model conflict misses and achieve better precision than fully-associative cache models. It is targeted at code structures that arise with optimized implementations of tensor operations such as matrix multiplication, convolution, tensor contraction, arising in machine learning applications. These may feature several levels of tiling, but with only hyper-rectangular tile shapes. Importantly, it is fast enough to be applied at compile time. The SARCASM cache model is based on the notion of detailed footprint , a natural generalization of the notion of footprint of existing models that considers the footprint for each cache set. Once the detailed footprint is computed for each loop level, it uses a fully associative model for each cache set to obtain the number of cache misses per cache set. We show that the predictions of this model induce an ordering of configurations much closer to that of measured cache misses than a fully-associative model. We also show that it correlates much better with execution time compared to a fully-associative model.