The Sparse Abstract Machine

Sparse tensor algebra accelerators were point solutions — one expression, one loop order, baked into silicon — and general expressions had to shatter into matrix-multiply chains with order-of-magnitude asymptotic penalties; SAM supplies the missing LLVM-like layer, flattening sparse tensors into streams with hierarchical control tokens and defining nine composable dataflow blocks that express EVERY tensor-algebra expression in any iteration order with fusion — plus a compiler (Custard) from index notation down, and the demonstration that prior accelerators are just particular SAM graphs.

Why this problem is worth solving

The paper’s framing borrows the most successful idea in compiler history: what LLVM did for instruction-based processors — a shared abstract machine that lets front-ends and back-ends evolve independently — sparse dataflow needs too. Without it, every accelerator is a silo: its capabilities can’t be stated precisely, its performance can’t be compared like-for-like, its software is a hand-built library, and general expressions pay the factorization tax (unfused sparse computation can be asymptotically worse — cost scaling with dense volume instead of nonzero count). An abstract machine answers all four at once: it is the capability statement, the comparison substrate, the compiler target, and the fused-execution model. The ambition is infrastructural rather than a single speedup number — which is exactly what makes this paper’s influence compound.

What people did before, and where it broke

• Fixed-function point solutions. Each hardens one expression and one loop order: SIGMA does inner-product (i→j→k) sparse matrix multiply — clean output, but it enumerates all (i,j) pairs before intersecting at k, asymptotically poor; GAMMA does Gustavson’s i→k→j linear-combination-of-rows, better asymptotics at the cost of merge hardware; OuterSPACE does outer-product k→i→j with a whole-matrix merge phase. Each choice is a legitimate point in a tradeoff space — but silicon freezes the choice.
• Factorization as the escape hatch. Arbitrary tensor contractions reduce to matmul chains via transposes, tensor-to-matrix conversions, and temporaries. For sparse data this is not a minor tax: sequences of matrix multiplies run an order of magnitude slower than bespoke fused contractions, and unfused execution can change the complexity class — runtime growing with tensor volume rather than nonzero count.
• Programmable sparse hardware without full generality. The SPU streams arrays through a CGRA with intersection hardware; ExTensor hierarchically intersects with skipping; Capstan adds sparse support to an RDA. All influenced SAM’s primitives — none supports the full feature set general tensor algebra needs (arbitrary traversal and co-traversal, broadcast repetition, reductions, assignment, compressed formats, arbitrary iteration order, fusion).
• TACO’s von Neumann lock-in. The compiler with full generality lowers co-iteration into while loops, ifs, and indirect accesses — constructs dataflow hardware lacks by design. Converting that control flow back into dataflow would require heroic synthesis; SAM instead defines a different lowering target where sparse iteration is first-class.

What SAM is

The idea

Flatten the tree into a stream, and sparsity becomes transportable. Dataflow hardware moves streams, not data structures — so SAM’s foundational move is a wire encoding of multidimensional sparsity: fibertrees serialized with hierarchical stop tokens, where the token’s level says how many nesting levels just ended (S0: this fiber; S1: the fiber of fibers; D: the whole tensor). This single idea decouples everything downstream: blocks operate on flat streams with local rules (“on S0, emit accumulated sum”), formats become interchangeable level implementations behind the scanner interface, and no block ever needs random access or a pointer. It is the sparse-streaming analog of what serialized IRs did for compilers.

Sparse iteration is algebra, so co-iteration is set algebra. The reason sparse code generation breeds while-loops is co-iteration: walking two compressed tensors in lockstep, advancing whichever lags. SAM observes that tensor algebra only ever needs two co-iteration semantics — intersection (multiplying, because a·0 = 0 lets you skip mismatches) and union (adding, because a+0 = a means nothing is skipped) — and freezes them into two block types with identical interfaces. Together with repeaters (broadcast), reducers (summation), and droppers (output compression), the messy control flow of sparse loops becomes a wiring diagram. The ablation over 23,794 real user algorithms from the TACO website shows this block set is minimal: remove any primitive and part of the domain becomes inexpressible.

One machine, every algorithm — so the tradeoffs finally become visible. Because SAM separates expression from schedule from format, the design points that used to be different chips become different graphs over the same blocks: all six loop orders of sparse matrix multiply (SIGMA’s, GAMMA’s, and OuterSPACE’s among them), fused versus factorized SDDMM, skip-enabled versus streaming intersection, bitvectors versus coordinate lists. The paper’s evaluation exploits exactly this: simulate the whole space, observe that k-first orders beat inner-product by an order of magnitude, that fusion’s advantage grows with sparsity, that locating wins when compute is modest — and conclude, with evidence, what programmable sparse hardware must therefore support. The abstract machine is simultaneously the argument for building it.

Gustavson’s SpMM as a SAM graph

same blocks, different wiring = SIGMA, GAMMA, or OuterSPACE
six ijk permutations; k-position dictates asymptotics

Why it works

• Dataflow hardware transports streams, not data structures → fibertrees flattened with hierarchical stop tokens carry arbitrary-dimensional sparsity over plain wires → every block needs only local, token-triggered rules, and no general control flow is ever reintroduced.
• Tensor algebra’s identities (a·0 = 0, a+0 = a) mean co-iteration only ever needs intersection and union → two merge blocks with fixed interfaces replace the while-loop/if jungles TACO generates → the domain’s irregularity is contained in nine primitive types, shown minimal by ablation over 23,794 real algorithms.
• Scanner and writer interfaces are format-agnostic → compressed, dense, bitvector, and linked-list levels swap behind the same contract → algorithms and formats decouple, and one graph serves many storage choices.
• Expression, schedule, and format are independent inputs → all six SpMM dataflows, fused and factorized SDDMM, and skipping/ bitvector/tiling variants are graphs over the same blocks → the design space becomes searchable by simulation instead of by fabricating chips, and the case for programmable hardware (orders must vary: k-first wins by 10× here, inner-product wins memory elsewhere) is made with data.
• A stable abstract machine between compiler and hardware → Custard lowers mechanically (scanners from tensor paths, merges where paths meet, repeaters for missing variables) while implementations optimize below the interface → the LLVM dynamic: both sides evolve without renegotiating the contract.

What it costs

• An abstract machine, not a chip. Evaluation runs on a cycle-approximate simulator; no silicon performance, area, or energy numbers exist in this paper. SAM’s bet is infrastructural — the payoff arrives when hardware implementations and compilers adopt the interface (as the authors’ subsequent CGRA silicon did).
• Automatic binding to existing accelerators is future work. Custard emits SAM graphs; mapping those onto SPU, ExTensor, or Capstan configurations remains manual.
• Pre-tiled tensors assumed. Like ExTensor and Capstan, SAM assumes tensors arrive tiled to fit accelerator memories; dynamic re-splitting of compressed structures requires a full scan and sits outside the streaming model’s comfort zone.
• Tensor algebra, not all of sparse computing. The domain is Einsum-style expressions; iterative solvers’ control flow, data-dependent convergence, and non-algebraic kernels live outside the machine.
• Streams serialize. The model’s simplicity comes from flat streams with token punctuation; exploiting reordering or out-of-order merging beyond what vectorization and graph duplication give requires extensions.

The evaluation

The evaluation matches the artifact: not one speedup number but four demonstrations of generality and analytical power. (1) Necessity: over the TACO website’s 23,794 user-compiled algorithms (3,839 distinct), removing any SAM primitive renders part of the domain inexpressible. (2) Tradeoff exploration: simulating all six SpMM dataflows shows inner-product orders losing by ≥10× to k-first orders; fused SDDMM beats factorized by the predicted asymptotic margins (nnz·K vs I·J·K); skipping, bitvectors, and splitting each win on the data patterns theory predicts. (3) Finite memory: tiled SAM graphs sequence tiles through buffer hierarchies, exposing memory-configuration tradeoffs. (4) Hardware representation: OuterSPACE’s two-phase outer-product design — multiply phase, linked-list intermediate, merge phase — is drawn as a SAM graph, with SPU, ExTensor, and Capstan discussed as further instances.

Check yourself

Sources

• arXiv preprint 2208.14610 (v2) — full text used for this explainer
• ACM DL: The Sparse Abstract Machine — ASPLOS 2023