skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · thesis 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

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:40)