Search papers, labs, and topics across Lattice.
This paper introduces DB-SpMSpV, a dual-view blocked framework for Sparse Matrix-Sparse Vector Multiplication (SpMSpV) tailored for dynamic GPU workloads. By partitioning the matrix into fixed-size 2D blocks and employing a flexible traversal strategy based on input sparsity, DB-SpMSpV significantly reduces irregular memory accesses and enhances performance. The framework achieves remarkable speedups, with average improvements of 5.48脳 to 64.34脳 over existing methods like cuSPARSE, demonstrating its effectiveness across various GPU architectures and applications in graph traversal and model inference.
Achieving up to 64.34脳 speedup in dynamic GPU workloads, DB-SpMSpV redefines the efficiency of Sparse Matrix-Sparse Vector Multiplication.
Sparse Matrix-Sparse Vector Multiplication (SpMSpV) is a core primitive in graph traversal, sparse linear algebra, and sparse model inference. Its input vector is often dynamically sparse, so the best GPU execution path depends on both global sparsity and the local vector-block distribution. Existing GPU SpMSpV methods often bind storage layouts, push/pull traversal, and kernels together, making fine-grained adaptation difficult without extra storage or scheduling overhead. This paper presents DB-SpMSpV, a dual-view blocked SpMSpV framework for dynamic GPU workloads. DB-SpMSpV partitions the matrix into fixed-size 2D blocks, maintains block-level CSR/CSC views at the high level, and reuses a single low-level block payload to support both row-driven pull and column-driven push. At runtime, it selects the global traversal path based on input block sparsity, chooses block microkernels from the local matrix/vector block structure, and uses load balancing, asynchronous prefetching, and hierarchical writeback to reduce irregular memory accesses, writeback conflicts, and load imbalance. We further integrate the framework into DB-BFS and DB-Decoding. We evaluate DB-SpMSpV on NVIDIA A100 and RTX 4090 using SuiteSparse matrices, symmetric graphs, and three open-source LLMs. Across input sparsities, DB-SpMSpV achieves average speedups of 5.48$\times$--64.34$\times$ over cuSPARSE and 2.36$\times$--14.01$\times$ over TileSpMSpV on A100, with similar gains on RTX 4090. DB-BFS further improves end-to-end graph traversal by 2.66$\times$ over TileBFS on A100 and 3.60$\times$ on RTX 4090 on average, while DB-Decoding accelerates single-token linear layers by up to 4.50$\times$.
