BlockSmith: Ultra-dense Block Transformation for Efficient Sparse Matrix Multiplication Using Tensor Cores

Sparse-dense Matrix Multiplication (SpMM) is a fundamental operation in various fields. Recently, leveraging Tensor Cores (TCs) on GPUs to accelerate SpMM has attracted growing interest. Given the block-wise computation nature of TCs, existing TC-based SpMM methods typically apply preprocessing techniques, such as similarity-based row reordering, to cluster similar rows and improve data locality, with the goal of forming denser matrix blocks that better utilize TCs and enhance SpMM performance. However, these methods typically apply TCs only at the final computation stage, without fully accounting for the block-wise execution characteristic during the reordering process. As a result, the clustering outcomes often misalign with the actual computation pattern of TCs, limiting potential performance gains. To this end, we propose BlockSmith , an end-to-end framework for accelerating SpMM by leveraging TCs. The name BlockSmith reflects its core design principle: to forge high-density matrix blocks from sparse matrices. The key innovation lies in the Ultra-dense Block Transformation (UBT) approach, which significantly improves the data locality of sparse matrices by integrating a novel row-reordering algorithm and column compression technique, while also taking into account the block-wise characteristics of TCs. Moreover, we design a novel storage format to maximize memory access efficiency, together with an optimized GPU kernel that leverages low-level PTX instructions to fully exploit the capabilities of TCs. Extensive evaluations on modern GPUs, including RTX 4090 and RTX 5090, show that BlockSmith outperforms the state-of-the-art SpMM method Acc-SpMM, achieving average speedups of 1.89 × and 4.35 ×, respectively, with the maximum speedup exceeding 100 ×. Moreover, for GNN inference tasks, BlockSmith-GCN achieves over 10 × speedup compared with mainstream frameworks such as PyG and DGL. The source code of BlockSmith is publicly available at: https://github.com/CGCL-codes/BlockSmith.git.