Data Locality Optimization for Synthesis of Efficient OutofCore Algorithms.pdf

Data Locality Optimization for Synthesis of Efficient Out-of-Core Algorithms 1 1 1 Sandhya Krishnan , Sriram Krishnamoorthy , Gerald Baumgartner , Daniel 1 1 1 2 3 Cociorva , Chi-Chung Lam , P. Sadayappan , J. Ramanujam , David E. Bernholdt , and Venkatesh Choppella3 1 Department of Computer and Information Science The Ohio State University, Columbus, OH 43210, USA. {krishnas,krishnsr,gb,cociorva,clam,saday}@cis.ohio-state.edu 2 Department of Electrical and Computer Engineering Louisiana State University, Baton Rouge, LA 70803, USA. jxr@ece.lsu.edu 3 Oak Ridge National Laboratory, Oak Ridge, TN 37831, USA. {bernholdtde,choppellav}@ornl.gov Abstract. This paper describes an approach to synthesis of efficient out-of-core code for a class of imperfectly nested loops that represent tensor contraction com- putations. Tensor contraction expressions arise in many accurate computational models of electronic structure. The developed approach combines loop fusion with loop tiling and uses a performance-model driven approach to loop tiling for the generation of out-of-core code. Experimental measurements are provided that show a good match with model-based predictions and demonstrate the effective- ness of the proposed algorithm. 1 Introduction Many scientific and engineering applications need to operate on data sets that are too large to fit in the physical memory of the machine. Some applications, like video, for example, process data by streaming : each input dat