Back to Search Start Over

STRASSEN'S ALGORITHM FOR TENSOR CONTRACTION.

Authors :
JIANYU HUANG
MATTHEWS, DEVIN A.
VAN DE GEIJN, ROBERT A.
Source :
SIAM Journal on Scientific Computing. 2018, Vol. 40 Issue 3, pC305-C326. 22p.
Publication Year :
2018

Abstract

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 distributed memory parallel architectures, achieving up to 1.3 x speedup. The resulting implementations can serve as a drop-in replacement for various applications with significant speedup. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
10648275
Volume :
40
Issue :
3
Database :
Academic Search Index
Journal :
SIAM Journal on Scientific Computing
Publication Type :
Academic Journal
Accession number :
131527654
Full Text :
https://doi.org/10.1137/17M1135578