Research and ACM SRC Posters Archive

CLASP: Index Compression for Finite Element SpMV


Poster Type: ACM SRC Posters

Author: Budvin Edippuliarachchi (Tufts University), Ponnuswamy Sadayappan (University of Utah), Hari Sundar (Tufts University)

Abstract: Sparse matrix-vector multiplication (SpMV) in finite element methods is memory-bound, with index storage consuming a significant fraction of bandwidth. We exploit mesh connectivity to partition the assembled matrix into element-wise blocks each covering at most B = 256 nodes, enabling 8-bit column indices and 16-bit row pointers, a 4x index compression over standard CSR. We show that the encoding is provably compressive with node duplication overhead bounded by $1 + O(B^{-1/d})$ for d-dimensional meshes. We present three GPU kernels: partitioned CSR, partitioned CSR with shared-memory buffering, and a prefix-sum-based COO variant. We test our kernels on four NVIDIA GPU generations and show that the proposed encoding results in a faster SpMV operation achieving 1.4x-1.7x speedup over cuSPARSE CSR. We further show that COO-variant is more suitable for high-bandwidth-equipped GPU systems. A direct CPU implementation of partitioning CSR kernel with vectorization achieves up to 2x speedup over Intel-MKL for SpMV operation.

Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing