跳到主要內容

臺灣博碩士論文加值系統

(44.201.97.0) 您好!臺灣時間:2024/04/14 04:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:吳宗祐
研究生(外文):Wu, Tsung-You
論文名稱:具備最小干擾於標準元件下的電路快速合法化方法
論文名稱(外文):FastLegalize: Legalization for Standard Cell Based Design with Minimal Disturbance
指導教授:李育民李育民引用關係
指導教授(外文):Lee, Yu-Min
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電信工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
畢業學年度:97
語文別:英文
論文頁數:44
中文關鍵詞:合法化實體設計超大型積體電路擺置
外文關鍵詞:legalizationphysical designVLSIplacement
相關次數:
  • 被引用被引用:0
  • 點閱點閱:209
  • 評分評分:
  • 下載下載:11
  • 收藏至我的研究室書目清單書目收藏:0
隨著製程進入奈米時代,現今的積體電路中有著數以百萬計的可移動標準元件(standard cell)與固定單元(fixed macros)。在做電路合法化時為了維持原有的全域擺置結果,在晶片上標準元件的移動量必須要最小化。因此在這一篇論文中我們提出了一個有效將電路中標準元件移動量達到最小化的方法。
為了能夠有效限制標準元件的移動量,首先將晶片切割成每一個大小都相同的格子,然後從密度最大的格子開始做合法化。由於密度太大的格子裡的空間不足給標準元件做合法化,因此必須嘗試合併周圍的格子直到它的密度小於臨界值,在這�塈畯抴ㄔX兩種結構以有效的去合法化電路。
合併後的格子開始透過我們有效的方法去做合法化,所提出的方法可同時維持在全域擺置結果的特性與最小化移動距離。為了能夠改進效能,在合法化的過程中每個標準元件都會隨時做擺置上的更新。直到所有的格子都做完合法化後即結束。
與最新的研究結果“Abacus”比較後,我們所提出的方法可減少平均48%的移動量,最大的移動量可減少140%,此外,執行上的速度有將近1.11倍的提升。實驗結果證明我們的方法可以獲得一個好的合法化電路。
An efficient legalization approach is necessary for the integrated circuit design which consists of millions of movable standard cells and fixed macros. To maintain the global placement result, the disturbance of cells must be minimized. In this work, a fast legalization placer, FastLegalize, is developed to legalize standard cells with minimal movement.
First, a chip is divided into several bins with equal size to limit the movable scope of cells. Then, starting with the most crowed unlegalized bin, a merging procedure for bins is used to integrate bins into a cross-shaped bin-merged structure or a square-shaped bin-merged structure until the cell density in that bin-merged structure is less than a defined threshold. After that, an efficient legalization method which simultaneously preserves the ordering in each row and minimizes the sum of absolute movement distances is developed to legalize cells in that bin-merged structure. To improve the legalization quality, the proposed legalization method refreshes the positions of legalized cells during legalization. Finally, the above legalizing procedure is repeated until all cells are non-overlapped.
Compared with the state-of-the-art method, Abacus, FastLegalize can reduce the total movement of cells to be 48% in average, and save the largest movement of cells to be 140% in average. Moreover, FastLegalize can obtain average 1.11X runtime speed up.
1 Introduction 1
1.1 Design Flow of an Integrated Circuit . . . 1
1.2 Motivation . . . 2
1.3 Our Features . . . 3
1.4 Organization of the Thesis . . . 4
2 Preliminary and Literature Overview 5
2.1 Physical Design . . . 5
2.2 Basic Concept of Placement . . . 6
2.2.1 Standard Cells . . . 7
2.2.2 Fixed Blocks . . . 8
2.3 Cost Function to Legalization . . . 8
2.4 Literature Survey of Legalization . . . 9
3 The Legalization Approach for Standard Cell Based Design with Minimal Disturbance 11
3.1 Legalization . . . 11
3.2 Overview of the Approach . . . 12
3.3 Pre-Work and Bin Merged Procedure . . . 13
3.4 Legalization Framework. . . 16
3.5 Legalization Core (LegCore) . . . 17
3.5.1 Collapse . . . 20
3.5.2 Optimal Position of Cells . . . 21
3.5.3 Cost Function . . . 21
3.6 The Optimal Position for Clusters by Sum of Absolute Distances Solver (SADS) 23
3.7 Runtime Complexity Analysis of FastLegalize Approach . . . 28
4 Experimental Results 30
5 Conclusion 40
[1] International Symposium on Physical Design 2005 placement contest.
http://www.sigda.org/ispd2005/contest.htm, April 2005.
[2] Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes. Abacus: Fast legalization of standard cell circuits with minimal movement. In Proceedings ACM/SIGDA International Symposium on Physical Design, pages 47–53, April 2008.
[3] Paul Villarrubia. Important placement considerations for modern vlsi chips. In Proceedings ACM/SIGDA International Symposium on Physical Design, pages 6–6, 2003.
[4] Tung-Chieh Chen, Zhe-Wei Jiang, Tien-Chang Hsu, Hsin-Chen Chen, and Yao-Wen Chang. Ntuplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(7):1228–1240, July 2008.
[5] Natarajan Viswanathan, Min Pan, and Chris Chu. Fastplace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control. In Proceedings Asia and South Pacific Design Automation Conference, pages 135–140, January 2007.
[6] Tao Luo and David Z. Pan. Dplace2.0: A stable and efficient analytical placement based on diffusion. In Proceedings Asia and South Pacific Design Automation Conference, pages 346–351, 2008.
[7] Dwight Hill. Method and system for high speed detailed placement of cells within an integrated circuit design. U.S. Patent 6370673, April 2002.
[8] Chen Li, Min Xie, Cheng-Kok Koh, Jason Cong, and Patrick H. Madden. Routabilitydriven placement and white space allocation. IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems, 26(5):858–871, May 2007.
[9] Ateen Khatkhate, Chen Li, Ameya R. Agnihotri, Mehmet C. Yildiz, Satoshi Ono, Cheng-Kok Koh, and Patrick H. Madden. Recursive bisection based mixed block placement. In Proceedings ACM/SIGDA International Symposium on Physical Design, pages 84–89, 2004.
[10] Andrew B. Kahng and Qinke Wang. Implementation and extensibility of an analytic placer. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(5):734–747, May 2005.
[11] Chen Li and Cheng-Kok Koh. On improving recursive bipartitioning-based placement. Technical Report TR-ECE 03-14, Purdue University, December 2003.
[12] Jason Cong and Min Xie. A robust detailed placement for mixed-size ic design. In Proceedings Asia and South Pacific Design Automation Conference, pages 188–194, 2006.
[13] Haoxing Ren, David Z. Pan, Charles J. Alpert, Paul G. Villarrubia, and Gi-Joon Nam. Diffusion-based placement migration with application on legalization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26(12):2158–2172, December 2007.
[14] Tao Luo, Haoxing Ren, Charles J. Alpert, and David Z. Pan. Computational geometry based placement migration. In Proceedings ACM/IEEE Design Automation Conference, pages 41–47, 2007.
[15] Carl Sechen and Alberto Sangiovanni-Vincentelli. Timberwolf 3.2: A new standard cell placement and global routing package. In Proceedings ACM/IEEE Design Automation
Conference, pages 432–439, 1986.
[16] Jason Cong and Min Xie. Dragon2000: Standard-cell placement tool for large industry circuits. In Proceedings IEEE/ACM International Conference on Computer-Aided Design,
pages 260–263, 2000.
[17] M. Sarrafzadeh and M. Wang. Nrg: Global and detailed placement. In Proceedings IEEE/ACM International Conference on Computer-Aided Design, pages 532–537, 1997.
[18] Min Pan, Natarajan Viswanathan, and Chris Chu. An efficient and effective detailed placement algorithm. In Proceedings IEEE/ACM International Conference on Computer-Aided Design, pages 48–55, 2005.
[19] Ulrich Brenner, Anna Pauli, and Jens Vygen. Almost optimum placement legalization by minimum cost flow and dynamic programming. In Proceedings ACM/SIGDA International
Symposium on Physical design, pages 2–9, 2004.
[20] Ulrich Brenner and Jens Vygen. Legalizing a placement with minimum total movement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23(12):1597–1613, December 2004.
[21] Andrew B. Kahng, Paul Tucker, and Alex Zelikovsky. Optimization of linear placements for wirelength minimization with free sites. In Proceedings Asia and South Pacific Design Automation Conference, pages 241–244, 1999.
[22] Ulrich Brenner and Jens Vygen. Faster optimal single-row placement with fixed ordering. In Proceedings Design Automation and Test in Europe, pages 117–121, 2000.
[23] Ameya Agnihotri, Mehmet Can Yildiz, Ateen Khatkhate, Ajita Mathur, Satoshi Ono, and Patrick H. Madden. Fractional cut: Improved recursive bisection placement. In Proceedings International Conference on Computer Aided Design, pages 307–310, November 2003.
[24] Andrew B. Kahng, Igor L. Markov, and Sherief Reda. On legalization of row-based placements. In Great Lakes Symposium on VLSI, pages 214–219, 2004.
[25] Sung-Woo Hur and John Lillis. Mongrel: Hybrid techniques for standard cell placement. In Proceedings IEEE/ACM International Conference on Computer-Aided Design, pages 165–170, 2000.
[26] Konrad Doll, Frank M. Johannes, and Kurt J. Antreich. Iterative placement improvement by network flow methods. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(10):1189–1200, October 1994.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊