A compiler framework for restructuring data declarations to enhance cache and TLB effectiveness

It has been observed that memory access performance can be improved by restructuring data declarations, using simple transformations such as array dimension padding and inter-array padding (array alignment) to reduce the number of misses in the cache and TLB (translation lookaside bu er). These transformations can be applied to both static and dynamic array variables. In this paper, we provide a padding algorithm for selecting appropriate padding amounts, which takes into account various cache and TLB e ects collectively within a single framework. In addition to reducing the number of misses, we identify the importance of reducing the impact of cache miss jamming by spreading cache misses more uniformly across loop iterations. We translate undesirable cache and TLB behaviors into a set of constraints on padding amounts and propose a heuristic algorithm of polynomial time complexity to nd the padding amounts to satisfy these constraints. The goal of the padding algorithm is to select padding amounts so that there are no set con icts and no o set con icts in the cache and TLB, for a given loop. In practice, this algorithm can e ciently nd small padding amounts to satisfy these constraints