[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.107-138 (March 1998)
Locality Optimization Algorithms for
Compilation of Out-of-Core Codes*

M. Kandermir, A. Choudhary+, J. ramanujam#
and M. Kandaswamy@
EECS Deptartment
Syracuse University
Syracuse, NY 13244
+ ECE Deptartment
Northwestern University
Evanston, IL 60208-3118
# ECE Department
Louisiana State University
Baton Rouge, LA 70803
@ EECS Department
Syracuse University
Syracuse, NY 13244

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.

  • This work was supported in part by an NSF Young Investigator Award CCR-9357840, NSF CCR-9509143.
  • This work was supported in part by the Scalable I/O Initiative, contract number DABT63-94-C-0049 from the Defense Advanced Research Projects Agency (DARPA), administered by the US Army at Fort Huachuca.
  • The work of J. Ramanujam was supported in part by an NSF Young Investigator Award CCR-9457768, by an NSF grant CCRr-9210422.
  • The work of J. Ramanujam was supported in part by the Louisiana Board of Regents through contract LEQSF (1991-94)-RD-A-09.