Toggle Main Menu Toggle Search

Open Access padlockePrints

Logic Synthesis for Asynchronous Circuits Based on STG Unfoldings and Incremental SAT

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

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.


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 deriving equations for logic gates implementing each output signal of the circuit. This is usually done using reachability graphs. 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 structural conflicts between the events involved in a finite and complete prefix of its unfolding. We propose an efficient algorithm for logic synthesis based on the Incremental Boolean Satisfiability (SAT) approach. Experimental results show that this technique leads not only to huge memory savings when compared with the methods based on reachability graphs, but also to significant speedups in many cases, without affecting the quality of the solution.


Publication metadata

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

Publication type: Article

Publication status: Published

Journal: Fundamenta Informaticae

Year: 2006

Volume: 70

Issue: 1-2

Pages: 49-73

ISSN (print): 0169-2968

ISSN (electronic): 1875-8681

Publisher: IOS Press

URL: http://iospress.metapress.com/content/2lnurudcfg8w5hwk/


Share