Static reuse distances for locality-based optimizations in MATLAB
- 2 June 2010
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 295-304
- https://doi.org/10.1145/1810085.1810125
Abstract
The problem of modeling memory locality of applications to guide compiler optimizations in a systematic manner is an important unsolved problem, made even more significant with the advent of multi-core and many-core architectures. We describe an approach based on a novel source-level metric, called static reuse distance, to model the memory behavior of applications written in matlab. We use matlab as a representative language that lets end-users express their algorithms precisely, but at a relatively high level. Matlab's "high-level" characteristics allow the static analysis to focus on large objects, such as arrays, without losing accuracy due to processor-specific layout of scalar values in memory. We present an efficient algorithm to compute static reuse distances using an extended version of dependence graphs. Our approach differs from earlier similar attempts in three important aspects: it targets high-level programming systems characterized by heavy use of libraries; it works on full programs, instead of being confined to loops; and it integrates practical mechanisms to handle separately compiled procedures as well as pre-compiled library procedures that are only available in binary form. We study matlab code, taken from real programs, to demonstrate the effectiveness of our model. Finally, we present some applications of our approach to program transformations that are known to be important in matlab, but are expected to be relevant to other similar high level languages as well.Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF-0811703)
This publication has 15 references indexed in Scilit:
- Experimental algorithmicsCommunications of the ACM, 2007
- An experimental comparison of cache-oblivious and cache-conscious programsPublished by Association for Computing Machinery (ACM) ,2007
- A Dimension Abstraction Approach to Vectorization in MatlabPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Estimating cache misses and locality using stack distancesPublished by Association for Computing Machinery (ACM) ,2003
- Predicting whole-program locality through reuse distance analysisPublished by Association for Computing Machinery (ACM) ,2003
- FFTW: an adaptive software architecture for the FFTPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Techniques for the translation of MATLAB programs into Fortran 90ACM Transactions on Programming Languages and Systems, 1999
- Compiler transformations for high-performance computingACM Computing Surveys, 1994
- A data locality optimizing algorithmPublished by Association for Computing Machinery (ACM) ,1991
- Evaluation techniques for storage hierarchiesIBM Systems Journal, 1970