SLAWS: Spatial Locality Analysis and Workload Orchestration for Sparse Matrix Multiplication

Multiplying two sparse matrices (SpMSpM) drives graph processing and scientific computing, but the nonzeros scatter so unevenly that fixed-dataflow accelerators either waste chip time or miss reuse — this paper (Guoyu Li, Zheng Guan, Kun Wang, and colleagues) presents SLAWS, a general-purpose SpMSpM accelerator that analyzes each matrix's sparsity pattern and treats the two operands differently — a Pass-Aware strategy tunes memory access for the left matrix and a Shuffle-Compare strategy balances the workload for the right one by approximating the top-K outputs per cycle — reaching 1.46 and 1.43 times the speed of two state-of-the-art accelerators and 1.55 times a GPU.

The argument in one glance

Problem

Multiplying two sparse matrices is everywhere, yet stubbornly hard to do fast

Sparse matrix-sparse matrix multiplication, written SpMSpM, multiplies two matrices that are mostly zeros. It sits at the heart of high-performance computing, linear algebra, and graph processing — many graph algorithms are, underneath, exactly this operation on a sparse adjacency matrix. Because most entries are zero, the sensible thing is to store and compute only the nonzeros, and skip the rest. But that is precisely what makes it hard for hardware. The nonzeros are scattered unevenly and unpredictably across the matrices, and the distribution varies wildly from one matrix to the next: some rows are dense, others nearly empty, and the pattern of which entries are present is different every time. This irregularity wrecks the things a processor relies on to go fast. Memory accesses become scattered rather than sequential, so data locality suffers; the amount of useful work per row varies enormously, so some compute units sit idle while others are swamped; and it is hard to reuse data that has been fetched, because which values meet which is data-dependent. The result is that a computation with very few actual multiplications can still run slowly, bottlenecked not by arithmetic but by irregular data movement and imbalance.
What people did

Build a specialized accelerator tuned to one sparse dataflow

A common answer is a custom hardware accelerator for SpMSpM. There are a few canonical ways to schedule the multiplication — often called dataflows — such as inner-product, outer-product, and row-wise (Gustavson) styles, each of which fetches, multiplies, and accumulates the operands in a different order, and each of which favors a different kind of matrix. So accelerators are typically designed around one chosen dataflow, laying out on-chip memory and compute to make that particular schedule efficient. The idea is that by committing to a specific dataflow, the hardware can be tightly optimized for it.
Why it fell short

Committing to one dataflow sacrifices generality and leaves reuse on the table

The trouble is that no single dataflow is best for every matrix. Because the distribution of nonzeros varies so much, a schedule that is efficient for one sparsity pattern is wasteful for another — so an accelerator hard-wired to a specific dataflow buys peak performance on its favored inputs by sacrificing generality on the rest, and it fails to fully exploit the data reuse opportunities that a different schedule would expose. There is a further subtlety the abstract highlights: the two matrix operands are not symmetric. The left multiplicand and the right multiplicand play different roles in the computation and are accessed in different ways, so treating both with one uniform strategy leaves performance on the table for at least one of them. What was missing was an accelerator general enough to handle diverse sparsity patterns, exploit multiple reuse opportunities rather than one, and give each operand a strategy suited to its role.
This paper's idea

Analyze each matrix's sparsity and give each operand its own strategy

SLAWS is an efficient, general-purpose accelerator architecture for SpMSpM. Instead of committing to a single dataflow, it accelerates computation by analyzing the distinct sparsity patterns of its inputs and leveraging various data reuse opportunities. Its central move is to treat the two operands differently, because they occupy different positions in the multiplication. For the left multiplicand, SLAWS uses a Pass-Aware strategy: it analyzes the matrix structure, identifies unique sparsity patterns, and optimizes memory access accordingly — the spatial-locality-analysis half of the name. For the right multiplicand, it uses a Shuffle-Compare strategy: it dynamically balances the multiplication workload across the computing units, and by approximating the top-K outputs per cycle it minimizes idle time and keeps the work evenly distributed — the workload-orchestration half. Together these let one architecture adapt to varied sparsity instead of being locked to a single schedule. In the authors' experiments, SLAWS achieves 1.46 and 1.43 times speedups over two state-of-the-art accelerators, and 1.55 times over a GPU.

Why this problem is worth solving

The reason SpMSpM is a hardware problem and not just a math problem is that its cost is dominated by irregular data movement, not arithmetic.

Multiplying two dense matrices is a model citizen for hardware: the access pattern is completely regular, every value is reused a predictable number of times, and the work divides evenly across compute units. Sparsity destroys all three properties at once. Storing only the nonzeros saves enormous arithmetic, but it means the data no longer lives at predictable addresses — you must chase indices to find which nonzeros exist and which of them actually meet during the multiplication. That makes memory accesses scattered instead of sequential, so caches and on-chip buffers work poorly. It makes reuse data-dependent, so it is hard to know in advance which fetched value will be needed again. And because some rows have many nonzeros and others almost none, the work is wildly unbalanced, leaving compute units idle. So the bottleneck shifts from the multiplications themselves — of which there are few — to the irregular movement and scheduling of the data around them. This is why a general, efficient SpMSpM accelerator is valuable: the applications that use it (scientific computing, graph analytics) are important and data-hungry, and the inefficiency being attacked is structural, not incidental.

A second idea worth drawing out is that generality and specialization need not be opposites if the hardware can adapt to what it sees.

The usual assumption is a trade-off: you can have a specialized accelerator that is fast on one kind of input, or a general one that is mediocre on everything. SLAWS’s framing is that for sparse matrix multiplication the specialization that matters is a choice of dataflow, and the right dataflow depends on the sparsity pattern — which the hardware can inspect. So rather than freezing that choice at design time, an accelerator can analyze the actual structure of the matrices it is given and adapt its handling to them, capturing the reuse a fixed schedule would miss. The abstract adds a second lever: recognizing that the two operands are different and deserve different strategies — memory-access optimization for the left, dynamic load balancing for the right — rather than one uniform treatment. Generality here comes not from being agnostic to structure but from being responsive to it. That is the difference between a design that is efficient only on its favored inputs and one that stays efficient across the highly variable matrices real workloads actually contain.

What people did before, and where it broke

Single-dataflow SpMSpM accelerators. Design the chip around one schedule — inner-product, outer-product, or row-wise (Gustavson) — and optimize memory and compute for it. Where it broke. No single dataflow is best across the highly variable sparsity of real matrices, so peak performance on favored inputs comes at the cost of generality and missed reuse elsewhere.
Uniform handling of both operands. Treat the left and right matrices with the same strategy. Where it broke. The two operands occupy different positions in the multiplication and are accessed differently, so one uniform scheme underserves at least one of them.
Reuse tied to a fixed schedule. Exploit whatever data reuse the chosen dataflow happens to expose. Where it broke. Different sparsity patterns expose different reuse opportunities, and a design locked to one schedule cannot capture the ones its schedule hides.
General processors and GPUs. Run SpMSpM on flexible hardware that is not specialized for sparse structure. Where it broke. Their generality is not sparsity-aware, so irregular access and load imbalance leave them slower than a structure-aware accelerator — the paper reports SLAWS is 1.55 times faster than a GPU.
The gap. No accelerator combined generality across sparsity patterns, exploitation of multiple reuse opportunities, and operand-specific strategies matched to the different roles of the two matrices.

How SLAWS works

From a fixed-dataflow accelerator to structure-aware, operand-specific SpMSpM

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

The idea

Adapt to the sparsity pattern instead of freezing one dataflow. SLAWS analyzes the distinct structure of the matrices it is given and leverages whatever reuse that structure exposes, rather than committing at design time to a single inner-, outer-, or row-wise schedule. Building a sparse matrix multiplication accelerator that is not locked to one dataflow but adapts its handling to the input is the same generality-through-flexibility idea the work on a multi-dataflow sparse-sparse matrix multiplication accelerator (Flexagon) covered elsewhere on this site is built around, choosing the schedule that suits the data instead of forcing every matrix through one. SLAWS pushes that adaptivity down to the level of analyzing each operand’s pattern and reacting to it.

Reorganize sparse data so memory access becomes local. The Pass-Aware half of SLAWS analyzes the left matrix’s structure specifically to optimize its memory access — turning the scattered accesses that irregular sparsity produces into more local, efficient ones. Restructuring how sparse data is traversed so that a memory hierarchy is used well, rather than accepting the scatter that raw sparsity imposes, is the same locality-first instinct the work on accelerating sparse data orchestration through structure-aware tiling (dynamic reflexive tiling) covered elsewhere on this site pursues, reshaping the access pattern to fit the hardware. SLAWS applies that locality analysis to the left operand as its dedicated strategy.

Balance the work dynamically so no compute unit idles. The Shuffle-Compare half distributes the right matrix’s multiplication workload across the computing units and approximates the top-K outputs per cycle to keep them evenly loaded. Confronting the load imbalance that irregular data creates by spreading work dynamically across units, rather than assigning it statically and letting some units stall, is the same balancing concern the work on co-optimizing data access and load balance in near-data processing (ABNDP) covered elsewhere on this site centers on, keeping every unit productive. SLAWS makes that dynamic balancing the defining strategy for its right operand.

Following a multiplication through SLAWS

How SLAWS handles the two operands of one SpMSpM

An illustration, at the level the paper's abstract describes, of SLAWS's operand-specific strategies. Internal mechanism details are in the full paper, which was not available for this explainer.

Step 1 of 5

Receive the two sparse operands

SLAWS is given the left multiplicand and the right multiplicand — two sparse matrices whose nonzeros are distributed irregularly and differently from each other. Because the operands play different roles, SLAWS does not treat them the same way.

The asymmetry of the two operands is the premise the design is built on.

Why it works

Analyzing structure beats assuming it. A fixed dataflow is efficient only on its favored inputs → but inspecting each matrix’s actual sparsity pattern → so SLAWS captures reuse opportunities a single frozen schedule would miss.
Different operands deserve different strategies. One uniform scheme underserves at least one operand → but giving the left and right matrices roles-matched strategies → so each is handled by a method suited to how it is actually accessed.
Locality analysis tames scattered access. Irregular sparsity turns memory access into random scatter → but Pass-Aware analysis of the left matrix’s structure → so accesses become more local and the memory hierarchy is used well.
Dynamic balancing keeps units busy. Uneven nonzero counts leave some compute units idle → but Shuffle-Compare spreading the right operand’s workload across units → so idle time falls and utilization rises.
Prioritizing the top-K sustains the balance. Blindly issuing work lets imbalance creep back each cycle → but approximating the top-K outputs per cycle → so the most useful work keeps flowing and the load stays even.

What it costs (trade-offs and scope)

Analysis and orchestration are not free. Analyzing matrix structure and dynamically balancing workload require dedicated logic and effort on chip; the abstract reports the speedups but does not quantify this overhead here.
Top-K is an approximation. Approximating the top-K outputs per cycle trades exact scheduling for balance and speed, and how that approximation affects results or accuracy is a detail for the full paper, not the abstract.
General-purpose is not always peak. A design built for generality across sparsity patterns may not beat a perfectly-matched specialized accelerator on that accelerator’s single favored pattern; the reported gains are aggregate speedups over the evaluated set.
Numbers are tied to specific baselines and workloads. The 1.46, 1.43, and 1.55 times speedups are measured against two particular accelerators and one GPU on the paper’s benchmarks; other matrices, baselines, or settings may give different results.
This explainer is built from the abstract only. The internal mechanisms of Pass-Aware and Shuffle-Compare, the exact dataflow handling, and any area, power, or accuracy figures are not available here and should be read in the full paper.

The comparison

Accelerating sparse matrix-sparse matrix multiplication

Property	Fixed-dataflow accelerator	GPU	SLAWS
Generality across sparsity patterns
Data reuse exploited
Handling of the two operands
Load balancing
Reported speedup

A comparison of ways to accelerate SpMSpM. Fixed-dataflow accelerators optimize one schedule and are fast on favored inputs but miss reuse on others; GPUs are general but not tuned to sparse structure. SLAWS analyzes each matrix's sparsity pattern and gives the two operands different strategies — a Pass-Aware strategy that optimizes memory access for the left matrix and a Shuffle-Compare strategy that dynamically balances the right matrix's workload via top-K approximation — reporting 1.46 and 1.43 times speedups over two state-of-the-art accelerators and 1.55 times over a GPU. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based only on the paper’s abstract and TLDR (obtained via Semantic Scholar); the full text was not available — the paper is behind the ACM Digital Library with no open preprint reachable at the time of writing, so this page is marked a draft. What is reported here is what the abstract states: SLAWS is an efficient, general-purpose accelerator architecture for sparse matrix-sparse matrix multiplication (SpMSpM) that accelerates computation by analyzing distinct sparsity patterns and leveraging various data reuse opportunities. It introduces two strategies for the two operand positions: a Pass-Aware strategy for the left multiplicand that analyzes matrix structure, identifies unique sparsity patterns, and optimizes memory access; and a Shuffle-Compare strategy for the right multiplicand that dynamically balances the multiplication workload across computing units, approximating the top-K outputs per cycle to minimize idle time. The reported results are 1.46 and 1.43 times speedups over two state-of-the-art accelerators and 1.55 times over a GPU. Everything beyond these claims — how Pass-Aware and Shuffle-Compare are implemented, the exact dataflow handling, the benchmark set, and any area, power, or accuracy figures — is not covered by the abstract and should be read in the full paper. The background on SpMSpM, dataflows, and sparse acceleration is standard context, and the step-by-step walkthrough is an illustration at the abstract’s level, not a verbatim trace of the paper’s mechanism.

Background

Why sparse matrix accelerators keep circling back to dataflow, reuse, and balance

It helps to see SLAWS within a long line of sparse-accelerator research. The field has learned that the hard part of sparse matrix multiplication is not the arithmetic but the data: how it is scheduled (the dataflow), how much of it can be reused once fetched, and how evenly the work spreads across compute units. Different designs pick different points in that space — some commit to an outer-product schedule for its reuse properties, some to a row-wise schedule for its locality, some add adaptivity so the schedule can change with the input. The recurring lesson is that because real sparse matrices vary so much, rigidity is costly: a design frozen to one schedule wins on some matrices and loses on others. SLAWS’s contribution is to lean hard into adaptivity and asymmetry — analyze the sparsity pattern rather than assume it, and give each operand a strategy matched to its role rather than one uniform treatment. This drive to make a sparse matrix multiplication accelerator fast by choosing its dataflow to fit the data, rather than forcing all data through one fixed schedule, is the same terrain the work on accelerating sparse matrix multiplication with an adaptive dataflow (Spada) covered elsewhere on this site occupies, adapting the schedule to the sparsity at hand. SLAWS’s particular angle is to split that adaptivity across the two operands, pairing spatial-locality analysis for one with dynamic workload orchestration for the other.

If you remember only three things

1. Sparse matrix-sparse matrix multiplication (SpMSpM) underlies high-performance computing, linear algebra, and graph processing, but the nonzero elements are distributed so irregularly and so variably from one matrix to the next that the bottleneck is data movement and load imbalance, not arithmetic. Existing sparse accelerators are typically built around one fixed dataflow (inner-, outer-, or row-wise), which makes them fast on their favored inputs but sacrifices generality and misses the data reuse that a different schedule would expose. A further subtlety is that the two matrix operands play different roles and are accessed differently, so handling both with one uniform strategy leaves performance on the table.
2. SLAWS is a general-purpose SpMSpM accelerator that, instead of freezing a single dataflow, analyzes the distinct sparsity patterns of its inputs to leverage various reuse opportunities, and gives each operand its own strategy. For the left multiplicand, a Pass-Aware strategy analyzes the matrix structure, identifies unique sparsity patterns, and optimizes memory access — the spatial-locality-analysis half. For the right multiplicand, a Shuffle-Compare strategy dynamically balances the multiplication workload across compute units and approximates the top-K outputs per cycle to minimize idle time — the workload-orchestration half. Together they let one architecture adapt to varied sparsity rather than being locked to a single schedule.
3. In the authors' experiments, SLAWS reaches 1.46 and 1.43 times the speed of two state-of-the-art accelerators and 1.55 times a GPU. This explainer is drawn only from the paper's abstract — the full text was not reachable, so the internal workings of Pass-Aware and Shuffle-Compare, the exact dataflow handling, the benchmark set, and any area, power, or accuracy figures are not covered here and should be read in the full paper. What the abstract makes clear is the design philosophy: generality through analyzing sparsity rather than assuming it, and efficiency through matching each operand to a strategy that fits its role.

Check yourself

Check your understanding

1. Why is sparse matrix-sparse matrix multiplication (SpMSpM) hard to run efficiently on hardware?
2. What is the limitation of fixed-dataflow SpMSpM accelerators that SLAWS targets?
3. How does SLAWS handle the two matrix operands differently?
4. What speedups does SLAWS report, and how should they be read?

Sources

The paper is “SLAWS: Spatial Locality Analysis and Workload Orchestration for Sparse Matrix Multiplication” by Guoyu Li, Zheng Guan, Beichen Zhang, Junhui Yu, and Kun Wang, published at ASPLOS 2026, DOI 10.1145/3779212.3790222.

This explainer is written only from the paper’s abstract and TLDR, obtained via the Semantic Scholar API; the full text was not available, because the paper is behind the ACM Digital Library and no open preprint was reachable at the time of writing. Accordingly this page is marked a draft. The abstract describes SLAWS as an efficient, general-purpose accelerator for sparse matrix-sparse matrix multiplication (SpMSpM) that analyzes distinct sparsity patterns and leverages various data reuse opportunities, using a Pass-Aware strategy for the left multiplicand (analyzing matrix structure, identifying unique sparsity patterns, and optimizing memory access) and a Shuffle-Compare strategy for the right multiplicand (dynamically balancing the multiplication workload across computing units and approximating the top-K outputs per cycle to minimize idle time). The reported results are 1.46 and 1.43 times speedups over two state-of-the-art accelerators and 1.55 times over a GPU. Background on SpMSpM, dataflows, data reuse, and load balancing is standard context. All quantitative claims are the paper’s own; the internal mechanisms and full evaluation should be confirmed in the paper.