Data relation vectors: A new abstraction for data optimizations

We present an abstraction, called data relation vectors, to improve the dat a access characteristics and memory layouts in regular computations. The ke y idea is to define a relation between the data elements accessed by close- by iterations and use this relation to guide to a number of optimizations f or array-based computations. The specific optimizations studied in this pap er include enhancing group-spatial and self-spatial reuses and improving in tratile and intertile data reuses. In addition, this abstraction works well with other known abstractions such as data reuse vectors. We also present a unified scheme for optimizing the memory performance of programs using th is new abstraction in conjunction with reuse vectors. The data relation vec tor abstraction has been implemented in the SUIF compilation framework and has been tested using a set of 12 benchmarks from image processing and scie ntific computation domains. Preliminary results on a superscalar processor show that it is successful in reducing compilation time and outperforms two previously proposed techniques, one that uses only loop transformations an d one that uses both loop and data transformations. Our experiments also sh ow that the proposed abstraction helps one to select good data tile shapes which can subsequently be used to determine iteration space tiles.