Toggle Main Menu Toggle Search

ePrints

Detecting State Coding Conflicts in STGs Using Integer Programming

Lookup NU author(s): Dr Victor Khomenko, Professor Maciej Koutny, Professor Alex Yakovlev

Downloads


Abstract

The behaviour of asynchronous circuits is often described by Signal Transition Graphs (STGs), which are Petri nets whose transitions are interpreted as rising and falling edges of signals. One of the crucial problems in the synthesis of such circuits is that of identifying whether an STG satisfies the Complete State Coding (CSC) or Unique State Coding (USC) requirements, e.g. by using model-checking based on the reachability graph of an STG. In this paper, we avoid constructing the reachability graph of an STG, which can lead to state space explosion, and instead use only the information about causality and conflicts between the events involved in a finite and complete prefix of its unfolding. The model-checking algorithm is derived by adopting the integer programming approach. Following the basic formulation of the state coding conflict relationship, we present some problem-specific optimisation rules. This technique leads not only to huge memory savings when compared to the CSC (or USC) detection methods based on reachability graphs, but also to significant speedups in many cases. In addition, the method allows one to easily derive execution paths leading to an encoding conflict. Finally, the approach is also extended for checking the normalcy property of STGs, which is a necessary condition for their implementability using gates whose characteristic functions are monotonic.


Publication metadata

Author(s): Khomenko V, Koutny M, Yakovlev A

Publication type: Report

Publication status: Published

Series Title: Department of Computing Science Technical Report Series

Year: 2001

Pages: 22

Report Number: 736

Institution: Department of Computing Science, University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne

URL: http://www.cs.ncl.ac.uk/publications/trs/papers/736.pdf


Share