Cache Awareness in Blocking Techniques, Part II

To date, data locality optimizing algorithms mostly aim at providing efficient strategies for blocking and reordering loops. But little research has been devoted to the final step, i.e., computing the optimal block size. Optimal block sizes are currently computed as if a cache behaves as a local memory, i.e., cache interference phenomena are ignored. Case-studies have already shown that cache interferences can greatly affect the optimal block size. The purpose of this paper is to propose a methodology for estimating interference misses in a regular do-loop nest, and use that knowledge to derive the optimal block size. First, the different types of interference phenomena are identified, and a method for predicting their occurrence and evaluating their impact is proposed. Second, current techniques for computing the optimal block size are analytically and experimentally shown to yield far below optimal performance. Third, cache interference phenomena and even TLB behavior are taken into ..