Formal Verification of Flow Equivalence in Desynchronized Designs

Jennifer Paykin, Brian Huffman, Daniel M. Zimmerman, Peter A. Beerel

TL;DR

Researchers identified a subtle but critical flaw in a seminal hand-written proof regarding asynchronous circuit design. By using the Coq proof assistant, they provided a concrete counterexample to a widely accepted protocol and produced the first machine-checked proofs for two alternative "decoupled" protocols that successfully preserve functional equivalence.

What Problem Does This Paper Address?

In traditional chip design, a global clock synchronizes everything. Desynchronization is a technique to strip away that global clock and replace it with local "handshaking" controllers, creating an asynchronous circuit that is often more power-efficient.

However, for this to be useful, the asynchronous version must be flow equivalent to the original synchronous design—meaning it must produce the exact same sequence of data at every latch. A landmark 2006 paper by Cortadella et al. provided a hand-written proof that a specific, highly concurrent handshaking protocol preserved this equivalence. This paper reveals that the 2006 proof was wrong: under certain timing conditions, the protocol allows a latch to capture data before its predecessor has finished updating, leading to corrupted output.

Methods

The authors combine manual "pencil-and-paper" counterexample generation with formal mechanized verification:

  • Counterexample Construction: They designed a three-stage pipeline and a specific sequence of clock transitions (a "trace") that obeys the original protocol but results in the wrong data being latched.
  • Formalization in Coq: They used the Coq proof assistant to build a mathematical model of circuits, synchronous execution, and asynchronous traces.
  • Marked Graphs: They modeled the asynchronous controllers as Marked Graphs (a subset of Petri nets). This allowed them to reason about the state of the system based on the number of "tokens" (events like rising or falling edges) that have occurred.
  • Inductive Proofs: They developed a 5-ary relation to describe asynchronous execution and used it to prove that two less-aggressive protocols—rise-decoupled and fall-decoupled—guarantee flow equivalence.

Datasets

As a formal methods paper, it does not use traditional training datasets. Instead, the "data" consists of:

  • Formal Models: Definitions of circuit structures and execution semantics in Coq.
  • Proof Scripts: Approximately 70 lines of Coq tactics for core lemmas, available in a public GitHub repository.
  • Circuit Examples: A specific three-stage pipeline used to demonstrate the counterexample.

Key Insights and Ideas

  • The "Induction Trap": The flaw in the original 2006 proof was a subtle misuse of an induction hypothesis. It assumed that because a predecessor's clock had risen, the new data was already available. In reality, the data is only guaranteed to be stable after the predecessor's clock falls (becomes opaque).
  • Transparency Matters: The authors formalize "transparency" (when a latch is open) as a first-class property in their execution model. This was key to identifying exactly when a circuit state becomes "unsafe."
  • Decoupling as a Safety Net: While the original "highly concurrent" protocol was too aggressive, the "rise-decoupled" and "fall-decoupled" variants work because they enforce a stricter invariant: a latch cannot change state until its neighbors have reached a specific, safe point in their own cycles.

Key Results

  • The Counterexample: The authors proved that the original protocol could cause a circuit to latch the sequence [c0, c1, c1, c3] instead of the correct [c0, c1, c2, c3], effectively "dropping" a data value.
  • Mechanized Verification: They successfully proved Theorem 5 and Theorem 7, confirming that the rise-decoupled and fall-decoupled protocols are mathematically sound and preserve flow equivalence.
  • Proof Portability: The authors note that while they used Coq, their inductive definitions are structured such that they could likely be replicated in other provers like ACL2 or Isabelle.

Limitations and Future Work

  • Zero-Delay Assumption: The current model assumes combinational logic and latches have zero delay. While standard for high-level flow equivalence, real-world circuits have physical delays that could introduce further complications.
  • Liveness: The paper focuses on safety (doing the right thing) but does not yet formally verify liveness (ensuring the circuit doesn't deadlock).
  • Complexity: The verification is currently limited to bundled-data designs. Future work aims to extend this to more complex architectures, such as flip-flop-based designs and circuits with retimed datapaths.

Summary updated

Abstract

Seminal work by Cortadella, Kondratyev, Lavagno, and Sotiriou includes a hand-written proof that a particular handshaking protocol preserves flow equivalence, a notion of equivalence between synchronous latchbased specifications and their desynchronized bundled-data asynchronous implementations. In this work we identify a counterexample to Cortadella et al.'s proof illustrating how their protocol can in fact lead to a violation of flow equivalence. However, two of the less concurrent protocols identified in their paper do preserve flow equivalence. To verify this fact, we formalize flow equivalence in the Coq proof assistant and provide mechanized, machinecheckable proofs of our results.
BibTeX
@inproceedings{paykin2020formal,
  author = {Jennifer Paykin and Brian Huffman and Daniel M. Zimmerman and Peter A. Beerel},
  title = {{Formal Verification of Flow Equivalence in Desynchronized Designs}},
  booktitle = {ASYNC},
  year = {2020},
  url = {https://openreview.net/forum?id=nRVoUNPnaR},
}

Loading related content...

Figure