HARP: Hardware-Based Pseudo-Tiling for Sparse Matrix Multiplication Accelerator

Abstract

General sparse matrix-matrix multiplication (SpGEMM) is a memory bound workload, due to the compression format used. To minimize data movements for input matrices, outer product accelerators have been proposed. Since these accelerators access input matrices only once and then generate numerous partial products, managing the generated partial products is the key optimization factor. To reduce the number of partial products handled, the state-of-the-art accelerator uses software to tile an input matrix. However, the software-based tiling has three limitations. First, a user manually executes the tiling software and manages the tiles. Second, generating a compression format for each tile incurs memory-intensive operations. Third, an accelerator that uses the compression format cannot skip ineffectual accesses for input matrices. To overcome these limitations, this paper proposes hardware based pseudo-tiling (HARP), which enables logical tiling of the original compressed matrix without generating a compression format for each tile. To this end, HARP utilizes our proposed Runtime Operand Descriptor to point to an effectual column-row pair in a pseudo-tile. Consequently, HARP enables a user to use the accelerator as a normal SpGEMM operation does without tiling. Furthermore, HARP does not require a compression format for each tile and can skip ineffectual accesses for input matrices. To further improve the efficiency of pseudo-tiling, HARP performs super-tiling to combine pseudo-tiles and sub-tiling to further tile a pseudo-tile. Experiment results show that HARP achieves 4×, 35×, and 33× speedup and 5×, 664×, and 233× energy efficiency on average compared to the state-of-the-art outer product accelerator, CPU (MKL), and GPU (cuSPARSE), respectively.