Toward Software Tools for Memory-Efficient Matrix Algebra

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

A scientific program is a mathematical one so there are two factors contributing to its performance. One is the time required to perform arithmetic. The other is the time needed to move data through the memory hierarchy of the computer. In today's large applications, the latter cost often dominates. The work funded by this grant focuses on efficient computational methods for solving the problems in matrix algebra that arise in a wide variety of science and engineering applications. Codes for such problems are typically constructed as sequences of calls to the routines known as the Basic Linear Algebra Subprograms (BLAS). Writing programs in this way promotes readability and maintainability but can be costly in terms of memory efficiency especially for matrices of large order. The grant will be used primarily to support a Ph.D. student who will study ways to combine multiple BLAS routines into a single routine that performs the functions of more than one BLAS. He will examine ways to create composed BLAS via novel algorithms and performance programming techniques, developing a general methodology for their creation in the process. His work will ultimately form the basis for a tool that creates composed BLAS automatically. Composed routines can significantly reduce the amount of data read from main memory. Preliminary results include speedups as large as 90\%.