Physical Sciences and Mathematics Commons^™

Improving Data Locality With Loop Transformations, Kathryn S. Mckinley, Steve Carr, Chau-Wen Tseng

Computer Science Department Faculty Publication Series

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit data locality. In this article, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both temporal and spatial reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. We demonstrate that these program transformations are useful for optimizing many programs. …