Compiler Optimization of Array Data Storage

Abstract

The literature has witnessed much work aimed at improving the efficiency of mernory systems. The motivation is obvious: the high cost of page faults in hierarchical stores. Most architectures, including vector processors, shared - and distributed - memory multiprocessors, and interleaved memories, similarly reward data locality and predictable patterns of access. Most current endeavors, however, prefix the storage organization of data operands and either manipulate loops in the code, tailor algorithms, or tune prefetching strategies and replacement policies. A methodology and an algorithm for automatically organizing the storage of array data for efficient access by the executing code are described. The simple techniques presented may be incorporated in a compiler and are complementary to the other optimizations in the literature. Furthermore, examples in Fortran 8X and Fortran 77 pseudo-code support the general applicability of the work to programming languages, both scalar as well as array. Notwithstanding the column-major storage constraints, a technique for optiimizing storage in Fortran 77 is outlined. The prudence of of a compiler-optimized approach over a user-optimized approach to data storage organization is discussed.