Improving data locality for caches
Cooper, Keith D.
Master of Science
Since the introduction of cache memories in computer architecture, techniques to improve the data locality of programs with respect to cache have been essential to good performance. This thesis is a contribution in that direction. It is divided in three main parts: (1) A survey of the existing techniques that address data locality and the different approaches proposed in the literature. (2) The introduction of a new program transformation that is in fact a combination of two known transformations, namely iteration space tiling and copy optimization, to achieve better data locality than can be attained with either of the two techniques by themselves. (3) A suggestion of a general approach to data locality improvement as a whole, and an algorithm to compute block sizes for tiled programs that avoid self interferences in cache.