Compiler Cache Optimizations for Banded Matrix Problems

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 bandedness. The complicated memory accesspatterns in the banded ..