The difficulty of handling out-of-core data limits the performance of supercomputers as well as the potential of parallel machines. Since writing an efficient out-of-core version of a program is a difficult tasks, and since virtual memory systems do not perform well on scientific computations, we believe that there is a clear need for a compiler-directed explicit I/O approach for out-of-core computations. In this paper, we present a compiler algorithm to optimize the locality of disk accesses in out-of-core codes by choosing a good combination of file layouts on disks and loop transformations. The transformations change the access order of array data. Our solution goes beyond the single-loop level (called global I/O optimization in this paper) for out-of-core computations. Since the general problem is NP-complete, we present efficient heuristics that produce near-optimal solutions for several programs encountered in practice. Experimental results obtained on an IBM SP-2 and Intel Paragon provide encouraging evidence that our approach is successful at optimizing programs which depend on disk-resident data in distributed-memory machines.

Keywords: compilation techniques, out-of-core computations, parallel I/O, global I/O optimization, loop transformations

Received April 30, 1997; revised November 20, 1997.
Communicated by Chau-Huang Huang.
^*