Applying data copy to improve memory performance of general array computations.pdf

Applying Data Copy to Improve Memory Performance of General Array Computations Qing Yi Department of Computer Science, University of Texas at San Antonio ? Abstract. Data copy is an important compiler optimization which dy- namically rearranges the layout of arrays by copying their elements into local buffers. Traditionally, array copy is considered expensive and has been applied only to the working sets of fully blocked computations. This paper presents an algorithm which automatically applies data copy to optimize the performance of general computations independent of block- ing. The algorithm automatically decides where to insert copy operations and which regions of arrays to copy. In addition, when specialized, it is equivalent to a general scalar replacement algorithm on arbitrary array computations. The algorithm is fully implemented and has been applied to optimize several scientific kernels. The results show that the algorithm is highly effective and that data copy can significantly improve the per- formance of scientific computations, both when combined with blocking and when applied alone without blocking. 1 Introduction Most scientific applications operate on large multi-dimensional arrays that can- not fit in the caches of modern computers. Such computations typically include sequences of loop nests, with each loop selectively accessing elements of arrays. When a loop accesses a non-continuous collection of array elements, that is, when the array elements accessed together close in time are far from each other in the memory, the loop demonstrates poor spatial locality and additionally could incur conflict misses in the cache. Data copy is an important compiler optimization that can dynamically re- arrange the layout of arrays. At the beginning of each computation phase, the transformation can choose to copy a subset of array elements into local buffers. All the relevant array accesses within the computation phase can then be changed to instead operate on