Hardware is conventionally described as a datapath plus a state machine that tells each piece when to act, and writing that state machine by hand is much of what makes hardware design hard; HIR (Indian Institute of Science) proposes describing it instead as a datapath plus a schedule — every operation states when it happens, relative to the moment its enclosing loop or function began — and lets a compiler synthesise the state machine, which also makes the timing contract between one module and another something a compiler can check the way a type checker checks argument types.
The argument in one glance
-
Problem
Custom hardware is efficient and nobody can write it
Machine learning and signal processing on battery-powered devices want custom accelerators, and reconfigurable chips are the obvious way to get them without the cost of designing a chip. The obstacle is that programming them is a different discipline: in a hardware description language every unit acts on every clock tick unless something stops it, so a design is a datapath plus a state machine whose job is to keep everything from firing at once. Writing that state machine correctly is a large part of what makes hardware design slow and unapproachable.
-
What people did
Compile a normal program into hardware instead
High-level synthesis takes something written in C and produces a circuit. Every major electronic design vendor sells such a tool, and there is a two-decade research literature behind them. A related line builds domain-specific languages for particular areas — image processing, systolic arrays — which can bring domain knowledge to bear and often produce better hardware than a general tool would.
-
Why it fell short
Every one of them rebuilds the same compiler from scratch
Each synthesis tool invents its own intermediate representation, its own optimisation passes and its own code generator. Each domain-specific language either surrenders to a vendor tool or reimplements that whole stack itself. So the same transformations get written many times over, and a researcher proposing a new optimisation has to build a front end and a Verilog emitter before they can demonstrate it. Software compilation solved this decades ago by standardising on a shared intermediate representation; hardware has no equivalent.
-
This paper's idea
Describe hardware as a datapath plus a schedule, and share the rest
HIR is a mid-level intermediate representation that keeps loops, function calls and multi-dimensional arrays, so a front end can lower to it easily, while adding one thing hardware needs and software does not: every operation states explicitly when it executes. Timing is expressed relative to the moment the enclosing region began, so the same written instruction can occur at different times on different loop iterations. Given that, the compiler synthesises the state machine itself. And because a function signature carries the timing of each argument and result, one module using another can be checked for timing agreement at compile time.
Why this problem is worth solving
Hardware and software compilation have taken opposite paths on the same question. Compiling an ordinary program, usually in C, into a hardware circuit rather than into machine instructions. Every major electronic design automation vendor sells such a tool and the research literature runs back two decades. The recurring structural complaint is that each of these tools, and each domain-specific hardware language built alongside them, constructs its own intermediate representation and its own optimisation and code generation passes — so work that could be shared is instead duplicated, and a new optimisation cannot be demonstrated without first building an entire compiler around it.
What makes a shared representation hard here is that hardware carries a dimension software does not. The conventional decomposition of a hardware design. The datapath is the arithmetic and storage; the state machine generates the control signals saying which parts of it should act on which clock cycle. The state machine is necessary because hardware is inherently parallel — without control signals a multiplier multiplies every cycle and a register writes every cycle, whether or not the input means anything. Writing that control logic correctly is a large share of the difficulty of hardware design, and it is what an intermediate representation borrowed from software has no way to express.
What people did before, and where it broke
- Reuse a software intermediate representation and insert handshakes. Several synthesis compilers take a representation designed for software and lower it by adding handshake signals, producing a circuit that schedules itself at runtime. Where it broke. Dynamic scheduling costs hardware: every module pair needs handshaking logic, and the paper cites prior work showing statically scheduled designs use fewer resources precisely because they do not need that control machinery.
- Design a low-level hardware representation instead. Several recent representations sit one step above the final hardware description language, capturing structure faithfully and enabling logic-level optimisation. Where it broke. They are at the abstraction level of the hardware description language itself. Loops are gone by then, so anything wanting to reason about loop pipelining has already lost the information it needs, and a domain-specific language lowering to them must do all the hard work first.
- Separate control from structure in the representation. One well-known representation splits a design into a structural sub-language and a control sub-language with sequential and parallel blocks. Where it broke. Because it does not carry a schedule, it cannot interface with external hardware modules that impose timing requirements — the paper’s example is a vendor multiply-accumulate block whose third input must arrive a fixed number of cycles after the other two, which is inexpressible without a notion of when.
- Build a domain-specific language with its own scheduler. Languages for image processing and dataflow pipelines compute their own schedules, tailored to their domain, and often beat general tools. Where it broke. Having computed a schedule, they have nowhere to put it. Vendor tools and unscheduled representations cannot accept one, so these languages must carry the whole path down to a hardware description language themselves.
- The gap. The representations that were high-level enough to be a good target had no way to say when, and the ones that could say when had already thrown away loops. Nothing occupied the middle, which is exactly where a scheduler wants to write its answer down.
How HIR describes a circuit
From a C program to synthesisable hardware through a shared representation
-
-
new
-
new
-
new
-
new
-
new
The idea
Replace the state machine with a statement of when, and let the compiler derive the rest. This is the reframing, and the paper states it in one line: instead of datapath plus finite state machine, datapath plus schedule. The observation underneath is that a state machine is not really information — it is the mechanical consequence of a timing decision somebody already made, encoded in a form that is hard to write and harder to check. If the representation records the decision directly, saying that this load happens one cycle after its loop iteration starts and that store happens two, then generating the control logic is a compilation problem rather than a design problem. That also makes the schedule something passes can transform, which is the property that lets pipelining and retiming be expressed as changes to the representation rather than as rewrites of hand-built logic. Designing an abstraction so that the scheduling decision becomes an explicit, manipulable object rather than something baked into generated code is the same move as the tensorised program abstraction work covered elsewhere on this site.
Time has to be relative, because one written instruction happens many times. The naive way to record a schedule is to stamp each operation with an absolute cycle number, and it fails immediately: a load inside a loop executes once per iteration, and once per call of the enclosing function, so a single number cannot describe it. HIR gives every region — a function body, a loop body — a time variable standing for the moment that particular execution of the region began, and schedules operations as fixed offsets from it. The variable takes a different value on every iteration and every call, so one written instruction maps to many distinct moments through a single constant offset. Values inherit the same treatment: each carries the cycle on which it holds a meaningful result, which lets combinational operations be scheduled implicitly from their inputs since they complete within the cycle. Making the mapping from a written program onto its execution explicit in the representation, rather than leaving it implicit in generated code, is the same discipline as the tensor computation representation work covered elsewhere on this site.
Once timing is in the signature, it is a type, and it can be checked. A function in HIR does not merely declare what types its arguments have; it declares when each is read relative to the function starting, and when each result becomes available. That turns the interface between two modules into a contract with the same standing as an argument type list, and a verification pass checks it — walking the representation, computing the cycle on which every value is valid, and confirming every consumer reads at the right moment. Catching an unbalanced pipeline at compile time rather than in simulation is a real change to the debugging experience, and it is what makes it safe for many independently written front ends to target the same infrastructure. It also solves the external-module problem cleanly: a vendor block whose third input must arrive three cycles after the others is describable, and misuse of it is detectable. Elevating a timing property into a checkable contract rather than a convention is the same instinct as the hardware verification work on speculation contracts covered elsewhere on this site.
Walking a loop nest through HIR
Scheduling a matrix transpose that also increments
Two nested loops reading from one array and writing to another, compiled from C to synthesisable hardware.
Step 1 of 5
Name the moment each region starts
The function declares a time variable for when it begins executing. The outer loop declares one for the start of each of its iterations, and the inner loop another for each of its own. A region cannot see the time variables of regions enclosing it — only its own.
That scoping is what keeps the abstraction honest. An operation inside the inner loop should be positioned relative to that iteration, not relative to when the whole function started, because the function start is the same for all iterations while the iteration start is not. The restriction makes the relative reading the only expressible one.
Why it works
- A state machine is a consequence, not a decision. The control logic exists only to enforce a timing choice somebody made → recording the choice directly means the logic can be derived → what was a hand-written design artifact becomes compiler output, and passes can rewrite the timing instead of rewriting logic.
- Relative time is the only formulation that survives repetition. A single written instruction executes once per iteration and once per call → an absolute cycle number cannot describe that, but an offset from a per-execution region start can → one constant covers arbitrarily many distinct moments.
- Static scheduling removes handshaking rather than optimising it. Two modules running in lockstep, one producing a value each cycle and the other consuming it, need no runtime agreement → the schedule already guarantees the timing → so the synchronisation logic a dynamically scheduled design needs simply is not built, which is where its resource advantage comes from.
- Restricting to affine programs is what makes any of this possible. Regular loop nests with regular array subscripts permit exact dependence analysis → the scheduler can prove which accesses never touch the same location and discard the apparent conflicts → a fixed schedule can be computed at all, which it could not be for arbitrary code.
- Putting timing in the signature makes it checkable and makes external modules usable. The interface between modules becomes a contract with the standing of a type → the compiler verifies consumers read values when they are actually valid → and a vendor block requiring one input three cycles after the others becomes describable rather than requiring handshakes around it.
What it costs (trade-offs and scope)
- The generated hardware is comparable to the commercial tool, not better. The paper’s own framing is that quality is on a par. Resource usage goes both ways across ten benchmarks: much lower register count on transpose and much lower lookup-table count on one linear algebra kernel, but more lookup tables on small matrix multiplications and more registers on the largest, where the authors state directly that the lowering passes have room to improve.
- The scope is narrow and the paper is explicit about it. Affine programs only, statically scheduled only. It names several hardware languages and domain-specific languages that cannot use this stack at all because they need non-affine workloads or dynamic scheduling.
- The dataflow comparison required rewriting the programs for the baseline. The commercial tool can only overlap producer and consumer loop nests when there is exactly one of each and the consumer reads in the order the producer wrote. To enable its dataflow optimisation at all, array duplication loops had to be added to the source. The resulting speedup, 2.3 times against 1.7 times on one image kernel, is real and reflects a genuine limitation of the baseline, and the two are not running identical programs.
- The pipeline is not fully automatic. The C front end does not support specifying unroll factors or loop pipelining rates, so those are added by hand as attributes on the generated representation before scheduling. The authors expect this to go away when the front end gains support.
- Verification covers values but not memory. It will catch an unbalanced pipeline; it will not catch reading a memory location before anything wrote it. The paper states this limit plainly.
- Undefined behaviour is load-bearing. Multiple writers to one memory are permitted by assuming they never hit the same port on the same cycle, with anything else undefined. The bit-width narrowing optimisation likewise leans on a no-overflow annotation. Both are reasonable and both mean an incorrect front end produces silently wrong hardware.
- Partial unrolling is not supported. It has to be expressed by splitting a loop and fully unrolling the inner one.
- A central component is described elsewhere. The integer programming scheduler is summarised here and its detailed treatment is a separate paper, so the compilation quality partly rests on work outside this one.
- One platform, one vendor, ten benchmarks. Everything is synthesised for a single Xilinx board using that vendor’s tools, and the Verilog emission itself is inherited from the shared infrastructure rather than contributed here.
The evaluation
Four kinds of intermediate representation in a hardware compilation flow
| Property | Reused software representation | Low-level hardware representation | HIR (mid-level, explicitly scheduled) |
|---|---|---|---|
| What survives into it | |||
| How timing gets decided | |||
| Can a language with its own scheduler use it | |||
| External modules with timing requirements | Need handshake wrappers | Expressible, but at hardware-description level | |
| Measured hardware quality | Not compared here | Not compared here |
Check yourself
Check your understanding
1. What does replacing datapath plus finite state machine with datapath plus schedule actually change?
2. Why must schedules be expressed relative to a region start time rather than as absolute cycle numbers?
3. What does putting timing information into a function signature enable?
4. How does the generated hardware compare to the commercial high-level synthesis tool?
Sources
The paper is “HIR: An MLIR-based Intermediate Representation for Hardware Accelerator Description” by Kingshuk Majumder and Uday Bondhugula, published at ASPLOS 2023 Volume 4, pages 189-201, DOI 10.1145/3623278.3624767. Both authors are at the Indian Institute of Science, Bangalore. The implementation is open-sourced.
This explainer is written from the full text of the published version, read through a proxy of the ACM Digital Library copy. Everything above comes from the paper’s own sections 2 through 7: the framing of hardware as datapath plus schedule in place of datapath plus finite state machine; the distinction between a written instruction and each of its executions, and the argument that absolute cycle numbers cannot express the latter; the definition of time variables per region with their scoping rules, and the treatment of values as carrying a validity cycle with combinational operations inheriting timing from their inputs; the function signature carrying read times for arguments and availability times for results as a scheduling contract; the discussion of why statically scheduled designs avoid the handshaking overhead of dynamically scheduled ones, with the lockstep producer-consumer example; the expression of instruction-level parallelism, loop pipelining, task-level parallelism and memory banking; the compilation flow through an existing C front end, an integer programming scheduler treated in detail elsewhere, delay coalescing that cuts one shift register from depth 104 to depth 4, and bit-width narrowing that relies on a no-overflow annotation; the schedule verification pass and its stated limitation to values rather than memory; the backend passes converting loops to counters, delays to shift registers and the schedule to a state machine; the implementation at roughly 8,000 lines with Verilog emission inherited from the shared infrastructure; the ten-benchmark comparison against the commercial tool at 200 MHz on a Xilinx board with its two-directional resource results; the dataflow comparison requiring array duplication loops in the baseline programs and yielding 2.3 times against 1.7 times on one kernel; and the related work section naming the language families the compiler cannot serve.