Introduction

 People

 Research themes:

   Embedded Systems

   Hybrid Systems

   Deep Submicron

   Logic Synthesis

 Other links:

   EE249

   CHESS

   GSRC

   BWRC

Exact BDD Minimization

Luca Carloni, University of California at Berkeley
Arlindo Oliveira, Inesc, Lisbon 
Alberto Sangiovanni-Vincentelli, University of California at Berkeley
Tiziano Villa, Parades, Rome


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

 

Contact 
©2002-2018 U.C. Regents