Sigma: Compiling Einstein Summations to Locality-Aware Dataflow

Reconfigurable dataflow accelerators can run tensor math extremely fast, but only if the compiler keeps reused data flowing through the chip's tiny, fast on-chip memories instead of re-reading it — and today's compilers, which just drop each operation onto its own hardware block, miss that reuse and demand deep accelerator expertise from programmers; this work from Stanford builds Sigma, which lets a user write the computation in the concise mathematical notation of Einstein summations and automatically compiles it into a locality-aware dataflow that exploits the fine-grained memory, so non-experts get high performance from a short formula.

The argument in one glance

Problem

Dataflow accelerators are fast only if data is reused on-chip

Reconfigurable dataflow accelerators run tensor math by laying a program out across a fabric of compute and memory elements, with data streaming through. They are fast only when the compiler keeps reused data in the chip's tiny, fast on-chip memories rather than re-reading it. But that reuse is exactly what standard compilers miss.
What people did

Map each operation to its own hardware element

Most dataflow accelerator compilers reach high performance by mapping each node of a dataflow program to a dedicated hardware element on the accelerator, laying the whole computation out in space.
Why it fell short

Per-node mapping misses reuse and needs expertise

This per-node mapping optimizes where operations sit but not how data moves, so it misses the data-reuse optimizations needed to exploit the huge bandwidth of fine-grained memories like FIFOs and pipeline registers — the same values get fetched over and over. And writing a performant dataflow program in the first place demands deep expertise in the specific accelerator, which most users lack.
This paper's idea

Compile Einstein summations to locality-aware dataflow (Sigma)

Sigma lets users write the computation in Einstein summation notation — a concise, hardware-agnostic description of a tensor operation — and automatically compiles it to a locality-aware dataflow. Because the notation exposes exactly which data is shared across the computation, Sigma can place reused values in the fine-grained on-chip memory and feed the compute at full bandwidth, giving non-experts high performance from a short formula.

Why this problem is worth solving

These accelerators are powerful, but their power is bottlenecked by how data is fed to them.

A reconfigurable dataflow accelerator is a chip built from a fabric of many small compute units interleaved with small memory elements. Rather than running instructions one after another as a normal processor does, it lays a whole computation out in space: each operation is placed on its own hardware unit, and data streams through the fabric from one unit to the next, so many operations run at once in a pipeline. This gives enormous compute throughput. The catch is feeding it. The compute units can only work as fast as data arrives, and the accelerator’s real advantage comes from its fine-grained memories — the small, fast FIFOs (first-in, first-out queues) and pipeline registers that sit directly beside the compute and can supply a value every single cycle. To use that bandwidth, a computation must reuse data: keep a value that will be needed many times close to the compute and use it repeatedly, rather than fetching it again from slower, larger memory each time. Tensor computations, which dominate machine learning and scientific computing, are full of such reuse — the same weight or input feeds many multiplications. Exploiting it is where the accelerator’s performance is won or lost, and it is precisely what a good compiler for these accelerators must get right.

The way current tools work leaves that performance unclaimed, and locks non-experts out.

Most compilers for dataflow accelerators take a program written as a dataflow graph and map each node of that graph to a dedicated hardware element on the accelerator. This is a natural strategy and reaches high performance on the compute side, because it spreads the operations across the fabric to run in parallel. But it optimizes the wrong thing. It decides where each operation goes, yet it does not optimize how data moves between operations, so it misses the data-reuse optimizations that would keep a reused value in a nearby FIFO or pipeline register. As a result, the fine-grained memories — the very thing that makes the accelerator fast — are underused, and the same data is fetched from larger memory again and again, wasting bandwidth. There is a second problem layered on top. To get good performance out of these accelerators, a programmer today has to write the dataflow program carefully, with the accelerator’s memory hierarchy and pipeline structure in mind. That requires deep, accelerator-specific expertise that most users of machine learning or scientific tensor computations simply do not have, so the accelerators are hard to program well and remain the province of specialists.

What people did before, and where it broke

Map each dataflow node to a hardware element. Spread a dataflow program’s operations across the accelerator fabric, one hardware unit per node. Where it broke. This optimizes the placement of compute but not the movement of data, so it misses reuse and leaves the fine-grained memories underused.
Hand-tune the dataflow program for reuse. Have an expert carefully structure the program to keep reused data in fast on-chip memory. Where it broke. It works only if the programmer has deep, accelerator-specific expertise, which most users lack, so the accelerators are hard to program well.
Use high-level frameworks that ignore the hardware’s memory. Write in a familiar high-level tensor framework and rely on a generic backend. Where it broke. Generic backends do not target the accelerator’s fine-grained FIFOs and pipeline registers, so they leave the reuse-driven bandwidth unexploited.
The gap. No approach let a user express a tensor computation at a high, hardware-agnostic level and automatically get a dataflow that exploits fine-grained-memory data reuse. Doing that, by compiling Einstein summations to a locality-aware dataflow, is what Sigma sets out to do.

How Sigma works

From per-node mapping to reuse-aware dataflow from a formula

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Let the user write the math, and let the compiler find the dataflow. Sigma’s starting point is to raise the level at which a computation is expressed: instead of a hand-crafted dataflow program tuned to a particular accelerator, the user writes an Einstein summation, a concise mathematical description of a tensor operation that says nothing about the hardware. From that high-level form, the compiler derives an efficient, locality-aware dataflow. Expressing a computation in a clean high-level notation and letting good execution follow from it, rather than hand-writing the low-level schedule, is the same design the time-indexed stream-query work covered elsewhere on this site follows, writing queries in a form from which fusion and parallelism emerge automatically instead of being coded by hand.

Exploit the notation to keep reused data in the fastest memory. The performance of these accelerators lives in reuse — keeping a value that feeds many operations in a fine-grained FIFO or pipeline register beside the compute, rather than re-fetching it. Einstein summation notation names the shared indices of a tensor operation directly, so it exposes exactly which data is reused, letting Sigma place those values in the fast on-chip memory and feed the compute every cycle. Keeping the hot, reused data in the small fast memory closest to the compute is the same instinct the manycore work-stealing work covered elsewhere on this site relies on, moving the frequently-touched data into fast local scratchpad memory so the common accesses run at full speed instead of paying for slow memory.

Turn a high-level description into an efficient hardware mapping automatically. At heart Sigma is a compiler that closes the gap between a mathematical specification and a good accelerator implementation, sparing the user the accelerator-specific tuning that used to be required. Automatically translating a high-level intent into an efficient mapping onto specialized hardware, rather than leaving it to expert hand-effort, is the same move the sketch-guided hardware-mapping work covered elsewhere on this site makes, taking a high-level description and having the tool produce the correct, efficient low-level configuration so a non-specialist can target the hardware.

Following a tensor computation through Sigma

Compiling a matrix-multiply-style contraction

A high-level trace of the approach as suggested by the title and the abstract; the exact compiler internals are beyond the abstract this page is based on.

Step 1 of 5

Write the computation as an Einstein summation

A user wants a tensor contraction — say a matrix multiply — and writes it in Einstein summation notation, naming the shared index that is summed over to combine the two inputs.

The notation is short and says nothing about the accelerator.

Why it works

Moving data dominates on accelerators. Because a dataflow accelerator has abundant compute but limited memory bandwidth → the cost of a computation is set by how much data it moves, not how much it computes → so exploiting on-chip data reuse is where performance is won.
Per-node mapping ignores reuse. Because mapping each operation to its own hardware element optimizes the compute layout but not the data movement → the same values are re-fetched instead of reused → so the fine-grained memories that could feed the compute go underused.
Fine-grained memory has the bandwidth. Because FIFOs and pipeline registers sit right beside the compute and can supply data every cycle → keeping reused values there feeds the compute at full rate → so a compiler that targets them unlocks the accelerator’s real throughput.
Einstein summation exposes the reuse. Because the notation names the indices of every tensor and the index summed over → the compiler can read directly which data is shared across the computation → so it can place reused values in fast memory without the user annotating anything.
A high-level notation removes the expertise barrier. Because the user writes only the math, not the dataflow → the compiler handles the accelerator-specific locality optimization → so non-experts obtain performant mappings they could not have hand-written.

What it costs (trade-offs and scope)

It targets computations expressible as Einstein summations. Sigma’s input is tensor operations written as Einstein summations — contractions, and the operations that compose from them. Computations that do not fit that notation fall outside its model.
It targets reconfigurable dataflow accelerators. The locality optimization is aimed at the fine-grained memories of dataflow accelerators. The approach is specific to that hardware class, not general-purpose processors or every accelerator design.
The benefit tracks how much reuse exists. Sigma’s advantage comes from exploiting data reuse in fine-grained memory. A computation with little reuse, or one already memory-bandwidth-bound elsewhere, has less for it to capture.
It is a compiler that must be built and maintained. Getting Sigma’s benefits requires its compilation stack targeting a specific accelerator; it raises the abstraction for users but is itself real infrastructure tied to the hardware it targets.
Raising abstraction can cede fine control. Writing at the Einstein-summation level frees users from low-level tuning, but an expert who wants to hand-craft an unusual dataflow gives up some of that direct control to the compiler.
This page is written from the abstract. The full text was not available when this explainer was prepared, and the published abstract states the problem but not the mechanism or the results, so the details of how Sigma analyzes reuse and generates dataflow, and its quantitative results, are not reproduced here; the mechanism is described only at the level the title and problem statement imply, with standard background clearly marked.

The evaluation

Three ways to get a tensor computation onto a dataflow accelerator

Property	Hand-written dataflow	Per-node mapping compiler
What the user writes		A dataflow program
Needs accelerator expertise		Yes
Exploits fine-grained memory reuse	If the expert does it
Optimizes for	Whatever the expert tunes
What this page reports	Background	Background

Three ways to run a tensor computation on a reconfigurable dataflow accelerator, as framed by the paper's abstract. Hand-writing a dataflow program can be fast but demands accelerator-specific expertise. Per-node mapping compilers spread operations across the fabric but optimize compute placement rather than data movement, so they miss the reuse that would exploit the accelerator's fine-grained FIFOs and pipeline registers. Sigma lets the user write the computation as an Einstein summation — a concise, hardware-agnostic notation whose named indices expose which data is reused — and compiles it to a locality-aware dataflow that keeps reused values in the fine-grained memory to feed the compute at full bandwidth, without requiring the user to be an accelerator expert. The published abstract states this problem and approach but not the mechanism details or quantitative results, which are in the full paper; this table conveys the approach only.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is written from the paper’s abstract, because the full text was not available when it was prepared, and the published abstract itself states the problem while stopping short of the detailed mechanism and results. So this page explains the setting and the shape of the idea, and treats the specifics only at the level the title and problem statement imply, with standard background about dataflow accelerators and Einstein summation clearly marked as such. What is clear and worth taking away is the motivation and the approach. Reconfigurable dataflow accelerators are fast only when a computation reuses data in their fine-grained on-chip memories — the FIFOs and pipeline registers that can feed the compute every cycle — yet the usual compiler strategy of mapping each operation to its own hardware element optimizes compute placement and misses that reuse, and writing a fast dataflow program by hand requires accelerator-specific expertise. Sigma’s response is to raise the abstraction: users write the computation as an Einstein summation, a concise notation whose named indices reveal which data is shared, and Sigma compiles that to a locality-aware dataflow that exploits the fine-grained memory. Treat the details — exactly how Sigma analyzes reuse and generates the dataflow, and how much it improves performance — as beyond what this summary can responsibly claim; those are in the full paper. The durable idea is that on data-movement-bound accelerators, a compiler must optimize for reuse and locality, and that a high-level, index-named notation both exposes the reuse to the compiler and frees the user from expert hand-tuning.

Background

Why data movement, not compute, sets accelerator performance

It helps to place Sigma within a theme that dominates modern accelerator design: as compute grows cheap and plentiful, the real cost and the real bottleneck is moving data, so the systems that win are the ones whose compilers and hardware keep data close to the compute and reuse it. Sigma pursues this by targeting the fine-grained on-chip memories of dataflow accelerators and keeping reused tensor values there. The pointer-traversal-acceleration work covered elsewhere on this site attacks the same underlying truth from the memory side, placing computation next to the data so that work which would otherwise shuttle across a slow interconnect happens locally. The common thread is that a fast compute fabric is useless if it is starved for data, so the leverage is in locality — reusing what you have fetched, and putting computation where the data already is. A second thread runs alongside it: as this hardware grows more specialized and harder to program, raising the level at which people express computations, so a compiler can handle the locality optimization, is what lets non-experts actually use it. The general lesson is that accelerator performance is increasingly a data-movement problem solved by a compiler, and that the right high-level abstraction is what makes both the optimization and the accessibility possible.

If you remember only three things

1. Reconfigurable dataflow accelerators run tensor computations fast by laying operations out in space across a fabric of compute and memory, but their real advantage comes from fine-grained on-chip memories (FIFOs and pipeline registers) that can feed the compute every cycle — which requires reusing data, keeping a value that feeds many operations close to the compute rather than re-fetching it. Most compilers for these accelerators map each operation of a dataflow program to its own hardware element, which optimizes compute placement but not data movement, so it misses this reuse and leaves the fine-grained memories underused. Worse, writing a performant dataflow program by hand demands deep, accelerator-specific expertise most users lack.
2. Sigma raises the level of abstraction: users write the computation as an Einstein summation, a concise, hardware-agnostic notation that names the indices of each tensor and the index summed over, and Sigma automatically compiles it to a locality-aware dataflow. Because the notation names shared indices explicitly, it exposes exactly which data is reused across the computation, so Sigma can place those reused values in the fine-grained on-chip memory and feed the compute at full bandwidth — giving non-experts reuse-driven performance from a short formula rather than hand-tuning.
3. The approach targets tensor computations expressible as Einstein summations, on reconfigurable dataflow accelerators, and its benefit tracks how much data reuse the computation has; it is a compiler tied to the hardware it targets, and raising the abstraction cedes some fine control to the compiler. The broader lesson is that accelerator performance is a data-movement problem best solved by a compiler that optimizes for reuse and locality, and that an index-named high-level notation both exposes the reuse and removes the expertise barrier. Note: this explainer is written from the abstract, which states the problem but not the mechanism or results, so the compiler internals and quantitative results are not reproduced here.

Check yourself

Check your understanding

1. Why is data reuse the key to performance on a reconfigurable dataflow accelerator?
2. Why does mapping each dataflow node to its own hardware element miss performance?
3. What does using Einstein summation notation give Sigma?
4. A computation has almost no data reuse — every value is used just once. What does Sigma's reasoning imply for it?

Sources

The paper is “Sigma: Compiling Einstein Summations to Locality-Aware Dataflow” by Tian Zhao, Alexander Rucker, and Kunle Olukotun, published at ASPLOS 2023, DOI 10.1145/3575693.3575694. The authors are at Stanford University.

This explainer is written from the paper’s abstract, because the full text was not available at the time of writing: although the paper is open access under a Creative Commons Attribution license, the publisher’s copy was behind automated-access protection, no preprint was available, and no separately hosted author copy could be retrieved. The published abstract states the problem — that most dataflow accelerator compilers achieve high performance by mapping each node in a dataflow program to a dedicated hardware element, that this misses the critical data-reuse optimizations required to exploit the bandwidth of fine-grained memory elements such as FIFOs and pipeline registers, and that writing performant dataflow programs requires domain expertise in the underlying dataflow accelerators — and, from the title, that the paper’s system Sigma compiles Einstein summations to locality-aware dataflow. Those framing points come directly from the abstract and title. The abstract as published does not detail Sigma’s mechanism (how it analyzes reuse and generates the dataflow) or report quantitative results, so those are not reproduced here. The surrounding explanation of reconfigurable dataflow accelerators, fine-grained on-chip memories, data reuse and locality, and Einstein summation notation is standard, widely-known background provided to make the abstract’s framing understandable, and is not specific to this paper. The compiler internals and the evaluation are not reproduced here because they were not available.