DATA TRANSFORMATIONS FOR ELIMINATING CONFLICT MISSES

Many cache misses in scientific programs are due to conflicts caused b y limited set associativity. We examine two compile-time data-layout t ransformations for eliminating conflict misses, concentrating on misse s occuring on every loop iteration. inter-variable padding adjusts var iable base addresses, while intra-variable padding modifies array dime nsion sizes. Two levels of precision are evaluated. PADLITE only uses array and column dimension sizes, relying on assumptions about common array reference patterns. PAD analyzes programs, detecting conflict mi sses by linearizing array references and calculating conflict distance s between uniformly-generated references. The Euclidean algorithm for computing the gcd of two numbers is used to predict conflicts between different array columns for linear algebra codes. Experiments on a ran ge of programs indicate PADLITE can eliminate conflicts for benchmarks , but PAD is more effective over a range of cache and problem sizes. P adding reduces cache miss rates by 16% on average for a 16K direct-map ped cache. Execution times are reduced by 6% on average, with some SPE C95 programs improving up to 15%.