Symmetric and sparse tensors arise naturally in many domains including linear algebra, statistics, physics, chemistry, and graph theory. Symmetric tensors are equal to their transposes, so in the $n$-dimensional case we can save up to a factor of $n!$ by avoiding redundant operations. Sparse tensors, on the other hand, are mostly zero, and we can save asymptotically by processing only nonzeros. Unfortunately, specializing for both symmetry and sparsity at the same time is uniquely challenging. Optimizing for symmetry requires consideration of $n!$ transpositions of a triangular kernel, which can be complex and error prone. Considering multiple transposed iteration orders and triangular loop bounds also complicates iteration through intricate sparse tensor formats. Additionally, since each combination of symmetry and sparse tensor formats requires a specialized implementation, this leads to a combinatorial number of cases. A compiler is needed, but existing compilers cannot take advantage of both symmetry and sparsity within the same kernel. In this paper, we describe the first compiler which can automatically generate symmetry-aware code for sparse or structured tensor kernels. We introduce a taxonomy for symmetry in tensor kernels, and show how to target each kind of symmetry. Our implementation demonstrates significant speedups ranging from 1.36x for SSYMV to 30.4x for a 5-dimensional MTTKRP over the non-symmetric state of the art.

Mon 3 Mar

Displayed time zone: Pacific Time (US & Canada) change

11:20 - 12:20
Optimizations & Transformations (1)Main Conference at Casuarina Ballroom (Level 2)
Chair(s): Oleksandr Zinenko n/a
11:20
20m
Talk
SySTeC: A Symmetric Sparse Tensor Compiler
Main Conference
Radha Patel Massachusetts Institute of Technology, Willow Ahrens Massachusetts Institute of Technology, Saman Amarasinghe Massachusetts Institute of Technology
11:40
20m
Talk
Pattern Matching in AI Compilers and its Formalization
Main Conference
Joseph W. Cutler University of Pennsylvania, Alexander Collins NVIDIA, Bin Fan Nvidia, Mahesh Ravishankar , Vinod Grover NVIDIA
12:00
20m
Talk
Scalar Interpolation: A Better Balance Between Vector and Scalar Execution for SuperScalar Architectures
Main Conference
Reza Ghanbari University of Alberta, Henry Kao Huawei Technologies Canada, João P. L. De Carvalho AMD, Ehsan Amiri Huawei Technologies Canada, Jose Nelson Amaral University of Alberta