Accelerating Sparse Data Orchestration via Dynamic Reflexive Tiling

Toluwanimi O. Odemuyiwa, Hadi Asghari Moghaddam, Michael Pellauer, Kartik Hegde, Po-An Tsai, Neal Clayton Crago and 5 others

Multiplying sparse matrices and tensors — the core of graph analytics, solvers, and chemistry — is starved by memory bandwidth, moving 2-3x more data than it should, and the classic cure, TILING (chop the data into on-chip-buffer-sized blocks and reuse each block many times), backfires on sparse data because a fixed-shape block catches an unpredictable, usually tiny scattering of non-zeros, so it either overflows the buffer or leaves it mostly empty; DRT (Dynamic Reflexive Tiling, from UC Davis, NVIDIA, and Illinois) fixes this by sizing tiles at RUNTIME to the actual non-zeros — grow each tile until the buffer is genuinely full — and REFLEXIVELY, so one operand's tiling adapts to where the other operand actually has data, cutting DRAM traffic near its theoretical floor and giving 2.4-16.6x more arithmetic intensity than the best prior sparse accelerators, at 0.1% extra chip area and 85% less energy.

The argument in one glance

Problem

Sparse tensor math is starved by memory, not compute

Multiplying sparse matrices and tensors — sparse matrix times sparse matrix, higher-order tensor contractions — is the workhorse of graph analytics, linear solvers, and computational chemistry. These kernels are severely MEMORY-BOUND: they do very little arithmetic per byte of data they move, so their speed is set by how fast data streams from DRAM, not by how fast the processor computes. And they are inefficient at it: even purpose-built sparse accelerators move 2-3x more DRAM traffic than the theoretical minimum, because clever dataflow alone cannot bring the traffic down to the floor. The processor sits idle waiting for scattered data. Closing that memory gap is the whole performance problem for sparse tensor algebra.
What people did

Tile the data to reuse it on-chip

The textbook cure for a memory-bound kernel is TILING (blocking): partition the data into tiles small enough to fit in fast on-chip memory, load each tile once, and reuse it many times before evicting it — so the same bytes are read from DRAM once instead of repeatedly. For dense matrix multiply this is spectacularly effective and well understood: you know exactly how much data a tile of a given shape holds, so you size tiles to fill the buffer and maximize reuse. State-of-the-art sparse accelerators like ExTensor bring tiling to sparse tensors by carving them into uniform coordinate-space tiles — fixed-shape blocks of the coordinate grid.
Why it fell short

A fixed-shape tile catches the wrong number of non-zeros

Tiling by a fixed coordinate shape is exactly wrong for sparse data, because the coordinate shape does not tell you how much data is inside. A uniform tile — say a 128-by-128 block of the coordinate grid — contains however many non-zeros happen to fall in that region, and with irregular sparsity that number is unpredictable and usually tiny: most of the grid is empty. So a fixed-shape tile UNDER-FILLS the on-chip buffer (a mostly-empty tile wastes the capacity and yields almost no reuse) in the common case, and OVERFLOWS it in the dense regions. Low-occupancy tiles mean low reuse, which means the DRAM traffic the tiling was supposed to cut stays high. Worse, the right tile shape cannot be chosen ahead of time, because it depends entirely on where the non-zeros actually are — and, for a joined operation, on where BOTH operands have data. Coordinate volume is simply the wrong measure of what a tile holds.
This paper's idea

Size tiles to the real non-zeros, at runtime, jointly across operands

DRT (Dynamic Reflexive Tiling — Odemuyiwa, Asghari-Moghaddam, Pellauer, Hegde, Fletcher, and colleagues from UC Davis, NVIDIA, and Illinois) tiles by OCCUPANCY, not by coordinate shape. DYNAMIC: at runtime it grows each tile — expanding its coordinate range one step at a time and counting the non-zeros it accumulates — until the on-chip buffer is genuinely full, so every tile is high-occupancy regardless of the local density, and tiles take non-uniform coordinate shapes. REFLEXIVE: because the ideal tile of one operand depends on where the other operand has active data (the best tile of A's rows changes with B's active columns), DRT CO-TILES all operands jointly, growing them together so their coordinate ranges align for the operation. A tiny Tile Extractor unit does this in hardware, pipelined, at 0.1% extra die area — bringing DRAM traffic near its theoretical floor and delivering 2.4-16.6x more arithmetic intensity than prior sparse accelerators, with 85% less energy.

Why this problem is worth solving

Sparse tensor algebra is everywhere in scientific and graph computing, and its performance is dictated almost entirely by memory traffic — so anything that cuts that traffic is a direct, broad win. The reason it is so memory-bound is a matter of

the ratio of arithmetic operations a kernel performs to the bytes of data it must move from memory. When this ratio is high (many computations per byte), a processor can be kept busy and is compute-bound; when it is low, the processor finishes its work and stalls waiting for the next data, and performance is capped by memory bandwidth — the “memory wall.” Sparse tensor operations have very low arithmetic intensity: each non-zero is typically touched for a single multiply-accumulate, so there is almost no computation to hide the cost of fetching it, and the data is scattered irregularly through memory. This is why even accelerators with sophisticated dataflows move 2-3x more DRAM traffic than the minimum — the fundamental problem is not how they compute but how much data they move

. The lever for a memory-bound kernel is data REUSE: if you can load a piece of data once and use it many times before evicting it, you cut the DRAM traffic and raise the effective arithmetic intensity, moving the kernel off the memory wall. Tiling is how you achieve reuse, so the entire game is tiling well.

Tiling well for sparse data, though, requires abandoning the measure that works for dense data. The trap is

the standard approach of carving a tensor into fixed, uniform tiles of its coordinate grid — a 128-by-128 block, say. For a dense tensor this is perfect, because a coordinate shape and a data amount are the same thing: a 128-by-128 dense block always holds 16,384 values, so you can size tiles to exactly fill the on-chip buffer. For a SPARSE tensor, coordinate shape and data amount are decoupled: a 128-by-128 region might hold three non-zeros or three thousand, depending on where the non-zeros happen to lie. So a fixed coordinate tile size is a proxy that lies about how full the buffer will be — most tiles come out nearly empty (wasting the buffer and the reuse it could have provided), and the occasional dense tile overflows. The quantity that actually matters is OCCUPANCY: the number of non-zeros in the tile, which is what determines whether the buffer is used well. Sizing by coordinate shape optimizes the wrong thing

. And there is a second complication unique to a joined operation like A times B: the right way to tile A depends on which parts of B are active, so the tiles cannot be chosen independently. DRT’s opportunity is to tile by the real metric — occupancy — decided at runtime from the actual data, and jointly across the operands whose sparsity determines each other’s ideal shape. That is what finally makes tiling deliver its promised reuse on sparse tensors.

What people did before, and where it broke

No tiling (stream the data). Read the sparse operands straight from DRAM. Simple, but with no reuse the kernel is fully memory-bound and moves far more traffic than necessary — the baseline DRT improves on by 7.29x in software.
Static uniform-coordinate tiling (ExTensor). Carve tensors into fixed-shape coordinate blocks. Brings tiling to sparse accelerators, but because coordinate shape does not equal occupancy, most tiles under-fill the buffer, yielding low reuse — and on irregular matrices it can even do worse than an optimized CPU library, because the tiles capture too few non-zeros.
Dataflow-focused sparse accelerators (OuterSPACE, MatRaptor). Optimize the order and pattern of computation (outer-product, Gustavson) to improve locality. Real gains, but dataflow alone cannot bring DRAM traffic to the floor — they still move 2-3x the minimum, because the tiling underneath is still occupancy-blind.
Tuning a single static tile size per workload. Pick the best fixed tile shape for a given matrix offline. Better than a default, but a single shape cannot fit a matrix whose density varies from region to region, and it must be re-tuned per input.
The gap. No approach sized tiles by their actual non-zero OCCUPANCY, decided dynamically at runtime, and co-tiled the operands so each reflects the others’ sparsity. DRT does, filling the buffer with real data on every tile and cutting traffic near the theoretical floor.

How DRT works

Pre-tile cheaply, grow macro tiles to fill the buffer, and co-tile the operands

Recognize the goal: fill the buffer with non-zeros

Tiling only cuts DRAM traffic if each on-chip tile holds enough data to reuse. The quantity that matters is OCCUPANCY (non-zeros per tile), not coordinate shape — so DRT tiles to maximize occupancy, filling the buffer on every tile regardless of how the sparsity is distributed.
↓ →
Pre-tile each tensor into cheap uniform micro tiles new

Introspecting a whole sparse tensor to find good tile boundaries would be expensive, so DRT pre-processes each tensor into small fixed-size MICRO tiles (32-by-32 in the evaluation) whose non-zero occupancy is cheap to count. The micro tile is the atomic unit of the dynamic decision, decoupling the buffer size from the eventual tile shape.
↓ →
Grow macro tiles to the buffer (the DYNAMIC part) new

At runtime DRT groups micro tiles into a variable-shape MACRO tile: starting from a seed, it grows the tile one coordinate step at a time — expanding contracted dimensions first — accumulating the non-zero count as it goes, and halts the moment the on-chip buffer partition is full. Every macro tile thus comes out high-occupancy, non-uniform in coordinate volume but uniform in how well it fills the buffer.
↓ →
Co-tile the operands jointly (the REFLEXIVE part) new

Because the ideal tile of one operand depends on where the other has active data, DRT does not tile tensors independently: it processes them in order of stationarity and grows each subject to the co-tiling constraint that co-iterated dimensions cover the same coordinate range in all operands — so one tensor's tiling reflects the others' sparsity and the tiles actually align for the operation.
↓ →
Extract tiles in cheap, pipelined hardware new

A hardware Tile Extractor reads the compressed (CSR/CSC) representation, AGGREGATES occupancy with a parallel adder that counts 32 micro tiles per cycle, BUILDS the macro tile's coordinate/segment metadata, and PIPELINES it — overlapping the use of tile i with the extraction of tile i+1 through dual-port buffers — so extraction adds under 1% latency versus an ideal zero-cost extractor.
↓ →
Track coordinates so tiling stays seamless new

Tiles are defined by coordinate ranges in the parent tensor, and successive extractions chain their base points (the end coordinate of one tile becomes the start of the next), so the whole tensor is covered by non-overlapping, occupancy-filled tiles. The design drops into existing accelerators (ExTensor, OuterSPACE, MatRaptor) across outer-product, inner-product, and Gustavson dataflows.

Evaluated on 18 SuiteSparse and SNAP matrices (densities 0.0006% to 0.356%) across SpMSpM, tall-skinny products, multi-source BFS, and higher-order tensor contractions, integrated into ExTensor, OuterSPACE, and MatRaptor, plus a CPU software implementation. The Tile Extractor adds only 0.1% die area.

The idea

Size the tile by the real content, not by a coordinate shape that lies about it. For dense data a tile’s coordinate shape IS its data amount, so you tile by shape. For sparse data the two come apart: a fixed coordinate block holds an unpredictable, usually tiny number of non-zeros, so tiling by shape leaves the buffer mostly empty and squanders the reuse tiling exists to provide. DRT’s foundational move is to tile by OCCUPANCY instead — grow each tile until it actually fills the buffer with non-zeros — so coordinate shape becomes an output of the process rather than a fixed input. This is the measure-the-true-quantity-not-a-proxy discipline the site has been circling: the datacenter-IO page invents a device-occupancy metric because bytes lie about how much a request occupies a disk, the tiered-memory page counts real accesses because the access bit lies about hotness — and here DRT counts real non-zeros because coordinate volume lies about how full a tile is. The proxy that is exact for dense data is a lie for sparse data, and the fix in every case is to measure and act on the true quantity.

Tile the operands together, because each one’s ideal shape depends on the others. A joined operation like A times B cannot be tiled by looking at one operand alone: the best tile of A’s rows depends on which of B’s columns are active, since only where both have data does any work happen. DRT is REFLEXIVE — it co-tiles all the operands jointly, growing them under the constraint that their co-iterated dimensions cover the same coordinate range, so each tensor’s tiling reflects the sparsity of the others and the resulting tiles align. This is the co-optimize-the-coupled-decisions discipline the site rewards — the heterogeneous-serving page folding placement and routing into one problem, the FHE-compiler page co-optimizing data layout with scheduling — the recognition that when two choices each determine the other’s ideal value, optimizing them separately leaves the joint optimum unreachable.

Decide at runtime because sparse data cannot be planned in advance — and make the decision cheap. Where a static compiler problem can be solved ahead of time, sparse structure is data-dependent and unknown until you see it, so DRT must choose tile boundaries at runtime from the actual data — the opposite pole from an offline allocator that plans a known layout once. The cost of doing this per tile could be prohibitive, so DRT makes the dynamic decision affordable by coarsening its granularity: it pre-tiles into cheap uniform micro tiles whose occupancy is trivial to count, then groups them into macro tiles, and does the counting in a tiny pipelined hardware unit that overlaps with the compute it feeds. This is the match-the-granularity- to-make-the-decision-cheap discipline the site sees when a system tracks per-word rather than per-byte access, or packs work at the segment rather than the element level — decide dynamically, but at a grain coarse enough that deciding is nearly free.

Why a fixed tile wastes the buffer, and how DRT fills it

From an occupancy-blind box to a buffer full of data

Tiling a sparse matrix product for an on-chip buffer. Numbers from DRT's evaluation.

Step 1 of 5

The memory wall

Sparse tensor multiply does almost no arithmetic per byte, so it is limited by DRAM bandwidth, and even specialized accelerators move 2-3x more traffic than the theoretical minimum. Tiling should fix this by loading data into on-chip memory once and reusing it — but only if each tile actually holds enough data to reuse.

the whole performance problem is data movement, not computation — dataflow alone cannot reach the floor
reuse raises the effective arithmetic intensity, moving the kernel off the memory wall

Why it works

Sparse kernels are memory-bound and tiling cuts traffic only if tiles are full → DRT sizes tiles by non-zero OCCUPANCY rather than coordinate shape → every tile fills the buffer and delivers reuse even in sparse regions.
Coordinate shape is decoupled from data amount for sparse tensors → DRT grows each tile at runtime, counting non-zeros until the buffer fills → tiles take non-uniform shapes but uniformly high occupancy.
The ideal tile of one operand depends on where the others have data → DRT co-tiles all operands jointly with aligned coordinate ranges → tiles that meet on-chip both carry useful data, so no work is wasted on empty intersections.
Introspecting whole tensors per tile would be too costly → a micro/macro hierarchy plus a pipelined Tile Extractor (counting 32 micro tiles per cycle) makes the dynamic decision nearly free → under 1% latency overhead and only 0.1% die area.
Filling tiles with real data raises arithmetic intensity → DRAM traffic drops near the theoretical floor → 2.4-16.6x intensity gains and 85% less energy, portable across accelerator dataflows.

What it costs

Micro-tile size must be chosen carefully. Too-large micro tiles approach the static-tiling failure they replace; too-small ones inflate metadata (over 8x overhead on two workloads with the current coordinate representation), so the micro-tile shape is a real tuning knob.
The intersection unit can bottleneck the win. On-chip logic that intersects the co-iterated tiles limits how much of the improved reuse becomes actual speedup; with ideal intersection the bandwidth scaling improves further, so headroom remains.
Buffers are statically partitioned. The on-chip buffer is split across tensors at design time; dynamic allocation is left to future work, which is suboptimal when output density varies a lot.
The tiling heuristic is greedy, not optimal. Finding optimal tile shapes is NP-hard, so DRT grows tiles greedily in a fixed dimension order; other orderings sometimes do better, and a rare fallback recursion handles dense tiles.
Load balance and software maturity are unfinished. Round-robin distribution of tiles to processing elements leaves load-imbalance headroom, and the CPU software implementation is preliminary, with two workloads where tiling metadata overhead still exceeds its gains.

The evaluation

Eighteen SuiteSparse and SNAP matrices (densities 0.0006% to 0.356%, varied sparsity patterns) across SpMSpM, tall-skinny products, multi-source BFS, and higher-order tensor contractions, integrated into the ExTensor, OuterSPACE, and MatRaptor accelerators and a CPU software implementation, measured against static tiling, dataflow-only designs, and CPU libraries (MKL, TACO).

Tiling sparse tensors for on-chip reuse

Property	No tiling (stream)	Static uniform-coordinate tiling (ExTensor)	DRT (dynamic reflexive)
What sizes a tile
Tile occupancy (buffer fill)	n/a
Adapts to irregular sparsity?
Co-tiles multiple operands?	No
DRAM traffic / intensity

DRT converts the abundant-but-irregular sparsity into full on-chip tiles by measuring real occupancy and co-tiling operands, so it brings DRAM traffic near its floor where static tiling leaves 2-3x on the table — at 0.1% extra die area — and the design ports across ExTensor, OuterSPACE, and MatRaptor dataflows.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

DRT’s dynamic tiling is powerful but has moving parts to tune and bottlenecks that cap it. The micro-tile size is a genuine knob — too large and it inherits static tiling’s low occupancy, too small and metadata overhead balloons (over 8x on two workloads) — and the on-chip intersection unit limits how fully the improved reuse turns into speedup, leaving headroom an ideal intersector would recover. Its buffers are statically partitioned across tensors at design time, suboptimal when output density varies, and its tile-growth heuristic is greedy (optimal tiling is NP-hard), so some inputs favor a different growth order and a rare fallback handles dense tiles. Load-balancing across processing elements and the CPU software path are unfinished, with two workloads where metadata overhead still outweighs the gains. None of this dulls the core insight — that tiling, the standard cure for a memory-bound kernel, fails on sparse data because a fixed coordinate shape is a lying proxy for how full a tile is, so the fix is to size tiles by their real non-zero occupancy, decided dynamically at runtime and jointly (reflexively) across the operands whose sparsity determines each other’s ideal shape — filling every tile with useful data, cutting DRAM traffic near its floor, at 0.1% area and 85% less energy, portable across sparse-accelerator dataflows.

Background

Measure the true occupancy, tile jointly, and decide at runtime because the data is irregular

DRT sits in the site’s sparse-accelerator cluster, near the graph-mining, GNN-operator, and robotic-accelerator pages, and rhymes with several ideas covered elsewhere on this site. Its founding move is the measure-the-true-quantity-not-a-proxy discipline the site keeps sharpening: a tile’s coordinate shape is exact for dense data but a lie for sparse data, so DRT sizes tiles by real non-zero OCCUPANCY — the same reframing the datacenter-IO-control page makes when it builds a device-occupancy metric because bytes lie about how much a request occupies a disk, and the tiered-memory page makes when it counts real accesses because the access bit lies about hotness. Its second move is to co-tile the operands REFLEXIVELY, since the ideal tile of one depends on where the others have data — the co-optimize-the-coupled- decisions discipline the heterogeneous-serving page brings to placement and routing and the FHE-compiler page brings to layout and scheduling. Its third move is instructive by contrast with the on-chip-memory- allocation page from the same domain: that problem is STATIC and known in advance, so it can be planned offline, whereas sparse structure is data-dependent and unknowable until seen, so DRT must decide at runtime — and it makes that runtime decision cheap by coarsening its granularity into micro tiles, the match-the-granularity-to-make-the- decision-affordable move the graph-mining and tiered-memory pages share. And underneath it all is the roofline logic the edge-inference page turns on — raise arithmetic intensity by reuse to escape the memory wall — achieved here by a tiny 0.1%-area hardware unit, the cheap-mechanism-for-an-outsized-payoff lesson the accelerator pages keep teaching.

If you remember only three things

1. Sparse tensor-algebra kernels (sparse matrix times sparse matrix, tensor contractions) that power graph analytics, solvers, and chemistry are severely memory-bound — very little arithmetic per byte moved — so even specialized accelerators move 2-3x more DRAM traffic than the minimum; tiling (blocking data into on-chip tiles for reuse) is the standard cure, but on sparse data a fixed coordinate-shaped tile catches an unpredictable, usually tiny number of non-zeros, so it under-fills the buffer (little reuse) or overflows it, and the right shape cannot be known ahead of time because it depends on where the data actually is.
2. DRT tiles by real OCCUPANCY rather than coordinate shape: DYNAMICALLY, growing each tile at runtime — expanding its coordinate range and counting non-zeros until the on-chip buffer is genuinely full, so every tile is high-occupancy with a non-uniform coordinate shape — and REFLEXIVELY, co-tiling all operands jointly with aligned coordinate ranges so one tensor's tiling reflects where the others have data; a micro/macro hierarchy (cheap uniform 32-by-32 micro tiles grouped into variable macro tiles) plus a pipelined hardware Tile Extractor make the runtime decision nearly free.
3. The result brings DRAM traffic near its theoretical floor (about 29.6 GB versus 65 GB for a dataflow-only design) and lifts arithmetic intensity 2.4x on square SpMSpM up to 16.6x on higher-order contractions over prior accelerators, at only 0.1% extra die area and 85% less energy, and ports across ExTensor, OuterSPACE, and MatRaptor — with honest limits (micro-tile-size tuning, an intersection-unit bottleneck, static buffer partitioning, and a greedy NP-hard heuristic). The durable lessons: measure the true quantity (occupancy) not a proxy (coordinate volume) that only happens to be exact for the dense case, co-optimize decisions that determine each other, and decide dynamically when the data is irregular — cheaply, by coarsening the grain.

Check yourself

Check your understanding

1. Tiling by a fixed coordinate shape works perfectly for dense matrix multiply but fails for sparse tensors. Predict the root reason.
2. DRT is "reflexive" — it co-tiles the operands of A times B together rather than tiling each independently. Predict why joint tiling is necessary.
3. The on-chip-memory allocation problem for ML (in a sibling paper) is solved by planning OFFLINE, but DRT must decide tile boundaries dynamically at RUNTIME. Predict what makes the difference.
4. DRT introduces a "micro tile / macro tile" hierarchy — pre-tiling tensors into small fixed 32-by-32 micro tiles, then dynamically grouping them into variable macro tiles. Predict why this hierarchy matters.

Sources

ACM DL: Accelerating Sparse Data Orchestration via Dynamic Reflexive Tiling — ASPLOS 2023 (full text read via the author-hosted PDF; no arXiv preprint).