SHF: Small: Making Strassen's Algorithm Practical

University Of Texas At Austin, Austin TX

Investigators

Abstract

High-performance linear algebra software libraries are at the core of scientific computing and machine learning applications. At the core of many high-performance linear algebra libraries lies the matrix multiplication operation because many other matrix operations can be cast in terms of matrix multiplication and matrix multiplication itself can attain high performance. Strassen?s algorithm, first proposed in 1969, is a clever scheme for reducing the number of arithmetic calculations that must be performed when computing a matrix multiplication. It has mostly been a theoretical curiosity that has led to a sequence of improvements over the years. Some practical applications of Strassen?s algorithm for very large problem sizes have been encountered in, for example, the aerospace industry. Very recently, it was shown that Strassen?s algorithm, and some of its variations, can be made practical for small problem sizes, opening up a range of new academic and practical directions of research. The project will pursue these directions and will incorporate the advances in high-performance software libraries. In essence, it will give the user a performance boost of up to around 30%, for free. The proposed work will create a practical framework and analysis for the implementation of a broad family of Strassen-like algorithms, building on a model of computation that captures the interaction between software and hardware. This will yield the most thorough understanding to date of the practical implementation of such algorithms. The proposed project will also deliver a software library for practical use in computational science and machine learning applications that cast computation in terms of matrix-matrix multiplication and/or tensor contractions, with a mechanism for choosing the best algorithm from that family. It builds on recent advances regarding the high-performance implementation of linear algebra software libraries. What was shown was that such libraries can be composed from small kernels that can be highly optimized for a specific architecture. These kernels have become the building blocks for traditional algorithms for matrix operations. In this research, they also become the building blocks for high-performance algorithms that incorporate Strassen?s algorithm and closely related so-called fast matrix multiplication algorithms. The resulting software will be released under open source license to facilitate its use and study. Pedagogical outreach will include the development of a Massive Open Online Course on "Programming for Performance" in which Strassen-like algorithms and their practical implementation will be a prominent enrichment. The project involves several members from traditionally underrepresented groups and will continue a long tradition of involvement by undergraduates.