臺灣博碩士論文加值系統

隨著積體電路製程的演進，最小線寬(feature size)的微小化，單一晶片上有數以百萬的標準元件(standard cell)以及智慧產權(Intellectual Property,簡稱 IP)模組或巨集模組塊(macro block)，使得超大型積體電路擺置(placement)的問題愈趨於複雜。然而一個合法的擺置必須所有元件之間沒有交疊並且所有的標準元件須對齊至列上；因此在積體電路設計中，擺置的合法化(legalization)為一個重要的環節。
此篇論文主要對已發表的合法化方法HiBinLegalizer，證明其所提出的位置解法器可得的最佳移動量，此外我們也提出數個定理改進搜尋列的尋找中位數的時間複雜度。由於HiBinLegalizer是一個階層式的方法，亦為將晶片分割成許多大小相同的單元格，並且透過每一個單元格的密度資訊，決定是否合併其他單元格一同納入合法化。對擺置合法化而言，分割晶片，除了可以增進執行速度，還可限制每一個標準元件的最大移動量以及減少列的搜索次數。然而初始的總單元格數量及單元格的長寬比會影響後續合併及最終結果的效能(移動量和執行時間)，因此本篇提出如何利用巨集模組塊的長寬比和最大合併區域內的標準單元個數，決定單元格長寬比以及決定總格數的範圍，最後合併兩者資訊找出好的分割網格尺寸，以取捨執行時間和最小移動量。

With semiconductor fabrication technology developing, millions of standard cells and macros (pre-designed blocks or intellectual property (IP)) are integrated into a single chip. Legalization procedure is part of placement design in physical design automation. For a legal placement, all elements (cells and macros) are non-overlapping and all cells must be aligns to row. In this paper, we based on a method, HiBinLegalizer, which was published in ASPDAC-2010, proposed the grid bin size refinement and proved the solver for the objective function is optimal solution. The grid bin size refinement use the aspect ratio of macros to obtain the aspect ratio of grid and use the number of cells in maximum merged-bin to determine the bin size for HiBinLegalizer. Moreover, we proposed some lemmas to improve the procedure of trial row in HiBinLegalizer, so that, the order of time complexity is O(1) as compared with the original O(n) . The experimental results demonstrate the effectiveness of our method.

目錄
第一章 導論 1
第1.1節 背景簡介 1
第1.2節 研究貢獻 3
第二章 背景與相關文獻簡介 4
第2.1節 標準單元的擺置合法化 4
第2.2節 擺置合法化相關文獻 5
第2.3節 概述HiBinLegalizer的架構 6
第三章 對HiBinLegalizer之最小擾動的最佳化分析以及網格數的精化 12
第3.1節 交疊連續性 12
第3.2節 部分交疊連續性 17
第3.3節 改善HiBinLegalizer尋找中位數的過程 24
第3.4節 網格數的精化 29
第四章 實驗結果 33
第五章 結論 36
附錄 40

[1] Yu-Min Lee, Tsung-YouWu, and Po-Yi Chiang. A hierarchical bin-based legalizer for standard-cell designs with minimal disturbance. In Design Automation Conference
(ASP-DAC), 2010 15th Asia and South Pacic, pages 568-573, Jan. 2010.
[2] Carl Sechen William Swartz. Timing driven placement for large standard cell circuits. In Design Automation, 1995. DAC '95. 32nd Conference on, pages 211-215, 1995.
[3] A.B. Kahng and Q. Wang. An analytic placer for mixed-size placement and timing-driven placement. In Computer Aided Design, 2004. ICCAD-2004. IEEE/ACM International Conference on, pages 565-572, nov. 2004.
[4] Chen Li, Min Xie, Cheng-Kok Koh, J. Cong, and P.H. Madden. Routability-driven placement and white space allocation. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 26(5):858-871, may 2007.
[5] Xiaojian Yang, Bo-Kyung Choi, and M. Sarrafzadeh.
Routability-driven white space allocation for xed-die standard-cell placement. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 22(4):410-419, apr 2003.
[6] Yongseok Cheon, Pei-Hsin Ho, A.B. Kahng, S. Reda, and Qinke Wang. Power-aware placement. In Design Automation Conference, 2005. Proceedings. 42nd, pages 795-800, june 2005.
[7] Kimiyoshi Usami and Mark Horowitz. Clustered voltage scaling technique for low-power design. In Proceedings of the 1995 international symposium on Low power design, ISLPED '95, pages 3{8, New York, NY, USA, 1995. ACM.
[8] U. Brenner and J. Vygen. Legalizing a placement with minimum total movement. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 23(12):1597-1613, dec. 2004.
[9] 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.
[10] Andrew B. Kahng. On legalization of row-based placements. In in Proceedings 14th Great Lakes Symposium on VLSI, pages 214-219, 2004.
[11] Dwight Hill. Method and system for high speed detailed placement of cells within an integrated circuit design. U.S. Patent 6370673, April 2002.
[12] 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.
[13] Tsung-Yi Ho and Sheng-Hung Liu. Fast legalization for standard cell placement with simultaneous wirelength and displacement minimization. In VLSI System on Chip Conference (VLSI-SoC), 2010 18th IEEE/IFIP, pages 369-374, Sept. 2010.
[14] Andrew B. Kahng, Sherief Reda, and Qinke Wang. Architecture and details of high quality large-scale analytical placer. In Proceedings Asia and South Pacic Design Automation Conference, pages 890{897, 2005.
[15] 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.
[16] Tao Luo and David Z. Pan. Dplace2.0: A stable and ecient analytical placement based on diusion. In Proceedings Asia and South Pacic Design Automation Con-
ference, pages 346-351, 2008.
[17] Stanislaw H. Z_ ak Edwin Kah Pin Chong. An Introduction to Optimization. Wiley-Interscience, 3rd edition, 2008.
[18] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliord Stein. Introduction to Algorithms. The MIT Press, Cambridge, MA, USA, 2nd edition,
2001.