跳到主要內容

臺灣博碩士論文加值系統

(3.236.124.56) 您好!臺灣時間:2021/07/30 06:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:洪勗
研究生(外文):Hsi Hung
論文名稱:統一使用凸面最佳化演算法來處理固定框架之平面規劃並能考量先行擺置之區塊
論文名稱(外文):UFO: Unified Convex Optimization Algorithms for Fixed-Outline Floorplanning with Pre-placed Constraint
指導教授:林家民林家民引用關係
指導教授(外文):Jai-Ming Lin
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:41
中文關鍵詞:固定框架平面規劃最佳化
外文關鍵詞:OptimizationFloorplanningFixed-outline
相關次數:
  • 被引用被引用:0
  • 點閱點閱:115
  • 評分評分:
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
考量固定大小框架面積之平面規劃為目前實體設計中必需考量之因素; 除此之外,在晶片上經常擺放著某些已經先行擺置之區塊,因此為了得到一個可用的平面規劃結果,一個好的平面規劃工具必需能同時滿足這些條件,這使得平面規劃的問題變得越來越困難。在這本碩士論文中,我們第一個提出能在固定框架平面規劃之中考量先行擺置區塊之方法,並且分別於全域分佈規劃和局部合理化統一使用凸面最佳化演算法以解決這個問題。在第一階段全域分佈規劃中,我們提出了一推拉模型(Push-Pull Model)將模組均勻分散在固定區域內並且同時減少整體之繞線長度;而在第二階段中,我們則會根據所得到模組之位置並利用Delaunary三角化方法,來擷取模組間之相對位置以建立出拓樸關係限制圖,以限制模組間能不相互重疊,最後再根據一個二次函數附加以固定邊界之限制,來決定區塊確實之位置與形狀。根據實驗的結果顯示,我們的方法在考慮了更複雜的設計限制條件下,仍能得到比目前文獻更佳之結果。
Fixed-outline floorplanning has attracted more attention for the real requirement in current IC design flow. In addition, there may exist several pre-placed modules in the specified region. In order to get a feasible foorplan, a floorplanner should have the ability to consider these constraints, which makes foorplanning a more difficult problem. In this thesis, we propose a it first work to consider pre-placed modules in a fixed-outline floorplan. Two-stages unified convex optimization methods, called UFO, are used in a global distribution and a local legalization stages, respectively. In the first stage, a pull-push model is used to distribute modules over a fixed outline under the wirelength consideration. In the second stage, the geometrical relations between modules are extracted by applying the Delaunay triangulation method on the result of the first stage. Then, a quadratic function as well as the constraint graphs are used to determine the locations and shapes of modules so that no module overlaps and all modules are in the outline. Experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC benchmarks.
Chinese Abstract i
Abstract iii
List of Tables vii
List of Figures viii
Chapter 1. Introduction 1
1.1 Previous Work. . . 2
1.2 Our Contribution . . . 5
Chapter 2. Problem Formulation 8
Chapter 3. Global Distribution Stage 10
3.1 Review of Attractor-Repeller (AR) Model. . . 10
3.1.1 Pull-Push Model . . . 12
3.2 Convex Property . . . 15
Chapter 4. Local Legalization Stage 19
4.1 Constraint Graph Construction . . . 19
4.2 QOPL : Quadratic Optimization Programming for Legalization . . 21
4.3 Hierarchical UFO Flow. . . 23
Chapter 5. Floorplanning with Pre-Placed Modules 27
Chapter 6. Experimental Results 30
6.1 Fixed-Outline Floorplanning with Zero Dead Space. . . 30
6.2 Fixed-Outline Floorplanning with Pre-placed Modules. . . 34
Chapter 7. Conclusion 37
Bibliography 38
[1] S. N. Adya and I. L. Markov. “Fixed-outline floorplanning: enabling hierarchical design.” IEEE TVLSI, Vol.11, No.6, pages 1120-1135, 2003.
[2] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa and I. L. Markov.“Unification of partitioning, placement and floorplanning.” In Proc. of ICCAD, pages 550-557, 2004.
[3] M. F. Anjos and A. Vannelli. “A new mathematical-programming frame-work for facility-layout design.” INFORMS Journal on Computing, Vol.18, No.1, pages 111-118, 2006.
[4] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu. “B*-trees: A new representation for non-slicing floorplans.” In Proc. of DAC, pages 458-463, 2000.
[5] T.-C. Chen, Y.-W. Chang and S.-C. Lin. “IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs.” In Proc. of ICCAD, pages 159-164, 2005.
[6] T. Chen and Y. W. Chang. “Modern floorplanning based on B*-tree and fast simulated annealing.” IEEE TCAD, Vol. 25, No. 4, pages 637-650, 2006.
[7] S. Chen and T. Yoshimura. “A stable fixed-Outline floorplanning method.” In Proc. ISPD, pages 119-126, 2007.
[8] Edwin K. P. Chong and Stanislaw H. ZAK. “An Introduction to Optimization.”John Wiley & Sons, Inc., second edition, 2001.
[9] J. Cong, M. Romesis, and J. Shinnerl. “Fast floorplanning by look ahead enabled recursive bipartitioning.” IEEE TCAD., Vol. 25, No. 9, pages
1719-1732, Sep. 2006.
[10] J. Cong, G. Nataneli, M. Romesis, and J. Shinnerl. “An area-optimality study of floorplanning.” In Proc. of ISPD, pages 78-83, 2004.
[11] Yan Feng, Dinesh P. Mehta , Hannah Yang. “Constrained modern floorplanning.” In Proc. of ISPD, pages 128-135, 2003.
[12] Yan Feng and Dinesh P. Mehta. “Constrained floorplanning using network flows.” IEEE TCAD, Vol. 23, No.4, APRIL 2004.
[13] P.-N. Guo, C.-K. Cheng, and T. Yoshimura. “An O-Tree representation of non-slicing floorplan and its applications.” In Proc. of DAC, pages 268-273, 1999.
[14] O. He, S. Dong, J. Bian, S. Goto, C.-K. Chen. “A novel fixed-outlined floorplanner with zero dead space for hierarcical design.” In Proc. of ICCAD, pages 16-23, 2008.
[15] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu.“Corner Block List: An effective and efficient topological representation of non-slicing floorplan.” In Proc. of ICCAD, pages 8-12, 2000.
[16] H. Itoga, C. Kodama and K. Fujuyoshi. “A Graph Based Soft Module Handling in Floorplan.”IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E88-A No.12, pages 3390-3397, 2005.
[17] L. Jin, D. Kim, L. Mu, D.-S. Kim and S.-M. Hu. “A sweepline algorithm for Euclidean Voronoi diagram of circules.” IEEE TCAD, Vol. 38, pages 260-272, 2006.
[18] A. B. Kahng. “Classical floorplanning harmful?” In Proc. of ISPD, pages 207-213, 2000.
[19] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.”Optimization by simulated annealing.” Science, vol. 220, no. 4598, pages 671-680, 1983.
[20] C. Lin, D. Chen and Y. Wang. “Robust fixed-outline floorplanning through evolutionary search.” In Proc. of ASP-DAC, pages 42-44, 2004.
[21] J.-M Lin and Y.-W Chang. “TCG: A transitive closure graph-based representation for non-slicing floorplans.” In Proc. of DAC, pages 764-769, 2001.
[22] Chaomin Luo, Miguel F. Anjos, Anthony Vannelli. “Large-scale fixed-outline floorplanning design using convex optimization Techniques.” In Proc. of ASP-DAC, pages 198-203, 2008.
[23] R. Liu, S. Dong, X. Hong and Y. Kajitani. “Fixed-outline floorplanning with constraints through instance augmentation.” In Proc. of ISCAS, pages 1883-1886, 2005
[24] C. Lin, H. Zhou and C. C. N. Chu. “A Revisit to Floorplan Optimization by Lagrangian Relaxation.” In Proc. of ICCAD, pages 164-171, 2006.
[25] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. “Rectangle-packing based module placement.” In Proc. of ICCAD, pages 472-479, Nov, 1995.
[26] T.-S. Moh, T.-S. Chang and S. L. Hakimi. “Globally optimal floorplanning for a layout problem.”IEEE TCS, Vol.43, No.9, pages 713-720,1996.
[27] S. Nakatake, K. Fujiyoshi, H. Murata, and Y.Kajitani. “Module placement on BSG-structure and IC layout applications.” In Proc. of ICCAD, pages 484-491, 1996.
[28] R.H.J.M. Otten. “Automatic floorplan design.” In Proc. of DAC, pages 261-267, June 1982.
[29] D. F. Wong, and C.-L. Liu. “A new algorithm for floorplan design.” In Proc. of DAC, pages 101-107, June 1986.
[30] Jackey Z. Yan and Chris Chu. “DeFer: Deferred decision making enabled fixed-outline floorplanner.” In Proc. of DAC, pages 161-166, June 2008.
[31] H. Zhou and J. Wang., “Acg. adjacent constraint graph for general floorplans,” In Proc. of ICCD, pp. 572-575, 2004.
[32] Y. Zhan, Y. Feng and S. Sapatnekar. “A fixed-die floorplanning algorithm using an analytical approach." In Proc. of ASP-DAC, pages 771-776, 2006.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊