A STRATEGY FOR ARRAY MANAGEMENT IN LOCAL MEMORY

One major point in loop restructuring for data locality optimization i s the choice and the evaluation of data locality criteria. In this pap er we show how to compute approximations of window sets defined by can non, Jalby, and Gallivan. The window associated with an iteration i de scribes the ''active'' portion of an array: elements that have already been referenced before iteration i and that will be referenced after iteration i. Such a notion is extremely useful for data localization b ecause it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The comput ation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may b e combined efficiently with various parallelization and/or vectorizati on optimizations. Indeed, the effects of loop transformations fit natu rally into the geometrical framework we use for the calculations. The determination of window approximations is studied both from a theoreti cal and a computational point of view, and examples of applications ar e given.