顏嗣鈞臺灣大學：電機工程學研究所柯信豪Ke, Sin-HaoSin-HaoKe2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/52949傳統的二元決策圖運算方式，採用深度優先演算法。一旦運算的記憶體超出實際記憶體時，造成大量記憶體置換(memoryswapping )，使得效能大幅下滑。為改善二元決策圖的運算效率，OCHI等人[5] 提出了廣度優先的演算法，來增加記憶體局部性，但是在運算的過程中，要求佇列將會產生龐大的記憶體負擔。 Bwolen Yang等人提出了深度廣度混合的方法[7]，當要求佇列過大時，在執行一定容量的佇列後，便將剩下的要求佇列丟進堆疊中，等到下面的運算都做完時，才回過頭來從堆疊中取出未完成的運算繼續執行。 我們的方法是對Bwolen Yang人提出的深度廣度混合的方法 [7]做改良。當應用階段時，所產生的下一要求佇列超過預設值時，則下一要求佇列切成兩半。當目前這段要求佇列運算結束後，所產生的下一要求佇列存到檔案中，等運算至下一層時才提出來做運算。而運算完要求佇列則成為往前參考佇列 ( forwarding queue )存到檔案中，等到簡化階段才拿來計算運算結果。 由於我們的方法是一層一層做運算，只需運算變數的那一層二元決策圖節點。而當這層的要求佇列全做完，則原先二元決策圖節點的空間可全釋放。來載入下一層的節點，節省記憶體空間。此外，因為我們只有目前的要求佇列和下一要求佇列，因此對於佇列的管理與利用可有效安排，不會造成下面的要求佇列暫去太多記憶體空間，產生大量記憶體置換的情形。目錄 ……………………………………………………………………1 圖列表 …………………………………………………………………3 表列表 …………………………………………………………………4 摘要 ……………………………………………………………………5 第一章 緒論 …………………………………………………………7 第二章 理論基礎 ……………………………………………………11 2.1 決策樹( Decision trees ) ………………………………11 2.1.1 一般的決策樹 ………………………………………………11 2.1.2 有序的完整決策樹 …………………………………………14 2.2 二元決策圖( BDDs binary decision diagrams ) ……15 2.2.1 二元決策圖是簡化節點的決策樹 ………………………15 2.2.2 共用的二元決策圖( shared BBDs ) ……………………18 2.2.3 屬性弧( attributed arc ) ………………………………19 2.2.4 伙伴因子( cofactors ) …………………………………21 第三章 相關演算法 …………………………………………………23 3.1 深度優先( depth-first ) ………………………………23 3.2 廣度優先( breadth-first ) ……………………………26 3.3 廣度深度混合( hybrid ) …………………………………30 3.4 深度廣度混合 ………………………………………………31 第四章 實作細節 ……………………………………………………33 4.1 廣度優先( partial breath-first ) ……………………33 4.2 佇列的管理( request queue ) …………………………36 4.3 記憶體管理 …………………………………………………38 4.4 增加新節點 …………………………………………………38 4.5 廢棄空間的收集( garbage collection ) ………………39 第五章 實驗數據 ……………………………………………………44 5.1 實驗數據 ……………………………………………………44 5.2 實驗討論 ……………………………………………………46 第六章 結論 …………………………………………………………47 第七章 參考文獻 ……………………………………………………48348048 bytesapplication/pdfen-US二元決策圖分段廣度優先Partial Breadth-FirstBinary Decision Diagramsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/52949/1/ntu-93-R91921086-1.pdf