A Fully Implicit Algorithm 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/79
November 1993

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

Implicit computations of the solution set of optimization problems arising in logic synthesis hold the promise of enlarging the size of 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. An exact algorithm consists of two steps: generation of sets of compatibles, and solution of a binate covering problem. This paper presents an implicit algorithm for exact state minimization of FSM's. There are various applications of logic synthesis that generate FSM's beyond the reach of state-of-art state minimization tools. Therefore it is of practical importance to revisit exact state minimization of ISFSM's and address the issue of representing implicitly the solution space. In this paper we show how to compute sets of maximal compatibles, compatibles and prime compatibles with implicit techniques and demonstrate that in this way it is possible to handle examples exhibiting a number of compatibles up to 21200, a number outside the scope of programs based on explicit enumeration [13]. We indicate also where such examples arise in practice. Then we address the final step of an implicit exact state minimization procedure, i.e. solving a binate table covering problem [24]. We present the first published algorithm for fully implicit exact binate covering. We report preliminary results of a prototype implementation capable of reducing huge binate tables (up to 106 rows and column)s and of carrying on the branch-and-bound procedure on an implicit representation of the table. Exact solutions to problems beyond the reach of traditional tools are so found.


BibTeX citation:

@techreport{Kam:M93/79,
    Author = {Kam, T. and Villa, T. and Brayton, Robert K. and Sangiovanni-Vincentelli, Alberto L.},
    Title = {A Fully Implicit Algorithm for Exact State Minimization},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2448.html},
    Number = {UCB/ERL M93/79},
    Abstract = { Implicit computations of the solution set of optimization problems arising in logic synthesis hold the promise of enlarging the size of 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. An exact algorithm consists of two steps: generation of sets of compatibles, and solution of a binate covering problem. This paper presents an implicit algorithm for exact state minimization of FSM's. There are various applications of logic synthesis that generate FSM's beyond the reach of state-of-art state minimization tools. Therefore it is of practical importance to revisit exact state minimization of ISFSM's and address the issue of representing implicitly the solution space. In this paper we show how to compute sets of maximal compatibles, compatibles and prime compatibles with implicit techniques and demonstrate that in this way it is possible to handle examples exhibiting a number of compatibles up to 21200, a number outside the scope of programs based on explicit enumeration [13]. We indicate also where such examples arise in practice. Then we address the final step of an implicit exact state minimization procedure, i.e. solving a binate table covering problem [24]. We present the first published algorithm for fully implicit exact binate covering. We report preliminary results of a prototype implementation capable of reducing huge binate tables (up to 106 rows and column)s and of carrying on the branch-and-bound procedure on an implicit representation of the table. Exact solutions to problems beyond the reach of traditional tools are so found.}
}

EndNote citation:

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