SHF: Small: Making Strassen's Algorithm Practical

SHF：小：使 Strassen 的算法变得实用

• 批准号: 1714091
• 负责人: Robert van de Geijn
• 金额: $ 46.59万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-01 至 2021-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714091&HistoricalAwards=false
• 关键词: SHF; Small; Making; Strassen; Algorithm

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.

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

项目成果

Strassen's Algorithm for Tensor Contraction

• DOI: 10.1137/17m1135578
• 发表时间: 2017-04
• 期刊: SIAM J. Sci. Comput.
• 作者: Jianyu Huang;D. Matthews;R. Geijn

Lowering Barriers into HPC through Open Education

通过开放教育降低 HPC 的障碍

• 发表时间: 2017
• 期刊: EdEduHPC-17: Workshop on Education for High-Performance Computing.
• 作者: van de Geijn, Robert A.;Huang, Jianyu;Myers, Margaret E.;Parikh, Devangi N.;Smith, Tyler M.
• 通讯作者: Smith, Tyler M.

Learning from Optimizing Matrix-Matrix Multiplication

从优化矩阵-矩阵乘法中学习

• 发表时间: 2018
• 期刊: NSF/TCPP Workshop on Parallel and Distributed Computing Education (EduPar-18
• 作者: Parikh, Devangi N.;Huang, Jianyu;Myers, Margaret E.;van de Geijn, Robert A.
• 通讯作者: van de Geijn, Robert A.