(34.237.52.11) 您好!臺灣時間:2021/05/18 12:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:康師誠
研究生(外文):Shy-Cherng Kang
論文名稱:以磁碟機為基礎的二元決策圖設計
論文名稱(外文):The Design of Disk-Based Binary Decision Diagrams
指導教授:顏嗣鈞
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:71
中文關鍵詞:二元決策圖磁碟機
外文關鍵詞:Binary Decision DiagramsDisk
相關次數:
  • 被引用被引用:0
  • 點閱點閱:95
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文嘗試以資料在磁碟機與內部記憶體的轉換機制作為主要考量去發展出二元決策圖操作方式,以便讓資料在內部記憶體上和磁碟機的轉換能夠更有效率,此機制嘗試將二元決策圖做有效的分割,使得只需將必要的二元決策圖資料放於主記憶體上,因此可以增加主記憶體使用的效率。
二元決策圖就是一個常被使用和研究的資料結構。在近年來,二元決策圖已被廣泛應用且成功的使用在各種問題上,而這些研究在現實的應用上亦有良好的表現。但是過去大部分研究是以主記憶體為考量,也就是說以減少分頁錯誤為考量,實際的分頁置換仍交給作業系統,因為作業系統無法有效地考慮二元決策圖在操作機制,因此無法解決二元決策圖在操作上的瓶頸,會花費過多時間在無效的資料轉換上,產生降低了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測試資料規格 71
[1] K. S. Brace, R. L. Rudell, and R. E. Bryant. “ Efficient implementation of a BDD package.” In Proceedings of the 7th Design Automation Conference, pages 40–45, Orlando, FL, June 1990
[2] R. E. Bryant. “Graph-based algorithms for boolean function manipulation.” IEEE Transactions on Computers, -35(8):677–691, August 1986.
[3] R. E. Bryant. “Symbolic manipulation of boolean functions using a graphical representation.” In Proceedings of he 22nd Design Automation Conference, June 1985.
[4] Fabio Somenzi. “Binary Decision Diagrams”,1999
[5] P. Ashar and M. Cheong. “Efficient breadth-first manipulation of binary decision diagrams.” In Proceedings of the International Conference on Computer-Aided Design, pages 622–627, San Jose, CA, November 1994.
[6] H. Ochi, K. Yasuoka, and S. Yajima. “Breadth-first manipulation of very large binary-decision diagrams.” In Proceedings f the International Conference on Computer-Aided Design, pages 48–55, Santa Clara, CA, November 1993.
[7] D. E. Long. The design of a cache-friendly BDD library. In Proceedings of the International Conference on Computer-Aided Design, pages 639–645, San Jose, CA, November 1998.
[8] B. Yang, Y.-A. Chen, R. Bryant, and D. O’Hallaron. “Space- and time-efficient BDD construction via working set control.” In Proc. of Asia and South Pacific Design Automation Conference (ASPDAC’98), Yokohama, Japan, February 1998.
[9] S. Manne, D. C. Grunwald, and F. Somenzi. “Remembrance of things past: Locality and memory in BDDs.” In Proceedings of the Design Automation Conference, pages 196–201, Anaheim, CA, June 1997.
[10]J.V.Sanghavi,R.K.Ranjan, R.K.Brayton, and A. Sangiovanni-Vincentelli. “High performance BDD package based on exploiting memory hierarchy.” In Proceedings of the Design Automation Conference, pages 635–640, Las Vegas, NV, June 1996.
[11] Stephen M. Blackburn, Kathryn S. McKinley .”Ulterior reference counting: fast garbage collection without a long wait.”ACM SIGPLAN Notices , Proceedings of the 18th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, Volume 38 Issue October 2003.
[12] Henry G. Baker “Minimizing reference count updating with deferred and anchored pointers for functional data structures”ACM SIGPLAN Notices, Volume 29 Issue 9 September 1994
[13] Benjamin Zorn. “Comparing mark-and sweep and stop-and-copy garbage collection.“ Proceedings of the 1990 ACM conference on LISP and functional programming. May 1990.
[14] R. Rudell. “Dynamic variable ordering for ordered binary decision diagrams.“In Proceedings of the International Conference on Computer-Aided Design, pages 42–47, Santa Clara, CA, November 1993.
[15] S.-I. Minato, N. Ishiura, and S. Yajima. “Shared binary decision diagram with attributed edges for efficient Boolean function manipulation.” In Proceedings of the Design Automation Conference, pages 52–57, Orlando, L, June 1990.
[16] R. Drechsler, N. Drechsler, and W. G¨unther. “Fast exact minimization of BDDs.” In Proceedings of the Design Automation Conference, pages 200–205, San Francisco, CA, June 1998.
[17] T. R. Shiple, R. Hojati, A. L. Sangiovanni-Vincentelli, and R. K. Brayton. “Heuristic minimization of BDDs using don’t cares.” In Proceedings of the Design Automation Conference, pages 225–231, San Diego, CA, June 1994.
[18] R. Drechsler, B. Becker, and N. G¨ockel.” A genetic algorithm for variable ordering of OBDDs. “Presented at the International Workshop on Logic Synthesis, Granlibakken, CA, May 1995.
[19] S. Panda, F. Somenzi, and B. F. Plessier. “Symmetry detection and dynamic variable ordering of decision diagrams.” In Proceedings of the International Conference on Computer-Aided Design, pages 628–631, San Jose, CA, November 1994.
[20] S.-W. Jeong, T.-S. Kim, and F. Somenzi. “An efficient method for optimal BDD ordering computation.” International Conference on VLSI and CAD (ICVC’93), Taejon, Korea, November 1993.
[21] S. J. Friedman and K. J. Supowit. “Finding the optimal variable ordering for binary decision diagrams.” IEEE Transactions on Computers, 39(5):710–713, May 1990.
[22] Ranjan, R.K. Sanghavi, J.V. Brayton, R.K.; Sangiovanni-Vincentelli, A “Binary decision diagrams on network of workstations” 1996 IEEE International Conference on , Pages:358 – 364 7-9 Oct. 1996
[23] T. E. Anderson, D. E. Culler, and D. A. Patterson. “A Case for NOW: Network of Workstations.” Technical Report UCB/ERL M94/58, Electronics Research Lab, Univ. of California, Berkeley, CA 94720, Nov. 1994.
[24] Jer-Sheng Chen. Banerjee, P.”Parallel construction algorithms for BDDs”Circuits and Systems, 1999. ISCAS ''99. Proceedings of the 1999 IEEE International Symposium on , Volume: 1 , 30 May-2 June 1999
[25] Stornetta, T.; Brewer, F.”Implementation of an efficient parallel BDD package” Design Automation Conference Proceedings 1996, 33rd , 3-7 Pages:641 – 644 June 1996
[26] Gai, S. Rebaudengo, M. Sonza Reorda M.”An improved data parallel algorithm for Boolean function manipulation using BDDs” Parallel and Distributed Processing, 1995. Proceedings. Euromicro Workshop on , 25-27 Pages:33 – 39 Jan. 1995
[27] Cabodi, G. Gai, S. Rebaudengo, M. Sonza Reorda, M.”A data parallel approach to Boolean function manipulation using BDDs”Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on , 2-6 Pages:163 - 175May 1994
[28] S. Kimura and E. M. Clarke. “A Parallel Algorithm for Constructing Binary Decision Diagrams.” In Proc. Intl. Conf. on Computer Design, pages 220–223, Nov. 1990.
[29] Parasuram, Y.; Stabler, E. Shiu-Kai Chin;”Parallel implementation of BDD algorithms using a distributed shared memory”System Sciences, 1994. Vol. I: Architecture, Proceedings of the Twenty-Seventh Hawaii International Conference on , Volume: 1 , 4-7 Pages:16 – 25 Jan. 1994
[30] H. Ochi, N. Ishiura, and S. Yajima. “Breadth-First Manipulation of SBDD of Boolean Functions for Vector Processing. “In Proc. of the Design Automation Conf., pages 413–416, June 1991.
[31] B. Yang, R. E. Bryant, D. R. O’Hallaron, A. Biere, O. Coudert, G. Janssen, R. K. Ranjan, and F. Somenzi. “A performance study of BDD-based model checking.” In Formal Methods in Computer Aided Design, November 1998.
[32] R. E. Bryant. “Binary decision diagrams and beyond: Enabling technologies for formal verification.” In Proceedings of the International Conference on Computer-Aided Design, pages 236–243, San Jose, CA, November 1995.
[33] R. E. Bryant.” On the complexity of VLSI implementations and graph representations of boolean functions with application to integer multiplication.” IEEE Transactions on Computers, 40(2):205–213, February 1991.
[34] R. Bryant. “A methodology for hardware verification based on logic simulation.” Journal of the Association for Computing Machinery, 38(2):299–328, Apr. 1991.
[35]Lars Arge “The I/O-Complexity of Ordered Binary-Decision Diagram Manipulation.” ESPRIT II Basic Research Actions Program of the EC under contract No. 7141 (project ALCOM II).1995
[36]Lars. Arge. “The Buffer Tree: A New Technique for Optimal I/O-Algorithms.” In Proc. of 4th Workshop on Algorithms and Data Structures, 1995.
[37] S. B. Akers. “Binary decision diagrams.” IEEE Transactions on Computers, C-27(6):509–516, June 1978.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 溫振華,〈清代中部平埔族遷移埔里分析〉,《臺灣文獻》,第51卷2期,民89,頁27-37。
2. 張其祿、黃榮護,〈全球化下的地方政府「治理」-理論挑戰與策略展望〉,《空大行政學報》,第12期,民91.8,頁147-167。
3. 許志雄,〈地方自治的普遍化與國際化〉,《律師雜誌》,第244期,民88,頁92-102。
4. 謝繼昌,〈平埔族之漢化—臺灣埔里平原之研究〉,《中央研究院民族學研究所集刊》,第47期,民68,頁49-72。
5. 陳欽春,〈社區主義在當代治理模式中的定位與展望〉,《中國行政評論》,第10卷,第1期,民89.12,頁183-213。
6. 陳立剛、李長晏,〈全球化治理—臺灣都會治理的困境與體制建構:地方政府跨區域合作探究〉,《中國地方自治月刊》,第56卷,第2期,民92,頁4-19。
7. 陳立剛,〈府際關係研究-區域治理問題及其策略〉,《中國地方自治》,第54卷,第1期,民90.1,頁20-29。
8. 陳美鈴,〈埔里盆地的平埔族聚落分佈型態〉,《國立僑生大學先修班學報》,第2期,民83年,頁229-264。
9. 林水波、李長晏,〈標竿學習與地方治理能力〉,《中國地方自治》,第56卷,第5期,民92.5,頁4-32。
10. 吳松林,〈變遷中的中央與地方關係〉,《研考雙月刊》,第26期,頁66-74。
11. 李長晏,〈中央與地方關係的重構與運作〉,《中國地方自治》,第53卷,第2期,頁30-41。
12. 江大樹,〈臺灣地方自治的改造與重建〉,《理論與政策》,第43期,民86,頁3-17。
13. 王灝,〈埔里平埔族的走標〉,《水沙連雜誌》,第14期,民85,頁8-12。