Compiler cache optimizations for banded matrix problems
Wei Li · 1995
Almost every modern processor is designed with a memory hierarchy organized into several levels, each of which is smaller, faster, and more expensive than the level below.High performance requires the effective use of the cached data, i.e. cache locality.Smart compiler transformations can relieve the programmer from hand-optimizing for the specific machine architectures.Most of the existing compiler optimizations are developed for dense matrix programs.Irregular problems, on the other hand, have to rely on runtime optimizations, since the data access patterns are unknown at the compile-time.However, many scientific computing problems result in solving linear systems where the matrix of coefficients is banded, a structure known at the compile-time, but more complicated than the dense matrices.Banded matrix problems are interesting since substantial savings can be made by exploiting the mathematical properties of the handedness.The complicated memory access patterns in the banded matrix programs make the existing compile-time optimization impossible to use.In this paper, we present a new compile-time technique for optimizing banded-matrix programs.We first develop a new data reuse model and an algorithm called height reduction to improve cache locality.Then with the height reduction algorithm, we extend loop tiling to exploit not only intra-tile data Iocality but also inter-tile data locality.We call the new tiling a#irrity tiling.We show that the algorithms also helps to eliminate or reduce false sharing in multiprocessor systems.With the height reduction algorithm and affinity tiling, significant performance improvement (speedups from 2,5 to 10) has been observed on HP workstations (over the original sequential code) and KSR1 multiprocessors (over the original parallel code), *This work WJS supported m ptit by m NSF Research Initiation Award (CCR-9409 120) and ARPA contract F] 9628