C3ache: Towards Hierarchical Cache-Centric Computing for Sparse Matrix Multiplication on GPGPUs

Sparse matrix multiplications (SPMMs) are fundamental kernels in various domains and are highly demanded to be executed on general-purpose graphics processing units (GPGPUs).However, it is a challenge to efficiently execute SPMMs across varying sparsity regimes on GPGPUs due to the significant variations in sparsity patterns across different domains.Most of the state-of-the-art works enhance GPGPUs by integrating dedicated accelerator units in processor, which prioritize computational density over memory subsystem optimizations.As sparsity increases, the overhead from expensive memory accesses and redundant input fetches in sparse matrices constrains the effectiveness of processor-centric optimization schemes.Consequently, these optimizations become suboptimal for workloads dominated by irregular memory access patterns and low arithmetic intensity.To address these problems, we proposed a hierarchical cachecentric computing architecture with hybrid dataflow, 𝐶 3 𝑎𝑐ℎ𝑒, to achieve near-optimal memory efficiency and data reuse.First, the hybrid dataflow based on the outer-product dataflow and Gustavson's dataflow is proposed to decouple the SPMM computation into two distinct phases (multiplication and merging) with different behavioral characteristics and align with the memory access pattern.Furthermore, 𝐶 3 𝑎𝑐ℎ𝑒 restructures the cache hierarchy through in-cache computing, transforming the two levels of cache into largescale data parallel processing in memory (PIM) units and in-situ merging PIM units respectively to map the two computation phases of SPMMs.To synchronize the granularity of data fetching with the memory access pattern, a novel memory-aware compressed format is proposed for sparse encoding to further reduce the memory transaction and the decoding overhead of 𝐶 3 𝑎𝑐ℎ𝑒.To realize 𝐶 3 𝑎𝑐ℎ𝑒, an