Hazard-Freedom Checking in Speed-Independent Systems

Hüsnü Yenigün, Vladimir Levin, Doron A. Peled, Peter A. BeerelCHARME 1999 · OpenReview

Abstract

Verifying hazard-freedom in speed-independent (SI) asynchronous systems is a computationally intensive task due to the state explosion problem. This paper presents a methodology for such verification using the COSPAN model checking tool. By introducing a specialized "Asynchrony Manager" and a static partial order reduction technique based on "ample" gate identification, the authors achieve significant reductions in the state space. Experimental results on scalable FIFO circuits show that the proposed reduction method enables the verification of larger systems that were previously computationally infeasible.

Introduction

Asynchronous digital designs, specifically speed-independent (SI) systems, operate without a global clock. Their correctness relies on the assumption that gates have arbitrary delays while wires have zero delay. While this paradigm offers potential benefits in power and performance, it introduces the risk of functional hazards—unwanted signal transitions that can lead to circuit failure.

Verifying that an SI circuit is hazard-free requires exploring all possible interleavings of gate transitions. As the number of gates increases, the state space grows exponentially, a phenomenon known as the state explosion problem. Traditional model checking tools often struggle with this complexity, necessitating more efficient search strategies.

Methodology

The authors utilize the COSPAN formal verification tool, which operates on the Selection/Resolution (S/R) language. Since S/R is natively synchronous, an Asynchrony Manager (AM) was developed to simulate asynchronous behavior by ensuring only one gate transition occurs per step.

The core contribution is a static partial order reduction approach. Instead of an exhaustive search, the algorithm identifies "ample" gates at each state. A gate is considered ample if it is enabled and its transition does not interfere with other concurrent transitions in a way that could hide a hazard. By only exploring transitions of ample gates, the search tree is pruned significantly without compromising the integrity of the hazard-freedom check. This logic is implemented symbolically using Binary Decision Diagrams (BDDs) within COSPAN.

Experimental Results

The method was evaluated using a scalable family of FIFO queue circuits composed of Muller C-elements. Performance was measured across two dimensions: memory consumption and execution time.

Memory usage comparison between explicit and BDD-based methods, with and without reduction.

As shown in the memory analysis above, the "Explicit, no reduction" approach quickly exceeds practical limits as the number of C-elements grows. The reduced methods, particularly when combined with BDD representation, maintain much lower memory profiles, allowing for the analysis of circuits with up to 50 elements.

Execution time comparison on a logarithmic scale, showing the efficiency of the reduced approach.

The timing results further highlight the benefits of the reduction technique. For circuits larger than 16 elements, the reduced analysis is significantly faster. While the growth remains fundamentally exponential, the reduction effectively lowers the exponent, extending the reach of formal verification to more complex asynchronous architectures.

Conclusion

The application of static partial order reduction to hazard-freedom checking provides a powerful tool for asynchronous system designers. By leveraging the "ample" gate criteria, the authors successfully mitigated the state explosion problem in COSPAN. Future work will focus on automating the translation from circuit schematics to S/R processes and testing the methodology on a wider variety of asynchronous design styles beyond FIFO queues.

Summary updated

BibTeX
@inproceedings{yenigun1999hazard,
  author = {Hüsnü Yenigün and Vladimir Levin and Doron A. Peled and Peter A. Beerel},
  title = {{Hazard-Freedom Checking in Speed-Independent Systems}},
  booktitle = {CHARME},
  year = {1999},
  url = {https://openreview.net/forum?id=BIbkuQXhF9},
}
Figure