Title :
Reducing BDD size by exploiting structural connectivity
Author :
Wright, Ronnie L. ; Shanblatt, Michael A.
Author_Institution :
Dept. of Electr. & Comput. Eng., Michigan State Univ., East Lansing, MI, USA
Abstract :
Computer-aided design tools have been limited by the use of the Binary Decision Diagram (BDD). The major drawback of the BDD is its abundant usage of CPU time and memory. Techniques such as BDD variable ordering and sharing have been used in the past to address the size issue. However these techniques remain to be limited to modest-sized circuits. In this paper, we present a significant variation to the conventional BDD, the Connective Binary Decision Diagram (CBDD). The CBDD addresses the size issue concerning conventional BDD implementations by employing the use of minimized-scalable binary decision diagrams (MSBDDs) combined with the structural connectivity present in the circuit´s netlist. The experimental results section will demonstrate that the proposed method reduces the BDD size by more than two orders of magnitude for large circuits
Keywords :
VLSI; binary decision diagrams; circuit CAD; integrated circuit design; logic CAD; BDD size; VLSI; computer-aided design tools; connective binary decision diagram; minimized-scalable binary decision diagrams; netlist; structural connectivity; Binary decision diagrams; Bismuth; Boolean functions; Central Processing Unit; Circuit testing; Data structures; Electronic switching systems; Energy consumption; Portable computers; Very large scale integration;
Conference_Titel :
VLSI, 1999. Proceedings. Ninth Great Lakes Symposium on
Conference_Location :
Ypsilanti, MI
Print_ISBN :
0-7695-0104-4
DOI :
10.1109/GLSV.1999.757394