(3.226.72.118) 您好!臺灣時間:2021/05/13 06:57
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林明勳
研究生(外文):Ming-Shiun Lin
論文名稱:使用動態加鎖及節點複製技巧改進具複雜資源限制之二重最小切電路分割
論文名稱(外文):Improved Two-Way Min-Cut Circuit Partitioning with Complex Resource Constraints Using Dynamic Locking and Node Replication Techniques
指導教授:王廷基
指導教授(外文):Ting-Chi Wang
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:43
中文關鍵詞:電路分割現場可程式閘陣列超大型積體電路
外文關鍵詞:VLSIFPGAcircuit partitioning
相關次數:
  • 被引用被引用:0
  • 點閱點閱:74
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
電路分割在不同階級的超大型積體電路設計中,一直扮演著非常重要的角色。它的主要目的是利用電路中各元件相互連接的資訊來對已知電路求得一個分割解,以讓隨後的設計流程能更順暢。Liu, Zhu及Wong等人[18]提出一個稱為“具複雜資源限制的FPGA二重最小切分割問題”,此問題所探討的FPGA晶片內包含有多種不同的資源型態,每一種資源型態可以實現電路中一種或數種不同型態的基本元件,同時每一基本元件可以被一種或數種不同的資源來實現。給定一個已知的電路G以及兩個資源的集合R1與R2,此分割問題是要將所給定的已知電路G分割成兩個子電路V1及V2,使得介於V1及V2兩者之間被切到的線路總數越小越好,同時V1中所有的基本元件都必須能被R1中的資源所實現,且V2中所有的基本元件也都能被R2中的資源所實現。
為了解決具複雜資源限制之二重最小切分割問題,在本論文中我們研究如何利用動態加鎖和節點複製等技巧,以降低子電路間互連訊號線,並得到下列三項具體成果:
(1)我們將[18]中所採用的FFC-fm演算法之加鎖方式予以動態化,改進分割品質達8.07%至75.22%。
(2)我們研發一個節點複製的演算法,改進[18]之分割品質達23.05%至83.57%。
(3)最後我們將所提的動態加鎖及節點複製兩個方法結合在一起,改進[18]之分割結果達35.67%至99.39%。

Circuit partitioning has played a very important role at different levels of VLSI design. Recently, a new circuit partitioning problem, called two-way min-cut partitioning for FPGAs with complex resources, was addressed by Liu, Zhu and Wong [18]. For this type of FPGAs, multiple types of resources are contained. Each resource type has multiple choices to implement a basic cell in the circuit, and each basic cell also has multiple choices to be implemented by a resource type. Given a circuit G and two resource sets R1 and R2, the two-way min-cut partitioning problem with complex resource constraints is to partition G into two subcircuits V1 and V2 such that the total number of cut nets between V1 and V2 is as small as possible, subject to the constraints that the nodes in V1 can be implemented by the resources in R1, and V2 can be implemented by the resources in R2.
To solve the problem, we study in this thesis how to apply the dynamic locking and node replication techniques to improve a given initial partitioning, respectively. In particular, we have obtained the following three significant and encouraging results:
(1)We have modified the FFC-fm algorithm [18] by using the dynamic locking scheme. The experimental results show that this modification generated better cut size quality than the FFC-fm algorithm by 8.07%~75.22%.
(2)We have developed an efficient algorithm for node replication. The experimental results show that using the solution generated by the FFC-fm algorithm as the initial solution, the replication algorithm could further reduce the cut size quality by 23.05%~83.57%.
(3)Finally, we combined both dynamic locking and node replication, and the experimental results show that the cut size could be improved by 35.67%~99.39% as compared to the FFC-fm algorithm.

摘要______________________________________________________1
Abstract___________________________________________________2
第一章序論____________________________________________6
第二章問題描述_______________________________________11
第三章回顧___________________________________________13
第四章動態加鎖演算法_________________________________24
第五章節點複製演算法_________________________________30
第六章實驗結果_______________________________________34
第七章結論___________________________________________37
參考文獻_________________________________________________38

[1]Actel FPGA Data Book and Design Guide, Actel Corporation, 1996.[2]Actel’s Reprogrammable SPGAs, Preliminary Advance Information, Actel Corporation, October 1996.[3]C. J. Alpert and A. B. Kahng, “Recent Directions in Netlist Partitioning: A Survey,” INTEGRATION, the VLSI Journal, 1995, pp. 1-81.[4]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.[5]W.-J. Fang and A. C.-H. Wu, “Multi-Way FPGA Partitioning by Fully Exploiting Design Hierarchy”, Proc. Design Automation Conf., 1997, pp. 518-521.[6]C. M. Fiduccia and R. M. Mattheyses, ”A Linear-time Heuristic for Improving Network Partitions”, Proc. Design Automation Conf., 1982, pp. 175-181.[7]J. R. Ford and D. F. Fulkerson, Flows in Networks, Princeton University Press, 1962.[8]M. Garey and S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.[9]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.[10]A. G. Hoffmann, “The Dynamic Locking Heuristic — A New Graph Partitioning Algorithm”, Proc. International Symp. on Circuit and Systems, 1994, pp. 173-176.[11]J. Hwang and A. El Gamal, “Min-Cut Replication in Partitioned Networks,” IEEE Trans. on Computer-Aided Design, Jan. 1995, pp. 96-106.[12]A. B. Kahng, “Futures for Partitioning in Physical Design”, Proc. International Symp. on Physical Design, 1998, pp. 190-193.[13]B. W. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs,” Bell System Tech. Journal, 1970, pp. 291-307.[14]S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing”, Science, 1983, pp. 671-780.[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]H.-C. Lee and T.-C. Wang, “Feasible Two-Way Circuit Partitioning with Complex Resource Constraints”, Proc. Aisa and South Pacific Design Automation Conf., 2000, pp. 435-440.[18]H. Liu, K. Zhu and D.F. Wong, “Circuit Partitioning with Complex Resource Constraints in FPGAs”, Proc. FPGA, 1998, pp. 77-84.[19]H. Yang and D. F. Wong, “Efficient Network Flow Based Min-Cut Balanced Partitioning”, Proc. International Conf. on Computer-Aided Design, 1994, pp. 50-55.[20]H. Yang and D.F. Wong, “New Algorithm for Min-Cut Replication in Partitioned Circuits”, Proc. International Conf. on Computer-Aided Design, 1995, pp. 216-222.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔