Improving data locality with loop transformations

Reviewer: Noah S. Prywes

When using a processor with a cache memory of limited size, the order of memory referencing in the program can affect the overall computation time. It would be too difficult for a programmer to consider this effect in composing a program. Instead, the authors propose incorporating in the compiler the program optimization needed to accelerate program execution for the cache memory of the processor where the program will be executed. The optimization consists of reordering the loops in the program. The paper presents cost models to evaluate the impact of reordering the loops. These are presented for four schemes for reordering loops—loop permutation, fusion, distribution, and reversal. A cost model for combining such schemes is also presented. Finally, results of experimental work are provided to assess the effectiveness of using the loop reordering cost models. Experimental data are presented for a number of programs and for respective cache memories and processors. The cache memories and processors are 64 KB cache direct-mapped, 32-byte cache line for the HP 715/50; 64 KB cache, four-way, 128-byte cache line for the RS/6000; and 8 KB cache, two-way, 32-byte cache line for the i 860. The programs were executed on the RS/6000 and HP 715/50 as well as simulated for different cache memories of the RS/6000 and i 860. The experimental result validates the cost model. The improvement in execution is significant for only some of the programs studied, and particularly for the use of smaller cache memory. The paper reports on important concepts and experiments, not only for use in compiler construction (as suggested), but also for the design of cache memories. Its readers should already be familiar with the concepts of data dependence and temporal reuse.