Enhancing CGRA Efficiency Through Aligned Compute and Communication Provisioning

Reconfigurable arrays give every small compute unit its own router powerful enough to reach any neighbour every cycle, so that the array can survive peak routing congestion — congestion that only happens occasionally, leaving the wiring and its instruction memory drawing 44 percent of the power to serve arithmetic that draws 9; Plaid (NUS) observes that dataflow graphs are not arbitrary because a node takes at most two inputs, that every three-node piece of one is therefore one of exactly three shapes, and builds a tile where three compute units share a single router that handles the traffic inside such a shape locally.

Why this problem is worth solving

The machine is a grid whose cost is dominated by the part nobody counts.

Fitting a loop onto the grid is a scheduling problem with a rhythm.

What people did before, and where it broke

• Give every element a fully capable router and reconfigure it every cycle. The high-performance design point, and the reason these arrays are general — any operation can go anywhere and talk to anyone. Where it broke. Peak routing congestion happens only intermittently, so the capacity provisioned for it sits idle most of the time, and describing it is expensive: a single dependency between two operations means configuring at least two routers, which is why the instruction memory alone reaches 48 percent of power.
• Hold one fixed configuration for a whole code segment. Energy-minimal designs do this, and it works — the instruction memory can be gated off entirely, and power falls sharply. Where it broke. A graph too complex to fit in one arrangement must be cut into pieces, with the values that cross the cut written out to memory and read back, adding loads and stores that cost real cycles.
• Prune the array to the workload. A framework can take a homogeneous array plus the applications it must run and cut each tile down to what the statistics justify, saving substantial power. Where it broke. The result is fast for the target domain and worse for everything else, which trades away the property that made the array worth building.
• Hard-wire the frequently occurring subgraphs of a domain. Several designs identify common patterns in a target application suite and build fixed circuits for them, with one block handling each code section. Where it broke. Same trade, plus under-utilisation when the running code does not match the patterns chosen at design time, and a network whose depth and timing must be re-explored for each new target.
• Build a better network instead. Multi-hop single-cycle interconnects, hybrid networks, and designs that split control traffic from data traffic all attack the routing cost directly. Where it broke. They make the communication cheaper without asking whether the amount provisioned was right in the first place.
• The gap. Every approach either kept the per-element router and tried to make it cheaper, or narrowed the target so less router was needed. Nobody asked whether the graphs being mapped have a structure that would let the routing shrink without the generality shrinking with it.

How a router shared by three units replaces three routers

The idea

The routing was sized for a peak that almost never arrives. Each element in a conventional array is given a router with enough freedom to let its arithmetic unit talk to any neighbour, every cycle, because somewhere in some mapping the congestion will demand it. That capacity is then idle for the rest of the execution, and the bill is not only the wires: describing what the router should do each cycle takes instruction bits, a single dependency between two operations needs at least two routers configured, and the instruction memory ends up at 48 percent of total power. Set against arithmetic at 9 percent, the array is mostly a machine for moving data that occasionally computes. The observation that a homogeneous grid carries capability its workload never exercises is exactly what the heterogeneous realisation work covered elsewhere on this site acts on when it prunes each tile down to what the application statistics justify — the difference here is what gets given up, since pruning to a workload costs generality and pruning to a graph property does not.

Three is not a tuning parameter, it is the whole enumeration. The reason this shrinks routing without shrinking what can be mapped is a small piece of graph reasoning. An operation in a dataflow graph takes at most two inputs, so these are not arbitrary graphs — a graph with n nodes carries at most 2n edges. Start from the only two-node graph, one node feeding another, and enumerate every way a third node can attach: it can take input from the first, giving one node feeding two; it can send output to the second, giving two nodes feeding one; or it can extend the chain in either direction, giving a three-node line. A triangle is possible too, but it is any of those three with one edge added, so it is not a separate case. Three shapes exhaust it, and a graph of any size decomposes into groups of three plus at most two leftover nodes. Two is too few, because a two-node group has only one possible connection and needs no router at all; larger groups appear rarely, fragment the graph, and cost more to route than they save. The authors note that work on motifs in far messier real-world graphs converges on three-node patterns as well — the same recurring shapes the graph mining acceleration work covered elsewhere on this site is built to count at speed.

Two networks, because uniform reach is the expensive part. Once operations are grouped, the traffic splits cleanly into dependencies that stay inside a group and dependencies that cross between them. The first kind is handled by the small router the three units share, which is why it is worth having at all — it sees heavy, guaranteed use rather than the intermittent peaks that justified the old per-element router. The second kind goes to a separate router facing the four compass directions, which the paper describes as a conveyor belt: the local network deposits data onto it and retrieves data from it only when a dependency genuinely leaves the group. Memory access is deliberately kept off the shared router and given its own path, since a load or a store cannot be part of a three-node compute group. Refusing to give every unit uniform access to everything is the same concession the non-uniform bandwidth work covered elsewhere on this site makes about graphics processors, where a network that treats all pairs equally is fair, easy to reason about, and grows ruinous as the array does.

Following one loop from C code to a mapped array

The evaluated graphs run from 7 to 54 nodes. Memory operations matter here — they cannot join a compute group, so a graph heavy in loads and stores has less to gain.

Why it works

• Dataflow graphs have a shape budget, and it is small. An operation takes at most two inputs, so a graph of n nodes has at most 2n edges → which means every three-node piece of one is a member of a set with exactly three elements, and any larger graph decomposes into those plus at most two leftovers → so a router able to realise all three internally can handle any graph, and the generality is a consequence of the enumeration rather than a hope.
• Shared routing is used constantly where per-element routing was used rarely. A private router per element must be sized for congestion that arrives intermittently → but a router serving the traffic inside a three-node group is exercised on every dependency that group contains → so the same silicon does far more work, and the array reaches roughly 40 percent of its area in communication hardware while keeping it busy.
• Fewer routers means far fewer instruction bits. Expressing one dependency in the conventional design means configuring at least two routers every cycle → collapsing three elements onto one shared router removes most of those descriptions from the instruction stream → which is where the bulk of the 43 percent power saving comes from, since the instruction memory was 48 percent of power before.
• Splitting the network lets each half be sized for its own job. Dependencies inside a group and dependencies between groups have completely different frequencies and distances → so a small local router handles the first and a four-direction global router handles the second, with data moving between them only when a dependency actually leaves the group → and neither has to be provisioned for the other’s worst case.
• The compiler recovers what a rigid tile would have lost. Three units behind one router could easily sit idle if operations had to be laid out in a fixed order → so several schedule templates per shape allow reversed and spread-out layouts, and the mapper scores each → giving about 1.25 times the performance a mapper without any notion of groups achieves on the same hardware.

What it costs (trade-offs and scope)

• Nothing was fabricated, and performance is calculated rather than measured. The design is written in Verilog and synthesised at a 22-nanometre node running at 100 megahertz, with power taken from post-synthesis estimates. The paper is explicit that the simulator exists mainly to verify the mapping and the hardware, with cycle counts derived from the initiation interval and the iteration count.
• The baselines are the authors’ own constructions. The energy-efficient spatial comparison follows published designs but with a mesh network substituted, and the graph partitioning it needs for complex kernels is performed by a Python script written for this paper. Since partitioning quality determines how many extra loads and stores appear, that script largely determines the 1.40 times performance claim.
• The array loses on some kernels, and for a reason that will recur. Three kernels run slower than the conventional baseline because unrolling introduced long dependencies spanning distant parts of the graph, forcing groups into frequent long-latency global communication. The benefit is a function of graph shape.
• The scalability result is measured on a filtered subset. Graphs that the larger array cannot speed up because of loop-carried dependencies are excluded from that comparison. On what remains, 2.25 times the functional units yields 1.71 times the performance, which the paper explains but which is also the only evidence offered beyond the smallest configuration.
• The evaluated array is very small. Four tiles, sixteen functional units, four 4-kilobyte memory banks. The larger version is nine tiles. Whether the two-level network holds up at the scale where a uniform network becomes genuinely unaffordable is not shown.
• Memory operations cannot join a group at all, by construction, since the shared router carries no path to memory. Graphs dominated by loads and stores therefore have less to gain, and the reported coverage figures reflect this — in some kernels barely half the nodes end up inside groups.
• The domain-specialised variant is designed by hand. Deciding to hard-wire two of one shape, one of another and one of a third across four tiles came from manually inspecting the machine learning graphs. The general framework is automated; this part is not.
• Both compiler stages are randomised heuristics. Group formation breaks and rebuilds at random until a counter stops rising; mapping is simulated annealing under a time limit. No variance across seeds is reported, and no optimality is claimed.
• Compile time is stated only as a few minutes with no comparison against the baseline mappers, which is a relevant number given that the group-aware mapper does strictly more work.
• The design introduces a correctness obligation. Data can circulate between the local and global routers and form a hardware loop when synthesised, so both the compiler and the hardware carry constraints to prevent it, checked after synthesis by the design tools.
• Two-node groups are also run on the three-unit tile, which is sensible but sits slightly outside the three-shape argument the design is built on.

The evaluation

Check yourself

Sources

The paper is “Enhancing CGRA Efficiency Through Aligned Compute and Communication Provisioning” by Zhaoying Li, Pranav Dangi, Chenyang Yin, Thilini Kaushalya Bandara, Rohan Juneja, Cheng Tan, Zhenyu Bai and Tulika Mitra, published at ASPLOS 2025, pages 410-425, DOI 10.1145/3669940.3707230. The authors are at the National University of Singapore, Peking University and Google, and the system is named Plaid.

This explainer is written from the full arXiv text, arXiv:2412.08137. Everything above comes from the paper’s own sections: the background classifying existing designs into flexible, fixed-configuration and specialised, with the power breakdown attributing 48 percent of power to instruction memory; the argument for collective routing from the bounded number of inputs per operation, the enumeration of three-node directed acyclic graphs into three basic shapes with the triangle as a derived case, and the compositional argument that any graph decomposes into those groups plus at most two leftover nodes; the architecture covering the tile with three 16-bit arithmetic units supporting fifteen operations behind a shared local router, the bypass paths between units, the separate four-direction global router and the dedicated arithmetic-load-store unit for memory operations, the 120-bit instruction format, the constraints preventing hardware loops between the two routers, and the mechanism for hard-wiring shapes into specific tiles for domain specialisation; the compiler covering the modulo scheduling formulation, the randomised group generation algorithm with its greedy initialisation and break-and-rebuild loop, the hierarchical mapping algorithm augmenting simulated annealing, and the flexible schedule templates per shape; and the evaluation covering the synthesis methodology, the three baselines and two comparison mappers, the thirty graphs across three domains and three neural network applications, the performance, energy and performance-per-area comparisons with their per-kernel exceptions, the area breakdown, the scalability analysis on the larger array, the mapper comparison, and the domain specialisation results.