Seventeen years after its publication, "Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors" by Nathan Bell and Michael Garland has won the SC26 Test of Time Award. The paper, presented at SC09 in Portland when general-purpose GPU computing was still in its infancy — CUDA had been introduced only a few years earlier — established techniques for mapping irregular sparse computations onto highly parallel hardware that remain influential across today's HPC and AI software stacks.

The award recognizes research published at the SC conference series that has continued to shape the field long after its original appearance. Bell and Garland's work tackled a problem that has only grown more relevant: how to extract efficiency from parallel processors when the problem itself resists regularity.

Finding structure in sparsity

Sparse matrix-vector multiplication (SpMV) sits at the core of computational science. It appears repeatedly in methods for solving large-scale linear systems and eigenvalue problems across scientific and engineering applications. But sparse matrices present a structural challenge for parallel hardware. Unlike dense matrices, where data and computation follow predictable patterns, sparse matrices range from highly regular to highly irregular, and GPUs of the era needed enough fine-grained parallelism while keeping execution and memory access sufficiently uniform to perform well.

Rather than treating all sparse matrices identically, Bell and Garland examined how different sparsity patterns suit different data formats. The paper analyzed formats including DIA, ELL, CSR and COO, and showed how computation could be organized to reduce the execution and memory divergence that irregular matrix structures cause.

The results proved sparse computation could map successfully onto GPU architectures. On the NVIDIA GeForce GTX 285 used in the study, the proposed techniques achieved high memory bandwidth utilization and substantial performance gains over comparison systems available at the time. The lasting contribution, however, went beyond benchmark numbers: the work demonstrated that understanding a problem's structure can matter as much as the hardware used to solve it.

Twenty years of sparsity on GPUs

At SC26, Garland will revisit the work in a retrospective talk, "Twenty Years of Sparsity on GPUs." Garland joined NVIDIA in 2006 as a founding member of NVIDIA Research and now serves as Senior Director of Programming Research, leading a group spanning parallel algorithms, programming languages, compilers and runtime systems, and low-level hardware/software interfaces.

SpMV was among the first CUDA kernels Garland attempted. The SIMT execution model made a working implementation relatively straightforward; achieving genuinely high throughput was a different matter. A few years later, he and Bell built kernels that delivered high performance while making effective use of GPU memory bandwidth — work that became the SC09 paper.

Looking back, Garland highlights two ideas from the research: choosing the right data structure to exploit known matrix structure makes high performance far easier to achieve, and irregularity can be managed effectively when it is relatively rare.

From early CUDA to today

Both authors continued to shape GPU computing well beyond the paper. Bell is now a Principal Engineer at Google, working on Search. During his time as a Research Scientist at NVIDIA Research, he specialized in sparse linear algebra and parallel programming models and co-developed the Thrust and Cusp libraries.

Garland and his team have worked across the GPU software stack, producing high-performance sparse matrix methods; algorithm libraries including Thrust and CUB; Python frameworks for programming large numbers of GPUs; new approaches to tensor layouts; and methods for scheduling AI kernels. Many of these innovations have become foundational components of the CUDA ecosystem.

The GeForce GTX 285 belongs to another era of computing. The questions the paper raised do not. How should data be represented? Where is the regularity in an irregular problem? How should work be organized to exploit increasingly parallel hardware? Those questions have followed GPU computing from its early years into today's HPC and AI systems — and Garland's SC26 retrospective will revisit the original lessons, notable developments since, and the challenges that remain as sparsity continues to define the frontier of GPU performance.