Automated memory analysis: improving the design and implementation of iterative algorithms
John M. Dennis · 2005
Historically, iterative solvers have been designed to achieve the best numerical accuracy for a given number of floating-point operations. However, this approach ignores the cost of memory access, which has not seen nearly as rapid of an improvement as floating-point costs. To reduce the time to solution, we need to address both the numerical efficiency and memory efficiency of an iterative algorithm. We contend that it is possible to evaluate the memory efficiency of an iterative algorithm during the design process. There are two techniques for a priori evaluation of memory efficiency: manual and automated memory analysis. Manual memory analysis, which involves the derivation of analytical expression for data movement, is a laborious, error-prone process that is too complex to perform on a regular basis. Automated memory analysis is possible through the use of the Sparse Linear Algebra Memory Model (SLAMM) language processor. The SLAMM language processor accepts as input Matlab code and outputs a suitably transformed Matlab source that contains blocks of code that predict data movement. We demonstrate that the SLAMM language processor accurately predicts the amount of data loaded from the memory hierarchy to the L1 cache (Mbytes L1) to within 20% error for numerous small kernels and complete iterative algorithms on three different compute platforms. SLAMM reduces the time to perform memory analysis from as long as several days to 20 minutes. SLAMM provides the ability to rapidly evaluate the memory efficiency of particular design choices during the design phase of an iterative algorithm. Additionally, we demonstrate how SLAMM is used to improve the memory efficiency of a pre-existing solver.