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 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. [3] and Cascaval et. al. [6]. We illustrate the application of the approach for determination of effective tile sizes and parallelization on shared-memory parallel systems.