Cache Miss Characterization and Data Locality Optimization for Imperfectly Nested Loops on Shared Memory Multiprocessors

This paper develops an algorithm to accurately characterize the number of cache misses for a class of computeintensive 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. and Cascaval et. al. We illustrate the application of the approach for determination of effective tile sizes and parallelization on shared-memory parallel systems.