二元決策圖演算法：分段廣度優先運算方式

Partial Breadth-First Manipulation of Binary Decision Diagrams

柯信豪(Sin-Hao Ke)

指導教授 ： 顏嗣鈞

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.01924

摘要

傳統的二元決策圖運算方式，採用深度優先演算法。一旦運算的記憶體超出實際記憶體時，造成大量記憶體置換(memoryswapping )，使得效能大幅下滑。為改善二元決策圖的運算效率，OCHI等人[5] 提出了廣度優先的演算法，來增加記憶體局部性，但是在運算的過程中，要求佇列將會產生龐大的記憶體負擔。
Bwolen Yang等人提出了深度廣度混合的方法[7]，當要求佇列過大時，在執行一定容量的佇列後，便將剩下的要求佇列丟進堆疊中，等到下面的運算都做完時，才回過頭來從堆疊中取出未完成的運算繼續執行。
我們的方法是對Bwolen Yang人提出的深度廣度混合的方法 [7]做改良。當應用階段時，所產生的下一要求佇列超過預設值時，則下一要求佇列切成兩半。當目前這段要求佇列運算結束後，所產生的下一要求佇列存到檔案中，等運算至下一層時才提出來做運算。而運算完要求佇列則成為往前參考佇列 ( forwarding queue )存到檔案中，等到簡化階段才拿來計算運算結果。
由於我們的方法是一層一層做運算，只需運算變數的那一層二元決策圖節點。而當這層的要求佇列全做完，則原先二元決策圖節點的空間可全釋放。來載入下一層的節點，節省記憶體空間。此外，因為我們只有目前的要求佇列和下一要求佇列，因此對於佇列的管理與利用可有效安排，不會造成下面的要求佇列暫去太多記憶體空間，產生大量記憶體置換的情形。

關鍵字

二元決策圖 ； 分段廣度優先

並列摘要

無資料

並列關鍵字

Partial Breadth-First ； Binary Decision Diagrams

參考文獻

[1] S.B.Akers “Binary Decision Diagrams.” IEEE Transactions on Computers, C-27( 6 ): 509-516, June 1978.

[2] R.E.Bryant “Graph-Based Algorithms for Boolean Functions Manipulation.” IEEE Transactions on Computers, C-35( 8 ) : 677-691, August 1986.

[4] B.E.Moret “Decision Trees and Diagrams.” ACM Computing Surveys, 14( 4 ) : 593-623, December 1982.

[3] C.Y.Lee “Binary Decision Programs.” Bell system Technical Journal, 38( 4 ): 985-999, July 1959.

[5] H.Ochi, K.Yasuoka, and S.Yajima “Breadth-First Manipulation of Very Large Binary-Decision Diagram.” In Proceedings of the International Conference on Computer-Aided Design, 6-9, November 1993.