Cache Miss Characterization and Data Locality Optimization for Imperfectly Nested Loops on Shared Memory Multiprocessors
Sanjaya Kumar Sahoo, R. Panuganti, Sriram Krishnamoorthy, Ponnuswamy Sadayappan · 2005
This paper develops an algorithm to accurately characterize the number of cache misses for a class of compute-intensive calculations encountered in accurate quantum chemistry models of electronic structure. The proposed approach can handle imperfectly nested loop structures, symbolic loop bounds, and non-constant dependences for a constrained class of array references. It is proposed in the context of tensor contraction computations, and extends previous work on "stack distances" by Almasi et al. (2002) and Cascaval et al. (2003). We illustrate the application of the approach for determination of effective tile sizes and parallelization on shared-memory parallel systems.