Sparse computation — matrices, tensors, and graphs where almost everything is zero — runs badly on normal processors because the non-zeros sit at irregular places, filling the code with unpredictable branches and scattered memory reads; the usual fix is a specialized accelerator chip, but each one wires a single algorithm into silicon and cannot adapt when the software changes, so you get speed or flexibility but not both; this paper (Purdue) builds SparseCore, which instead extends a general processor's instruction set to make a "stream" — a sparse vector stored as an ordered list of indices, optionally with values — a first-class citizen with its own registers and about eleven instructions, and the key realization is that both sparse linear algebra and graph pattern mining reduce to the SAME set operations on ordered lists (a sparse dot product is just intersect-and-multiply, counting triangles is just intersecting two neighbor lists), so one small instruction-set extension flexibly accelerates both — reaching 13.5x the speed of a CPU on graph mining and 2.7x a specialized graph accelerator in under five percent extra core area, while staying fully programmable.
The argument in one glance
-
Problem
Sparse computation runs badly on general processors
Sparse data is data where almost every entry is zero or absent — sparse matrices, sparse tensors, and graphs (a graph's connections form a sparse matrix). It is everywhere: recommendation systems, scientific computing, graph analytics, machine learning. But general processors run it poorly. A processor is built for DENSE, regular data — it is fast when it can march through contiguous memory and apply the same operation to every element. Sparse data breaks that: the non-zeros sit at irregular positions, so the program turns into pointer-chasing, unpredictable branches, and scattered memory reads. On graph pattern mining a CPU wastes 20 to 40 percent of its cycles just recovering from mispredicted branches, and a GPU uses only about 4 percent of each group of threads because the threads take different paths. Most of the processor's throughput goes unused.
-
What people did
Build a specialized accelerator chip for each sparse workload
The standard response is to design a dedicated hardware accelerator for each sparse workload — a chip whose datapath is wired for one algorithm. For sparse matrix multiplication there are accelerators like OuterSPACE, ExTensor, and Gamma; for graph pattern mining there is FlexMiner. Each is fast because its hardware embodies exactly one dataflow, with the memory layout and compute units tuned for it.
-
Why it fell short
A fixed accelerator wires in one algorithm and cannot adapt
Each accelerator bakes a single algorithm and dataflow into silicon, so it is inflexible. Sparse matrix multiplication has three good algorithms — inner-product, outer-product, and Gustavson's — and which is best depends on the inputs, but a fixed accelerator forces one choice. Graph pattern mining evolves quickly (new pruning rules, new patterns, new symmetry-breaking tricks), yet a chip with the algorithm skeleton wired in cannot adopt a new software optimization. So you get speed OR flexibility, never both, and you need a different, expensive chip for every workload. The general processor stays flexible but slow; the accelerator is fast but rigid. Nothing in between gives a programmer fast sparse computation that still bends to new algorithms.
-
This paper's idea
Make the sparse vector a first-class ISA citizen, and compute with set operations
This paper (Purdue — Rao, Chen, Yik, Qian) builds SparseCore, which instead EXTENDS a general processor's instruction set (ISA) so that a STREAM — a sparse vector stored as an ordered list of indices, optionally paired with values — is a first-class citizen, like an integer or a vector. It adds stream registers and about eleven stream instructions that operate on a whole stream at once: intersect two streams, take their union, take their difference, and value-combining variants that multiply-accumulate or scale. The key realization is that both sparse linear algebra and graph pattern mining reduce to the SAME set operations on ordered lists: a sparse dot product IS "intersect the two index sets, multiply the matching values, and sum"; counting triangles IS "intersect two neighbor lists and count." So one small ISA extension flexibly accelerates both domains — and any algorithm expressible as set operations — while remaining a programmable general processor. Special hardware (parallel Stream Units, a small Stream Cache that prefetches the sorted keys, and separate value units) executes the set operations without the branchy inner loops. The result: 13.5x the speed of a CPU on graph pattern mining (64.4x at peak), 2.7x the specialized FlexMiner accelerator, and up to 6.9x on sparse tensor computation — in only 4.9 percent extra core area — at the honest cost of being 2.4 to 5.2x slower than a fixed-dataflow accelerator on that accelerator's one chosen dataflow.
Why this problem is worth solving
Sparse computation underlies a huge share of modern workloads, and today it
runs on hardware that was never built for it — so understanding exactly why
a general processor struggles comes first.
SPARSE COMPUTATION is computation on data where
most entries are zero or absent, so the data is stored compactly as only the
non-zero entries plus their positions (indices). Sparse matrices, sparse
tensors, and graphs are all sparse data — a graph’s adjacency structure is a
sparse matrix, where an entry is non-zero only if two vertices are
connected. The difficulty is that a general processor is built for DENSE,
regular data: it is fast when it can walk through contiguous memory and
apply the same operation to every element in lockstep. Sparse data destroys
that regularity. The non-zeros sit at irregular positions, so the code
becomes pointer-chasing, unpredictable branches, and scattered memory
accesses. On graph pattern mining a general CPU spends 20 to 40 percent of
its cycles recovering from mispredicted branches, and a GPU uses only about
4 percent of each group of threads because the threads follow different
control paths. Most of the machine sits idle
The insight SparseCore is built on is that the sparse work itself has a
simple shape. A
a STREAM in SparseCore is a sparse
vector treated as one first-class value the processor understands: an ordered
(sorted) list of indices, optionally paired with values. A graph vertex’s
neighbor list is a KEY stream (indices only); a sparse matrix row is a (KEY,
VALUE) stream (index-value pairs). What makes streams powerful is that the
fundamental operations of sparse computation are SET OPERATIONS on these
ordered lists — INTERSECTION (which indices appear in both), UNION (all
indices from either, combining their values), and DIFFERENCE (indices in one
but not the other). A sparse dot product is exactly “intersect the two index
sets, multiply the matching values, and sum them.” Counting triangles in a
graph is exactly “intersect two neighbor lists and count the overlap.”
Because both sparse linear algebra and graph pattern mining reduce to the
same few set operations on ordered streams, a single set of stream
instructions can accelerate both
What people did before, and where it broke
- General CPUs and GPUs. Fully programmable, so they run any sparse algorithm, but the irregular data defeats them: branches mispredict (20 to 40 percent of CPU cycles), threads diverge (a GPU uses about 4 percent of a warp), and memory bandwidth is wasted on scattered reads (about 13 percent utilization on graph mining). Flexible but slow.
- Sparse matrix accelerators (OuterSPACE, ExTensor, Gamma). Wire one matrix-multiply dataflow into silicon and run it very fast. But each fixes a single algorithm, and the best algorithm depends on the input, so no one chip is right for all sparse matrices.
- Graph pattern mining accelerators (FlexMiner). Embed an algorithm skeleton in hardware for pattern counting. Fast, but the field evolves quickly, and a new pruning rule or pattern cannot be added to a fixed chip.
- Vector and SIMD extensions. Add wide data-parallel instructions to a CPU, but they assume dense, contiguous data; a sparse vector is neither, so they do not help with the intersection-and-merge work at the heart of sparse computation.
- The gap. No approach gave a programmer fast sparse computation that still adapts to new algorithms. Accelerators are fast but rigid; general processors are flexible but slow; vectors assume dense data. That is the gap SparseCore fills — by making the sparse vector and its set operations first-class in the ISA.
How SparseCore turns sparse computation into stream set operations
Represent sparse vectors as streams, then compute with set-operation instructions
-
Sparse data breaks a general processor
The non-zeros sit at irregular positions, so sparse code is full of unpredictable branches and scattered memory reads. A CPU loses 20 to 40 percent of its cycles to branch mispredictions and a GPU uses about 4 percent of a warp, leaving most of the machine idle.
-
Represent each sparse vector as a stream new
A stream is an ordered list of indices (a key stream) or index-value pairs (a key,value stream). SparseCore makes it a first-class value with its own stream registers, tracked by a Stream Mapping Table that renames streams the same way the core renames ordinary registers — so it adds no pipeline latency.
-
Add stream set-operation instructions new
About eleven new instructions operate on whole streams: S_READ and S_VREAD load a stream, S_INTER intersects, S_MERGE takes the union, S_SUB takes the difference; value-combining S_VINTER intersects keys then multiply-accumulates, S_VMERGE merges then scales; S_NESTINTER runs a nested graph intersection; S_FREE releases a stream.
-
Execute set operations in parallel Stream Units new
Four Stream Units compare the two sorted streams in parallel and emit matches directly, with no per-element branch. A small 4 kilobyte Stream Cache prefetches the sorted keys sequentially (streams are ordered, so no complex predictor is needed) and feeds the units; a 16 kilobyte scratchpad keeps hot streams for reuse.
-
Process the values on a separate path new
For (key,value) streams, each matched key drives a value address generator that computes where the value lives; the values are fetched into a buffer and the Stream Value Processing Units multiply-accumulate or scale them. The value path runs independently of the key path, so keys and values overlap.
-
Map both domains onto the same primitives new
Sparse matrix multiply (inner-product, outer-product, or Gustavson's), tensor operations (tensor-times-vector, tensor-times-matrix), and graph pattern mining (triangle and clique counting) all compile to sequences of these stream set operations — so one ISA extension serves both domains, and the algorithm is chosen in software, not in silicon.
The idea
Find the operation that many workloads secretly share, and put it in the hardware. Sparse matrix multiplication and graph pattern mining look like different problems, handled by different accelerators. SparseCore’s insight is that both are the same underneath: they are SET OPERATIONS on ordered lists of indices. A sparse dot product is an intersection of two index sets followed by multiply-and-add; counting triangles is an intersection of two neighbor lists followed by a count. Once you see that shared primitive, you do not build a chip per algorithm — you make the primitive itself a hardware instruction, and every algorithm that reduces to set operations gets fast at once. Discovering the common abstraction beneath diverse workloads and building the system around it is the same map-onto-a-shared-primitive move the site’s high-level-synthesis and in-memory-computing pages make when they reduce many optimizations to rewrites on one intermediate representation — here the shared representation is the ordered stream, and the shared operation is the set operation.
Make the sparse vector a first-class citizen of the instruction set. A normal ISA knows about integers, floats, and dense vectors, but a sparse vector is a second-class thing built by hand out of loops and pointers. SparseCore promotes it: a stream has its own registers, its own instructions, and its own renaming table (the Stream Mapping Table), exactly as an integer register does. That is what turns “a slow library routine” into “a single instruction the out-of-order core schedules.” Elevating a representation from an ad-hoc software construct into a first-class hardware type — with its own registers and operations — is the same reify-the-representation discipline the site’s pages on new intermediate representations and hardware data types share; when the thing you care about becomes a named, first-class object, the machine can be built to serve it directly instead of emulating it.
Refuse the choice between fast and flexible — get both with a programmable extension. The field had accepted a dichotomy: a fixed accelerator is fast but rigid, a general processor is flexible but slow. SparseCore rejects it by adding SPECIALIZED instructions to a GENERAL processor. The set operations run in dedicated Stream Units at accelerator-like speed, but the surrounding program is ordinary code, so a new algorithm is just a new sequence of instructions — no new chip. Pairing a general, programmable substrate with a few specialized units, rather than choosing one or the other, is the same reject-the-false-dichotomy, have-both instinct the site’s accelerator- companion page uses when it pairs a general arithmetic unit with specialized memory logic, and the compression and decoupling pages use when they keep a general path and a fast path together. The honest price of that flexibility appears in the evaluation: on a fixed accelerator’s one chosen dataflow, SparseCore is a few times slower — flexibility is not free.
Counting triangles with stream instructions
From a branchy nested loop to a few stream set operations
Triangle counting: for each edge, count the common neighbors of its two endpoints. Numbers from the paper's simulation.
Step 1 of 5
The task
Count triangles in a graph: for each edge connecting v0 and v1, count how many neighbors v0 and v1 share. On a CPU this is a nested loop over two neighbor lists with a branch at every comparison, and the branches mispredict — 20 to 40 percent of cycles are lost recovering from them.
the graph is stored in CSR format (a sorted neighbor list per vertex), so each vertex's neighbors are already an ordered list the inner comparison is data-dependent, so the branch predictor cannot learn it
Why it works
- Sparse code is slow because irregular data causes mispredicted branches and scattered memory reads → representing a sparse vector as an ordered stream and intersecting two streams in a Stream Unit removes the per-element branch → branch mispredictions fall from 20 to 40 percent of cycles to below 5 percent, and the freed throughput does real work.
- Sparse linear algebra and graph pattern mining seem unrelated → both reduce to the same set operations on ordered lists (intersection, union, difference) → one ISA extension with those operations accelerates both domains instead of needing a separate accelerator for each.
- A stream is ordered → the Stream Cache can prefetch its keys with a simple sequential fetch, no complex predictor → data arrives ahead of the Stream Units and they rarely stall.
- Streams are first-class, renamed like registers → the out-of-order core schedules stream instructions and overlaps the value path with the key path → keys, values, and other work proceed together instead of serializing.
- The set operations are specialized but the program is ordinary code → a new algorithm (a new pattern, a new pruning rule, a different matrix-multiply dataflow) is just a new instruction sequence → the hardware stays fast while the software stays flexible.
What it costs (trade-offs and scope)
- Flexibility is slower than fixed silicon on its home turf. On a fixed accelerator’s one chosen dataflow, SparseCore is 2.4 to 5.2x slower than Gamma on sparse matrix multiplication. A general extension cannot match hardware wired for exactly one algorithm; you trade peak performance for breadth and programmability.
- A hard limit on live streams. There are 16 stream registers. An algorithm that needs more than 16 streams active at once must fall back to scalar code (rare in practice, but a real ceiling), and the compiler must schedule S_FREE aggressively to stay within budget.
- The wins scale with density. Longer neighbor lists and rows make longer streams with more reuse, so denser graphs speed up much more; on very sparse, short-stream inputs there is less set-operation work to amortize the machinery.
- It assumes ordered streams and set operations. Workloads that do not reduce to intersection, union, or difference on sorted lists fit less naturally, and inputs must already be in the expected sorted or CSR format; converting or sorting data is extra work the model assumes is done.
- It is still added hardware and a compiler. The block is small (0.73 square millimeters, 4.9 percent of a Skylake core), but it adds stream registers, four Stream Units, a Stream Cache, a scratchpad, value units, and graph-format registers to the core, plus compiler support (a graph-mining compiler and a modified TACO tensor compiler). The results come from simulation with a synthesized block, not a fabricated chip.
The evaluation
SparseCore was modeled in the zSim simulator on a 6-core out-of-order design (128-entry reorder buffer, 32 kilobyte L1 data cache, 256 kilobyte L2, 12 megabyte L3), with a 4 kilobyte Stream Cache, a 16 kilobyte scratchpad, and four Stream Units; the block synthesized to 0.73 square millimeters at 15 nanometers and 4.35 gigahertz. It was compared against CPU miners (AutoMine), a graph-mining accelerator (FlexMiner), a GPU, and sparse-tensor accelerators (OuterSPACE, ExTensor, Gamma), across seven mining patterns on ten real graphs and several sparse-tensor kernels.
Accelerating sparse computation
| Property | General CPU / GPU | Fixed accelerator (per-algorithm) | SparseCore (this work) |
|---|---|---|---|
| Flexibility | |||
| Adapts to new software | |||
| Handling of sparse data | |||
| Performance | |||
| Cost |
Check yourself
Check your understanding
1. SparseCore accelerates both sparse matrix multiplication and graph pattern mining with one ISA extension. Predict what makes a single extension able to serve two seemingly different domains.
2. On graph pattern mining a CPU loses 20 to 40 percent of its cycles to branch mispredictions, and SparseCore cuts that to below 5 percent. Predict why turning the loop into a set operation removes the branches.
3. On a fixed accelerator's chosen dataflow, SparseCore is 2.4 to 5.2x SLOWER than Gamma. Predict what this reveals about SparseCore's design choice.
4. Predict what happens if a graph-mining algorithm needs more than 16 streams active at the same time on SparseCore.
Sources
- SparseCore: stream ISA and processor specialization for sparse computation (ACM DL, DOI 10.1145/3503222.3507705) — ASPLOS 2022; full text read via the ACM PDF.
- dblp record — bibliographic entry and authors (Gengyu Rao, Jingji Chen, Jason Yik, Xuehai Qian).
- ASPLOS’22 conference talk (YouTube) — authors’ presentation of the design and results.