二元決策圖(BDD)最小化問題之改良演算法

魏君任

指導教授 ： 林順喜

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2000年)

摘要

自二元決策圖﹙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.

關鍵字

二元決策圖 ； 亂數演算法 ； 最小化 ； 篩選演算法 ； 探索式演算法 ； 精確最小化演算法 ； -

並列摘要

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. R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,”

IEEE Trans. Comput., vol. 35, pp. 677-691, Aug. 1986.

for binary decision diagrams,” IEEE Trans. Comput., pp. 710-713, May 1990.

4. R. Rudell, “Dynamic variable ordering for ordered binary decision diagrams,

” Int. Conf. Computer-Aided Design, pp. 42-47, 1993.