Dataflow and spatial meshes

A spatial or dataflow architecture distributes a computation across an array of processing elements, each with local SRAM, connected by an exposed network-on-chip, and executes it under a schedule fixed largely at compile time. Sze et al. contrast it with temporal architectures (SIMD/SIMT CPUs and GPUs), whose ALUs share centralized control and cannot communicate except through the memory hierarchy.¹ The design premise is Dally’s cost model for accelerators: arithmetic is nearly free, global memory is expensive, and memory dominates area and power.²

The family spans a wide range of PE granularity. At one end are the systolic arrays of the previous chapter, where a PE is one MAC and a register. In the middle are coarse-grained reconfigurable arrays such as Stanford’s Plasticine, whose units are SIMD pipelines and banked scratchpads.⁴ At the other end are many-core designs whose “PE” is a full processor with hundreds of KB to MB of SRAM.⁶⁸ All of them share one problem: a model must be tiled, placed and routed onto the fabric, and the result is bounded by the slowest stage, the busiest link, or whatever does not fit in SRAM.

This chapter covers the execution model, the network (topology, routing, channel load, flow control), how layers are tiled and placed, the compiler’s central role, and the flexibility-versus-efficiency trade-off. Case studies are open publications on Plasticine, SambaNova’s SN40L, Graphcore’s IPU, Tesla’s Dojo D1 and AMD’s AI Engine. Wafer-scale designs push the same ideas past the reticle limit and have their own chapter, Wafer-scale and SRAM-heavy designs.

The energy argument, quantified

The normalized data-movement costs from the Eyeriss work, as summarized by Sze et al., are 1× for a register file of 0.5–1.0 kB inside the PE, 2× for a transfer from a neighbor PE over an array of 200–1000 PEs, 6× for a global buffer of 100–500 kB, and 200× for DRAM.¹ Two consequences follow. First, every reuse of a fetched value at a cheaper level pays back part of the fetch from a dearer level, so reuse is the objective of a dataflow. Second, large memories are dear per access even on chip, which argues for many small distributed banks over one big one. Dally et al. state the same conclusion as a design rule: memory, not arithmetic, typically dominates both the area and the power of a domain-specific accelerator.²

Granularity of the processing element

• Coarse-grained reconfigurable units. Plasticine splits the fabric into Pattern Compute Units (pipelines of reconfigurable SIMD stages) and Pattern Memory Units (banked scratchpads with their own address logic), in a 16 × 8 array with a 1:1 ratio and 256 KB per PMU.⁴ SambaNova’s SN40L uses the same unit names, adds address-generation and coalescing units, and connects them in a two-dimensional mesh.⁵
• Processor tiles. Each IPU tile is a multithreaded core with 256 KiB of SRAM that holds both its code and its data, in its own 21-bit address space.⁶ Each Dojo node is a vector core with matrix units and 1.25 MB of SRAM.⁸
• Tiles with shared neighbor memory. AMD’s AI Engine array is a 2D array of tiles, each a VLIW processor with memory and streaming interconnect.⁹ A tile has 32 KB of data memory in eight banks, and its processor can address its own memory and the memories of its north, south and one east-or-west neighbor as one contiguous block; cascade streams pass results from tile to tile.¹⁰ Shared neighbor memory is a second way, besides the network, to move data one hop.

Streaming dataflow versus kernel-by-kernel execution

A GPU typically runs one kernel (one or a few fused operators) across the whole chip, writes the result to HBM or a shared cache, then launches the next. The SN40L paper argues why this caps fusion: a grid of thread blocks is fixed for a kernel’s lifetime, so a transpose that crosses blocks forces a trip through shared cache or HBM; limited SRAM forces large intermediates out; and the programming model offers no straightforward way to run small matrix multiplies as a pipeline.⁵ On its Monarch-FFT example, the paper reports arithmetic intensity of 39.5 FLOP/byte unfused, 102.6 with partial fusion and 410.4 fully spatially fused, against an A100’s ratio of about 150 FLOP/byte, the point below which a kernel is memory-bound.⁵ (The workloads chapter explains the roofline reasoning behind that threshold.)

The spatial alternative maps the operators as stages of a coarse-grained pipeline. Stages with more of the work get more compute units, and stage buffers between them are split over enough memory units to match the bandwidth and capacity each needs. A transpose becomes an access pattern on a buffer rather than a data movement.⁵ The pipeline’s rate is the minimum over stages of their throughput, so the mapping problem is a load-balancing problem in three resources at once: compute, SRAM and network bandwidth.

Topology metrics

For a $k \times k$ mesh, node degree is 4, the diameter is $2(k-1)$ hops, and the bisection is $k$ links per direction, half that of a torus.¹² Latency splits into head latency (hops × per-hop router and link delay) and serialization latency (packet length ÷ link bandwidth).¹² Dojo’s D1 quotes one cycle per hop, 256 GB/s of bidirectional bandwidth on every row and column, and up to eight packets per cycle across each node’s boundary.⁸ Raw exposed wire delay to software directly as network hops.³

Routing

Routing functions are deterministic (one path per source–destination pair), oblivious (chosen without regard to network state, possibly randomized) or adaptive (chosen using local congestion).¹¹ Dimension-order (XY) routing is deterministic and minimal. It is simple and deadlock-free, but it throws away the mesh’s path diversity and load-balances poorly; turn-model routing recovers some adaptivity by forbidding only two of the eight possible turns, and minimal routing is the norm on chip.¹¹ Spatial accelerators add a third option that matters more than adaptivity: routes fixed by the compiler. SN40L supports both 2D dimension-order routing and software-assigned static flows, in which a flow ID carried by the packet is decoded and reassigned at every switch port; static flows also support multicast.⁵ Raw had two static networks, with routes specified at compile time, and two dynamic ones.³ Plasticine’s interconnect is entirely statically configured, with registers in the switch links to avoid long wire delays.⁴

Channel load and saturation

For a traffic pattern and routing function, the load $\gamma_c$ on channel $c$ is the traffic that crosses it per unit of injected traffic. The network saturates when the most loaded channel is busy every cycle, so maximum throughput is $b / \max_c \gamma_c$ for link bandwidth $b$. A channel load of 2 relative to injection means each node can inject at most half the link bandwidth.¹² For an accelerator the “traffic pattern” is not random: it is the producer-to-consumer streams the compiler created, known exactly in advance. That is why the compiler can, and must, compute channel loads before it commits to a placement.

Flow control, congestion and throttling

SN40L’s vector and scalar fabrics are packet-switched with credit-based flow control at every hop, plus end-to-end flow control between communicating units that combines software tokens, hardware credits and forward-progress guarantees; a separate circuit-switched control fabric of single-bit wires carries tokens, typically marking the end of a loop, that orchestrate execution of the graph.⁵ Its designers report that bandwidth problems “often boiled down to” network congestion or memory bank conflicts, that bursty traffic could slow an entire kernel, and that programmable packet throttling mitigated many of the congestion issues, with stall counters in the switches and memory units helping to find hot spots.⁵

Many-to-one and multicast

Layer boundaries rarely have equal producer and consumer counts, so traffic is often one-to-many (a weight or activation broadcast) or many-to-one (a gather or reduction). SN40L lists hardware fan-out paths for multicast and sequence IDs on vector packets so that a consumer can reorder data arriving out of order from many producers.⁵ Eyeriss v2 makes the same point at small scale: a broadcast network starves PEs when reuse is low, and an all-unicast network wastes energy when reuse is high, so its hierarchical mesh switches between the two per data type, raising MobileNet throughput 5.6×.¹³

Mesh versus exchange

The IPU is the useful counterexample. Its on-chip exchange sustained 7.7 TB/s in an all-to-all test, every tile could use 6.3 GB/s to any destination, tile-to-tile latency was at most 165 ns and did not degrade under load, and near and far tile pairs reached the same bandwidth for blocks of 32 KiB or more.⁶ The IPU pairs that network with the bulk synchronous parallel model: compute, then exchange, then barrier, with the exchange scheduled by the compiler.⁶ Dojo takes the opposite stance: its slides say the system network has less bandwidth for long routes, which cross die and tile boundaries, that long routes consume a lot more of the system’s resources, and that software has a strong incentive to keep most communication local, with the amount of data transferred falling quickly with distance.⁸

The three budgets

For a chain of layers $i = 1 \dots L$ on a mesh of identical cores of rate $F$ (FLOP/s) and usable SRAM $S$, assigning $n_i$ cores to layer $i$ with work $W_i$ (FLOP per input), weights $M_i$ and output activations $A_i$ per input gives, with weights split evenly:

• Compute per stage: $t_i = W_i / (n_i F)$.
• SRAM per core: $M_i / n_i + B$, for streaming buffers $B$, which must not exceed $S$.
• Network: the per-link load produced by streaming each $A_i$ to layer $i + 1$’s cores, which depends on the split, the placement and the routing.

The pipeline’s time per input is the maximum over all three, and $\sum n_i$ is bounded by the core count. Compute balance alone would give $n_i \propto W_i$, but late layers of many networks carry most of the weights and little of the work, so the SRAM constraint, not compute, sets their core count. The sim’s model has exactly this shape.

How the split determines the traffic

For a dense layer $Y = XW$, splitting $W$ by output columns over $n_i$ cores (weights divided evenly) leaves each core with a column slice of $Y$. If the next layer is also column-split, each of its cores needs all of $Y$: all-to-all traffic, or a gather followed by a broadcast. Splitting the next layer by rows of its weight matrix instead lets core $k$ consume only slice $k$ of $Y$, so traffic is point-to-point between matching slices, but each consumer then produces a partial sum and the partial sums must be reduced. Splitting activations spatially (bands of an image, chunks of a sequence) keeps traffic local at the price of replicating weights and exchanging halos at band edges. These are the same tensor-, pipeline- and data-parallel choices that the parallelism chapter covers across chips, applied within one die; the SN40L paper notes that, to its compiler, mapping parallel dataflows across sockets is similar to mapping them within one.⁵

Describing a mapping

MAESTRO describes a mapping with data-centric directives: a spatial map distributes a loop dimension across PEs, a temporal map steps it over time, and clusters group PEs into levels so that the same notation describes nested arrays.¹⁵ Timeloop represents mappings as loop nests with tiling factors and orderings at each storage level, and treats the set of valid mappings for an architecture as a mapspace to be searched.¹⁴ Both make the point that the dataflow, not just the hardware, determines reuse, utilization and energy.

What gets decided statically

In a spatial machine the compiler absorbs work a GPU does in hardware at run time: operand delivery (instead of caches and warp schedulers), routing (static flows instead of only dynamic routing) and synchronization (compiled barriers or tokens instead of hardware scheduling).

• Plasticine’s flow. Applications in a parallel-pattern language are unrolled by parallelization factors, lowered to virtual PCUs and PMUs with unlimited resources, partitioned onto physical units by a greedy algorithm with a cost metric over stages, live variables and I/O buses (graph partitioning being NP-hard in general), then bound hierarchically with placement, routing and register allocation. The hierarchy keeps each level of mapping under 1,000 nodes, and together with the coarse buses it lets compilation finish in minutes.⁴
• SN40L’s flow. A place-and-route layer programs the routing tables of all three network fabrics. The compiler allocates HBM and DDR, using static symbol-lifetime analysis because the programming model has neither dynamic allocation nor pointer aliasing. A static bandwidth model of application and hardware drives how many streams each unit gets, and kernel schedules can be offloaded to hardware to cut launch overhead.⁵
• IPU’s flow. Programs are vertices, tensors and static exchange edges; Poplar allocates data at rest, I/O buffers and the timing of every transfer, all organized as bulk-synchronous supersteps.⁶
• Dojo’s flow. A flat address scheme exposes the topology to software; software avoids dead nodes, and the compiler defines barrier domains and their communication trees.⁸

Why search is unavoidable

Timeloop’s motivating example: on a 1,024-MAC accelerator, 480k mappings of VGG conv3_2 within 5% of peak performance span nearly 19× in energy, only one is energy-optimal, and 6,582 mappings with the same (minimum) DRAM traffic still vary 11× because on-chip buffer accesses are not free. The optimal mapping changes across workloads, and a mapping that is optimal on one architecture can be poor or invalid on another.¹⁴ A spatial compiler therefore needs a fast, accurate cost model and a search procedure, and its quality is part of the chip’s measured performance: a benchmark result measures a chip and its compiler together (see Comparing chips).

Each layer’s weights are split evenly over its cores, with 64 KB per core reserved for stream buffers. Producer core $j$ of layer $i$ sends core $k$ of layer $i + 1$ the share of $A_i$ where their output and input fractions overlap (a matched-slice split), routed XY. Time per image is max(slowest stage, busiest link ÷ link bandwidth, SRAM overflow ÷ 100 GB/s of off-chip bandwidth). The Expert view adds link-bandwidth and SRAM sliders, the three bounds in µs, and traffic × distance (MB·hop) as a proxy for network energy. Try:

• In Pipelined, find the binding constraints. Then lower the link bandwidth: at what point does the network take over?
• Compare byte-hops for Pipelined and Scattered. How does the hottest link’s load change, and why less than the byte-hops?
• Shrink SRAM to 256 KB. Which layer overflows first, and how many cores would it need?

It is a first-order model: no latency, no router contention beyond link loads, no input or output traffic to the chip edge, and spills charged as if every overflowing weight were re-read from off-chip memory for every image.

Points worth drawing out of the data:

• SRAM per unit of compute. SN40L pairs 638 BF16 TFLOPS with 520 MB of SRAM, and Dojo D1 pairs 362 BF16/CFP8 TFLOPS with 440 MB.⁵⁸ Both are around 1 MB of SRAM per TFLOPS of peak, which is the regime where a meaningful slice of a model, not just a tile of one layer, can stay resident.
• Network headroom. On the IPU, the 7.7 TB/s measured exchange throughput is about a sixth of the 45 TB/s nominal aggregate local-memory bandwidth.⁶ Local memory is the fast path; the network is the scarcer resource, which is the assumption behind keeping traffic local.
• Memory tiers. SN40L adds 64 GB of HBM at about 1.8–2 TB/s and up to 1.5 TB of DDR at about 200 GB/s per socket, with the compiler deciding what spills where.⁵ Pure-SRAM designs instead scale out to more chips when a model exceeds on-chip capacity, the subject of the wafer-scale chapter.
• Research versus product numbers. Plasticine’s 76.9× is a cycle-accurate simulation against an FPGA, with area from synthesis, not silicon.⁴ The Citadel IPU numbers are independent microbenchmarks; the others are the designers’ own figures.

Flexibility versus efficiency, quantified where possible

Plasticine’s case: bit-level reconfigurability costs FPGAs over 60% of their area and power in programmable interconnect and limits clock rates through long combinational paths, while word-level CGRAs offer denser compute and clock rates up to an order of magnitude higher; Plasticine’s simulated result was up to 76.9× perf/W over an FPGA.⁴ In the other direction, every bit of configurability a spatial chip keeps (routing tables, programmable address generators, flow IDs, sequence IDs for reordering) is area and energy a hard-wired systolic array does not spend, and the SN40L paper lists those features as requirements for streaming dataflow with arbitrary access patterns between operators.⁵ Dally et al. frame the middle ground: specialize for a domain, keep programmability where algorithms move, and co-design the algorithm with the hardware.²

Static versus dynamic

Static schedules make performance predictable and let the compiler compute channel loads exactly, but they fit poorly with data-dependent behavior: dynamic shapes, routing decisions inside the model, variable sequence lengths. SN40L’s answer for its composition-of-experts system is to compile each expert independently and switch models at run time, with model-switching cost (copying an expert from DDR to HBM) as the new bottleneck it optimizes.⁵ The IPU’s BSP discipline separates computation from exchange in time, at the cost of not overlapping compute and communication within a superstep and waiting at every barrier for the slowest tile.⁶

Mesh versus richer networks

A mesh is cheap and scales with the die, but its bisection is only $k$ links per direction and its diameter grows with $k$.¹² Designs answer with locality (Dojo restricts global traffic to synchronization and all-reduce), with static routes that spread load (SN40L’s flows), or with a non-mesh exchange whose bandwidth is nearly distance-independent (IPU).⁸⁵⁶

Failure modes and how they show up

• Load imbalance: stage utilization far below 100% except on one stage; fixed by reassigning cores or splitting the slow operator.
• Network saturation: stall counters climbing at a few switches; SN40L exposes per-switch performance counters and programmable packet throttling for this.⁵
• Bank conflicts: double buffers of arbitrary shapes landing in the same SRAM banks; fixed in SN40L by mapping buffers to different banks with programmable bank bits.⁵
• Deadlock: cyclic channel dependencies, avoided by dimension-order or turn-model routing, or by compiler-verified static routes.¹¹
• Defects: a dead core breaks the regular grid; Dojo requires every router on a usable die to work and has software avoid dead processing nodes.⁸

The analytic model behind the simulation, the routing and channel-load computation it uses, why dimension-order routing cannot deadlock, and how compilers search for mappings.

1. A three-bound pipeline model

Take a chain of $L$ layers. Layer $i$ needs $W_i$ FLOP per input, holds $M_i$ bytes of weights and emits $A_i$ bytes of activations. It runs on $n_i$ cores of rate $F$, each with SRAM $S$ of which $B$ bytes go to buffers. Links carry $b$ bytes/s per direction, off-chip memory $D$ bytes/s.

1. Compute bound:
   $$T_{\mathrm{comp}} = \max_i \frac{W_i}{n_i F}$$
2. Network bound:
   $$T_{\mathrm{net}} = \frac{\max_c \gamma_c}{b}$$
   where $\gamma_c$ is the bytes per input that cross directed link $c$ (step 2).
3. Memory bound: every byte of weights that does not fit is re-read for each input, so
   $$T_{\mathrm{mem}} = \frac{1}{D} \sum_i n_i \max\!\left(0,\ \frac{M_i}{n_i} + B - S\right)$$
4. Time per input
   $$T = \max(T_{\mathrm{comp}},\ T_{\mathrm{net}},\ T_{\mathrm{mem}})$$
   Throughput is $1/T$. Latency for one input would instead be the sum of stage delays plus network latency, which this model does not track.

In the sim, $F = 1\,\mathrm{TFLOP/s}$, $B = 64\,\mathrm{KB}$, $D = 100\,\mathrm{GB/s}$, and the five layers have ($W$ in MFLOP, $M$ in KB, $A$ in KB): conv1 (100, 32, 3000), conv2 (300, 600, 1800), conv3 (300, 2400, 900), conv4 (150, 4000, 300), fc (15, 1000, 4). With 512 KB per core and 16 GB/s links, the Pipelined preset (6, 9, 9, 9, 3 cores) has $T_{\mathrm{comp}} = 33.3\,\mu\mathrm{s}$ and $T_{\mathrm{net}} = 33.3\,\mu\mathrm{s}$, so about 30,000 images/s; Scattered (same counts, random placement) has $T_{\mathrm{net}} = 45.8\,\mu\mathrm{s}$ and 72% more byte-hops. These numbers are illustrative, chosen so that each bound can bind.

2. Channel loads under XY routing

Order each layer’s cores (the sim uses row-major order) and give producer $j$ of $n_i$ the output fraction $[\,j/n_i,\ (j+1)/n_i)$ and consumer $k$ of $n_{i+1}$ the input fraction $[\,k/n_{i+1},\ (k+1)/n_{i+1})$. The bytes from $j$ to $k$ are $A_i$ times the length of the intersection of those intervals. Each such flow is routed X first, then Y, and its bytes are added to every directed link on the path:

1. From $(r, c)$ step $c$ toward the destination column, adding the flow to the east or west link at each step.
2. Then step $r$ toward the destination row, adding it to the south or north links.
3. After all flows, $\gamma_c$ is the sum on link $c$ and the hottest link is $\operatorname{argmax}_c \gamma_c$. Byte-hops $\sum_c \gamma_c$ are a first-order proxy for network energy, since each hop costs roughly the same energy per byte.

Because XY routing is deterministic, $\gamma$ is a linear function of the flow matrix, which is what lets a compiler evaluate a candidate placement quickly and why static traffic is so much easier to plan than random traffic.¹¹¹²

Two observations the sim makes concrete. First, under XY routing a single core’s output leaves on at most four links (east, west, north, south), so $\max \gamma$ is at least $\max_i A_i/(4 n_i)$ for any placement; when all of a core’s consumers lie in one direction, as in banded placements, the bound tightens to $A_i/n_i$. Either way, the early, activation-heavy layer needs cores for injection bandwidth, not just compute. Second, scattering cores raises byte-hops a lot but the maximum load less, because the extra traffic spreads over many links; on a larger mesh, or one with more layers sharing it, the overlap and hence the maximum grows.

3. Why XY routing cannot deadlock

A routing deadlock needs a cycle of packets, each holding a channel and waiting for the next channel in the cycle. In a 2D mesh a packet can make eight kinds of turn (from ±X to ±Y and from ±Y to ±X), and any cycle in the channel-dependency graph needs at least one turn from Y back to X. Dimension-order routing finishes X before starting Y, so it never makes those turns, the dependency graph is acyclic, and no deadlock is possible.¹¹ The turn model generalizes this: forbid just two of the eight turns, one in each potential cycle direction, and routing stays deadlock-free while regaining some adaptivity.¹¹ Protocol-level deadlock (requests waiting on responses that wait on requests) is a separate issue, handled with separate message classes or, in statically scheduled machines, by the compiler’s schedule.

4. Mapping as search

A mapper needs three parts:

1. A mapspace. For each layer, the tiling factors per loop and memory level, loop orders, which dimensions are spread across PEs (spatial) and which are stepped through time (temporal). MAESTRO writes these as SpatialMap and TemporalMap directives within nested clusters of PEs.¹⁵ For a whole model on a mesh, add core counts per layer and a placement.
2. A cost model. It must be fast enough to evaluate many candidates and accurate enough not to mislead. Timeloop’s point that 6,582 mappings with equal DRAM traffic still differ 11× in energy shows that counting only off-chip traffic is not enough.¹⁴
3. A search. Exhaustive enumeration is feasible for small mapspaces; otherwise random sampling, heuristics or hierarchical decomposition. Plasticine partitions virtual units greedily with a cost metric and binds hierarchically so each level has fewer than 1,000 nodes.⁴

The placement part of the problem resembles VLSI placement: minimize communication weighted by distance, subject to capacity (SRAM per core) and congestion (channel loads), which is why the same families of techniques (partitioning, greedy construction, iterative improvement) appear in both. See Placement for the chip-level versions of those algorithms.

5. A simple balancing heuristic

One way to produce core counts like the sim’s Pipelined preset:

1. Give each layer the minimum that fits its weights: $n_i = \lceil M_i / (S - B) \rceil$. If $\sum n_i$ already exceeds the core count, the model needs off-chip memory or more chips.
2. While cores remain, give one to the layer with the largest $\max(W_i/F,\ A_i/b) / n_i$, a combined compute and injection time.
3. Place layers in consecutive column bands so that each layer’s slices sit beside the matching slices of the next.
4. Compute $\gamma$ under XY routing, and if one link dominates, move or swap cores near it and re-evaluate.

With the sim’s numbers at 512 KB and 16 GB/s, steps 1 and 2 give 6, 9, 9, 9 and 3 cores. Step 4 is where real compilers spend their effort, with richer splits, multicast, static flows that avoid hot links, and models of router latency and buffering that this model leaves out.⁵