Fast exact minimization of BDD's

被引：36

作者：

Drechsler, R ^{[1
]}

Drechsler, N ^{[1
]}

Günther, W ^{[1
]}

机构：

[1] Univ Freiburg, Inst Comp Sci, D-79110 Freiburg, Germany

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 2000年 / 19卷 / 03期

关键词：

binary decision diagrams (BDD's); exact minimization; lower bound technique;

D O I：

10.1109/43.833206

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a new exact algorithm for finding the optimal variable ordering for reduced ordered binary decision diagrams (BDD's), The algorithm makes use of a lower bound technique known from very large scale integration design. Up to now this technique has been used only for theoretical considerations and it is adapted here for this purpose. Furthermore, the algorithm supports symmetry aspects and uses a hashing based data structure. Experimental results are given to demonstrate the efficiency of our approach. We succeeded in minimizing several functions, including adders with up to 64 variables, for which all other previously presented approaches fail.

引用

页码：384 / 389

页数：6

共 16 条

[1] PATH-DELAY-FAULT TESTABILITY PROPERTIES OF MULTIPLEXOR-BASED NETWORKS [J].

ASHAR, P ;

DEVADAS, S ;

KEUTZER, K .

INTEGRATION-THE VLSI JOURNAL, 1993, 15 (01) :1-23

[2]

BECKER B, 1992, LECT NOTES COMPUT SC, V577, P501

[3]

Bertacco V., 1997, P INT WORKSH LOG SYN

[4] Improving the variable ordering of OBDDs is NP-complete [J].

Bollig, B ;

Wegener, I .

IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (09) :993-1002

[5]

BRYANT RE, 1986, IEEE T COMPUT, V35, P677, DOI 10.1109/TC.1986.1676819

[6] ON THE COMPLEXITY OF VLSI IMPLEMENTATIONS AND GRAPH REPRESENTATIONS OF BOOLEAN FUNCTIONS WITH APPLICATION TO INTEGER MULTIPLICATION [J].

BRYANT, RE .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (02) :205-213

[7]

Buch P, 1997, 1997 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN - DIGEST OF TECHNICAL PAPERS, P663, DOI 10.1109/ICCAD.1997.643609

[8]

FRIEDMAN SJ, 1987, P 24 ACM IEEE DES AU, P348

[9]

ISHIURA N, 1991, P INT C COMP AID DES, P472

[10]

JEONG SW, 1993, P INT C VLSI CAD

← 1 2 →