Heuristic Algorithms for Early Quantification and Partial Product Minimization

R. Hojati, S. Krishnan and Robert K. Brayton

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M94/11
March 1994

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/ERL-94-11.pdf

A set of interacting finite state machines is often used as a model for formal verification. Most formal verification algorithms, based on Binary Decision Diagrams (BDD's), build the transition relation of the product machine, and then existentially quantify out the non-state variables. The early quantification problem is to compute a schedule for multiplying and existentially quantifying variables, such that the maximum size BDD encountered at any point is minimized. We give two algorithms for the early quantification problem, one which is rather fast (running in linear time on sparse structures), and produces excellent results and another which produces an optimal schedule for a given linear ordering of the terms. Even with early quantification partial products can become very large. In this paper, we present techniques to find don't cares, with respect to which the partial products are minimized. Some of our techniques involve state minimization and can result in smaller BDD's for the reachable states set. Two notions for state minimization are new, and involve approximations to trace equivalence. All the algorithms have been implemented and integrated in our formal verification software for design verification. We present our experimental results.


BibTeX citation:

@techreport{Hojati:M94/11,
    Author = {Hojati, R. and Krishnan, S. and Brayton, Robert K.},
    Title = {Heuristic Algorithms for Early Quantification and Partial Product Minimization},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/2508.html},
    Number = {UCB/ERL M94/11},
    Abstract = {A set of interacting finite state machines is often used as a model for formal verification. Most formal verification algorithms, based on Binary Decision Diagrams (BDD's), build the transition relation of the product machine, and then existentially quantify out the non-state variables. The early quantification problem is to compute a schedule for multiplying and existentially quantifying variables, such that the maximum size BDD encountered at any point is minimized.  We give two algorithms for the early quantification problem, one which is rather fast (running in linear time on sparse structures), and produces excellent results and another which produces an optimal schedule for a given linear ordering of the terms. Even with early quantification partial products can become very large. In this paper, we present techniques to find don't cares, with respect to which the partial products are minimized. Some of our techniques involve state minimization and can result in smaller BDD's for the reachable states set.  Two notions for state minimization are new, and involve approximations to trace equivalence. All the algorithms have been implemented and integrated in our formal verification software for design verification. We present our experimental results.}
}

EndNote citation:

%0 Report
%A Hojati, R.
%A Krishnan, S.
%A Brayton, Robert K.
%T Heuristic Algorithms for Early Quantification and Partial Product Minimization
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/ERL M94/11
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/2508.html
%F Hojati:M94/11