Trapezoid: A Versatile Accelerator for Dense and Sparse Matrix Multiplications
Authors:
- 29 June 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 931-945
Abstract
Accelerating matrix multiplication is crucial to achieve high performance in many application domains, including neural networks, graph analytics, and scientific computing. These applications process matrices with a wide range of sparsities, from completely dense to highly sparse. Ideally, a single accelerator should handle matrices of all sparsity levels well. However, prior matrix multiplication accelerators each target a limited range of sparsity levels. We present Trapezoid, a versatile accelerator that performs matrix multiplication across all sparsity levels effectively. Trapezoid builds on a 2D spatial array design, which excels at dense matrix multiplication, and extends it with new hardware mechanisms that let it handle sparse inputs. We present a novel innerproduct-based dataflow with a multi-fiber intersection unit that handles mildly sparse matrices. Furthermore, novel Gustavsonbased dataflows and a multi-level memory hierarchy enable high performance on highly sparse matrices. Trapezoid’s hardware extensions are reused across dataflows to minimize area overheads. We evaluate Trapezoid on a broad range of dense and sparse matrix multiplication workloads. Trapezoid has gmean $19.7 \times$, $4.3 \times$, and $2.9 \times$ better performance/area than TPU, SIGMA, and Flexagon, prior state-of-the-art accelerators that target dense, mildly sparse, and highly sparse matrices, respectively.
Keywords
Funding Information
- Semiconductor Research Corporation
- National Science Foundation
This publication has 67 references indexed in Scilit:
- HyGCN: A GCN Accelerator with Hybrid Architecture2020
- Efficient Processing of Deep Neural Networks2020
- 4D Spatio-Temporal ConvNets: Minkowski Convolutional Neural Networks2019
- OuterSPACE: An Outer Product Based Sparse Matrix Multiplication Accelerator2018
- Deep Residual Learning for Image Recognition2016
- Graphs, Matrices, and the GraphBLAS: Seven Good ReasonsProcedia Computer Science, 2015
- The Design and Implementation of DDR PHY Static Low-Power Optimization Strategies2011
- ImageNet: A large-scale hierarchical image database2009
- High-Performance Graph Algorithms from Parallel Sparse Matrices2007
- The block conjugate gradient algorithm and related methodsLinear Algebra and its Applications, 1980