請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78035
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Szu-To Chen | en |
dc.contributor.author | 陳思鐸 | zh_TW |
dc.date.accessioned | 2021-07-11T14:40:17Z | - |
dc.date.available | 2022-02-21 | |
dc.date.copyright | 2017-02-21 | |
dc.date.issued | 2016 | |
dc.date.submitted | 2017-01-05 | |
dc.identifier.citation | [1] ICCAD 2012 Placement Contest, http://cad contest.cs.nctu.edu.tw/CAD-contest-at-ICCAD2012/.
[2] ISPD 2007 Routing Contest, http://www.sigda.org/ispd2007/contest.html. [3] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, and I. L. Markov, 'Uni cation of partitioning, placement and oorplanning,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 550--557, 2004. [4] T. F. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie, 'mPL6: Enhanced multilevel mixed-size placement,' in Proceedings of ACM International Symposium on Physical Design, pp. 212--214, 2006. [5] Y.-W. Chang, Z.-W. Jiang, and T.-C. Chen, Essential issues in analytical placement algorithms,' IPSJ Transactions on System LSI Design Methodology, vol. 2, pp. 145--166, August 2009. [6] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, 'NTU-place3: 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, vol. 27, no. 7, pp. 1228--1240, Jul. 2008. [7] T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, 'MP-trees: A packing-based macro placement algorithm for modern mixed-size designs,'IEEE transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 9, pp. 1621--1634, September 2008. [8] Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, 'Routability-driven blockage-aware macro placement,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 1--6, 2014. [9] C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, 'Circular-contour-based obstacle-aware macro placement,' in Proceedings of IEEE/ACM Asia and South Pacifi c Design Automation Conference, pp. 172--177, 2016. [10] J. Cong and M. Xie, 'A robust mixed-size legalization and detailed placement algorithm,' IEEE Transactions on Computer-Aided Design of Integrated Cir- cuits and Systems, vol. 27, no. 8, pp. 1349--1362, August 2008. [11] R. C. Gonzales and R. E. Woods, Digital Image Processing. Addison-Wesley, 1992. [12] X. He, T. Huang, W.-K. Chow, J. Kuang, K.-C. Lam, W. Cai, and E. F. Y. Young, 'Ripple2.0: High quality routability-driven placement via global router integration,' in Proceedings of ACM/IEEE Design Automation Conference, p.152, 2013. [13] X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. F. Y. Young, 'Ripple: An eff ective routability-driven placer by iterative cell movement,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 74--79, 2011. [14] D. Hill, 'US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design,' 2002. [15] M.-K. Hsu and Y.-W. Chang, 'Uni ed analytical global placement for large-scaled mixed-size circuit designs,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 9, 2012. [16] M.-K. Hsu, Y.-W. Chang, and V. Balabanov, 'TSV-aware analytical placement for 3D IC designs,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 664--669, 2011. [17] M.-K. Hsu, Y.-F. Chen, C.-C. Huang, and Y.-W. Chang, 'Routability-driven placement for hierarchical mixed-size circuit designs,' in Proceedings of ACM/IEEE Design Automation Conference, p. 151, Austin, TX, June 2013. [18] J. Hu, J. A. Roy, and I. L. Markov, 'Completing high-quality global routes,' in Proceedings of ACM International Symposium on Physical Design, pp. 35--41,2010. [19] J. Hu, M.-C. Kim, and I. L. Markov, 'Taming the complexity of coordinated place and route,' in Proceedings of ACM/IEEE Design Automation Conference, p. 150, 2013. [20] A. B. Kahng and Q. Wang, 'Implementation and extensibility of an analytic placer,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 5, pp. 734--747, May 2005. [21] M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, and S. Ramji, 'MAPLE: Multilevel adaptive placement for mixed-size designs,' in Proceedings of ACM International Symposium on Physical Design, pp. 193--200, 2012. [22] M.-C. Kim and I. L. Markov, 'ComPLx: A competitive primal-dual lagrange optimization for global placement,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 747--752, 2012. [23] 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. [24] J.-M. Lin, Y.-W. Chang, and S.-P. Lin, 'Corner sequence - A P-admissible floorplan representation with a worst case linear-time packing scheme,' IEEE Transactions on Very Large Scaled Integration Systems, vol. 11, no. 4, pp. 679--686, August 2003. [25] W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao, 'Multi-threaded collision-aware global routing with bounded-length maze routing,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 200--205, 2010. [26] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, and C.-K. Cheng, 'ePlace-MS: Electrostatics-based placement for mixed-size circuits,' vol. 34, no. 5, pp. 685--698, January 2015. [27] W. C. Naylor, R. Donelly, and L. Sha, 'US patent 6,301,693: Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer,' 2001. [28] P. Spindler and F. M. Johannes, 'Fast and accurate routing demand estimation for e ffcient routability-driven placement,' in Proceedings of ACM/IEEE Design, Automation and Test in Europe, pp. 1226--1231, 2007. [29] N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y. Wei, 'ICCAD-2012 CAD contest in design hierarchy aware routability-driven placement and benchmark suite,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 345--348, 2012. [30] N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, G.-J. Nam, and J. A. Roy, The ISPD 2011 routability-driven placement contest and benchmark suite,' in Proceedings of ACM International Symposium on Physical Design, pp. 141--146, 2011. [31] N. Viswanathan, C. J. Alpert, C. Sze, Z. Li, and Y. Wei, 'The DAC 2012 routability-driven placement contest and benchmark suite,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 774--782, 2012. [32] N. Viswanathan, G.-J. Nam, C. J. Alpert, P. Villarrubia, H. Ren, and C. Chu, 'RQL: Global placement via relaxed quadratic spreading and linearization,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 453--458, 2007. [33] J. Z. Yan, N. Viswanathan, and C. Chu, Handling Complexities in modern large-scale mixed-size placement,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 436--441, 2009. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78035 | - |
dc.description.abstract | 隨著預先設計巨集電路在當代晶片中逐漸日增的使用以及其所衍生的高設計複雜度,巨集電路擺置的問題變得相當具挑戰性。大多數巨集電路擺置演算法採用三個階段的擺置:原型擺置、巨集電路擺置及標準元件擺置,其中標準元件的位置在巨集電路擺置後仍被假設在與原型擺置相同,或許這樣的假設會對標準元件擺置產生誤導的資訊。
在本篇論文中,為了降低巨集電路擺置與標準元件擺置之間的落差,我們提出了一個採用同步擴散巨集電路擺置改善的演算法,意即在擴散擺置的同時考慮巨集電路以及標準元件動態位置的資訊以達到改善巨集電路擺置階段的結果。當我們在擴散巨集電路以及標準元件時,我們亦提出了一個力調節的方法用來改善巨集電路擺置的線長以及可繞度。當同步擴散的擺置狀況收斂後,我們也提出了一個感知繞線密集區域的巨集電路偏移器保留更多的擺置空間以考量更好的可繞度。實驗根據兩個不同的巨集電路擺置結果,展現了我們的巨集電路擺置改善演算法能在大型尺寸的混合尺寸電路設計上找到更為優異的擺置結果。 | zh_TW |
dc.description.abstract | With the increasing use of pre-designed macros in a modern chip and its induced high design complexity, macro placement has become a challenging problem. Most popular macro placement algorithms adopt a three-stage approach: placement prototyping, macro placement, and standard-cell placement, where cell positions after macro placement are assumed the same as those at the prototyping stage, possibly incurring misleading information for cell placement.
Therefore, to close the gap between macro and cell placement, we propose a macro-refining algorithm that adopts a technique, called integrated spreading, considering the spreading of both macros and cells to improve macro placement with the dynamic information of cell positions. We further propose a force modulation technique to refine macro placement considering both wirelength and routability when we spread both macros and cells. After the spreading is converged, we present a congested-region aware macro shifter to preserve more space for better routability. Experimental results based on different macro placements show that our macro-refining algorithm can find significantly better placement solutions for large-scale mixed-size circuit designs. | en |
dc.description.provenance | Made available in DSpace on 2021-07-11T14:40:17Z (GMT). No. of bitstreams: 1 ntu-105-R03943095-1.pdf: 3744747 bytes, checksum: 493b0f5cbb93609bd0dc64d729b4dd42 (MD5) Previous issue date: 2016 | en |
dc.description.tableofcontents | Table of Contents
Acknowledgements iii Abstract (Chinese) iv Abstract vi List of Tables x List of Figures xii Chapter 1. Introduction 1 1.1 Introduction to Mixed-Size Placement . . . . . . . . . . . . . . . . . . . 1 1.2 Related Work of Mixed-Size Placement . . . . . . . . . . . . . . . . . . . 2 1.2.1 One-Stage Approach . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Two-Stage Approach . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Three-Stage Approach . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Mixed-Size Placement Benchmarks . . . . . . . . . . . . . . . . . . . . . 8 1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chapter 2. Preliminaries 12 2.1 Problem Formulation of Circuit Placement . . . . . . . . . . . . . . . . . 12 2.2 Analytical Placement Framework . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Wirelength Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.2 Density Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 The Macro-Rening Placement Problem Formulation . . . . . . . . . . . 17 Chapter 3. The Integrated Spreading Macro Placement Algorithm 19 3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Two-Step Cell Size Control . . . . . . . . . . . . . . . . . . . . . . 20 3.1.2 Wire Force Modulation . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1.3 Congested Region Aware Macro Shifting . . . . . . . . . . . . . . . 25 Chapter 4. Experimental Results 28 4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.1.1 Routing Information Extraction . . . . . . . . . . . . . . . . . . . 29 4.1.2 Another Macro Placement Generation . . . . . . . . . . . . . . . . 30 4.2 Experimental Results and Comparisons . . . . . . . . . . . . . . . . . . . 34 4.3 Validation of Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Chapter 5. Conclusions and Future Work 50 Bibliography 52 Publication List 57 | |
dc.language.iso | en | |
dc.title | 基於同步擴散針對大型混合尺寸電路設計之巨集電路擺置 | zh_TW |
dc.title | Integrated Spreading Based Macro Placement for Large-Scale Mixed-Size Circuit Designs | en |
dc.type | Thesis | |
dc.date.schoolyear | 105-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 郭斯彥(Sy-Yen Kuo),陳東傑(Tung-Chieh Chen),方邵云(Shao-Yun Fang) | |
dc.subject.keyword | 實體設計,電路擺置,可繞度,巨集電路擺置, | zh_TW |
dc.subject.keyword | Physical Design,Placement,Routability,Macro Placement, | en |
dc.relation.page | 57 | |
dc.identifier.doi | 10.6342/NTU201700015 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2017-01-05 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-R03943095-1.pdf 目前未授權公開取用 | 3.66 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。