High-level synthesis was supposed to let ordinary C programmers build FPGA accelerators, but the C it accepts is a strict subset, so a normal program meets a wall of compatibility errors before it will compile at all; this paper (UCLA) automates the rewriting by treating it as search-based program repair — mine a thousand forum posts for the six recurring error families and their fixes, generate the test inputs nobody wrote, and search the space of edits while rejecting most candidates before paying for a synthesis run — producing compiling accelerator code for all ten real programs it was given, nine of them faster than the original, with up to 438 lines of edits applied automatically.
The argument in one glance
-
Problem
Accelerators are available to almost nobody
Reconfigurable chips are in every major cloud, and the performance and energy gains from moving a hot function onto one are large. Writing the accelerator is the obstacle. Doing it in a hardware description language demands expertise that most software engineers do not have and cannot acquire quickly, so in practice this hardware is programmed by a small number of specialists while everyone else leaves it unused.
-
What people did
Raise the abstraction so that C describes the hardware
High-level synthesis is the most successful answer to that gap. The developer writes a C or C++ dialect, and the tool generates the register-transfer level description that the chip is actually built from. The intent is that any C programmer can now target an accelerator, and the language they already know is the interface.
-
Why it fell short
The dialect is a strict subset, and the errors come first
What the synthesis tool accepts is much narrower than C. Dynamic allocation cannot exist on a chip whose resources are fixed before it runs, recursion has no stack to grow, pointers are forbidden except as hardware interfaces, and several ordinary types are unsupported. Parallelism must be requested with directives whose rules are easy to break. So a working C program does not compile, and the developer meets a wall of errors — a search of one vendor forum returns thousands of posts from people stuck on exactly this.
-
This paper's idea
Treat the rewrite as automated program repair, with generated tests
This paper (Qian Zhang, Jiyuan Wang, Guoqing Harry Xu and Miryung Kim) reads the compatibility errors as bugs to be repaired by search. A study of a thousand forum posts yields six recurring error families and the edits that fix them, encoded as templates. A fuzzer manufactures the tests that would otherwise not exist, so each candidate can be checked against the original program running on the processor. Two techniques keep the search affordable, since a single synthesis run costs minutes to hours.
Why this problem is worth solving
The gap this paper attacks is a gap in who can use the hardware at all.
HIGH-LEVEL
synthesis takes a program written in a C-like dialect and produces a description of a
circuit that computes the same thing. That is a much stranger job than compiling for a
processor. A processor already exists and the compiler chooses instructions for it,
whereas synthesis has to build the machine — deciding how many arithmetic units to
create, how wide each number should be, how work is pipelined, and how memory is laid
out on the chip. Everything must be fixed before the program runs, because a circuit
cannot ask for more of itself while running. This is why the accepted language is a
subset. There is no allocator to call, no stack that grows for recursion, and no
general pointer, since a pointer implies an address space the circuit does not have.
Parallelism is not inferred either. The developer requests it with directives that say
how to unroll a loop or split an array, and those directives have rules of their own
that a plausible-looking design can violate.
The second thing to settle is why the paper checks rewrites by running them.
A
rewrite can silently change what a program computes, so every candidate must be
validated. The natural instinct is to demand a proof of equivalence between the original
and the rewritten program, and the paper argues that this is not available and cannot be.
No synthesis compiler certifies that its output means the same as its input, so today
there is no way to compare the two except by running both. More fundamentally, the
rewrite deliberately does not preserve meaning in general. Turning an unbounded structure
into a fixed-size array is the whole point of targeting hardware, and a fixed-size array
behaves differently once the input exceeds the size chosen. Equivalence between a program
with unbounded resources and one with finite resources is not a property that holds, so
the honest question is whether the two agree on the inputs that matter, and answering it
requires inputs.
What people did before, and where it broke
-
Manual rewriting, guided by forum answers. The status quo. A developer hits an error, searches the vendor forum, finds someone who hit the same one, and adapts the accepted answer. It works, and the answers are often correct.
-
The gap. It is slow and it does not scale. Porting one image-processing application by hand in this paper’s benchmark set took 3,272 lines of edits. The knowledge stays scattered across thousands of posts instead of being encoded anywhere a tool can use.
-
Libraries and drop-in replacements. Provide hardware-friendly versions of the constructs the subset forbids — data-structure libraries, substitutes for recursion — so the developer swaps rather than redesigns.
-
The gap. The developer still has to know which construct to swap, and swapping is only part of the work. The sizes chosen for the fixed replacements have to be right, and nothing tells them whether a size is right except running the program.
-
Earlier automated refactoring for this domain. Prior work from the same area automates the removal of dynamic memory, pointers, and recursion, which are genuinely the constructs people trip over first.
-
The gap. Its scope is those constructs only. Run on the same ten programs here, it produced a compiling version for two of them, because the other errors — unsupported types, directive conflicts, structs, entry-point configuration — are outside what it handles.
-
Off-the-shelf search-based program repair. A mature software technique. Mutate the program, run the tests, keep what improves the score, repeat for thousands of generations.
-
The gap. It assumes compiling and running a candidate is nearly free. Here a single candidate costs a synthesis and simulation run measured in minutes to hours, so a search that tries thousands of random edits never finishes. It also assumes tests exist, and most of these programs came with none at all.
How a C program becomes a compiling accelerator design
One repair loop, run until the code compiles and the time budget expires
-
-
new
-
new
-
new
-
new
-
new
The idea
Fix patterns turn a hopeless search space into a small one. The starting move is empirical rather than algorithmic. The authors collected a thousand posts from the vendor support forum for synthesis errors, read the accepted answers, and grouped the causes into six families — unsupported data types at about a quarter of all cases, entry-point configuration at a fifth, dataflow directives and loop-parallelism directives at about a sixth each, structs and unions at a seventh, and dynamic data structures at a twelfth. For each family they wrote down the edits that fixed it as templates with holes, so an edit is a named operation on a syntax tree rather than a random mutation. This is what makes the search tractable, because every candidate the search proposes is an edit a human has already used successfully on this class of error. Encoding a domain’s accumulated repair knowledge so that a search can propose only sensible moves is exactly what the hardware repair work covered elsewhere on this site had to do when it brought automated repair to circuit code, where a generic mutation operator produces nothing usable.
The templates depend on each other, and knowing that is worth a large speedup. Fixing one error usually needs several edits applied in a particular order. Making a struct synthesizable may require inserting a constructor first and only then making its connecting stream static; replacing dynamic allocation with a fixed array requires declaring the array before there is any size to tune. The paper records those precedences and lets the search enumerate combinations along them, rather than picking edits at random and hoping the order works out. Measured against a version of itself that chooses edits in random order, the dependence-guided search is up to 35 times faster, and the random-order version fails to reach a compiling design at all for the largest program within twelve hours. The second speedup is about not paying for what will fail — a lightweight front-end checks whether a candidate even obeys the dialect coding rules before the synthesis tool is invoked, which removes up to three quarters of the invocations. That the cost of one compile dominates the whole workflow is the same pressure that drives the fast FPGA compilation work covered elsewhere on this site, which attacks the compile itself rather than avoiding it.
Without generated tests, the repair would be confidently wrong. The most convincing result in the paper is small. In a program whose recursion had to be turned into an explicit stack, the search using only the tests that shipped with the program settled on a stack of 1,024 entries and reported success. With generated tests, 44 percent of runs disagreed with the processor, because the stack overflowed on inputs the original tests never produced. The size was raised to 2,048 and the disagreement vanished. That is the entire argument for generating tests in one example — the finitization step at the heart of this translation picks a number, and only inputs that stress the number can tell you it is wrong. The generated tests reach 97 percent branch coverage, against 36 percent for whatever tests the programs already had. Getting the code to compile is only the first of the two problems here; making the resulting design fast is the separate question taken up by the equality-saturation optimizer for high-level synthesis covered elsewhere on this site, which starts from code that already compiles.
Watching one repair go wrong and then right
How generated tests caught a stack size that looked correct
Following a recursive program through the repair loop, with the pre-existing tests and then with the generated ones.
Step 1 of 5
The synthesis tool rejects the recursion
The kernel walks a structure by calling itself. The compiler reports that recursive functions are not supported, because a circuit has no stack that can grow while it runs.
The error message is classified into the dynamic-data-structure family, and that family knows how to find its repair site — look for a function whose call target resolves to its own defining declaration.
Why it works
- Fix patterns come from people who already solved the problem. Mining a thousand support posts for causes and their accepted answers → the search proposes edits that are known to fix this class of error → all but one of the ten programs are repaired by the patterns alone, instead of by random mutation that almost never compiles.
- Error messages localise the repair for free. The synthesis compiler names the offending construct in its diagnostic → the tool classifies the message into a family and applies that family’s site-finding rule → no statistical fault localisation is needed, which is fortunate since it would require test failures the compiler never reaches.
- Edit dependences shrink the enumeration. Recording which edit must precede which and walking combinations along that order → the search stops proposing sequences that cannot work → up to 35 times faster than choosing edits at random, and the random version does not finish at all on the largest program.
- Most bad candidates can be rejected without compiling. Checking dialect coding rules in a lightweight front-end first → up to three quarters of full synthesis invocations are avoided → about four times faster overall, and nothing is lost because these violations would have been reported early in synthesis anyway.
- Generated tests make the fitness function mean something. Fuzzing from real kernel-entry values with a type filter → 97 percent branch coverage instead of the 36 percent the existing tests reached → a candidate that agrees with the processor is agreeing on inputs that actually exercise the finitization choices.
What it costs (trade-offs and scope)
- One vendor, one kind of accelerator. The six error families and their edits were extracted from one vendor’s synthesis errors and target reconfigurable chips only. The approach carries over to another platform only by redoing that extraction.
- Sizes are estimated upward, and stay upward. Bit widths, array sizes, and stack sizes are set from the ranges the generated tests exposed, so the tool tends to over-allocate. Over-allocation wastes on-chip resources, which is the currency that buys parallelism.
- It fixes compatibility, it does not redesign. Speed improvements come almost entirely from exploring loop and array directives. Algorithmic restructuring and automatic parallelisation are out of scope, which is why the automated versions reach about two thirds of the speedup that hand-porting achieved.
- The kernel must be nominated. The tool does not decide which part of the application belongs on the accelerator. That remains a profiling task for the developer or another tool, and the quality of the answer depends on it.
- Correctness is only as good as the generated tests. Agreement on 97 percent of branches is strong evidence and not a proof. The paper is explicit that proof is unavailable here, so a rewrite could still diverge on an input the fuzzer never found.
The evaluation
| Property | What was measured | The result | What it tells you |
|---|---|---|---|
| Programs successfully translated | |||
| Speed of the result | |||
| Test generation | |||
| What the two speedups contribute | |||
| Human effort replaced |
Check yourself
Check your understanding
1. Why can standard search-based program repair not simply be pointed at this problem?
2. The paper argues that behaviour preservation here must be tested rather than proved. What is the deeper reason, beyond the absence of a certifying compiler?
3. What did the generated tests reveal about the recursive program that the pre-existing tests did not?
4. Predict what would happen if the tool applied its repair templates in a random order rather than following recorded dependences.
Sources
HeteroGen: Transpiling C to Heterogeneous HLS Code with Automated Test Generation and Program Repair. Qian Zhang, Jiyuan Wang, Guoqing Harry Xu, Miryung Kim. ASPLOS 2022, pages 1017 to 1029. DOI 10.1145/3503222.3507748. Full text read from the authors’ copy hosted at UCLA.