Strassen's Algorithm for Tensor Contraction
Strassen's Algorithm for Tensor Contraction
复制标题
DOI：
10.1137/17m1135578
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Jianyu Huang;D. Matthews;R. Geijn
中科院分区：
文献类型：
--
作者：
Jianyu Huang;D. Matthews;R. Geijn
张量收缩（TC）是在许多应用中广泛使用的重要计算内核。它是矩阵乘法（GEMM）的多维概括。尽管Strassen的Gemm算法在理论和实践中得到了很好的研究，但将其扩展到以前没有被追求。因此，我们认为这是第一篇论文，证明了在实践中如何使用Strassen的算法加速TC。通过采用块•筛分矩阵格式，一种新颖的以矩阵为中心的张量布局，我们可以从概念上将TC视为通用稳定存储的GEMM，并具有隐式张量与矩阵转换。这种洞察力使我们能够量身定制Strassen算法的最新实施，以避免进行最新的TC，避免明确的换位（排列）和额外的工作区，并减少记忆运动的头顶发生。通过性能模型以及现代单核，多核心和DI ...实践中的性能模型证明了性能好处。
Tensor contraction (TC) is an important computational kernel widely used in numerous applications. It is a multidimensional generalization of matrix multiplication (GEMM). While Strassen's algorithm for GEMM is well studied in theory and practice, extending it to accelerate TC has not been previously pursued. Thus, we believe this to be the first paper to demonstrate how one can in practice speed up TC with Strassen's algorithm. By adopting a block-scatter-matrix format, a novel matrix-centric tensor layout, we can conceptually view TC as GEMM for a general stride storage, with an implicit tensor-to-matrix transformation. This insight enables us to tailor a recent state-of-the-art implementation of Strassen's algorithm to a recent state-of-the-art TC, avoiding explicit transpositions (permutations) and extra workspace, and reducing the overhead of memory movement that is incurred. Performance benefits are demonstrated with a performance model as well as in practice on modern single core, multicore, and di...