SHF: Small: Making Strassen's Algorithm Practical

高性能线性代数软件库是科学计算和机器学习应用程序的核心。许多高性能线性代数库的核心是矩阵乘法运算，因为许多其他的矩阵运算都可以转化为矩阵乘法，而矩阵乘法本身就可以达到很高的性能。斯特拉森？S算法于1969年首次提出，是一种减少计算矩阵乘法时必须执行的算术运算次数的巧妙方案。这主要是一种理论上的好奇心，导致了多年来的一系列改进。斯特拉森？S算法在非常大的问题规模上的一些实际应用已经在例如航空航天工业中遇到。最近，有研究表明，斯特拉森？S算法及其一些变种可以使小问题变得实用，从而开辟了一系列新的理论和实践研究方向。该项目将遵循这些方向，并将纳入高性能软件库的进步。从本质上讲，它将免费给用户带来高达30%左右的性能提升。拟议的工作将为实现一系列类似Strassen的算法创建一个实用的框架和分析，建立在捕获软件和硬件之间相互作用的计算模型的基础上。这将产生迄今为止对这些算法的实际实施的最彻底的理解。拟议的项目还将提供一个软件库，供计算科学和机器学习应用程序实际使用，这些应用程序以矩阵-矩阵乘法和/或张量压缩的形式进行计算，并提供从该系列中选择最佳算法的机制。它建立在关于线性代数软件库的高性能实现的最新进展的基础上。展示的是，这样的库可以由可以针对特定体系结构高度优化的小内核组成。这些内核已经成为传统矩阵运算算法的构建块。在这项研究中，它们也成为结合Strassen-S算法和密切相关的所谓快速矩阵乘法算法的高性能算法的构建块。生成的软件将在开放源码许可下发布，以方便其使用和研究。教学外展将包括开发一个关于“为性能而编程”的大规模在线开放课程，其中Strassen类算法及其实际实施将是一个突出的丰富内容。该项目涉及来自传统上代表性不足的群体的几名成员，并将继续由本科生参与的长期传统。

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.