Automatic program restructuring to reduce average cache miss penalty

摘要

A method, a computer or computer program product for automatically restructuring a program having arrays in inner loops to reduce an average penalty incurred for bursty cache miss patterns by spreading out the cache misses. The method may be used separately or in conjunction with methods for reducing the number of cache misses. The method determines a padding required for each array according to a proportion of the cache line size, to offset the starting points of the arrays relative to the start of a cache line memory access address for each array. Preferably, the starting points of the arrays that induce bursty cache misses are padded so that they are uniformly spaced from one another.