Multiplying two mostly-empty matrices can be looped three different ways, each wasteful in a different manner, and which one wins depends on where the non-zeros happen to sit — so accelerators that commit to one loop order are fast on some matrices and poor on others; this paper (Illinois Tech and the Chinese Academy of Sciences) makes the loop order a continuous dial rather than a choice, sets it per region of the matrix by briefly trying the options, and then notices that the on-chip cache should evict by how many parallel requests a line is blocking rather than only by how recently it was used.
The argument in one glance
-
Problem
Almost everything is zero, and the rest is scattered
A sparse matrix is one whose entries are overwhelmingly zero, which is the normal shape of data in scientific simulation, graph analytics and increasingly in machine learning. Multiplying two of them is a foundational operation and it behaves badly on ordinary processors — the non-zeros sit at unpredictable positions, so accesses are irregular, caches built for dense regular data miss constantly, and both compute and memory resources sit idle waiting.
-
What people did
Build a dedicated accelerator around one loop order
A matrix product can be computed by ordering the loops three different ways, and each has been the basis of an accelerator. One computes each output element as a dot product. One takes an entire column against an entire row to produce a whole partial matrix. One works a row at a time, combining the rows of the second matrix selected by each non-zero in a row of the first. Each is efficient in a different respect.
-
Why it fell short
The best order depends on the matrix, and no order is safe
Every one of the three has a characteristic waste. Dot products reuse the output perfectly but spend enormous effort discovering that two fetched elements do not have matching indices. The column-times-row form reuses both inputs perfectly but generates partial matrices whose total size exceeds the answer, all of which must be merged. The row-wise form avoids the wasted searching but keeps refetching rows of the second matrix, and makes processing elements contend for the same output row.
-
This paper's idea
Make the trade a dial, set per region, and fix the cache too
This paper (Xiaoyang Lu, Boyu Long, Xiaoming Chen, Yinhe Han and Xian-He Sun) starts from the row-wise form and adds a knob — how aggressively the first matrix is compacted before traversal — which slides continuously between reusing the second input well and keeping processing elements independent. The setting is chosen per band of the matrix by briefly measuring. A second contribution then argues the cache should evict by how much parallelism a line is holding up, not only by how recently it was used.
Why this problem is worth solving
The three loop orders are the vocabulary of this whole field, so they are worth stating plainly.
A
matrix product can be computed as dot products, as a sum of outer products, or row by row,
and on dense data the choice barely matters. On sparse data each becomes a distinct machine
with a distinct failure. The DOT PRODUCT form computes one output element from one row and
one column, so every partial result is accumulated immediately and the output is reused
perfectly — but only elements whose indices match contribute anything, and with most entries
zero the great majority of fetched pairs match nothing, so effort is spent discovering
nothing. The OUTER PRODUCT form takes a column of the first matrix against a row of the
second, producing a whole partial matrix at a time. Each input is fetched exactly once,
which is optimal, but the partial matrices together are larger than the answer and must all
be merged, which dominates. The ROW-WISE form processes one output row at a time, combining
only the rows of the second matrix that a non-zero actually selects, so nothing is fetched
in vain — but those selections are scattered, so the second matrix is refetched constantly,
and several processing elements end up building the same output row and must
synchronise.
The second idea in the paper is about caches and is more general than sparse arithmetic.
A
cache replacement policy normally answers one question — which line will be needed furthest
in the future — and approximates it by recency of use. That treats every miss as equally
costly, which is true only if misses are serviced one at a time. Modern memory systems
overlap many outstanding misses, so what a miss actually costs depends on what else is in
flight and on what work it blocks. A line whose absence stalls many concurrent requests is
expensive to evict; a line whose absence stalls one is cheap. This paper applies that
reasoning to the specific structure of sparse multiplication, where the natural unit is a
FIBER, a compressed list of the non-zeros in one row. Its policy scores each line by a
recency term and by how many lines the fiber it belongs to occupies, evicting the line with
the highest sum, on the argument that a large fiber represents many concurrent accesses that
should not be tied up.
What people did before, and where it broke
-
Fixed dot-product accelerators. Improve the worst part of the dot-product form, the index matching, by representing sparsity as a bitmap so that non-matching pairs can be skipped efficiently.
-
The gap. The form still refetches the second matrix once per row of the first, so input reuse stays poor. On this paper’s benchmark set it is the slowest of the three baselines by a wide margin.
-
Fixed outer-product accelerators. Take the form with optimal input reuse and attack its weakness by engineering the merge of the partial matrices.
-
The gap. The partial matrices are collectively larger than the answer, so memory traffic is driven by merging rather than by the useful work, and the problem grows with matrix size.
-
Adaptive dataflow. The closest prior work makes the loop order itself adjustable, sliding a reshapeable window over the compressed rows and choosing its shape per region from a few profiled passes.
-
The gap. Coordinating that window couples the multipliers together, so a batch of them must finish before any can proceed. That collective dependency limits how much parallelism the hardware can actually extract, which shows up as processing elements sitting idle.
-
Caches managed for locality. Every accelerator in this space manages its on-chip cache with a recency-based policy, and improves performance by making the cache bigger.
-
The gap. Recency answers the wrong question when many misses are outstanding at once, and a bigger cache is expensive — the cache is by far the largest thing on these chips, at around 60 percent of the area here.
How one design covers the whole spectrum
From a sparse matrix to a merged output row
-
-
new
-
new
-
new
-
new
-
new
The idea
Turn a discrete choice into a continuous one. The design begins by fixing the worst problem — it gives each multiplier a single non-zero and the one row that non-zero selects, which is the row-wise form and means nothing is fetched that cannot contribute. Then it fixes the row-wise form’s own weakness by traversing the first matrix down its columns rather than across its rows, so that multipliers working at the same time want the same row of the second matrix, which is where the outer-product form gets its reuse. But that creates the row-wise form’s other problem, several multipliers producing pieces of the same output row and having to synchronise. The knob resolves this. Compacting the first matrix by shifting its non-zeros leftwards makes each traversed column denser, so more multipliers share a row of the second matrix; compacting less spreads them across different output rows and reduces contention. Three settings — none, moderate, aggressive — span the range between reuse and independence. Making the dataflow adjustable rather than chosen is precisely the move of the adaptive dataflow accelerator covered elsewhere on this site, which this paper takes as its main baseline and differs from in what it adjusts.
Choose the setting by trying it, on regions that look alike. No setting wins everywhere, so it has to be picked per matrix, and in fact per region, since sparsity varies within a matrix. The paper picks cheaply. It partitions rows into bands wherever the number of non-zeros in adjacent rows differs by more than a threshold, which is readable straight off the compressed format’s offset array and therefore costs nothing. Within a band the sparsity is assumed uniform, so a short sampling phase runs three passes of 32 rows each at the three settings, measures the time including merging, and applies the winner to the rest of the band. Bands too small to sample get the middle setting. This is deliberately a runtime procedure — the comparable accelerator that picks a dataflow per layer covered elsewhere on this site decides offline from the matrix dimensions, which cannot respond to a matrix the designer never saw.
A cache policy that asks what a line is blocking. The second half of the paper leaves dataflow behind. Its observation is that recency-based replacement implicitly assumes misses are serviced one at a time, which stopped being true long ago. The proposed policy scores each cached line by two terms — a reuse-distance counter that decays until the line is used again, giving the usual locality signal, and the number of cache lines occupied by the fiber that line belongs to, standing in for how many concurrent accesses depend on it. Eviction takes the line with the highest sum, breaking ties towards larger fibers, on the reasoning that a dense fiber which a sparse partial result must merge into is exactly what should not be evicted. Alongside it, a non-blocking buffer lets the cache continue serving hits while misses are outstanding, coalescing repeated misses to the same line. Reasoning about which misses actually matter rather than treating them uniformly is the same instinct as the critical-slice prefetching work covered elsewhere on this site, which reorders execution around the loads whose latency cannot be hidden.
Choosing how hard to squeeze
How the compaction setting is chosen for one region of a matrix
Following the adapter from a raw sparse matrix to a setting applied across a band of rows.
Step 1 of 5
Cut the matrix into bands by row length
Walking the compressed format's offset array gives the number of non-zeros in each row for free. A new band begins wherever that count differs from the previous row by more than ten.
The assumption is that adjacent rows with similar densities have similar structure, so one setting suits a whole band. Using the offsets means the partitioning costs a scan of an array that has already been loaded, with no analysis of the non-zeros themselves.
Why it works
- Row granularity removes the searching and keeps the merge small. Giving each multiplier one non-zero and the row it selects → no pair is ever fetched that cannot contribute, and partial results are single rows rather than whole matrices → the dot-product form’s wasted index matching and the outer-product form’s merge explosion are both avoided.
- Compaction converts reuse into contention at a controllable rate. Shifting non-zeros leftwards makes traversed columns denser → more multipliers share a row of the second matrix, and more of them target the same output row → one knob spans the whole trade, so the design can sit anywhere between the two failure modes instead of at one end.
- Sampling is affordable because regions are homogeneous. Banding by row length from data already in the compressed format, then testing three settings on 32 rows each → the measurement cost is amortised over a band of hundreds of rows → adaptive selection beats every fixed setting by 7 to 27 percent depending on which fixed setting it is compared with.
- Pairing each multiplier with a merger removes the collective wait. Immediate merging into the cache rather than a batched merge at the end → no multiplier waits for a batch of peers to finish → processing element utilisation reaches 95 percent on average, against 87 percent for the closest competitor.
- Evicting by blocked parallelism protects the pipeline. Scoring lines by fiber size as well as recency → a dense fiber that many pending merges depend on stays resident → 10 to 20 percent better than recency alone at every compaction setting, without enlarging the cache.
What it costs (trade-offs and scope)
- Sampling is wasted work. Three passes per large band are executed at settings that will be discarded. It is amortised over hundreds of rows, but it assumes bands are internally homogeneous, and a matrix whose structure varies within a band gets a setting chosen on unrepresentative rows.
- Small regions get a guess. Bands under 256 rows are not sampled at all and receive the middle setting by default, so a matrix made of many small irregular regions never benefits from the adaptation that is the paper’s headline idea.
- Three settings, not a continuum. The knob is described as spanning a spectrum but is implemented as none, moderate, and aggressive. Finer control might help and would cost more sampling.
- The cache policy needs extra state per line. Each line carries a decaying counter and its fiber size must be known, which is metadata the accelerator has to maintain and consult on every eviction decision.
- Everything is simulated. Core components were written in hardware description language and synthesised for area and power, but performance comes from a cycle-accurate simulator, and the comparisons against three other accelerators inherit that.
The evaluation
| Property | What was measured | The result | What it tells you |
|---|---|---|---|
| Speed against three accelerators | |||
| How busy the hardware stays | |||
| Value of adapting rather than fixing | |||
| Value of the cache policy | |||
| What it costs in silicon |
Check yourself
Check your understanding
1. Why does the design traverse the first matrix column by column rather than row by row?
2. What does compacting the first matrix trade against what?
3. How is the compaction setting chosen, and what does it cost?
4. Predict what a purely recency-based cache policy does wrong in this setting.
Sources
ACES: Accelerating Sparse Matrix Multiplication with Adaptive Execution Flow and Concurrency-Aware Cache Optimizations. Xiaoyang Lu, Boyu Long, Xiaoming Chen, Yinhe Han, Xian-He Sun. ASPLOS 2024, Volume 3, pages 71 to 85. DOI 10.1145/3620666.3651381. Full text read from the authors’ copy hosted at Illinois Institute of Technology.