顏嗣鈞臺灣大學：電機工程學研究所康師誠Kang, Shy-CherngShy-CherngKang2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/52995本論文嘗試以資料在磁碟機與內部記憶體的轉換機制作為主要考量去發展出二元決策圖操作方式，以便讓資料在內部記憶體上和磁碟機的轉換能夠更有效率，此機制嘗試將二元決策圖做有效的分割，使得只需將必要的二元決策圖資料放於主記憶體上，因此可以增加主記憶體使用的效率。 二元決策圖就是一個常被使用和研究的資料結構。在近年來，二元決策圖已被廣泛應用且成功的使用在各種問題上，而這些研究在現實的應用上亦有良好的表現。但是過去大部分研究是以主記憶體為考量，也就是說以減少分頁錯誤為考量，實際的分頁置換仍交給作業系統，因為作業系統無法有效地考慮二元決策圖在操作機制，因此無法解決二元決策圖在操作上的瓶頸，會花費過多時間在無效的資料轉換上，產生降低了CPU處理效能的問題。以轉換機制作為主要考量所發展出的二元決策圖操作方式有利於大型二元決策圖的操作，尤其在使得二元決策圖資料的置換方式能較符合大型二元決策圖的操作，同時亦能符合記憶體與硬碟間的置換方式，以期能夠讓無效的資料置換次數減少，而增加二元決策圖資料置換的可控制性，以避免當資料量暴增時，會造成以二元決策圖為表示的布林函數操作上，無法有效的在主記憶體上執行。第一章 緒論 8 1.1 研究動機與方法………………………………………………………… 8 1.2 論文結構………………………………………………………………… 10 第二章 理論基礎 11 2.1 二元決策圖的起源與介紹……………………………………………… 11 2.1.1 二元決策圖的起源…………………………………………… 11 2.1.2 二元決策圖的定義…………………………………………… 12 2.1.3 二元決策圖的操作…………………………………………… 17 2.1.4 二元決策圖資料結構………………………………………… 18 2.2 不同二元決策圖之操作方法…………………………………………… 20 2.2.1 深度優先遞迴二元決策圖操作……………………………… 21 2.2.2 寬度優先二元決策圖操作演算演算法……………………… 22 2.2.3 特殊硬體為基礎的二元決策圖操作演法…………………… 31 2.2.4 分散式系統為基礎的二元決策圖…………………………… 31 第三章 研究方法 35 3.1 研究目標……………………………………………………………… 35 3.2 研究議題與相關想法………………………………………………… 36 3.3 使用之資料結構………………………………………………………… 37 3.3.1 二元決策圖於主記憶體上的資料結構……………………… 37 3.3.2 所使用的獨特表結構………………………………………… 39 3.3.3 儲存計算要求的佇列資料結構……………………………… 41 3.4資料結構之操作………………………………………………………… 42 3.4.1獨特表置換…………………………………………………… 43 3.4.2 二元決策圖操作……………………………………………… 44 3.4.3 儲存計算要求的佇列操作…………………………………… 45 3.4.4 獨特表之分割………………………………………………… 50 3.5 整體設計流程…………………………………………………………… 51 3.6 廢棄空間之收集方式…………………………………………………… 53 3.6.1主記憶體的廢棄空間之收集方式…………………………… 53 3.6.2檔案的的廢棄空間之收集方式……………………………… 57 第四章 系統模擬及數據討論 58 4.1 系統模擬實作…………………………………………………………… 58 4.2 實驗設計與結果………………………………………………………… 58 4.2.1 較小型的測試資料…………………………………………… 58 4.2.2較大型的測試資料…………………………………………… 60 4.2.3 漸增的位元數量乘法器測試資料…………………………… 61 4.3 實驗結果討論…………………………………………………………… 64 第五章 結論 66 5.1 結論……………………………………………………………………… 66 5.2 未來工作………………………………………………………………… 66 參考文獻 67 附錄 ISCAS85測試資料規格 71446667 bytesapplication/pdfen-US二元決策圖磁碟機Binary Decision DiagramsDiskthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/52995/1/ntu-93-R91921092-1.pdf