RASSM: Residue-based Acceleration of Single Sparse Matrix Computation via Adaptive Tiling

Kernels that multiply or solve with a single sparse matrix — the mostly-empty tables behind graph analytics, finite-element solvers, and the GNNs and LLMs of machine learning — run slowly because the few scattered nonzeros give terrible cache reuse, and the usual fix of tiling the work to fit in cache is undermined by uniform tiles that waste space on a wildly irregular nonzero pattern; this paper (Georgia Tech — Anirudh Jain, Pulkit Gupta, Thomas M. Conte) presents RASSM, which first builds a residue matrix, a compact map of where the nonzeros actually sit, and uses it to choose adaptive two-dimensional tile sizes that pack the cache well and exploit both spatial and temporal locality, cutting data movement and running SpMM 1.30 to 1.38 times faster than strong baselines like Intel MKL and ASpT.

The argument in one glance

Problem

Sparse matrix kernels are everywhere, but their scattered nonzeros wreck the cache

A huge class of computations rests on kernels that operate on a single sparse matrix — a matrix that is mostly zeros. Sparse matrix times dense matrix (SpMM), sampled dense-dense multiplication (SDDMM), sparse matrix-vector (SpMV), and sparse triangular solve (SpTS) are the backbone of data analytics, graph processing, finite-element analysis, and machine learning, including graph neural networks and large language models. Because the matrix is mostly zeros, only the few nonzeros are stored and computed on, which saves memory but creates a performance problem: those nonzeros are scattered irregularly, so when the kernel touches them it pulls in rows or cache lines of the dense operand it can barely reuse before they are evicted. The computation ends up limited by moving data through the memory hierarchy rather than by arithmetic, so the challenge is to reorganize the work so the cache is actually used well.
What people did

Tile the computation into cache-sized blocks

The standard tool for cache reuse is tiling: break the computation into blocks (tiles) sized so that the data a tile touches fits in cache and gets reused before it is evicted. Libraries and prior sparse-tiling schemes — Intel MKL, J-Stream, ASpT, and CSF-4 variants with uniform tile shapes or uniform occupancy — apply tiling to sparse kernels, choosing tile dimensions to try to keep the working set resident.
Why it fell short

Uniform tiles ignore where the nonzeros actually are

Tiling a sparse matrix well is hard precisely because the nonzeros are irregular. A uniform tile shape gives every tile the same dimensions regardless of how many nonzeros fall inside it, so some tiles are packed while others are nearly empty, wasting the cache they occupy; a uniform occupancy gives every tile the same number of nonzeros but lets their shapes vary in ways that hurt the reuse of the dense operand. Either way, a fixed tiling policy is blind to the specific pattern of nonzeros in the matrix at hand, so it cannot consistently maximize how much useful data sits in cache. What is missing is a way to see the nonzero pattern compactly enough to choose tile sizes tailored to that pattern, optimizing both spatial locality (the data a tile needs being contiguous) and temporal locality (that data being reused while resident) at once.
This paper's idea

Summarize the nonzeros in a residue matrix, then tile adaptively from it

RASSM is an input-dependent, adaptive two-dimensional tiling technique for single-sparse-matrix kernels. Its key idea is the residue matrix: a compact data structure that captures the pattern of nonzeros in the sparse matrix — a downsampled map of where the nonzeros are, far smaller than the matrix itself. With the residue matrix in hand, RASSM can make intelligent decisions about adaptive tile sizes rather than fixing them, choosing per-region tile dimensions that increase how fully the cache is occupied by useful data. Because the residue captures the pattern in two dimensions, RASSM can optimize across both spatial locality and temporal locality, and it offers a spatial analysis and a stronger temporal analysis for choosing tiles. The effect is less data movement and higher performance than prior techniques: for SpMM on commodity server CPUs, RASSM reports up to 1.30 times over Intel MKL, 1.32 times over J-Stream, and 1.20 times over ASpT with spatial analysis, improving to 1.36, 1.38, and 1.26 times respectively with temporal analysis.

Why this problem is worth solving

Sparse matrix kernels are a rare case where a single family of routines sits under an enormous range of important applications.

A sparse matrix is one in which the overwhelming majority of entries are zero, so only the nonzeros are stored, in compressed formats that list where each nonzero sits and its value. Many core computations reduce to operating on one such matrix: SpMM multiplies a sparse matrix by a dense matrix, SDDMM samples a dense-dense product at the sparse matrix’s nonzero positions, SpMV multiplies a sparse matrix by a vector, and sparse triangular solve solves a triangular sparse system. These single-sparse-matrix kernels are not niche; they are the computational backbone of graph processing (a graph is an adjacency matrix, almost always sparse), finite-element analysis (physical simulations produce huge sparse systems), data analytics, and modern machine learning, where graph neural networks and even large language models lean on sparse operations. Because so much rides on them, even modest speedups compound across the whole ecosystem, and because they run on everything from laptops to supercomputers, improving them on commodity CPUs — as this work targets — has broad reach. The reason they are worth dedicated effort is not that the math is complex but that their performance is dominated by memory behavior, so the payoff comes from systems and architecture ideas about data movement rather than from better numerics.

The specific reason they underperform is a mismatch between irregular data and a cache that rewards regularity.

A cache speeds up computation by keeping recently or nearby data close, which pays off when a program exhibits locality: spatial locality, using data that sits near data it just used, and temporal locality, reusing the same data soon. Dense computations are naturally rich in both, which is why they run fast. Sparse computations break this. The nonzeros are scattered unpredictably through the matrix, so accessing them jumps around the corresponding rows or columns of the dense operand, pulling cache lines that hold mostly data the kernel will not reuse before eviction. The arithmetic per byte moved is low, so the kernel spends its time waiting on memory, not computing. Tiling is the main lever against this: by restricting the computation to a block small enough that its footprint fits in cache, you force reuse within the block before moving on. But tiling only helps if the tiles are chosen to match how the data is actually laid out; on a sparse matrix, where the density varies wildly from region to region, a single tile size cannot fit the pattern everywhere. That is why an adaptive, pattern-aware tiling — one that knows where the nonzeros are before deciding how to tile — is the missing piece, and it is exactly what a compact summary of the nonzero pattern would enable.

What people did before, and where it broke

General dense-tuned libraries (Intel MKL). Use a highly optimized library routine for the sparse kernel. Where it broke. These are strong but do not adapt their tiling to the specific nonzero pattern of the input, so they leave locality on the table for irregular matrices.
Streaming and reordering schemes (J-Stream). Reorganize the traversal of the sparse matrix to improve reuse. Where it broke. They improve some access patterns but still do not choose two-dimensional tile sizes tailored to the matrix’s nonzero distribution, limiting the cache occupancy achieved.
Adaptive sparse tiling (ASpT). Adapt tiling to the sparse structure to raise reuse. Where it broke. It is a step toward input-dependence, but RASSM reports outperforming it, indicating room to capture the nonzero pattern more precisely and optimize both spatial and temporal locality together.
Uniform-shape and uniform-occupancy tiling (CSF-4 variants). Fix either the tile dimensions or the number of nonzeros per tile across the matrix. Where it broke. Uniform shape wastes cache on sparse regions and packs dense ones poorly; uniform occupancy lets tile shapes vary in ways that hurt dense-operand reuse. Neither adapts both dimensions to the pattern.
The gap. No technique built a compact representation of the nonzero pattern and used it to choose adaptive two-dimensional tile sizes that maximize cache occupancy across both spatial and temporal locality, which is what consistently good sparse tiling requires.

How RASSM works

Tiling a sparse kernel adaptively using a compact map of its nonzeros

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

See the sparsity pattern compactly before deciding how to tile. The organizing move in RASSM is to make tiling decisions from an explicit, compact picture of where the nonzeros are, rather than from a fixed rule. The residue matrix is that picture: a small summary of the nonzero pattern that RASSM can consult cheaply to see which regions of the matrix are dense and which are sparse. Because the decision is driven by the actual input, the tiling becomes adaptive and input-dependent instead of one-size-fits-all. Tailoring how a sparse computation is organized to the specific structure of its data, rather than applying a generic schedule, is the same principle the work on composable abstractions for sparse compilation in deep learning covered elsewhere on this site is built on, making the sparsity structure a first-class input to how the computation is laid out. RASSM’s contribution is to distill that structure into a residue and use it specifically to size cache tiles.

Use a small index of the nonzeros to make the big decisions. Consulting the full sparse matrix to plan tiling would be expensive, so RASSM instead keeps a compact residue that captures the pattern at low cost, and lets that small structure drive the choice of tile sizes. This is the familiar idea of building a lightweight summary that stands in for a large, unwieldy data structure when you only need to reason about its shape, not its every entry. Maintaining a compact structure that captures where the meaningful data sits so the system can navigate a mostly-empty space efficiently is the same discipline the work on caching multi-level indexes for sparse data in domain-specific architectures covered elsewhere on this site is built on, using a small index to find the few values that matter. RASSM applies that instinct to tiling, letting the residue matrix, not the full matrix, decide how the cache is packed.

Optimize both kinds of locality at once, because sparse kernels need both. A tiling scheme that helps only spatial locality, or only temporal locality, leaves performance behind, because the cost of sparse kernels comes from failing at both. RASSM uses the two-dimensional residue to choose tiles that improve spatial locality — the data a tile needs being contiguous and fully used — and temporal locality — that data being reused while resident — offering a spatial analysis and a stronger temporal analysis. Squeezing more useful work out of every byte moved by attacking the reuse of sparse-matrix data directly is the same goal the work on accelerating sparse matrix-vector multiplication through better utilization covered elsewhere on this site pursues, raising how much of the fetched data actually contributes. RASSM pursues it through adaptive tiling guided by the residue, so both locality dimensions improve together and data movement drops.

Following a matrix through RASSM

Accelerating an SpMM on an irregular sparse matrix

An illustrative trace, based on the paper's abstract, of how RASSM tiles a sparse kernel using the residue matrix. Internal details beyond the abstract were not available for this draft.

Step 1 of 5

Start from a sparse matrix and a dense operand

The kernel must multiply a large, mostly-zero sparse matrix by a dense matrix (SpMM). The nonzeros are scattered irregularly, so a naive traversal fetches dense-operand data that is barely reused, making the kernel memory-bound.

The bottleneck is data movement through the cache hierarchy, not arithmetic.

Why it works

A compact residue makes pattern-aware tiling affordable. Consulting the full sparse matrix to plan tiling would be too costly → but a small residue captures the nonzero pattern cheaply → so RASSM can make input-dependent tile decisions without paying to scan the whole matrix each time.
Adaptive tiles fit dense and sparse regions alike. A uniform tile wastes cache on empty regions and packs dense ones poorly → but sizing tiles per region from the residue matches each region’s density → so more of the cache holds useful data across the whole matrix.
Two-dimensional decisions capture the real layout. Adapting only one tile dimension misses how nonzeros spread in both → but the residue is two-dimensional so RASSM sizes tiles in both directions → so the tiling reflects the actual shape of the nonzero pattern.
Serving both localities cuts more data movement. Optimizing only spatial or only temporal locality leaves reuse behind → but the residue lets RASSM target both, via spatial and temporal analyses → so fetched data is both contiguous and reused, lowering total traffic.
Less data movement is exactly what sparse kernels need. These kernels are bottlenecked by memory, not arithmetic → but higher cache occupancy means fewer trips to slower memory → so the end-to-end kernel runs faster, the reported 1.30 to 1.38 times over strong baselines.

What it costs (trade-offs and scope)

This is a draft built from the paper’s abstract. The full paper was behind a publisher access wall for this draft (no arXiv version, no open-access or author copy located, and the ACM Digital Library returned a bot-verification challenge), so this account is assembled from the paper’s complete abstract plus standard background on sparse kernels and cache tiling. The exact construction of the residue matrix, the tile-selection algorithms, the difference between the spatial and temporal analyses, and the evaluation setup are not reproduced here and should be read from the paper.
Building the residue and planning tiles is preprocessing overhead. RASSM must scan the matrix to form the residue and then choose tiles before executing; this is a one-time cost that pays off when the tiled kernel is run enough to amortize it, and the abstract does not detail that break-even in this draft.
The reported speedups are the abstract’s own, for SpMM on CPUs. The 1.30 to 1.38 times figures are for SpMM on commodity server CPUs against specific baselines (MKL, J-Stream, ASpT, CSF-4 variants); results for other kernels (SDDMM, SpMV, SpTS), matrices, and hardware are not quantified in this draft.
The benefit depends on the sparsity pattern being exploitable. Adaptive tiling helps most when density varies enough across the matrix for per-region tile sizes to matter; matrices whose nonzeros are near-uniform, or so irregular that no tiling captures them, would benefit less.
It targets single-sparse-matrix kernels on CPUs. RASSM is framed for SSMKs and evaluated on commodity server CPUs; how the residue-based approach transfers to GPUs, accelerators, or multi-sparse-operand kernels is not addressed by the abstract.

The evaluation

Tiling a single-sparse-matrix kernel (SpMM) for cache reuse

Property	Uniform tiling (CSF-4)	Adaptive sparse tiling (ASpT)	RASSM
Adapts to the nonzero pattern
Compact pattern summary
Two-dimensional adaptive tiles
Optimizes spatial and temporal locality
Reported SpMM speedup (per abstract)

A qualitative comparison based on the paper's abstract; the paper's main body, including the residue construction, the tile-selection algorithms, and the full evaluation, was not available for this draft. The reported SpMM speedups (up to 1.30-1.38 times over MKL, J-Stream, and ASpT, and 1.10-1.17 times over CSF-4 variants) are the abstract's own.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is an honest draft assembled from the paper’s complete abstract plus standard background on sparse matrix kernels and cache tiling; the full text was not accessible (no arXiv preprint, no open-access or author copy found, and the ACM Digital Library version returned a bot-verification challenge), so the internal design is not reproduced. What is solid and comes directly from the abstract: single-sparse-matrix kernels (SpMM, SDDMM, SpMV, SpTS) underpin data analytics, graph processing, finite-element analysis, and machine learning; RASSM is an input-dependent, adaptive two-dimensional tiling technique that leverages a residue matrix, a data structure that compactly captures the pattern of nonzeros; residues enable intelligent adaptive tile-size decisions that increase cache occupancy and allow optimizations across both spatial and temporal locality, improving data movement and performance; and for SpMM on commodity server CPUs, RASSM reports (with spatial analysis) 1.30 times over MKL, 1.32 times over J-Stream, 1.20 times over ASpT, 1.11 times over CSF-4 uniform-shape, and 1.10 times over CSF-4 uniform-occupancy, improving with temporal analysis to 1.36, 1.38, 1.26, 1.17, and 1.16 times respectively. The explanations of why sparsity destroys cache locality and why adaptive tiling helps are standard background and the natural reading of the abstract, not claims about RASSM’s specific internals. Read the residue construction, the tile-selection algorithms, and the full evaluation in the paper itself; treat this page as a faithful account at the level of the abstract, not of the implementation.

Background

Why sparse computation keeps demanding special treatment

It helps to see RASSM as one more entry in a long effort to make sparse computation fast on hardware that was designed for dense, regular work. Processors and their memory hierarchies reward regularity — contiguous accesses, predictable reuse, full cache lines — and sparse data offers the opposite: scattered nonzeros, unpredictable access, and cache lines mostly wasted. Yet sparse computations are unavoidable, because the real world is sparse: graphs connect each node to only a few others, physical simulations couple only neighboring elements, and even large neural models increasingly exploit sparsity to cut cost. This tension has produced a whole subfield of techniques — specialized formats, reordering, tiling, custom instructions, and dedicated accelerators — all aimed at bridging the gap between irregular data and regularity-loving hardware. The recurring insight is that you must either reshape the computation to the hardware or the hardware to the computation, and often both. That broad drive to specialize the machine and its execution model for the irregular access patterns of sparse work is the same ambition the work on a stream ISA and processor specialization for sparse computation covered elsewhere on this site embodies, redesigning around sparsity rather than tolerating it. RASSM takes the software-and-data-structure route on commodity CPUs, reshaping the tiling to fit the sparsity so the existing cache hierarchy is used well.

If you remember only three things

1. Single-sparse-matrix kernels (SpMM, SDDMM, SpMV, sparse triangular solve) underpin graph processing, finite-element analysis, data analytics, and machine learning including GNNs and LLMs, but they run slowly because a sparse matrix's few nonzeros are scattered irregularly, giving poor cache locality and making the kernels memory-bound. Tiling can improve reuse, but uniform tile shapes or occupancies ignore the actual nonzero pattern, wasting cache on sparse regions and packing dense ones poorly.
2. RASSM is an input-dependent, adaptive two-dimensional tiling technique. It first builds a residue matrix, a compact data structure that captures where the nonzeros sit, and uses that summary to choose adaptive per-region tile sizes that increase cache occupancy, optimizing both spatial locality (contiguous, fully-used data) and temporal locality (data reused while resident) via a spatial analysis and a stronger temporal analysis. This reduces data movement through the memory hierarchy.
3. For SpMM on commodity server CPUs, RASSM reports up to 1.30 times over Intel MKL, 1.32 times over J-Stream, and 1.20 times over ASpT with spatial analysis, improving to 1.36, 1.38, and 1.26 times with temporal analysis (and 1.10-1.17 times over CSF-4 uniform-shape and uniform-occupancy variants). This explainer is a draft from the abstract, so the residue construction, tile-selection algorithms, and full evaluation should be confirmed against the paper; the approach adds preprocessing overhead, depends on an exploitable sparsity pattern, and targets SSMKs on CPUs.

Check yourself

Check your understanding

1. Why do single-sparse-matrix kernels underperform on modern hardware?
2. What is RASSM's central idea?
3. Why does RASSM use a residue matrix instead of tiling directly from the full sparse matrix?
4. What should a reader keep in mind about this explainer, and what did the paper report?

Sources

The paper is “RASSM: Residue-based Acceleration of Single Sparse Matrix Computation via Adaptive Tiling” by Anirudh Jain, Pulkit Gupta, and Thomas M. Conte (Georgia Institute of Technology), published at ASPLOS 2025, DOI 10.1145/3669940.3707219. It is licensed CC BY.

This explainer is a draft. The paper’s main text was not accessible at the time of writing (there is no arXiv preprint, no open-access or author copy was located, and the ACM Digital Library PDF returned a bot-verification challenge), so it is written from the paper’s complete abstract together with standard background on sparse matrix kernels, cache behavior, and tiling. The abstract supplies the problem and approach: single-sparse-matrix kernels such as SpMM, SDDMM, SpMV, and SpTS form the backbone of data analytics, graph processing, finite-element analysis, and machine learning (including GNNs and LLMs); RASSM is an input-dependent, adaptive two-dimensional tiling technique for these kernels; the adaptation leverages a residue matrix, a data structure that compactly captures the pattern of nonzeros in the sparse matrix; with residues it is possible to make intelligent decisions on adaptive tile sizes, resulting in increased cache occupancy, and residues allow optimizations across both spatial and temporal locality, improving data movement and overall performance; and, for SpMM on commodity server CPUs, RASSM reports (with spatial analysis) 1.30 times over MKL, 1.32 times over J-Stream, 1.20 times over ASpT, 1.11 times over CSF-4 uniform-shape, and 1.10 times over CSF-4 uniform-occupancy, improving with temporal analysis to 1.36, 1.38, 1.26, 1.17, and 1.16 times respectively. The explanations of why sparsity destroys locality and why adaptive tiling helps are standard background and the natural reading of the abstract, not claims about RASSM’s specific internal design. The paper’s exact residue construction, tile-selection algorithms, the distinction between the spatial and temporal analyses, hardware configuration, and evaluation setup are not reproduced here and should be read from the paper. No numbers beyond the abstract’s have been introduced.