Flexagon: A Multi-dataflow Sparse-Sparse Matrix Multiplication Accelerator for Efficient DNN Processing

Sparse-times-sparse matrix multiply can loop three different ways, and the fastest way changes from one DNN layer to the next — Flexagon is one accelerator whose tree nodes flip between adders and comparators and whose three memory idioms match each access pattern, running every layer in its best dataflow for a few percent of extra area.

Why this problem is worth solving

Sparsity is now a design feature of deep networks: pruning zeroes out weights, and activation functions like ReLU zero out activations, with observed densities ranging from almost-dense to 99.96% empty. Storing and multiplying only the non-zeros —

But “multiply two sparse matrices” hides a three-way fork. The triple loop can be nested as: inner product (IP) — compute each output element as a dot product, intersecting two compressed

The paper’s motivating measurement is the important one: profiling eight production DNN models layer by layer, the fastest dataflow changes between models and between layers of the same model — driven by matrix dimensions, sparsity levels, and whether the streamed matrix fits in on-chip memory. A fixed-dataflow chip therefore runs many layers in the wrong gear; averaged end to end, that costs up to 4.59×. There is a second, quieter tax: dataflows consume and produce specific compression formats (CSR or CSC), so chaining layers on a fixed-dataflow chip can require explicit format conversion between layers — extra hardware, extra passes. (For the software-side view of the same format-diversity problem, see the SparseTIR explainer elsewhere on this site.)

What people did before, and where it broke

One accelerator per dataflow. SIGMA builds a flexible multiplier array with a fast asymmetric reduction tree (FAN) — ideal for IP’s clustered dot-product reductions. SpArch pipelines outer products through a specialized merge tree. GAMMA leans on a large fiber cache to feed Gustavson’s row gathers. Each design’s signature structure (reduction tree, merger, cache) is its dataflow commitment.

Why not just pick the best one? The layer-wise analysis shows each choice loses somewhere: the IP design touches vastly more data on mismatched layers (5.68× and 2.27× more on-chip traffic than OP/Gust designs on the six layers it loses worst); the Gust design collapses when matrix B outgrows its cache (L1 miss rate 2.43% vs 0.39%, translating to 6.25× more off-chip traffic); the OP design pays a heavy merge phase when outputs are large. These are structural consequences of loop order, not tuning artifacts.

Naive flexibility is expensive. Simply instantiating three reduction/merge networks side by side (one per dataflow) inflates area; supporting each dataflow’s memory pattern with dedicated controllers would need 6 dataflows × 5 controllers = 30 logic modules. Flexibility has to be unified to be affordable.

The idea

Reduction and merging are the same tree wearing different hats. IP needs a tree of adders to sum each dot product’s partial products. OP and Gust need a tree of comparators to merge coordinate-sorted psum fibers into output fibers. Prior accelerators built one or the other; Flexagon’s Merger-Reduction Network builds tree nodes that do either, switched by configuration, with dual links so coordinates travel alongside values (merging needs to compare coordinates; pure reduction does not). The MRN costs 28% more area than SIGMA’s reduction tree and 128% more than a plain merger — but it is only 4% of Flexagon’s total area, because memory dominates everything. That asymmetry is the whole economic argument: flexibility in the logic is nearly free; what matters is shaping the memory.

Three memory idioms, matched to three access patterns. The stationary matrix is always consumed once, in order — a FIFO, not a cache. The streamed matrix ranges from perfectly sequential (OP) to irregular gather-heavy (Gust) — a set-associative cache sized for the worst case. Partial sums are the hard part: OP and Gust produce psum fibers whose sizes are unknowable at compile time (they depend on where non-zeros landed), possibly for several k-iterations of several output rows at once. PSRAM handles this with row-indexed sets divided into tagged blocks — each block records which k-iteration its psums belong to, so variable-length fibers from parallel iterations coexist without static over-provisioning.

Execution in phases. Per tile: a stationary phase pins one matrix’s elements in the multipliers; a streaming phase flows the other matrix through, generating products (IP reduces them through adder-mode MRN immediately; OP/Gust park psum fibers in PSRAM); a merging phase (OP/Gust only) flips multipliers to forwarder mode and MRN nodes to comparator mode, streaming psum fibers back through the tree to merge into final output fibers.

Format freedom falls out. Because CSR and CSC are the same mechanism in row/column-major dress, one control logic handles both — and because Flexagon can pick per layer among six dataflows, it can always choose one that consumes the format the previous layer produced. Fixed-dataflow chips must sometimes convert (CSR↔CSC) between layers; Flexagon simply never needs to.

inputs: dims, sparsity, compressed sizes
output: dataflow + tiling + config signals (per layer)

Why it works

• The best loop order is a per-layer property (dimensions, sparsity, B-size vs cache) → an accelerator that switches per layer harvests every layer’s best case → end-to-end wins over every fixed design, on every model tested.
• Reduce-by-adding and merge-by-comparing have the same tree shape → one augmented tree with mode-switching nodes replaces two networks → full dataflow coverage for 4% of chip area.
• Memory access patterns, not compute, dominate cost (the streaming cache alone is 74–93% of area in all designs) → three purpose-shaped idioms (FIFO / cache / PSRAM) capture each pattern → flexibility costs 3–25% area rather than 3× replication.
• Psum fibers have unknowable lengths → PSRAM’s k-tagged blocks allocate on demand within row-indexed sets → OP and Gust run without worst-case static reservations.
• CSR and CSC share one compression mechanism → one control logic serves both, and per-layer dataflow choice always finds a consumer for the producer’s format → inter-layer conversions vanish.

What it costs

• Area over the leanest specialist. +25% versus the IP-only SIGMA-like design (which needs no PSRAM at all), +14% versus GAMMA-like, +3% versus SpArch-like — repaid as 265% / 18% / 67% better performance-per-area.
• PSRAM sized for the worst case. Outer product’s merge appetite sets the 256 KiB provisioning; GAMMA-like gets away with half.
• An offline mapper in the loop. Per-layer dataflow selection, tiling, and configuration generation happen before execution — and the automated selection tool is explicitly future work; the paper evaluates with the choice made by analysis.
• Simulation-first evidence. End-to-end numbers come from cycle-level simulation (STONNE + SST); RTL at 28 nm covers the key components (networks, merger, MRN) rather than a full chip tape-out.
• Baselines are re-modeled. Comparisons are against SIGMA-like / SpArch-like / GAMMA-like — the papers’ essential dataflow and structures re-implemented on a normalized substrate — not the original chips.

The evaluation

Eight DNN models spanning vision, detection, and NLP (AlexNet, SqueezeNet, VGG-16, ResNet-50, SSD-ResNets, SSD-MobileNets, DistilBERT, MobileBERT — largely from MLPerf) run end to end on cycle-level simulations of four accelerators sharing one normalized substrate: SIGMA-like (IP), SpArch-like (OP), GAMMA-like (Gust), and Flexagon. All use 64 multipliers, a 1 MiB streaming cache, and HBM 2.0 DRAM; area and power come from RTL synthesis and place-and-route at TSMC 28 nm, 800 MHz.