EMBARK: Memory Bounded Architectural Improvement in CSR-CSC Sparse Matrix Multiplication
Shakya Jayakody, Jun Wang · 2023
Sparse Matrix Multiplication (SpMM) is a crucial algorithm in modern platforms such as Artificial Intelligence (AI), Graph Neural Network (GNN), Graph Convolutional Network (GCN), and neural network image processing. However, the performance of SpMM is limited by several factors, such as memory storage, data reuse, I/O traffic, and memory access. To address these challenges, we have developed a dynamic memory allocation method called EMBARK, specifically including a new Compressed Sparse Row (CSR) × Compressed Sparse Column (CSC) matrix multiplication algorithm that reduces significant matrix decompression/compression overhead and optimizes storage allocation. Our CSR × CSC algorithm is based on memory partitioning techniques: EMBARK, values, and rowid are together, and colptr is stored separately in the main memory. To improve the performance of our algorithm, the main memory is utilized to store hot data for values, colid, and rowid, while the Non-volatile Memory (NVM) stores partial hot data based on a rank-based page replacement strategy. We have conducted experiments with SuiteSparse matrix real datasets, and our results show CSR×CSC-EMBARK reduced the execution time average by 46.44% compared to the baseline matrix-by-matrix multiplication (M×M).