(3.239.192.241) 您好!臺灣時間:2021/03/02 13:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:傅文佑
研究生(外文):Wen-Yu Fu
論文名稱:多階段階層式平面規劃
論文名稱(外文):Multistage Hierarchical Floorplanning
指導教授:謝財明謝財明引用關係
指導教授(外文):Tsai-Ming Hsieh
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:66
中文關鍵詞:模組置放連線總長度內接連線平面規劃階層式面積最小化
外文關鍵詞:interconnectionarea minimizationtotal wirelengthmodule placementfloorplanninghierarchical approach
相關次數:
  • 被引用被引用:0
  • 點閱點閱:147
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
隨著製程技術進入深次微米後,電路連線上的延遲效應愈來愈明顯。在考量電路的效能與穩定度時,如何有效降低連線上的延遲已成為當前的重要課題。平面規劃階段決定模組的擺放位置,因此會直接影響晶片上模組間的連線及晶片面積。
傳統平面規劃與模組置放問題之研究,大多於提出各種模組間關係位置之表示法後,再利用模擬退火演算法以單一階段(one stage)方式求解。求解的過程中,解的接受與否是由目標函數 所決定,其中A為該解的晶片面積大小,而W為晶片上模組間連線長度預估值之總和。此類方法在同時考慮面積最小化及連線最小化時,如何決定目標函數中的權重係數 , …值,使最後得到的解能在面積最佳化上與連線最佳化上取得很好效果卻是非常困難的。
本論文提出一個多階段 (multiple stage) 處理之平面規劃方法,不只使連線最小化並能同時有效降低晶片面積。在第一階段中本計劃將以模組間訊號連線為考量,求得一初始平面規劃;第二階段是根據前一階段所得之平面規劃,在不大幅更動原模組擺置相對位置之前提下,以階層式方法進行面積最小化。
實驗結果顯示,我們的演算法可以很有效率的使連線總長最小化並能同時有效降低晶片面積。
As the process technology enter the deep sub-micron era, the delay effect caused by the interconnection is more and more obvious. Today, how to reduce the interconnection delay effectively has become an important subject when we consider the performance and stability of circuits. Because the position of each module is decided during floorplanning, the overall interconnection delay among modules can be calculated from the result of floorplanning.
To solve floorplanning and module placement problems, most of the previous researches attempted to provide placement representations and used the single stage approach based on the simulated annealing algorithm. During the annealing process, the solution will be accepted or not is decided by the objective functions such as where A is the final chip size and W is the total wirelength. The one stage approach based on SA is powerful and can find satisfied solutions for the single optimized objective. However, when we consider the multiple optimization goals on both area and total wirelength at the same time, it is very difficult to find the balanced point for deciding the weighted cofactors , …and so on.
We propose a project to develop a multiple stage floorplanning algorithm that can minimize not only the total interconnection wirelength but also the chip area. In the first stage, we propose an algorithm to find an initial floorplan according the interconnection relation of signals among modules. In the second stage, we will develop a hierarchical area minimization algorithm that can premise the module topology generated by the first stage will not be modified violently. And we will introduce the module partition concept of in the second stage to further improve the solution for the area minimization.
目 錄 1
第一章 前言 2
第二章 平面規劃之相關研究 4
2.1 相關之研究 4
2.2 研究動機 19
第三章 問題描述與定義 21
第四章多階段階層式平面規劃演算法 22
4.1 訊號連線總長的估計方式 23
4.2 數學規劃模型 26
4.3 模組訊號連線為導向之演算法 30
4.3 階層式面積最小化之演算法 45
第五章 實驗結果 55
5.1 實驗平台 55
5.2 實驗流程 56
5.3 實驗結果 59
第六章 結論及未來展望 61
參考文獻 62
作 者 簡 介 66
[1]Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu and Shu-Wei Wu, “B*-trees: a new representation for non-slicing floorplans,” Proc. DAC, pp. 458-463, 2000.[2]T. Chen and M. K. H. Fan.,“On Convex Formulation of the Floorplan Area Minimization Problem,” Proc. ISPD, pp. 124-128, Apr. 1998. [3]Hung-Ming Chen, Hai Zhou, F.Y. Young, D.F. Wong, H.H. Yang and N. Sherwani, “Integrated floorplanning and interconnect planning,” Proc. ICCAD, pp. 354-357, 1999.[4]Jason Cong, Tianming Kong and D.Z. Pan “Buffer block planning for interconnect-driven floorplanning,” Proc. ICCAD, pp. 358 —363, 1999.[5]W. Dai, L. Wu and S. Zhang, on http://www.cse.ucsc.edu/research/surf/GSRC/results/MCNC,2001.[6]P.-N. Guo, C.-K. Cheng and T. Yoshimura, “An O-Tree Representation of Non-Slicing Floorplan and Its Application,” Proc. DAC, pp. 268-273, 1999.[7]Pei-Ning Guo, T. Takahashi, Chung-Kuan Cheng and T. Yoshimura “Floorplanning using a tree representation,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.20, No.2, pp. 281-289,Feb 2001.[8]Xianlong Hong, Sheqin Dong, Gang Huang, Yuchun Ma, Yici Cai, Chung-Kuan Cheng, Jun Gu, “A non-slicing floorplanning algorithm using corner block list topological representation,” IEEE APCCAS, pp. 833-836, 2000.[9]D.P. Lapotin and S.W. Director, “A global floor-planning tool,” Proc. ICCAD, pp. 143-145, 1985.[10]S.-C. Lee, J.-M. Hsu, and Y.-W. Chang, “Multilevel large-scale module placement/floorplanning using B*-trees,” in Proceedings of The 12th VLSI Design/CAD Symposium, Hsinchu, Taiwan, Aug. 2001.[11]Chih-Hung Lee, Yu-Chung Lin, Wen-Yu Fu, Chung-Chiao Chang, Tsai-Ming Hsieh, “A New Formulation for SOC Floorplan Area Minimization Problem” to appear in Proc. of ACM/IEEE Design Automation and Test in Europe (DATE-2002), Paris, France, March 2002.[12]T. Lengauer and R. Muller ,“Robust and accurate hierarchical floorplanning with integrated global wiring,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.12, No.6, pp. 802-809,June 1993.[13]J.-M Lin and Y.-W Chang, “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,” Proc. DAC, pp.764-769, 2001. [14]J.-M. Lin, S.-P. Lin, and Y.-W. Chang, “A P-admissible non-slicing floorplan representation with a worst-case linear-time packing scheme,” in Proceedings of The 12th VLSI Design/CAD Symposium, Hsinchu, Taiwan, Aug. 2001.[15]T.S. Moh, T.S. Chang, and S.L. Hakimi. “Globally optimal floorplanning for a layout problem”. IEEE Trans. on Circuit and Systems - I: Fundamental Theory and Applications, Vol. 43: pp.713—720, Sep. 1996.[16]H. Murata and E.S. Kuh, “Sequence-Pair Based Placement Method for Hard/Soft/Pre-placed Modules”. Proc. ISPD, pp. 167—172, Apr. 1998.[17]H. Murata, K. Fujiyoshi, S.Nakatake and Y.Kajitani, “Rectangle-Packing-Based Module Placement,” Proc. ICCAD, pp. 472-479, 1995.[18]S. Nakatake, K. Fujiyoshi, H. Murata and Y.Kajitani, “Module Placement on BSG-Structure and IC Layout Applications,” Proc. ICCAD, pp. 484-491, 1996.[19]Shigetoshi NAKATAKE, Yukiko KUBO and Yoji KAJITANI, “Consistent Floorplanning with Super Hierarchical Constraints” Proc. ISPD, pp. 144-149, 2001.[20]T. Ohmura, K. Fujiyoshi and C. Kodama, “Area optimization of packing represented by sequence-pair,” Proc. APCCAS, pp. 813 -816, 2000.[21]M. Ohmura, S. Wakabayashi, Y. Toyohara, J. Miyao and N. Yoshida, “Hierarchical floorplanning and detailed global routing with routing-based partitioning,” Proc. ISCAS, vol.2, pp.1640-1643, 1990.[22]R.H.J.M. Otten, “Automatic floorplan design,” Proc. DAC, pp. 261-267,1982.[23]M. Pedram and B. Preas, “A hierarchical floorplanning approach,” Proc. ICCD, pp. 332-338, 1990.[24]A. Ranjan, K. Bazargan, and M. Sarrafzadeh, “Floorplanner 1000 Times Faster: A Good Predictor and Constructor,” In System Level Interconnect Prediction, pp. 115-120, 1999.[25]A. Ranjan, K. Bazargan, S. Ogrenci, and M. Sarrafzadeh, “Fast Floorplanning for Effective Prediction and Constructor,” IEEE Transactions on VLSI System, Vol.9,No.2, pp. 341-351,April 2001.[26]A. Rnjan, K. Bazargan and M. Sarrafzadeh, “Fast hierarchical floorplanning with congestion and timing control,” Proc. ICCD, pp. 357-362, 2000.[27]E. Rosenberg, “Optimal Module Sizing in VLSI Floorplanning by Non-linear Programming,” Methods Models Operations Res., Vol. 33, pp. 131-143, 1989.[28]Y. Takashima and H. Murata, “SLASH: a deterministic block placement algorithm based on sequence-pair,” Proc. APCCAS, pp. 825 —828, 2000.[29]Xiaoping Tang, Ruiqi Tian and D.F. Wong, “Fast evaluation of sequence pair in block placement by longest common subsequence computation,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.20, No.12, pp. 1406-1413,Dec 2001.[30]Ting-Chi Wang and D.F. Wong, “Efficient Shape Curve Construction in Floorplan Design,” Proc. EDAC, pp. 356-360,1991.[31]S. Wimer. I. Koren, and J Cederbaum, “ Floorplans, planar graphs, and layouts,” IEEE Trans, Circuits Syst., Vol. 35, pp. 267-278, Mar. 1988.[32]D.F. Wong and K.-S. The “An algorithm for hierarchical floorplan design,” Proc. ICCAD, pp. 484-487, 1989.[33]D.F. Wong and C.L. Lin, “A New Algorithm for Floorplan Design,” Proc. DAC, pp. 101-107,1986.[34]G.-M. Wu, Y.-C. Chang, and Y.-W. Chang, “Rectilinear Block placement Using B*-Trees,” Proc. ICCD, pp. 351-356, Austin, TX, Oct. 2000.[35]J. Xu, P.-N. Guo, and C.-K. Cheng, “Rectilinear Block Placement Using Sequence-Pair,” Proc. ISPD, pp. 173-178, 1998.[36]F.Y. Young and D.F. Wong, “How good are slicing floorplans,” Integration VLSI J. vol. 23, pp. 61-73, 1997.[37]F.Y. Young, D.F. Wong, and Hannah H. Yang “Slicing Floorplans with Range Constraint,” IEEE Transactions on CAD of Integrated Circuits and Systems, Vol. 19, NO. 2, February, pp. 272-278,2000.[38]F.Y. Young, Chris C.N. Chu, W.S. Luk and Y.C. Wong. “Floorplan Area Minimization using Lagrangian Relaxation”. Proc. ISPD, San Diego, CA., pp.174-179,2000.[39]F.Y. Young, C.C.N. Chu, W.S. Luk and Y.C. Wong “Handling soft modules in general nonslicing floorplan using Lagrangian relaxation,” IEEE Trans. On Comp. Aided Design of IC’s and System, Vol.20, No.5, pp. 687-692,May 2001.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔