跳到主要內容

臺灣博碩士論文加值系統

(100.28.2.72) 您好!臺灣時間:2024/06/22 22:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張志榮
論文名稱:超大型積體電路分割演算法之研究
指導教授:魏凱城
學位類別:碩士
校院名稱:國立彰化師範大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:43
中文關鍵詞:電路分割
相關次數:
  • 被引用被引用:0
  • 點閱點閱:275
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
電路分割在超大型積體電路設計中一直扮演著重要的角色,其目的是在保持原電路邏輯架構下,利用電路中各個元件之間的連線資訊來分割電路。電路分割二重電路分割和多重電路分割,在本演算法中我們討論的是二重分割的問題。本演算法以分割成本來考量分割,所以分割後的結果將使得A和B兩子集合間的分割成本越小越好,同時經演算法調整後分別被配置至兩個子集合內的兩所有元件,在晶片中將是屬於不同區塊內的元件。
在本論文中我們研究如何計算和比較各節點的分割成本以降低分割成本,以及在調整兩個子集合大小的比例後對分割成本降低的效果。在本研究中我們得到下列具體的成果:我們同時參考[3][4][9]所提出的二重分割演算法,並且加入我們提出的演算方式改進分割成本(cut cost)的品質達 6.32% 至 34.26%。
中文摘要 I
英文摘要 II
誌謝 III
目錄 IV
圖目錄 V
表目錄 VI
第一章 緒論 1
第一節 前言 1
第二節 研究動機 2
第三節 研究目的及貢獻 3
第四節 後續章節介紹 5
第二章 文獻探討 6
第一節 Kernighan-Lin演算法 6
第二節 interleaved Cutting-Edge-Node Interleaved Sort for Leaching and Envelop 演算法 10
第三節 問題討論 14
2.3.1 分割線數 15
2.3.2 分割成本 15
第三章 問題描述與方法 17
第一節 問題描述 17
第二節 函式定義 18
第四章 演算法 20
第一節 演算法 20
4.1.1建立 EVW-matrix 21
4.1.2 Matrix之初始化 22
4.1.3 node 評估與移動 24
4.1.4 程式執行評估 29
4.1.5 子集合調整 30
第二節 流程圖 31
第五章 實驗結果 33
第一節 程式語言與工作平台 33
第二節 實驗數據與成果分析 33
第六章 結論與未來方向 39
第一節 結論 39
第二節 未來方向 41
參考文獻 42
[1] Ababei, C., Mogal, H., and Bazargan, K., “Three-dimensional place and route for FPGAs”, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on Vol. 25, Issue 6, June 2006 Page(s):1132 – 1140.
[2] Ababei, C., Mogal, H., and Bazargan, K., “Synthesis for FPGAs: Three-dimensional place and route for FPGAs”, Jan 2005 ASP-DAC '05, Page(s):773 - 778 .
[3] Kuo-Hsing Cheng and Shun-Wen Cheng, “A study on the relationship between initial node-edge pairs entropy and mincut circuit partitioning”, Electronics, Circuits and Systems, 2001. ICECS 2001. Vol. 2, 2-5 Sept. 2001 page(s): 889 – 893.
[4] Kuo-Hsing Cheng and Shun-Wen Cheng, “ENISLE: an intuitive heuristic nearly optimal solution for mincut and ratio mincut partitioning”, Circuits and Systems, ISCAS 2001. Vol. 5, 6-9 May 2001 Page(s):167 - 170.
[5] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multi-level hypergraph partitioning: Applications in VLSI design”, in Proc. ACM/IEEE Design Automation Conf. (DAC), Anaheim, CA, 1997, pp. 526-529.
[6] S. H. Gerez, Algorithm for VLSI Design Automation. John Wiley & Sons, 1999.
[7] C.M. Fiduccia and R.M. Mattheyses, “A linear-time Heuristic for improving network partitions”, Proc. ACM/IEEE Design Automation Conf, pp. 175-181, 1982.
[8] M. Garey and S. Johnson, “Computer and Intractability: A Guide to the Theory of NP-completeness”, Freeman, 1979.
[9] B. W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs”, Bell Syst. Tech. J., vol. 49, no. 2, pp. 291-307, Feb. 1970.
[10] S. Kirkpatrick, C. D. Gelatt and M. P. Wecchi, “Optimization by Simulated Annealing”, Science, 1983, pp. 671-780.
[11] C. J. Alpert and A. B. Kahng, “Recent Directions in Netlist Partitioning: A Survey,” INTEGRATION, the VLSI Journal, 1995, pp. 1-81.
[12] A. B. Kahng, “Futures for Partitioning in Physical Design”, Proc. International Symp. on Physical Design, 1998, pp. 190-193.
[13] C. Kring and A. R. Newton. “A Cell-Replicating Approach to Mincut-Based Circuit Partitioning”. Proc. International Conf. on Computer-Aided Design, 1991, pp. 2-5.

[14] L. Hagen and A. B. Kahng, “Fast Spectral Methods for Ratio Cut Partitioning and Clustering”, Proc. International Conf. on Computer-Aided Design, 1991, pp. 10-13.
[15] R. Kuznar, F. Brglez and B. Zajc, “Multi-way Netlist Partitioning into Heterogeneous FPGAs and Minimization of Total Device Cost and Interconnect”, Proc. Design Automation Conf., 1994, pp. 238-243.
[16] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel Hypergraph Partitioning: Application in VLSI Domain”, Proc. Design Automation Conf., 1997, pp. 526-529.
[17] Alpert, C.J., Hagen, L.W., Kahng, A.B., "A hybrid multilevel/genetic approach for circuit partitioning", Proceedings of IEEE Asia Pacific Conference on Circuits and Systems '96, pp. 298-301, 1996
[18] Sait, S.M., El-Maleh, A.H., Al-Abaji, R.H., "Simulated evolution algorithm for multiobjective VLSI netlist bi-partitioning", Circuits and Systems, pp. 459-460, 2003.
[19] S. Dutt and W. Deng, “A probability-based approach to VLSI circuit partitioning”, In ACM/IEEE DAC, 1996, Page(s):100 - 105
[20] S. Dutt and W. Deng, “VLSI circuit partitioning by cluster-removal using iterative improvement techniques”, In Proc. Physical Design Workshop, 1996, Page(s):194 - 200
[21] Bruce Hendrickson and Robert Leland, “A multilevel algorithm for partitioning graphs”, Technical Report SAND93-1301, Sandia National Laboratories, 1993, Page(s):28
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top