臺灣博碩士論文加值系統

自二元決策圖﹙Binary Decision Diagram﹚用來表示布林函數的概念和其相關運算的演算法被提出以來，就獲得許多研究者的採用。要找出表達函數的最佳變數順序，計算之時間複雜度相當高，於是在過去的十年間，BDD最小化的問題受到許多人的討論和研究。雖然如此，數十到數百個輸入的電路至今仍無實用的演算法能夠求出更為精確的解。本論文針對這樣的問題，以亂數演算法，將過去只能求出近似解的篩選﹙sifting﹚演算法的計算能力，提升到相當於求出精確最佳解演算法一樣；而且更容易平行化，以符合更大型電路求解的需求。
在本論文中，benchmark LGSynth91中輸入數小於500的電路除了C6288.blif之外，都找到了相當好的解，形成最小BDD的變數順序在附錄中一一列出，數據顯示，這些BDD的大小都比以往所知的小，計算時間也並未因為使用亂數演算法而有不穩定的現象，說明我們所提出的新方法有極佳的效能。

Binary Decision Diagram (BDD) is a data structure for the representation and manipulation of Boolean functions, which is applied in many areas. However, finding the optimal variable ordering of BDD seems to be intractable.
Though numerous algorithms for BDD minimization are proposed in the last decade, no feasible one is able to find a good variable ordering for Boolean functions with up to hundreds variables. In this thesis we present a randomized algorithm to minimize BDD. With the help of our new approach, Sifting algorithm works as well as an exact algorithm. The new approach can be parallelized easily to meet the need of complex function minimization.
In the thesis, LGSynth91 circuits with less than 500 variables are all minimized with very good results, except only C6288.blif. The better variable orderings of these benchmark circuits are listed in Appendix. Experimental results show that the BDDs' sizes are smaller than previous known results, and it's computing time is very small and very stable. It turns out that this randomized algorithm is a robust method for BDD minimization.

第一章 緒論 1
第一節 簡介 1
第二節 文獻探討 14
第三節 本篇論文結構 23
第二章 BDD介紹與問題定義 24
第一節 布林函數的圖形表示法 24
A. 定義 24
B. 與布林函數的關係 25
第二節 BDD的特性 26
A. 幾個BDD的例子 26
B. 變數順序（ordering）的影響 27
C. 簡化（reduction）和最小化（minimization） 28
D. 對稱性（symmetric relation） 29
第三節 名詞及符號的定義 31
第三章 我們所提出的亂數演算法 47
第一節 篩選（Sifting）演算法 47
第二節 以亂數演算法最小化（minimize）BDD 56
第一部份、效能比較 56
第二部份、計算成本之估算 66
第三部份、求解benchmark電路 70
第四章 效能分析 81
第五章 結論 87
參考文獻 89
附錄甲、程式碼﹙一﹚ 92
附錄乙、程式碼﹙二﹚ 104
附錄丙、最佳變數順序 111

1. R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput., vol. 35, pp. 677-691, Aug. 1986.
2. S. J. Friedman and K. J. Supowit, “Finding the optimal variable ordering for binary decision diagrams,” IEEE Trans. Comput., pp. 710-713, May 1990.
3. N. Ishiura, H. Sawada, and S. Yajima, “Minimization of binary decision diagrams based on exchange of variables,” in Proc. Int. Conf. Computer-Aided Design, pp. 472-475, Nov. 1991.
4. R. Rudell, “Dynamic variable ordering for ordered binary decision diagrams,” Int. Conf. Computer-Aided Design, pp. 42-47, 1993.
5. S.-W. Jeong, T.-S. Kim, and F. Somenzi, “An efficient method for optimal BDD ordering computation,” in Proc. Int. Conf. VLSI and CAD, 1993.
6. S. Panda and F. Somenzi, “Who are the variables in your neighborhood,” in Int. Conf. Computer-Aided Design, pp. 74-77, 1995.
7. B. Bolling, M. Löbbing, and I. Wegener, “On the effect of local changes in the variable ordering of ordered decision diagrams,” Inform. Processing Lett., vol. 59, pp. 233-239, Oct. 1996.
8. B. Bolling, I. Wegener, “Improving the variable ordering of OBDDs is NP-complete,” IEEE Trans. Computer., vol. 45, pp 993-1002, Sep. 1996.
9. R. Drechsler, W. Günther, and F. Somenzi, “Using lower bounds during dynamic BDD minimization,” IEEE Trans. Computer-Aided Designs, vol. 20, pp. 51-57, Jan. 2001.
10. R. Drechsler, N. Drechsler, and W. Günther, “Fast exact minimization of BDDs,” IEEE Trans. Computer-Aided Designs, vol. 19, pp. 384-389, Mar. 2000.
11. C. Scholl, D. Möller, and P. Molitor, “BDD minimization Using Symmetries,” IEEE Trans. Computer-Aided Designs of Integrated Circuits and Systems, vol. 18, no 2. Feb. 1999.
12. R. K. Brayton, G. D. Hachtel, C. T. McMullen and A. L. Sangiovanni-Vincentelli, "Logic Minimization Algorithms for VLSI Synthesis," Kluwer Academic Publishers, Boston. 1984.
13. D. Möller and R. Drechsler, “Symmetry based variable ordering for ROBDD’s,” in Proc. IFIP Workshop on Logic and Architecture Synthesis, pp. 47-53, Dec. 1994.
14. R. Drechsler and B. Becker, “Binary Decision Diagrams — Theory and Implementation.” Kluwer Acadmic Publishers, 1998.
15. R. E. Brant, “On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication,” IEEE Trans. on Comp., vol. 40, pp. 205-213, 1991.
16. W. Günther and R. Drechsler, “Minimization of Free BDDs,” IEEE Trans. on Comp., vol. , pp. 323-326, 1999.
17. F. M. Brown, "Boolean Reasoning," Kluwer Academic Publishers, Boston. 1990.
18. R. E. Brant, “Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams,” ACM, Comp. Surveys, vol. 24, 293-318, 1992.
19. J. C. Muzio, T. C. Wesselkamper, “Multiple-Valued Switching Theory,” Adam Hilger Ltd Bristol and Boston, 1986.
20. C. E. Shannon, “A symbolic analysis of relay and switching circuits,” Trans, AIEE, vol. 57, pp. 713-723, 1938.
21. U. Kebschull, E. Schubert and W. Rosenstiel, “Multilevel logic synthesis based on functional decision diagrams,” Proc. European Design Automation Conf. pp 43-47, 1992.
22. F. Somenzi, CUDD: CU Decision Diagram Package — Release 2.3.1 Technical report, Dept. of Electrical and Computer Engineering, University of Colorado, Boulder, Colorado, Feb. 2001.
23. 網站 http://vlsi.colorado.edu/~fabio