請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78034
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Chin-Hao Chang | en |
dc.contributor.author | 張晉豪 | zh_TW |
dc.date.accessioned | 2021-07-11T14:40:15Z | - |
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] Cadence Inc., http://www.cadence.com/.
[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] 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. ACM, 2005. [4] T. F. Chan, J. Cong, J. R. 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.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-Trees: A new representation for non-slicing floorplans,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 458–463, 2000. [6] H.-C. Chen, Y.-L. Chuang, Y.-W. Chang, and Y.-C. Chang, “Constraint graph- based macro placement for modern mixed-size circuit designs,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 218–223, 2008. [7] T.-C. Chen and Y.-W. Chang, “Modern floorplanning based on B*-Tree and fast simulated annealing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 4, pp. 637-650, April 2006. [8] T.-C. Chen, Y.-W. Chang, and S.-C. Lin, “A new multilevel framework for large-scale interconnect-driven floorplanning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 2, pp. 286-294, 2008. [9] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, 'NTUplace3: An analytical placer for large-scale mixed-size designs with pre-placed blocks and density constraints,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 7, pp. 1228-1240, July 2008. [10] 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. [11] 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. [12] C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, 'Circular-contour-based obstacle-aware macro placement,' in Proceedings of ACM/IEEE Asia South Pacifi c Design Automation Conference, pp. 172-177. IEEE, 2016. [13] J. Cong and M. Xie, 'A robust mixed-size legalization and detailed placement algorithm,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 8, pp. 1349-1362, August 2008. [14] D. Hill, 'Method and system for high speed detailed placement of cells within an integrated circuit design,' U.S. Patent 6,370,673, 2002. [15] M.-K. Hsu and Y.-W. Chang, 'Uni ed analytical global placement for large-scale mixed-size circuit designs,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 9, pp. 1366-1378, September 2012. [16] 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. [17] 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. [18] S. Kirkpatrick, C. D. Gelatt, and M. Vecchi, Optimization by simulated annealing,' Science, vol. 220, no. 4598, pp. 671-680, May 1983. [19] H.-C. Lee, Y.-W. Chang, J.-M. Hsu, and H. H. Yang, 'Multilevel floorplanning/placement for large-scale modules using B*-trees,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 812-817. ACM, 2003. [20] J.-M. Lin and Y.-W. Chang, 'TCG: A transitive closure graph-based representation for non-slicing floorplans,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 764-769, 2001. [21] 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,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 5, pp. 685-698, January 2015. [22] M. D. Moffi tt, A. N. Ng, I. L. Markov, and M. E. Pollack, 'Constraint-driven floorplan repair,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 1103-1108, 2006. [23] 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/78034 | - |
dc.description.abstract | 隨著奈米積體電路技術發展的日新月異,現代化的系統單晶片的設計複雜度也快速增加。因此,對於當今晶片設計來說,一個有效率的設計流程架構是不可或缺的。在本篇論文中,我們提出了「基於阻尼波的建構式多階層架構」(以下簡稱D-wave),在巨集電路擺置使用這個架構,可幫助我們放置巨集電路以同時達到線長與可繞度的最佳化。不同於傳統的V-型與Ʌ-型的多階層架構,可能導致在處理程序中缺乏局部或全面的個別考量,我們的基於阻尼波的多層次架構藉由下列兩個主要的技術,達到了兼顧局部及全面的資訊考量:(1)一個為改善規模可伸縮性的巨集電路群集演算法,以及 (2) 在一個建構性的機制下反群集巨集電路,以獲得線長與可繞度的最佳化。
此外,在近來提出的三種混合尺寸電路的擺置演算法之中,三階段的布局流程是當前業界最受歡迎的演算法,因為其易被整合進現存的設計流程當中。然而,傳統的混合尺寸擺置器僅考慮擺置原型中標準單元的位置,而忽略了原型與最終擺置結果的差異,此一缺陷也在我們的架構中被修正。為了修正這個缺陷,我們提出一個巨集電路分群的概念,以更精確地估計巨集電路擺置結果的品質。實驗結果證實,相較於業界的人工手動擺置以及學術界最先進的混合尺寸擺置器,我們的基於阻尼波的多階層架構可以在更短的處理時間內達到最好的擺置品質。 | zh_TW |
dc.description.abstract | As nanometer integrated circuit technologies improve, the design complexity of modern system-on-a-chip is growing rapidly. Therefore, the efficient methodology of a tool is essential for modern chip designs. In this thesis, we present a damped-wave (called D-wave) constructive multilevel framework for macro placement which packs big macros to optimize both wirelength and routability simultaneously. Unlike traditional V-shaped and Ʌ-shaped multilevel frameworks which might lack respective local and global information during processing, our D-wave framework considers both local and global information by the following two major techniques: (1) a macro clustering algorithm to improve scalability, and (2) declustering macros under a constructive scheme to obtain better wirelength and routing congestion.
Besides, among three types of recently proposed mixed-size placement algorithms, the three-stage approach is the most popular in industry, because it is easy to be integrated into the existing design flow. However, traditional mixed-size placers consider the locations of standard cells in the prototype alone, but ignore the difference between the prototype and the final placement result, which is also remedied by our framework. We present a concept of macro grouping to evaluate a macro placement result more accurately. Compared to manual placement results provided by industrial and leading mixed-size placers, experimental results show that our D-wave framework can achieve the shortest routed wire length in shorter runtime. | en |
dc.description.provenance | Made available in DSpace on 2021-07-11T14:40:15Z (GMT). No. of bitstreams: 1 ntu-105-R03921039-1.pdf: 1508442 bytes, checksum: 0ba14cb3d8a1c96dfa44be208effb177 (MD5) Previous issue date: 2016 | en |
dc.description.tableofcontents | Acknowledgements iii
Abstract (Chinese) iv Abstract vi List of Tables x List of Figures xi Chapter 1. Introduction 1 1.1 Introduction to Mixed-Size Placement . . . . . . . . . . . . . . . . . . . 1 1.1.1 One-stage Mixed-Dize Placement . . . . . . . . . . . . . . . . . . 2 1.1.2 Constructive Mixed-Size Placement . . . . . . . . . . . . . . . . . 3 1.1.3 Three-Stage Mixed-Size Placement . . . . . . . . . . . . . . . . . 3 1.2 Introduction to Multilevel Framework . . . . . . . . . . . . . . . . . . . 6 1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Some Diculties in Three-Stage Approaches . . . . . . . . . . . . . . . . 11 1.5 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Chapter 2. Preliminaries 16 2.1 Circular-Contour-Based Obstacle-Aware Macro Placement . . . . . . . . 16 2.2 Simulated Annealing Algorithm . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 B*-Tree Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Chapter 3. Damped-Wave Based Constructive Multilevel Framework 23 3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Combination of B*-tree and Extension of Corner Sequence . . . . . . . . 26 3.3 Simulated Annealing Optimization . . . . . . . . . . . . . . . . . . . . . . 26 3.4 Macro Grouping Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.5 Convexity Penalty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6 Damped-Wave Multilevel Framework . . . . . . . . . . . . . . . . . . . . 34 3.6.1 Constructive Mechanism . . . . . . . . . . . . . . . . . . . . . . . 34 3.6.2 Clustering Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.6.3 Declustering Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chapter 4. Experimental Results 38 4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2 Experimental Results and Comparisons . . . . . . . . . . . . . . . . . . . 41 Chapter 5. Conclusions and Future Work 49 Bibliography 52 Publication List 56 | |
dc.language.iso | en | |
dc.title | 基於阻尼波針對混合尺寸電路設計之巨集電路擺置 | zh_TW |
dc.title | Damped-Wave Based Macro Placement for 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,Macro Placement,Multilevel Framework, | en |
dc.relation.page | 56 | |
dc.identifier.doi | 10.6342/NTU201700016 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2017-01-05 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-R03921039-1.pdf 目前未授權公開取用 | 1.47 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。