請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33526
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Tien-Chang Hsu | en |
dc.contributor.author | 許天彰 | zh_TW |
dc.date.accessioned | 2021-06-13T04:45:27Z | - |
dc.date.available | 2007-07-14 | |
dc.date.copyright | 2006-07-20 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-07-17 | |
dc.identifier.citation | [1] ISPD 2006 Program. http://www.ispd.cc/program.html.
[2] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, and I. L. Markov, “Unification of partitioning, placement and floorplanning,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.550– 557, 2004. [3] S. N. Adya and I. L. Markov, “Consistent placement of macro-blocks using floorplanning and standard-cell placement,” in Proceedings of ACM International Symposium on Physical Design, pp.12–17, 2002. [4] A. R. Agnihotri, S. Ono, P. H. Madden, “Recursive bisection placement: Feng Shui 5.0 implementation details,” in Proceedings of ACM International Symposium on Physical Design, pp.230–232, 2005. [5] A. R. Agnihotri, S. Ono, C. Li, M. C. Yildiz, A. Khatkhate, C.-K. Koh, and P. H. Madden, “Mixed block placement via fractional cut recursive bisection,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(5):748–761, 2005. [6] S. B. Akers, “On the use of the linear assignment algorithm in module placement,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 137–144, 1981. [7] U. Brenner, A. Pauli, and J. Vygen, “Almost optimum placement legalization by minimum cost flow and dynamic programming,” in Proceedings of ACM International Symposium on Physical Design, pp.2–9, 2004. [8] A. E. Caldwell, A. B. Kahng, and I. L. Markov, “Optimal partitioners and end-case placers for standard-cell layout,” IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 19(11):1304–1313, 2000. [9] H. W. Carter, M. A. Breuer, and Z. A. Syed, “Incremental processing applied to steinberg’s placement procedure,” in Proceedings of ACM/IEEE Design Automation Conference, pp.26–31, 1979. [10] T. Chan, J. Cong, and K. Sze, “Multilevel generalized force-directed method for circuit placement,” in Proceedings of ACM International Symposium on Physical Design, pp.185–192, 2005. [11] K. Doll, F. M. Johannes, and K. Antreich, “Iterative placement improvement by network flow methods,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(10):1189–1200, 1994. [12] S. Goto, “An efficient algorithm for the two–dimensional placement problem in electrical circuit layout,” IEEE Transactions on Circuits and Systems, 28(1):12–18, 1981. [13] L. K. Grover, “A new simulated annealing algorithm for standard cell placement,” in Proceedings of IEEE/ACM International Conference on Computer- Aided Design, pp.378–380, 1986. [14] B. Hu, Y. Zeng, and M. M. Sadowska, “mFAR: fixed-points-addition-based VLSI placement algorithm,” in Proceedings of ACM International Symposium on Physical Design, pp.239–241, 2005. [15] S.-W. Hur and J. Lillis, “Mongrel: Hybrid techniques for standard cell placement,” in Proceedings of IEEE/ACM International Conference on Computer- Aided Design, pp.165–170, 2000. [16] Z.-W. Jiang, T.-C. Chen, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTUplace2: A hybrid placer using partitioning and analytical techniques,” in Proceedings of ACM International Symposium on Physical Design, pp.215– 217, 2006. [17] R. Jonker and A. Volgenant, “A shortest augmenting path algorithm for dense and sparse linear assignment problems,” Computing, 38(4):325–340, 1987. [18] A. B. Kahng, I. L. Markov, and S. Reda, “On legalization of row-based placements,” in Proceedings of IEEE Great Lake Symposium on VLSI, pp.214– 219, 2004. [19] A. B. Kahng, S. Reda, and Q. Wang, “Architecture and details of a high quality, large-scale analytical placer,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.890–897, 2005. [20] A. B. Kahng, P. Tucker, and A. Zelikovsky, “Optimization of linear placements for wirelength minimization with free sites,” in Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference, pp.241–244, 1999. [21] A. B. Kahng and Q. Wang, “A faster implementation of APlace,” in Proceedings of ACM International Symposium on Physical Design, pp.218–220, 2006. [22] C. Li, M. Xie, C.-K. Koh, J. Cong, and P. H. Madden, “Routability-driven placement and white space allocation,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.394–401, 2004. [23] G.-J. Nam, C. J. Alpert, P. Villarrubia, B. Winter, and M. Yildiz, “The ISPD2005 placement contest and benchmark suite,” in Proceedings of ACM International Symposium on Physical Design, pp.216–220, 2005. [24] G. J. Nam, C. J. Aplert, and P. G. Villarrubia, “The ISPD 2006 placement contest and benchmark suite,” in Slides presented at ACM International Symposium on Physical Design, 2006. [25] B. Obermeier, H. Ranke and F. M. Johannes, “Kraftwerk: a versatile placement approach,” in Proceedings of ACM International Symposium on Physical Design, pp.242–244, 2005. [26] M. Pan, N. Viswanathan, and C. Chu, “An efficient and effective detailed placement algorithm,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.48–55, 2005. [27] M. Sarrafzadeh and M. Wang, “NRG: global and detailed placement,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.532–537, 1997. [28] N. A. Sherwani, “Algorithms for VLSI Physcial Design Automation,” Kluwer Academic Publishers, Norwell, MA, USA, 1998. [29] A. Srinivasan, K. Chaudhary, and E. S. Kuh, “Ritual: Performance driven placement algorithm for small cell ics,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.48–51, 1991. [30] L. Steinberg, “The backboard wiring problem: A placement algorithm,” SIAM Review, 3:37–50, 1961. [31] W.-J. Sun and C. Sechen, “Efficient and effective placement for very large circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14(3):349–359, 1995. [32] T. Taghavi, X. Yang, B.-K. Choi, M. Wang, and M. Sarrafzadeh, “Dragon2006: Blockage-aware congestion-controlling mixed-size placer,” in Proceedings of ACM International Symposium on Physical Design, pp.209– 211, 2006. [33] N. Viswanathan, M. Pan, and C. Chu, “FastPlace 2.0: An efficient analytical placer for mixed-mode designs,” in Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference, pp.195–200, 2006. [34] M. Wang, X. Yang, and M. Sarrafzadeh, “Dragon2000: standard-cell placement tool for large industry circuits,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp.260–263, 2000. [35] X. Yang , B.-K. Choi, and M. Sarrafzadeh, “Routability-driven white space allocation for fixed-die standard-cell placement,” in Proceedings of ACM International Symposium on Physical Design, pp.42–47, 2002. [36] B. Yao, H. Chen, C.-K. Cheng, N.-C. Chou, L.-T. Liu, and P. Suaris, “Unified quadratic programming approach for mixed mode placement,” in Proceedings of ACM International Symposium on Physical Design, pp.193–199, 2005. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33526 | - |
dc.description.abstract | 近代高效能積體電路設計需要大量預留空間以利於後續效能最佳化,因此在擺置階段的元件擺置密度控制益發重要。有鑑於現有的細部擺置演算法往往為了縮減連線長度而大幅破壞原本的密度控制,在此篇論文中,我們提出一個能夠縮短連線長度同時保留元件密度分佈的細部擺置演算法。我們的方法包括能夠同時擺置大量元件的元件匹配技術、提高效能的窗格掃掠技術、以及漸近改善擺置密度分佈的元件滑動技術。根據實驗,我們的程式在考慮連線長度與擺置密度的擺置品質優於APlace2.0與FastPlace2.0的細部擺置程式達到4.9%與6.7%。而在僅考慮連線長度的擺置品質估計上也以0.3%、0.7%的幅度領先。實驗結果證明我們的演算法能夠在保留原本的元件擺置密度分佈的前提下,達到當今學術界細部擺置器的連線長度水平。 | zh_TW |
dc.description.abstract | A modern circuit placement algorithm consists of three steps: global placement, legalization, and detailed placement. Global placement finds rough positions of the circuit blocks, legalization removes the overlaps, and detailed placement refines the result. Modern high-performance IC designs integrate millions of blocks in a single chip. Traditional detailed placement methods consider only local cells and thus cannot handle modern large-scale designs well. It is therefore desirable to develop a better detailed placement algorithm with a more global view. Most detailed placement algorithms focus on the wirelength reduction, but the density control in the placement step becomes more important due to the increasing white space in modern designs for further performance optimization. We present a detailed placement algorithm that can minimize the wirelength and preserve the density controlled by the global placement. We adopt three major techniques in our detailed placement algorithm: (1) a cell matching technique to rearrange a group of cells simultaneously, (2) a window sweeping method to enhance the window-based local refinement by perturbing the window size and sweep direction, and (3) a cell sliding technique to gradually slide cells out of density overflow regions. Experimental results show that our algorithm achieves high-quality placement results. For the new cost metric which considers the wirelength and density constraints, our algorithm is 4.9% and 6.7% better than the state-of-the-art results from the APlace 2.0 and FastPlace 2.0, respectively. Our resulting HPWL is still 0.3% and 0.7% shorter than the above detailed placers. The results show that our algorithm can preserve the density controlled by the global placement and our wirelength improvement is still quite competitive with other state-of-the-art detailed placers. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T04:45:27Z (GMT). No. of bitstreams: 1 ntu-95-R93943030-1.pdf: 1247013 bytes, checksum: 6c1a6e67d6020d4372dd93050eaf3093 (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | Abstract (Chinese) i
Abstract ii Acknowledgements iv List of Tables vii List of Figures ix Chapter 1. Introduction 1 1.1 Design and Construction of an Integrated Circuit . . . . . . . . . . . . . 1 1.2 VLSI Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Global Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Legalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Detailed Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Importance of Detailed Placement . . . . . . . . . . . . . . . . . . . . . . 6 1.4 PreviousWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.1 Greedy Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.2 Domino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.3 Optimal Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.4 White Space Distribution . . . . . . . . . . . . . . . . . . . . . . . 11 1.4.5 GlobalMoving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Organization of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 2. Preliminaries 15 2.1 A VLSI Placement Instance . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.1 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.2 Pins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.4 Placement Region . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.5 Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Wirelength and NetModel . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 DensityModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 ProblemFormulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chapter 3. The Detailed Placement Algorithm 21 3.1 AlgorithmOverview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 CellMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 CellMatching Technique . . . . . . . . . . . . . . . . . . . . . . . 24 3.2.2 NetModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 Window SweepingMethod . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4 Cell Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.5 Cell Sliding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chapter 4. Experimental Results 40 4.1 ISPD’05 Placement Contest Benchmarks . . . . . . . . . . . . . . . . . . 41 4.2 ISPD’06 Placement Contest Benchmarks . . . . . . . . . . . . . . . . . . 43 4.3 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Chapter 5. Conclusion and Future Work 54 Bibliography 56 | |
dc.language.iso | en | |
dc.title | 應用於超大型積體電路擺置系統之細部擺置演算法 | zh_TW |
dc.title | A Detailed Placement Algorithm for Large-Scale VLSI Circuits | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 林永隆(Youn-Long Lin),王廷基(Ting-Chi Wang),陳宏明(Hung-Ming Chen) | |
dc.subject.keyword | 擺置,細部擺置, | zh_TW |
dc.subject.keyword | placement,detailed placement, | en |
dc.relation.page | 60 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-07-18 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 1.22 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。