Toward Software Tools for Memory-Efficient Matrix Algebra

一个科学的程序是一个数学程序，所以有两个因素影响它的性能。一个是计算所需的时间。另一个是在计算机的内存层次中移动数据所需的时间。在今天的大型应用中，后者的成本往往占主导地位。由该基金资助的工作重点是解决矩阵代数问题的有效计算方法，这些问题在各种科学和工程应用中出现。这类问题的代码通常构造为调用称为基本线性代数子程序（BLAS）的例程的序列。以这种方式编写程序可以提高可读性和可维护性，但在内存效率方面可能会付出代价，特别是对于大顺序矩阵。这笔资金将主要用于支持一名博士生，该博士生将研究如何将多个BLAS例程合并为一个例程，以执行多个BLAS的功能。他将研究通过新颖算法和性能编程技术创建组合BLAS的方法，并在此过程中为其创建开发通用方法。他的工作最终将成为自动创建组合BLAS的工具的基础。组合例程可以显著减少从主存中读取的数据量。初步结果包括高达90%的加速。

A scientific program is a mathematical one so there are two factorscontributing to its performance. One is the time required to performarithmetic. The other is the time needed to move data through thememory hierarchy of the computer. In today's large applications, thelatter cost often dominates. The work funded by this grant focuses onefficient computational methods for solving the problems in matrix algebrathat arise in a wide variety of science and engineering applications.Codes for such problems are typically constructed as sequences of calls tothe routines known as the Basic Linear Algebra Subprograms (BLAS). Writingprograms in this way promotes readability and maintainability but canbe costly in terms of memory efficiency especially for matrices oflarge order.The grant will be used primarily to support a Ph.D. student who willstudy ways to combine multiple BLAS routines into a single routine thatperforms the functions of more than one BLAS. He will examine ways tocreate composed BLAS via novel algorithms and performance programmingtechniques, developing a general methodology for their creation in theprocess. His work will ultimately form the basis for a tool that createscomposed BLAS automatically. Composed routines can significantly reducethe amount of data read from main memory. Preliminary results includespeedups as large as 90\%.