
Deriving Efficient Hardware in the Bluespec Style
Let’s forge ahead on the subject of deriving programs in a step-by-step way that guarantees correctness, which I have been arguing is an appealing replacement for the way that AI coding agents are being used in software…
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
Adam Chlipala
Oct 20, 2026
4
Share
Let’s forge ahead on the subject of deriving programs in a step-by-step way that guarantees correctness, which I have been arguing is an appealing replacement for the way that AI coding agents are being used in software engineering today, even when those agents output proofs of correctness. Last week, I used an example from software: optimizing tensor computations expressed in a functional language, where specifications are transformed into fast implementations using rewrite rules expressed with bog-standard mathematical equality. In general, derivations can benefit from more-nuanced kinds of algebraic rewriting, and I will now give one example, in digital hardware, where rewrite rules are oriented and can only be applied in one direction. Our implementations of this kind of framework so far have mostly been used to prove handwritten hardware designs correct, though I’m going to explain how the same tools can support gradual implementation of a specification by rewriting.
Multicore CPU systems are complex pieces of hardware that we all rely on daily, whether in our laptops or in servers that we access over the Internet. They allow multiple streams of code (threads) to run at the same time, which is great for performance. However, it introduces complexity that can lead to bugs in the hardware, which can be missed even by extensive testing. As a result, these kinds of designs have been major targets of formal verification.
One tricky part of a multicore system is its memory hierarchy. Main memory is typically large and slow. When certain memory addresses are accessed frequently, it makes sense to copy their values into particular caches. The payoff is that these caches, while smaller, can provide much quicker answers. In fact, this same argument for a performance payoff can repeat at finer and finer grains, so we typically see a whole hierarchy or tree of caches, each with one parent and perhaps some children. An algorithm that coordinates such a cache hierarchy is called a cache-coherence protocol. It is difficult to get right because the value of a given memory location may be replicated across different caches, and we need to make sure these copies are kept coherent with each other, as they are modified by different parts of the hardware simultaneously.
My introduction to the area came when Murali Vijayaraghavan, then a PhD student at MIT, asked me to help with a project he wanted to do in formal verification of cache coherence. He was advised by my late colleague Arvind, and this excuse to start a collaboration was very impactful on the direction of my research career. In MIT research, Arvind had coinvented the Bluespec hardware description language, whose implementation grew into the product of a startup, eventually to become open source. It offers appealing advantages familiar to software programmers but which hardware engineers had generally been suffering without.
Murali started out wanting to focus on cache coherence, but then it seemed like a good test of the associated correctness theorem to be sure it could be used to prove a system that includes multiple CPUs using the coherence protocol. Working out the details, we stumbled into a beautiful (if I may say so myself) framework for modular proof of Bluespec designs. That is, we came up with a way to specify and prove hardware modules separately and then compose the proofs in a relatively black-box and simple way, to justify correctness of larger systems. We adopted a reasoning style developed originally in the software world as process calculus. It is described in our first paper on formally verifying a multicore CPU (abstracted considerably) with its memory hierarchy (implemented more concretely).
This diagram shows a CPU and a cache-coherent memory system being verified against their natural specifications. Afterward, the composition of CPU and memory is almost automatically verified against the composition of their specifications. This description raises two important questions: what kinds of specifications are we working with, and how can this kind of composition theorem be related to the most natural specification of the full system, which in this case is a formal equivalent of a programmer-facing instruction-set manual (like e.g. those published by Intel for x86 processors).
The general idea is to consider a hardware component’s interface to the rest of a larger system it is included in. Broadly, a component is connected elsewhere via wires that carry values per step of execution (clock cycle). Imagine as a thought experiment that we keep a log. For every execution step, the log includes the value of each wire. A component’s relevant behavior can be summarized as the set of logs it could generate. Some wires contain inputs, which the component has no control over, but it gets to set the values on the output wires. Hence, sets of logs do capture all possible interactions with the rest of a hardware design.
Then, as we covered briefly in previous discussion of refinement as a specification technique, the right formalization of “A is a correct implementation of spec B” is “the possible-log set for A is a subset of the possible-log set for B.” That is, the implementation exhibits no behavior that can’t be matched by the spec. The following diagram shows an example for a CPU and its interface with memory, where I won’t bother to explain conventions like “ready” and “valid” wires, but their profusion even for such a simple interface (to let the CPU read and write memory) is representative of interface complexity.
There are at least two important nuisances in this style.
The convention of “ready” and “valid” wires is intricate to track. We might naturally hope to abstract out this common protocol.
Capturing precise timing makes specifications overly constraining, if we aren’t careful. A specification that mandates exactly when any important state transition happens is too constraining: we want to allow implementation of clever new optimizations that speed up processing. However, writing specifications explicitly to tolerate such timing changes is nontrivial.
The design of Bluespec unlocks solutions to both problems.
To avoid proliferation of administrative signals, Bluespec exposes an object-oriented-style interface that would be familiar to software programmers, where modules communicate with each other through calling methods, which manipulate the called module’s private state. In our CPU example, methods can be used for requesting memory reads/writes and receiving matching responses. An important distinction from object-oriented software is that methods have associated guard conditions, blocking execution safely when guards are false. For instance, a method to dequeue a value from a container often includes a guard saying that the container is not empty. A guard failure anywhere in the execution of a method call, including in other methods it calls, rolls back the whole top-level method call, undoing any side effects. (Such rollback is implemented efficiently in hardware, detecting the guard failure upfront and simply not enabling associated logic.) Now the log entries in our thought experiment record method calls, where each such entry includes not just a method’s name but also the parameter values passed to it and the return value that results.
To simplify timing reasoning, we adopt a latency-insensitive style. The logging thought experiment changes to skip logging a step where no methods are called. As a result, a specification may speedrun through executing some operation, while the implementation is allowed to take as many steps as it needs to match the same behavior.
The Algebra of Refinement
Our refinement relation is a handy one. It meets the traditional requirements to be used for rewriting, or gradually applying proved instances to transform one term into another. It is a preorder (reflexive and transitive). It also satisfies the relevant congruence properties, meaning that a rewrite rule can be used to transform a subterm deep within the structure of a larger term. (I’ve been using drawings of system structure with nested boxes, but imagine that we are really working with algebraic syntax trees, where each such term includes subterms as subtrees.) Congruence is actually the most interesting of these three properties, and it is a renaming of the modular linking of proofs described much earlier. It depends on a strong modularity discipline built into the hardware language (for instance, preventing one module from directly reading or writing the private state of another).
Let’s demonstrate the power of this kind of rewriting in our CPU example. We’ll need a few rewrite rules to work with. To start with, assume one showing that some optimized queue implementation refines an idealized queue specification.
Then consider one of the classics of this genre: a pipeline with multiple stages, connected by idealized queues, can be collapsed into a single node that applies the effects of all stages. Multiple stages are helpful to increase parallelism, letting each stage handle its assigned aspect of a different instruction, so progress is made on all of them at once. Queues sit between stages to coordinate handoff of entries for instructions. (Readers familiar with CPU design may object that the diagram here omits additional pathways for coordination across stages, which can indeed be accommodated as well, though I omit them here to keep the example tractable.)
Also assume two more proved refinements: (1) a system that explicitly separates CPU and memory refines a standard instruction-set specification, and (2) the cache-coherent memory system refines a simple specification of memory. (Each of these refinements may itself be proved with sequences of simpler refinements, but let’s not go there for this example.) Now we can use a sequence of four rewrites to derive the efficient implementation from the specification. Dashed outlines are used to indicate subterms that are about to be rewritten. This rendering reverses the direction from the earlier example refinement rules, going from specification to implementation.
Each of the rewrite rules can be stated in a suitably general way and proved independently. Then any sequence of rewrite rules transforms a specification into a functionally correct implementation. If we ask an AI agent to choose the rule sequence, it can take us to a design that is unappealing for some property that we haven’t formalized, like performance. However, a misguided agent can’t take us to a design with the wrong functional behavior.
We concretized such refinement reasoning with Bluespec-style hardware designs in Kami, which was later simplified into Fjfj. The earlier of these frameworks drove the hardware side of the end-to-end hardware-software verification case study I highlighted in an earlier article. More-realistic analogues of all of the refinement rules sketched here have been proved and applied in these systems, though mostly for verification of handwritten hardware designs, rather than deriving designs from specifications.
The specification style demonstrated above is convenient for collapsing away time steps where nothing interesting happens. However, sometimes timing is an important part of a specification. We developed Kôika to support fine-grained timing reasoning while preserving appealing abstractions of Bluespec. It was used to prove timing security of a hardware enclave system.
We have now seen examples of problems in both software and hardware that fit this framework of rewriting a specification into an efficient implementation through refinement, in a correct-by-construction way. Both examples use rewrite rules that are proved correct in full generality. The next article will explain a different style, with effective automation that checks individual program transformations for correctness, paired with search th
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。