Introduction
People Research
themes: Embedded Systems
Hybrid Systems
Deep Submicron
Logic Synthesis
Other links:
EE249
CHESS
GSRC
BWRC
|
Exact BDD Minimization
This project addresses the problem of binary decision diagram (BDD)
minimization in the presence of don't care sets. Specifically, given
an incompletely specified function g and a fixed ordering of the
variables, we propose an exact algorithm for selecting f such that f
is a cover for g and the binary decision diagram for f is of minimum
size. This approach is the only known exact algorithm for this problem
not based on the enumeration of the assignments to the points in the
don't care set.
We formulate the BDD minimization problem as a binate covering
problem. In particular, we find the minimum-sized binary decision
diagram compatible with the specification by solving a problem that is
very similar to the problem of reducing incompletely specified finite
state machines.
We have developed a prototype implementation of the algorithm based on
binary decision diagrams, using the implicit techniques developed by
T. Kam et al. ("Synthesis of FSMs: Functional Optimization", Kluwer Academic
Publishers, 1996) for state minimization of finite state
machines. This allowed us to solve exactly a class of interesting
examples and to measure the quality of existing heuristic
algorithms. We plan to extend the range of the problems that can be
solved exactly by fine-tuning the existing implementation and by
revising the computation of prime compatibles, which is currently the
bottleneck in the hard cases.
Publications:
A.L. Oliveira, L.P. Carloni, T. Villa and
A.L. Sangiovanni-Vincentelli,
Exact Minimization of Binary Decision Diagrams Using Implicit Techniques,
IEEE Transactions on Computers, Vol. 47, No. 11, November 1998.
A.L. Oliveira, L.P. Carloni, T. Villa and
A.L. Sangiovanni-Vincentelli,
An Implicit Formulation for Exact BDD Minimization of Incompletely Specified Functions,
in "VLSI: Integrated Systems on Silicon" (Ricardo Reis and Luc Claesen editors), Chapman-Hall 1997.
Notice:
This material is presented to ensure timely dissemination of scholarly and
technical work. Copyright and all rights therein are retained by authors or by
other copyright holders. All persons copying this information are expected to
adhere to the terms and constraints invoked by each author's copyright.
For questions and comments please write to lcarloni@eecs.berkeley.edu
|