home · mobile · calendar · defenses · 2004-2005 · 

Thesis Defense - Dennis

Automated Memory Analysis: Improving the Design and Implementation of Iterative Algorithms
Computer Science PhD Candidate

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 have 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 (memory analysis) 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 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 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.

Committee: Elizabeth Jessup, Associate Professor (Chair)
William Waite, Professor
Xiao-Chuan Cai, Professor
Steven Thomas, NCAR
Henry Tufo, Associate Professor
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:20)