REVAMP: a systematic framework for heterogeneous CGRA realization

Every tile in a reconfigurable array carries a full ALU, a fat crossbar, and a configuration memory that is mostly empty bits — REVAMP takes any homogeneous CGRA plus the applications it must run and automatically prunes each tile to what the workload statistics justify, cutting power by about 40% while loops keep running at nearly the same speed.

Why this problem is worth solving

A

The economics of the edge make every milliwatt count, and the paper’s own measurements show where homogeneous CGRAs spend theirs. On a commercial 22 nm process, the configuration memory — read every cycle to reprogram every PE — is the single largest power consumer in spatio-temporal designs, yet only 12% (ADRES-style) to 21% (HyCUBE-style) of its bits ever hold valid configuration. Full-ALU tiles provide flexibility the workload rarely exercises; crossbar switches burn power that grows quadratically with connectivity. Uniformity, chosen for design and compiler convenience, quietly became the efficiency ceiling.

Hand-built heterogeneous CGRAs demonstrate the upside but not a method: each is a specific architecture with localized tricks and a custom compiler. What was missing is a systematic path — take the homogeneous design a team already has, feed in the workloads the product will run, and get back a pruned, heterogeneous variant plus a compiler that can still map everything onto it.

What people did before, and where it broke

Homogeneous templates. ADRES, MorphoSys, Samsung’s SRP: identical PEs, regular networks. Power modes and cluster gating (as in SRP) claw back some waste, but power management machinery is itself at odds with tiny edge budgets — and gating an idle full ALU still paid its area.

One-off heterogeneous designs. Architectures with specialized tiles exist (expression-grained EGRA, pattern-specific designs, Plasticine’s compute/memory split), each with a hand-matched compiler. They prove heterogeneity works; they do not tell an architect how to derive it for their array and their workload.

CGRA compilers. A rich line of mappers — simulated annealing (DRESC), graph-theoretic (EPIMap, Graph Minor), ILP (CGRA-ME), heuristic (HyCUBE’s) — mostly assume regular hardware. Heterogeneity breaks their core assumption that any operation fits any tile, which is precisely why designers avoided it.

The idea

REVAMP’s premise: the workload’s statistics, not the architect’s caution, should decide how much generality each tile carries. Three axes, each with its compiler counterpart.

Compute: frequency-proportional flexibility. If additions are 40% of the suite’s operations and logic ops are 10%, then roughly 40% of PEs should have adders and 10% logic units — REVAMP sets each class’s PE count from its frequency in the application suite. Flexibility itself is placed deliberately: a hotspot index ranks tiles, and high-index (typically central) tiles support many classes while edge tiles support few. Multipliers — the largest units — go to few, high-index tiles. The mapper then simply filters placement candidates by class: an operation can only land on a PE that supports it.

Network: width follows need. Most transferred values do not need the full datapath every cycle. REVAMP halves the external (inter-PE) datapaths and gives the compiler three ways to cope: send a word’s two halves over two cycles (streaming), send them simultaneously over two disjoint routes when latency is critical, or skip the upper half entirely when the compiler can prove it carries nothing (predicates, narrow types). Pipelined streaming keeps throughput intact: when consecutive transfers use independent paths, their half-word cycles interleave — the paper’s example recovers the original initiation interval at the cost of a single extra cycle of latency. Crossbars are sliced into two half-width switches, cutting their quadratic cost.

Memory: pay only for change. The insight behind the biggest win is that per-cycle configurations are sparse in time: an opcode field that stays the same for four cycles does not need four copies. The decoupled configuration structure gives opcodes, constants, and switch settings separate small stores with independent program counters that advance only on change, coordinated by a bit-masked predicate register. Only valid configurations are stored (recall: 12–21% validity in the monolithic design), and quiet stores are clock-gated. On the ADRES-derived variant, per-PE configuration memory drops from 256 bytes to 66.5–87.8 bytes.

The safety net is the loop. None of these choices is trusted blindly: each candidate architecture must still map the entire suite (checked by II) and synthesize (checked by power/area) before acceptance. Specialization is bounded by the suite — which is the point: a domain’s diverse kernels keep the derived CGRA general enough, unlike an ASIC.

op classes: ADD/SUB, MUL, LOGIC, COMP, MEM
hotspots: discovered by profiling (dynamic mode) or user-specified (static)

Why it works

• Operation frequencies are heavily skewed and known in advance for a product’s domain → sizing each class’s PE count to that skew removes silicon that would idle → static and dynamic power fall with no algorithmic change.
• Flexibility concentrated by hotspot index → the mapper still finds feasible placements for every kernel (the flexible core catches the awkward operations) → class restriction costs almost no II.
• Configurations are sparse in time and mostly invalid in the monolithic layout → change-driven, decoupled stores shrink the array’s largest power consumer by ~3–4× → the single biggest contributor to the savings.
• Half-width links with pipelined streaming keep steady-state throughput → II, the metric that matters for loops, survives while wires, registers, and crossbar muxes halve or better.
• Every candidate must map the whole suite and synthesize before acceptance → the output is heterogeneous but never over-specialized → CGRA generality is preserved by construction, not by hope.

What it costs

• Compiler complexity. Class-restricted placement, width-aware routing, streaming decisions, and change-driven configuration generation all land in the mapper; REVAMP ships these, but they are intrinsic to any heterogeneous CGRA.
• A little latency, occasionally II. Streaming adds a cycle of latency; a few kernels lose one II step (GeMM on HyCUBE 6→7).
• Suite dependence. The derived architecture is tuned to the input applications: deriving from a subset of the suite lands on a different optimum, and workloads far outside the domain will map worse than on the homogeneous original.
• Design-time exploration cost. RTL synthesis and full-suite mapping inside the search loop — cheap next to a chip project, but not interactive.
• Thermal and layout constraints. Concentrating multipliers and flexibility centrally must respect thermal balance and placement regularity, which the framework treats as constraints rather than solving outright.

The evaluation

REVAMP’s claim is generality, so the evaluation derives heterogeneous variants of three deliberately different homogeneous CGRAs: HM-ADRES (neighbor-connected, spatio-temporal), HM-HyCUBE (single-cycle multi-hop crossbar network, spatio-temporal), and HM-Softbrain (spatial dataflow, decoupled memory streams). All six designs are implemented in RTL and synthesized on a commercial 22 nm process; five kernels from PolyBench/MachSuite (GeMM, Conv2D, CRS, ellpack, Stencil2D) are mapped by the extended compiler.

One experiment deserves a highlight: deriving HT-HyCUBE from a subset of the suite (only GeMM, Conv2D, Stencil2D) converges to a different optimal design point than the full suite does. That is the method’s honesty condition made visible — the output is only as general as the workloads you show it, which is exactly the trade an edge-product architect wants to control.