請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/55399
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Chien-Hsiung Chiou | en |
dc.contributor.author | 邱建雄 | zh_TW |
dc.date.accessioned | 2021-06-16T04:00:24Z | - |
dc.date.available | 2019-11-12 | |
dc.date.copyright | 2014-11-12 | |
dc.date.issued | 2014 | |
dc.date.submitted | 2014-11-10 | |
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. 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. [4] 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. [5] 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. [6] 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. [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] 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. [10] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, 'An O-tree representation of non-slicing oorplan and its applications,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 268--273, 1999. [11] D. Hill, 'Method and system for high speed detailed placement of cells within an integrated circuit design,' U.S. Patent 6,370,673, 2002. [12] M.-K. Hsu and Y.-W. Chang, 'Unified 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, Septem-ber 2012. [13] Y.-H. Jiang, J. Lai, and T.-C. Wang, 'Module placement with pre-placed modules using the B*-tree representation,' in Proceedings of IEEE International Symposium on Circuits and Systems, pp. 347--350, 2001. [14] M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, and S. Ramji, 'MAPLE: Multilevel adaptive placement for mixed-size designs,' in Proceed-ings of ACM International Symposium on Physical Design, pp. 193--200, 2012. [15] M.-C. Kim, D.-J. Lee, and I. L. Markov, 'SimPL: An efective placement algorithm,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 1, pp. 50--60, January 2012. [16] 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. [17] S. Kirkpatrick, C. D. Gelatt, and M. Vecchi, 'Optimization by simulated annealing,' Science, vol. 220, no. 4598, pp. 671--680, May 1983. [18] J.-M. Lin and Y.-W. Chang, 'TCG: A transitive closure graph-based representation for non-slicing oorplans,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 764--769, 2001. [19] J.-M. Lin, Y.-W. Chang, and S.-P. Lin, 'Corner sequence---a P-admissible oorplan representation with a worst case linear-time packing scheme,' IEEETransactions on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 4, pp. 679--686, August 2003. [20] J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng, and C.-K. Cheng, 'ePlace: Electrostatics based placement using nesterov's method,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 1--6, 2014. [21] M. D. Moffitt, 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. [22] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, 'VLSI module placement based on rectangle-packing by the sequence-pair,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518--1524, December 1996. [23] E. Wein and J. Benkoski, 'Hard macros will revolutionize SoC design,' EE Times Online, August 2004. [24] J. Z. Yan and C. Chu, 'DeFer: deferred decision making enabled fixed-outline oorplanning algorithm,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 3, pp. 367--381, March 2010. [25] 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/55399 | - |
dc.description.abstract | 由於廣泛地使用矽智財(Intellectual Property)巨集電路,一個現代化的系統單晶片(System-on-a-Chip)通常包含有一定數量的巨集電路。有一些巨集電路因為各種因素,例如功耗以及針角的位置,需要以特定的方向放置在規定的位置,稱之為預先擺置巨集電路。現代的系統單晶片存在著預先擺置巨集電路以及大型巨集電路加深了混合尺寸電路擺置問題的複雜度。現有的文獻中提出的方法可能無法對現代的混合尺寸設計提供合理的擺置。因此在這篇論文中,我們提出了一個三階段的混合尺寸佈局流程,其中包括:(1)擺置原型,(2)巨集電路擺置,和(3)標準單元擺置。巨集電路擺置在整個混合尺寸擺置器中扮演一個關鍵的角色,因此我們專注在這個問題上。我們所提出的巨集電路擺置器同時優化了線長,可繞度,以及標準單元佈局區域。首先,我們提出了環狀輪廓資料結構,它能有效地描述所有預先擺置巨集電路。基於這個資料結構,我們可以有效地避免巨集電路之間發生重疊。同時也可以優化標準單元佈局區域的形狀和面積。不同於以往的巨集電路擺置器,其往往花費太大的計算時間尋找可行的解,我們提出的環狀堆機方案,將可移動的巨集電路安放在環狀輪廓周邊,可以有效地產生可行解,並協助模擬退火(Simulated Annealing)專注於優化解的質量。實驗結果證實,我們所提出的演算法能夠比業界的人工手動擺置巨集電路以及學術界最先進的混合尺寸擺置器得到更好的結果。 | zh_TW |
dc.description.abstract | Due to the wide use of intellectual property (IP) macros, a modern system-on-a-chip (SoC) usually contains a significant number of large macros. Some macros, namely pre-placed macros, need to be placed at specified positions and in certain orientations due to various considerations, such as power and pin locations. The existence of pre-placed macros and large macros in modern SoCs has complicated modern mixed-size placement. However, existing works may fail to obtain a legal placement for modern mixed-size designs. Therefore, in this thesis, we present a three-stage mixed-size placement flow, which consists of: (1) placement prototyping, (2) macro placement, and (3) standard-cell placement. We focus on the macro placement stage, which plays a key role to determine the mixed-size placement quality. The proposed macro placer simultaneously optimizes wirelength, routability, and standard-cell placement region. We first propose a circular contour that can model all of the pre-placed macros. Based on the proposed circular contour, we can effectively avoid the overlap between movable macros and pre-placed macros. Meanwhile, the shape and area of the standard-cell placement region can also be optimized. Unlike previous macro placers that often spend much computational effort on searching a feasible solution, our circular packing scheme, which packs movable macros around the circular contour, can generate feasible solutions efficiently, and assist simulated annealing (SA) to focus on the optimization of solution quality. Experimental results show that our algorithm can achieve the best quality among both manual macro placements provided by industry and the leading academic mixed-size placers on industrial benchmarks. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T04:00:24Z (GMT). No. of bitstreams: 1 ntu-103-R01921033-1.pdf: 1990341 bytes, checksum: a26f6ecf63cf2b5244d7255190eba086 (MD5) Previous issue date: 2014 | 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.2 Related Work 2 1.2.1 Floorplanning Algorithm 3 1.2.2 Recent Research on Mixed-Size Placement 4 1.2.2.1 One-stage mixed-size placement 4 1.2.2.2 Constructive mixed-size placement 5 1.2.2.3 Three-stage mixed-size placement 5 1.3 Motivation 8 1.4 Our Contributions 11 1.5 Thesis Organization 13 Chapter 2. Preliminaries 14 2.1 Definition of Polygons 14 2.2 Review of Corner Sequence 16 2.3 The Three-Stage Mixed-Size Placement Flow 19 2.4 Review of Routability-Aware Wirelength Model 21 2.5 Problem Formulation 22 Chapter 3. Circular-Contour-Based Blockage-Aware Macro Placement Algorithm 24 3.1 Algorithm Overview 24 3.2 Circular Contour Construction 25 3.3 Circular Packing 27 3.3.1 Feasible Corner Examination 30 3.3.1.1 Macro Shifting 33 3.3.1.2 Overlap Checking 37 3.3.2 Circular Contour Update 41 3.3.3 Incremental Update 44 3.4 Simulated Annealing Optimization 46 3.4.1 Cost Evaluation 47 3.4.1.1 Macro Shifting Wasted Area 47 3.4.1.2 Boundary Cost 48 Chapter 4. Experimental Results 50 Chapter 5. Conclusions and Future Work 58 Bibliography 62 | |
dc.language.iso | en | |
dc.title | 基於環狀輪廓考慮障礙物之巨集電路擺置 | zh_TW |
dc.title | Circular-Contour-Based Blockage-Aware Macro Placement | en |
dc.type | Thesis | |
dc.date.schoolyear | 103-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳宏明(Hung-Ming Chen),林家民(Chia-Min Lin),陳東傑(Tung-Chieh Chen) | |
dc.subject.keyword | 實體設計,電路擺置,可繞度,巨集電路,超大型積體電路設計, | zh_TW |
dc.subject.keyword | Physical Design,Placement,Routability,Macro,VLSI Design, | en |
dc.relation.page | 65 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2014-11-10 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 1.94 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。