Implicit Generation of Compatibles for Exact State Minimization

T. Kam, T. Villa, Robert K. Brayton and Alberto L. Sangiovanni-Vincentelli

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M93/60
August 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/ERL-93-60.pdf

Implicit computations of the solution set of optimization problems arising in logic synthesis hold the promise of enlarging the size of input instances that can be solved exactly. The state minimization problem for incompletely specified machines is an important step for sequential circuit optimization. the problem is NP-hard and hence most techniques are heuristic. An exact algorithm consists of two steps: generation of sets of compatibles, and solving a binate covering problem. This paper presents implicit computations to obtain the sets of compatibles required for an exact state minimization of incompletely specified finite state machines (ISFSM's). Sets of maximal compatibles, compatibles, prime compatibles and implied class sets are all represented and manipulated implicitly by means f BDD's that realize the characteristic functions of the sets. We have demonstrated with experiments from a variety of benchmarks that implicit techniques allow to handle examples exhibiting a number of compatibles up to 2^1200, an achievement outside the scope of programs based on explicit enumeration [9]. We have shown in practice that ISFSM's with a very large number of compatibles may be produced as intermediate steps of logic synthesis algorithms, for instance in the case of asynchronous synthesis [13]. This shows that the proposed approach has not only theoretical interest, but also practical relevance for current logic synthesis applications. A recasting of the final binate covering step as an implicit computation is under progress.

BibTeX citation:

@techreport{Kam:M93/60,
    Author = {Kam, T. and Villa, T. and Brayton, Robert K. and Sangiovanni-Vincentelli, Alberto L.},
    Title = {Implicit Generation of Compatibles for Exact State Minimization},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2412.html},
    Number = {UCB/ERL M93/60},
    Abstract = {Implicit computations of the solution set of optimization problems arising in logic synthesis hold the promise of enlarging the size of input instances that can be solved exactly.  The state minimization problem for incompletely specified machines is an important step for sequential circuit optimization.  the problem is NP-hard and hence most techniques are heuristic.  An exact algorithm consists of two steps:  generation of sets of compatibles, and solving a binate covering problem.  This paper presents implicit computations to obtain the sets of compatibles required for an exact state minimization of incompletely specified finite state machines (ISFSM's).  Sets of maximal compatibles, compatibles, prime compatibles and implied class sets are all represented and manipulated implicitly by means f BDD's that realize the characteristic functions of the sets.  We have demonstrated with experiments from a variety of benchmarks that implicit techniques allow to handle examples exhibiting a number of compatibles up to 2^1200, an achievement outside the scope of programs based on explicit enumeration [9].  We have shown in practice that ISFSM's with a very large number of compatibles may be produced as intermediate steps of logic synthesis algorithms, for instance in the case of asynchronous synthesis [13].  This shows that the proposed approach has not only theoretical interest, but also practical relevance for current logic synthesis applications.  A recasting of the final binate covering step as an implicit computation is under progress.}
}

EndNote citation:

%0 Report
%A Kam, T.
%A Villa, T.
%A Brayton, Robert K.
%A Sangiovanni-Vincentelli, Alberto L.
%T Implicit Generation of Compatibles for Exact State Minimization
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/60
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2412.html
%F Kam:M93/60