Formal Verification of Flow Equivalence in Desynchronized Designs

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

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 latch-based 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, machine-checkable proofs of our results.

Introduction

In modern digital design, the global clock serves as a universal synchronizer, ensuring that data moves through latches in a predictable, lock-step fashion. Desynchronization is a design methodology that removes this global clock, replacing it with local asynchronous handshaking controllers. This approach can lead to significant improvements in power efficiency and electromagnetic interference.

However, the transition from synchronous to asynchronous must be functionally transparent. This is captured by the concept of flow equivalence: an asynchronous implementation is flow equivalent to its synchronous specification if it produces the exact same sequence of data values at every latch. For years, a 2006 proof by Cortadella et al. was widely accepted as a guarantee that a specific, highly concurrent handshaking protocol preserved this equivalence. This research identifies a critical flaw in that proof and provides a formal path forward.

The Flaw in the 2006 Proof

The original proof relied on a subtle inductive argument that the authors have now shown to be incorrect. The error, termed the "induction trap," stems from an assumption about latch transparency. The 2006 proof assumed that because a predecessor latch's clock signal had risen (opening the latch), the new data was already available for the successor. In reality, data stability is only guaranteed after the predecessor's clock signal falls, making the latch opaque and holding the value.

Counterexample trace showing a violation of flow equivalence where a data value is dropped.

By constructing a specific trace for a three-stage pipeline, the researchers demonstrated that the original protocol could allow a latch to capture data prematurely. In the example shown in Figure 1, the system produces the sequence [c0, c1, c1, c3] instead of the correct [c0, c1, c2, c3], effectively dropping the data value c2.

Formalization in Coq

To resolve these ambiguities and provide a rigorous foundation for desynchronization, the authors formalized the problem using the Coq proof assistant. This involved several key components:

  • Marked Graphs: The asynchronous controllers were modeled as Marked Graphs, a class of Petri nets suitable for modeling concurrent systems with fixed dependencies.
  • Execution Semantics: The researchers developed a 5-ary inductive relation to describe the state transitions of the asynchronous system, explicitly tracking the "transparency" of each latch.
  • Machine-Checked Proofs: By formalizing the definitions of synchronous and asynchronous traces, the authors were able to provide the first mechanized proofs of flow equivalence for alternative protocols.
Marked Graph models used to formalize the asynchronous handshaking protocols.

Verified Protocols and Results

While the most aggressive protocol was found to be flawed, the researchers successfully verified two "decoupled" variants: rise-decoupled and fall-decoupled. These protocols are slightly less concurrent but enforce stricter invariants that prevent the race conditions identified in the counterexample.

The key results include:

  1. Mechanized Verification of Theorems 5 and 7: These theorems confirm that the rise-decoupled and fall-decoupled protocols are mathematically sound and strictly preserve flow equivalence.
  2. Proof Portability: The inductive definitions used in Coq are structured to be accessible, suggesting that these results could be replicated in other formal environments like ACL2 or Isabelle.
  3. Publicly Available Proofs: The core lemmas, comprising approximately 70 lines of Coq tactics, are available for community review and extension.

Limitations and Future Work

The current formalization operates under a zero-delay assumption for combinational logic and latches. While this is a standard abstraction for high-level flow equivalence, physical delays in real-world silicon could introduce additional timing hazards not captured here. Furthermore, this work focuses on safety (correctness of data) rather than liveness (absence of deadlock). Future research aims to extend these mechanized proofs to include liveness properties and more complex hardware structures, such as flip-flop-based designs and 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 latch-based 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, machine-checkable 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},
}
Figure