跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:劉聖宏
研究生(外文):Sheng-Hong Liu
論文名稱:同時考慮線長與位移量最小化之擺置合法化
論文名稱(外文):Placement Legalization with Simultaneous Wirelength and Displacement Minimization
指導教授:曾新穆曾新穆引用關係何宗易
指導教授(外文):Vincent S. TsengTsung-Yi Ho
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:43
中文關鍵詞:叢集合法化位移線長
外文關鍵詞:LegalizationClusteringCADWirelengthDisplacement
相關次數:
  • 被引用被引用:0
  • 點閱點閱:133
  • 評分評分:
  • 下載下載:22
  • 收藏至我的研究室書目清單書目收藏:0
近年來,積體電路電腦輔助設計軟體隨著積體電路工業而越來越發達,擺置合法化是積體電路電腦輔助設計軟體中極為重要的部分。擺置合法化將電路元件擺在合法的位置。目前文獻上的擺置合法化方法通常只以位移量為考慮的準則,但卻有可能擺出線長過長的擺置結果。也因為管理空白空間的機制不好,導致執行效率不好。為此,合法化必須同時考慮到位移量與線長,並要有一套管理空白空間的機制。本論文中,提出了一套管理空白空間的機制,階層式地分群rows以建立索引,並藉由合理地計算出cell對每一群rows的距離以及修改深度優先搜尋的方式來搜尋,以達成縮小搜尋範圍的加速功能。在尋找空白空間時也同時考慮了位移量與線長。至於Cell擺入row中的方法,我們改進了Abacus [27]的公式,改為尋找中位數,也為此提出了更有效率的試擺方法。最後,藉由實作文獻上其他方法與本論文所提的方法,在2005年及2006年ACM ISPD擺置比賽用的電路上[30]進行合法化的動作,證明本論文之方法能有效率地獲得品質不錯的合法化結果。
In recent years, a number of studies have been done on Computer-Aided Design (CAD) for IC design. Legalization is one of important issues on CAD. The existed methods for legalization usually try to minimize the total displacements of cells. However, consideration of total displacements only may lead to the problem that wirelength is too large. Another critical problem is the row management, which may influence the efficiency of legalization. Therefore, the legalization must simultaneously consider the displacement and the wirelength, as well as the good row searching management. In this paper, we propose a novel clustering-based mechanism for row searching management. At first, a row index structure is established to search the best row by using recursive clustering algorithms. Then, we propose a method for trial placement to find the position of the cell on the row. Finally, all the cells would be inserted into their corresponding best rows. To evaluate our proposed method, we use ACM ISPD 2005 and 2006 placement contest benchmarks [30] as experimental data. Experimental results show that our proposed method can efficiently obtain high-quality results.
摘要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vii
1 導論 1
1.1 研究背景 1
1.2 研究動機 4
1.3 問題描述 5
1.4 研究貢獻 7
1.5 論文架構 7
2 文獻討論 8
2.1 合法化的相關方法(Legalization) 8
2.2 Row base的合法化(Legalization) 8
2.2.1 考慮HPWL為主的合法化 9
2.2.2 考慮位移為主的合法化 11
2.3 資料探勘方法 14
2.3.1 叢集方法 14
2.3.2 分割式的叢集方法 15
2.3.3 K-means 15
2.3.4 K-medoid 16
3 研究方法 17
3.1 LSWDM架構 17
3.2 資料格式 18
3.3 LSWDM之演算法 19
3.3.1 虛擬碼 20
3.3.2 為rows編索引 21
3.3.3 尋找best row 22
3.3.4 排序cells 25
3.3.5 把cell排入row中 25
3.3.6 尋找中位數 27
4 實驗分析 32
4.1 實驗資料 32
4.2 位移量的比較 33
4.3 HPWL的比較 35
4.4 執行時間的比較 36
4.5 實驗結論 38
5 結論 39
5.1 研究結論 39
5.2 未來發展 39
5.3 應用 40
參考文獻 41
[1]Ameya Agnihorti, Mehmet Can Yildiz, Ateen Khatkhate, Ajita Mathur, Satoshi Ono, and Patrick H. Madden, “Fractional cut: Improved recursive bisection placement,” Proc. ICCAD, pp. 307-310, 2003.
[2]Ulrich Brenner and Jens Vygen, “Legalizing a placement with minimum total movement,” IEEE TCAD, 23(12):1597-1613, Dec.2004.
[3]Ulrich Brenner and Markus Struzyna, “Faster and better global placement by a new transportation algorithm,” Proc. DAC, pp. 591-596, 2005.
[4]Tony Chan, Jason Cong, Kento Sze, and Min Xie, “mPL6: Enhanced multilevel mixed-size placement,” Proc. ISPD, pp. 212-214, 2006.
[5]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
[6]Yao-Wen Chang, Jai-Ming Lin, “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,” Proc. DAC, pp.764-769, 2001
[7]Tung-Chieh Chen and Yao-Wen Chang, “Modern Floorplanning Based on Fast Simulated Annealing,” Proc. ISPD I, pp.104-112, 2005
[8]Tung.Chieh. Chen, Zhe.Wei. Jiang, Tien.Chang. Hsu, Hsin.Chen. Chen, and Yao.Wen. Chang, “NTUplace3:A high-quality mixed-size analytical placer considering preplaced blocks and density constraints,” Proc. ICCAD, pp. 187-192, 2006.
[9]Konrad Doll, Frank M. Johannes, and Kurt J. Antreich, “Iterative placement improvement by network flow methods,” IEEE TCAD, 13(10):1189-1200, Oct. 1994.
[10] J. A. Hartigan and M. A. Wong, “A K-Means Clustering Algorithm,” Proc. Applied Statistics, Vol. 28, No. 1, p100-108.
[11]Dwight Hill, “Method and system for high speed detailed placement of cells within integrated circuit designs,” U.S. Patent 6370673, Apr. 2002.
[12]Sung-Woo Hur and John Lillis, “Mongrel: Hybrid techniques for standard cell placement,” Proc. ICCAD, pp. 165-170, 2000.
[13]Andrew B. Kahng, Paul Tucker and Alex Zelikovsky, “Optimization of Linear Placements for Wirelength Minimization with Free Sites,” Proc. Asia and South Pacific Design Automation Conference 1999 (ASP-DAC'99), pp. 241-244, 1999.
[14]Andrew B. Kahng, Igor L. Markov, and Sherief Reda, “On legalization of row-based placements,” Proc. GLS-VLSI, pp. 214-219, 2004.
[15]Andrew B. Kahng and Qinke Wang, “Implementation and extensibility of an
analytic placer,” IEEE TCAD, 24(05):734-747, May 2005.
[16]Jai-Ming Lin and Yao-Wen Chang, “TCG-S: orthogonal coupling of P*-admissible representations for general floorplans,” Proc. DAC, pp.842-847, 2002
[17]Jai-Ming Lin, Yao-Wen Chang, and Shih-Ping Lin, “Corner sequence - a P-admissible floorplan representation with a worst case linear-time packing scheme,” Proc. TVLSI, pp. 679- 686, Aug. 2003
[18]Carlos B. Lucasius, Adrie D. Dane, and Gerrit Kateman, “On k-medoid clustering of large data sets with the aid of a genetic algorithm: background, feasibility andcomparison,” Analytica Chimica Acta, vol. 282, no3, pp. 647-669, 1993.
[19]Tao Luo, Haoxing Ren, Charles J. Alpert, and David Z. Pan, “Computational geometry based placement migration,” Proc. DAC, pp. 41-47, 2007.
[20]Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake, and Yoji Kajitani, “Rectangle-packing-based module placement,” Proc. ICCAD, pp.472 - 479 ,1995
[21]Min Pan, Natarajan Viswanathan, and Chris Chu, “An efficient and effective detailed placement algorithm,” Proc. ICCAD, pp. 48-55, 2005.
[22]Haoxing Ren, David Z. Pan, Charles J. Alpert, and Paul Villarrubia, “Diffusion-
based placement migration,” Proc. DAC, pp. 515- 520, 2005.
[23]Jarrod A. Roy, David A. Papa, Saurabh N. Adya, Haward H. Chan, Aaron N. Ng, James F. Lu, and Igor L. Markov, “Capo: Robust and scalable open-source min-cut floorplacer,” Proc. ISPD, pp. 224- 226, 2005.
[24]T. Ohtsuki, N. Sugiyama, and H. Kawanishi, “An optimization technique for integrated circuit layout design,” Proc. ICCST-Kyoto, pp. 67-68, Sept. t970.
[25]M. Sarrafzadeh and M. Wang,“ NRG: Global and detailed placement,” Proc. ICCAD, pp. 532-537, 1997.
[26]Peter Spindler and Frank M. Johannes, “Fast and robust quadratic placement combined with an exact linear net model,” Proc. ICCAD, pp. 179-186, 2006.
[27]Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes, “Abacus: Fast legalization of standard cell circuits with minimal movement,” Proc. ISPD, pp. 47-53, 2008.
[28]T. C. Wang and D. F. Wong, “Optimal floorplan area optimization,” IEEE Trans. Computer-Aided Design,11 (1992), 992–1002.
[29]D. F. Wong and C. L. Liu, “A new algorithm for floorplan design,” Proc. ACM/IEEE Design Automation Conference, pp. 101-107, 1986.
[30]http://www.ispd.cc/
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top