A reconfigurable array is built from a grid of small programmable compute tiles, and how much arithmetic to put in one tile is a judgement call a human architect makes badly, because the space of options is enormous and each option needs a new compiler before it can be evaluated; this paper (Stanford) proposes that the applications should design the tile — mine them for the arithmetic patterns that recur, fuse those patterns into one datapath that can be configured to any of them, and generate the hardware and the compiler together, so a design that took a prior automated method nine to sixteen hours emerges in minutes.
The argument in one glance
-
Problem
Somebody has to decide what goes inside one tile
An array of small programmable compute tiles occupies the middle ground between a reconfigurable gate array and a fixed-function chip — more efficient than the first because it works on whole words, more flexible than the second because both its tiles and its wiring are configurable. But that middle ground is not a point, it is a large space, and the single biggest decision is what arithmetic lives inside one tile. Put in too little and an application needs many tiles and pays for the wires between them; put in too much and most of it sits unused.
-
What people did
Have an architect choose, guided by knowledge of the domain
The conventional answer is expert judgement. A designer who knows that image processing does a great many multiply-accumulates puts a fused multiply-add in the tile, decides how many multiplexers to spend on routing inside it, and picks how many inputs it takes. Each of those is a real axis with real consequences for area, energy, and how many applications the result can run.
-
Why it fell short
The space is too large and each point is too expensive to try
Enumerating combinations along several independent axes produces far more candidates than anyone can build. Worse, a candidate cannot be evaluated by building the hardware alone — an application only runs on it if a compiler knows how to map operations onto whatever arithmetic was chosen, and that compiler has to be written for each candidate. So designers evaluate a handful of points and choose largely by intuition about which operations a domain needs.
-
This paper's idea
Let the applications draw the tile, and generate the compiler with it
This paper (Melchert, Feng, Donovick, Daly, Sharma, Barrett, Horowitz, Hanrahan and Raina) treats the applications as the specification. Mine their dataflow graphs for the computation patterns that recur most, fuse several of those patterns into one datapath that can be configured to behave as any of them, and turn that into hardware. The compiler comes free, because the same specification yields a formal model from which the mapping rules can be solved for automatically.
Why this problem is worth solving
The thing being designed is unfamiliar enough to deserve a description.
A
FIELD-PROGRAMMABLE gate array is configurable down to individual bits, which makes it able
to become almost any circuit and also wasteful, since a single addition costs a great deal of
reconfigurable machinery. A fixed-function chip is the opposite. A coarse-grained
reconfigurable array sits between them — a grid of small compute tiles, each holding real
arithmetic units that operate on whole words, joined by a configurable interconnect of
routing tracks with boxes that bring signals into tiles and back out. Because the arithmetic
is fixed and only the configuration changes, it is far more efficient than bit-level
reconfiguration, and because everything is configurable it still runs many applications.
Surveys identify three axes for the compute tile — which operations it contains, how many
configurable paths run through it, and how many inputs and outputs it has. The last matters
more than it sounds, because every input needs a connection box, and the interconnect is
expensive enough that adding one input to a tile can cost more than the arithmetic
does.
The technique borrowed to make the choice is a graph algorithm with a subtlety in it.
AN
application compiled down to its dataflow becomes a graph — nodes are operations, edges carry
values between them. Frequent subgraph mining finds the small patterns that recur most within
that graph, which is exactly the question “what computation does this application keep doing”.
There is a trap. A subgraph may be reported as occurring four times while its occurrences
overlap, sharing nodes with one another, so only two of them could actually be executed
simultaneously on separate hardware. Counting occurrences therefore overstates how much a
pattern is worth accelerating. The paper corrects this by building a second graph whose nodes
are the occurrences and whose edges join occurrences that share anything, then computing a
maximal independent set — the largest collection of occurrences none of which touch. Its size
is how many fully utilised tiles implementing that pattern the application could actually
keep busy, and that is the number used to rank candidates.
What people did before, and where it broke
-
Design the tile by hand from domain knowledge. The standard practice. An architect who understands the workload picks the operations, the internal routing, and the input count.
-
The gap. The space has several axes and no way to search it. Evaluating one candidate properly means writing a compiler for it, so designers try very few and reason from intuition rather than measurement.
-
Start general and prune away what is unused. A systematic approach takes a homogeneous array with a full arithmetic unit in every tile and removes what the workload statistics do not justify, cutting power substantially.
-
The gap. Removing operations from an arithmetic unit can only simplify one stage of arithmetic. It cannot produce a tile containing several operations chained together, which is where the real savings are, and it leaves compute density low and the interconnect overhead untouched.
-
Search the space with an evolutionary algorithm. The closest prior work also aims to specialise tiles to a domain automatically, mutating designs and evaluating them.
-
The gap. Speed. Its iterative search took 9 to 16 hours to produce tile designs, against minutes here for the analysis, the tile, the compiler, and the hardware description for the entire array — because mining and merging is a directed construction rather than a search.
-
Explore the array rather than the tile. Other frameworks tune the whole array by simulated annealing over tile parameters, or by iteratively deleting unneeded resources.
-
The gap. They vary parameters of a tile whose structure is fixed. This work changes what the tile is, producing datapaths with multiple stages of arithmetic that a parameter sweep cannot express.
How applications become hardware and a compiler
From a domain-specific program to a specialised array with its own compiler
-
-
new
-
new
-
new
-
new
-
new
The idea
The application graph is already a description of the hardware you want. The move that organises everything is refusing to treat tile design as a search over configurations. A pattern that recurs in an application’s dataflow graph is, read directly, a proposed piece of hardware — each operation node has a hardware meaning, so a subgraph translates into a datapath without any inference. Mining therefore proposes candidates that are relevant by construction rather than by evaluation, which is why this is fast where the evolutionary alternative was slow. The refinement that makes the ranking honest is the independent-set analysis, which discounts a pattern whose many occurrences overlap and could never occupy separate tiles at once. The direction of travel is the opposite of the pruning approach in the heterogeneous-array work covered elsewhere on this site, which starts from a full arithmetic unit and removes what statistics do not justify — that can simplify one stage of arithmetic but cannot invent a tile holding several chained together.
Merging is a maximum-weight clique problem, and the weights are areas. Building a tile from one pattern is easy and nearly useless, since a tile should serve several patterns and several applications. The paper borrows a datapath merging algorithm and applies it with an explicit cost. Given two patterns, enumerate every pair of nodes that could share hardware — same operation, or implementable on the same block — and every pair of edges whose endpoints could merge and whose port positions agree, which matters for operations where operand order is significant. Turn those opportunities into a graph where nodes are proposed merges and edges join merges that can coexist, then weight each node by the area that merge would save, which is obtained by synthesising the primitive. The best fusion is the maximum-weight clique. Multiplexers appear exactly where the merged patterns take different paths, so the cost of generality is materialised rather than assumed. How many patterns to merge is left as a dial the designer turns, which is what makes this an exploration framework rather than a single answer. Driving a hardware search with a cost that was actually measured rather than estimated is the same commitment as the full-stack accelerator search covered elsewhere on this site, which searches datapath and software schedule together because neither one alone predicts what the pair will do.
A compiler you did not write is what makes the loop closed. The reason this space had gone unexplored is not that nobody could imagine a specialised tile — it is that a tile is useless until something can map applications onto it, and writing that by hand per candidate makes exploration impossible. The specification language here produces three interpretations of one description: an executable model, synthesisable hardware, and a formal model. From the formal model, the mapping rules are not written but solved — a satisfiability query asks whether there exists a configuration of the tile such that for all inputs its output matches a given operation, including all valid assignments of operands to ports. Instruction selection then covers the application graph greedily, trying complex rules before simple ones. Describing what a piece of hardware computes and letting tooling derive the rest is the same discipline as the custom-instruction work covered elsewhere on this site, which gets portability by saying what an instruction computes and never when.
Fusing two patterns into one datapath
How the merging algorithm decides what hardware two patterns can share
Merging two mined subgraphs into a single configurable datapath at the lowest area cost.
Step 1 of 5
List every pair of nodes that could share hardware
Two operation nodes can merge if they are the same operation, or if both can run on one hardware block. Two constants can merge. Two additions can merge. The result is a bipartite graph of possibilities.
Edges between nodes can merge too, but only if both their endpoints merge and the operand positions agree. That last condition exists because operand order matters for operations like a shift, where swapping the inputs changes the answer.
Why it works
- Mined patterns are candidates that need no evaluation to be plausible. Reading recurring subgraphs directly as datapaths → every candidate corresponds to computation the applications actually perform → the framework constructs a small number of good designs instead of searching a large space of mostly bad ones, which is why it takes minutes rather than the 9 to 16 hours of an evolutionary approach.
- Independent-set ranking measures usable parallelism, not popularity. Scoring a pattern by its largest set of non-overlapping occurrences → patterns whose occurrences share nodes are discounted → the tiles built from the top-ranked patterns can actually be kept fully utilised rather than partially.
- Weighting merges by synthesised area makes the fusion decision real. Pricing each merge by the silicon it removes and solving for maximum weight → the algorithm prefers sharing a multiplier over sharing an adder → multiplexers are added only where patterns diverge, so the cost of flexibility is paid where it buys something.
- Fewer, richer tiles shrink the wiring too. A tile that performs several chained operations → an application needs fewer tiles and fewer hops between them → switch box area and energy drop by 35 and 26 percent on one application, which is a saving in the interconnect rather than in the arithmetic.
- One specification yields hardware, model, and compiler. Deriving mapping rules by solving a satisfiability query against the formal model → no compiler has to be written per candidate → a designer can evaluate a tile end to end, which is the step that had made exploration impractical.
What it costs (trade-offs and scope)
- Specialising too far makes things worse. Merging one additional pattern per application into the shared tile increased both area and energy relative to the smaller tile. The dial has an interior optimum and the framework does not find it — a person reads the curves.
- Balance across applications matters and is not automatic. A tile weighted towards one application rewards that application and penalises the others. Deciding how to weight is left to the designer.
- The interconnect can move the wrong way. More inputs to a tile means more connection boxes. One specialised design increased connection box area by 44 percent even while its energy fell, so the area win is not guaranteed at the array level.
- Everything rests on the surrounding toolchain. The result depends on an existing agile hardware flow, a specification language with formal semantics, a solver, and a mining tool. The contribution is the assembly and the analysis, not a standalone artifact.
- It does not close the gap to fixed-function hardware. For the machine learning case, a dedicated accelerator remains 16 times more energy-efficient than the generated array. The claim is that programmability now costs much less, not that it costs nothing.
The evaluation
| Property | What was measured | The result | What it tells you |
|---|---|---|---|
| Specialising for one application | |||
| Specialising for a whole domain | |||
| Does it generalise beyond what was mined | |||
| The whole array, including wiring | |||
| Against the alternatives in kind |
Check yourself
Check your understanding
1. Why is the number of times a pattern occurs in an application graph a misleading measure of how much hardware to build for it?
2. In the merging algorithm, what do the weights represent and why does the maximum-weight clique give the right answer?
3. Why does automatically generating the compiler matter as much as automatically generating the hardware?
4. Predict what happens when more mined patterns are merged into a tile shared across a domain.
Sources
APEX: A Framework for Automated Processing Element Design Space Exploration using Frequent Subgraph Analysis. Jackson Melchert, Kathleen Feng, Caleb Donovick, Ross Daly, Ritvik Sharma, Clark Barrett, Mark A. Horowitz, Pat Hanrahan, Priyanka Raina. ASPLOS 2023, Volume 3, pages 33 to 45. DOI 10.1145/3582016.3582070. Full text read from the ACM Digital Library PDF.