Partial Breadth-First Manipulation of Binary Decision Diagrams
Date Issued
2004
Date
2004
Author(s)
Ke, Sin-Hao
DOI
zh-TW
Abstract
傳統的二元決策圖運算方式，採用深度優先演算法。一旦運算的記憶體超出實際記憶體時，造成大量記憶體置換(memoryswapping )，使得效能大幅下滑。為改善二元決策圖的運算效率，OCHI等人[5] 提出了廣度優先的演算法，來增加記憶體局部性，但是在運算的過程中，要求佇列將會產生龐大的記憶體負擔。
Bwolen Yang等人提出了深度廣度混合的方法[7]，當要求佇列過大時，在執行一定容量的佇列後，便將剩下的要求佇列丟進堆疊中，等到下面的運算都做完時，才回過頭來從堆疊中取出未完成的運算繼續執行。
我們的方法是對Bwolen Yang人提出的深度廣度混合的方法 [7]做改良。當應用階段時，所產生的下一要求佇列超過預設值時，則下一要求佇列切成兩半。當目前這段要求佇列運算結束後，所產生的下一要求佇列存到檔案中，等運算至下一層時才提出來做運算。而運算完要求佇列則成為往前參考佇列 ( forwarding queue )存到檔案中，等到簡化階段才拿來計算運算結果。
由於我們的方法是一層一層做運算，只需運算變數的那一層二元決策圖節點。而當這層的要求佇列全做完，則原先二元決策圖節點的空間可全釋放。來載入下一層的節點，節省記憶體空間。此外，因為我們只有目前的要求佇列和下一要求佇列，因此對於佇列的管理與利用可有效安排，不會造成下面的要求佇列暫去太多記憶體空間，產生大量記憶體置換的情形。
Subjects
二元決策圖
分段廣度優先
Partial Breadth-First
Binary Decision Diagrams
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R91921086-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):f21864e7385727ccfc5ecb0722e328be