Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78218Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
| dc.contributor.author | I-Peng Wu | en |
| dc.contributor.author | 吳一鵬 | zh_TW |
| dc.date.accessioned | 2021-07-11T14:46:27Z | - |
| dc.date.available | 2021-10-17 | |
| dc.date.copyright | 2016-10-17 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-07-04 | |
| dc.identifier.citation | [1] Low voltage switched capacitor circuits, http://www.ele.uva.es/jesus/analog/lowV/index_en.html.
[2] Noise Reduction Is Crucial To Mixed-Signal ASIC Design Success (PartII), http://electronicdesign.com/analog/noise-reduction-crucial-mixed-signalasic-design-success-part-ii. [3] Quick tip: Use quadtrees to detect likely collisions in 2D space, http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees to-detect-likely-collisions-in-2d-space-gamedev-374. [4] F. Balasa and K. Lampaert, 'Module placement for analog layout using the sequence-pair representation,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 274-279, June 1999. [5] F. Balasa, S. C. Maruvada, and K. Krishnamoorthy, 'Efficient solution space exploration based on segment trees in analog placement with symmetry constraints,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 497-502, November 2002. [6] 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, June 2000. [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] M. Chrzanowska-Jeske, B. Wang, and G. Greenwood, 'Floorplanning with performance-based clustering,' in Proceedings of IEEE International Symposium on Circuits and Systems, pp. 724-727, May 2003. [9] J. M. Cohn, D. J. Garrod, R. A. Rutenbar, and L. R. Carley, Analog device-level automation. Kluwer Academic Publishers, 1994. [10] J. Cong, L. He, C.-K. Koh, and P. H. Madden, 'Performance optimization of vlsi interconnect layout,' Integration, the VLSI Journal, vol. 21, no. 1-2, pp. 1-94, November 1996. [11] J. Cong, T. Kong, and Z. Pan, 'Bu er block planning for interconnect planning and prediction,' IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 9, no. 6, pp. 929-937, December 2001. [12] J. Cong, Z. Pan, L. He, C.-K. Koh, and K.-Y. Khoo, 'Interconnect design for deep submicron ICs,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 478-485, November 1997. [13] R. A. Finkel and J. L. Bentley, 'Quad trees a data structure for retrieval on composite keys,' Acta Informatica, vol. 4, no. 1, pp. 1-9, March 1974. [14] 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, May 2001. [15] C.-W. Lin, J.-M. Lin, C.-P. Huang, and S.-J. Chang, 'Performance-driven analog placement considering boundary constraint,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 292-297, June 2010. [16] P.-H. Lin, Y.-W. Chang, and S.-C. Lin, 'Analog placement based on symmetry-island formulation,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 6, pp. 791-804, June 2009. [17] P.-H. Lin and S.-C. Lin, 'Analog placement based on hierarchical module clustering,' in Proceedings of ACM/IEEE Design Automation Conference, pp. 50-55, June 2008. [18] Q. Ma, L. Xiao, Y.-C. Tam, and E. F. Y. Young, 'Simultaneous handling of symmetry, common-centroid, and general placement constraints,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 1, pp. 85-95, January 2011. [19] T. Nojima, X. Zhu, Y. Takashima, S. Nakatake, and Y. Kajitani, 'Multi-level placement with circuit schema based clustering in analog IC layouts,' in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 406-411, January 2004. [20] Y. Pang, F. Balasa, K. Lampaert, and C.-K. Cheng, 'Block placement with symmetry constraints based on the O-tree non-slicing representation,' in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 464-467, June 2000. [21] Y.-C. Tam, E. F. Y. Young, and C. Chu, 'Analog placement with symmetry and other placement constraints,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 349-354, November 2006. [22] H.-F. Tsao, P.-Y. Chou, S.-L. Huang, Y.-W. Chang, P.-H. Lin, D.-P. Chen, and D. Liu, 'A corner stitching compliant B*-tree representation and its applications to analog placement,' in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 507-511, November 2011. [23] E. F. Y. Young, M. D. F. Wong, and H. H. Yang, 'Slicing floorplans with range constraint,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, no. 2, pp. 272-278, February 2000. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78218 | - |
| dc.description.abstract | 現今的類比積體電路擺置需要考慮多樣化的幾何限制來產生符合要求的布局設計。為了要能夠同時解決一般性的幾何限制，文獻上最先進的研究通常基於拓樸表示法並使用simulated annealing 來產生結果，由於拓樸表示法的解空間較小並且效率較好。然而，沒有文獻能夠對一般幾何性的限制達到最佳的時間複雜度，此外，每份文獻僅能處理部分的限制。為了要彌補這些不足，在這篇論文裡我們提出了一個混合式的表示法，結合四分樹以及B*樹 (簡稱QB 樹) 在線性且最低時間複雜度內處理所有的限制。實驗結果顯示，跟目前文獻相比，本論文所提出的拓樸表示法及演算法不僅能同時最小化晶片的連線半周長以及面積，並且能在不同的工業界晶片上都有穩定且有效率的結果。 | zh_TW |
| dc.description.abstract | A modern analog placer often needs to consider various geometrical constraints to generate desired layouts. To handle general constraints simultaneously, current state-of-the-art works adopt simulated annealing based on topological representations, due to their smaller solution spaces and higher efficiency. However, no published work achieves the optimal time complexity for general geometrical constraint handling and module packing. Besides, only limited constraints are considered and handled in each work. To remedy these insufficiencies, we present a new hybrid representation of a quadtree and B*-trees (QB-tree, for short) to handle general geometrical constraints while achieving linear, lower-bound time complexity of module packing and constraint handling. Experimental results based on real industrial designs with various constraints show that our placer outperforms the
leading published works in both runtime and solution quality. | en |
| dc.description.provenance | Made available in DSpace on 2021-07-11T14:46:27Z (GMT). No. of bitstreams: 1 ntu-105-R03943092-1.pdf: 2583695 bytes, checksum: 674c3dc6eed51d5f6b65dbcb88f9a439 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | Acknowledgements iii
Abstract (Chinese) iv Abstract v List of Tables viii List of Figures ix Chapter 1. Introduction 1 1.1 Analog/Mixed-signal Design Constraints . . . . . . . . . . . . . . . . . . 1 1.1.1 Symmetry Constraints . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Proximity Constraints . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.3 Preplaced Constraints . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.4 Fixed-boundary Constraints . . . . . . . . . . . . . . . . . . . . . 4 1.1.5 Minimum Separation Constraints . . . . . . . . . . . . . . . . . . 5 1.1.6 Maximum Separation Constraints . . . . . . . . . . . . . . . . . . 5 1.1.7 Range Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.8 Boundary Constraints . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.9 Close-to-boundary Constraints . . . . . . . . . . . . . . . . . . . . 7 1.1.10 Variant Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chapter 2. Preliminaries 17 2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Review of the Quadtree . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Review of the B*-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Chapter 3. Data Structure 21 3.1 Construction Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Packing Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Chapter 4. Analog Placement Algorithm 27 4.1 Analog Placement Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Operations on QB-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 Look-ahead Constraint Checking . . . . . . . . . . . . . . . . . . . . . . 30 4.4 Candidate Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.5 Constraint Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.5.1 Symmetry/Proximity Constraints . . . . . . . . . . . . . . . . . . 37 4.5.2 Preplaced/Fixed-boundary Constraints . . . . . . . . . . . . . . . 37 4.5.3 Minimum Separation Constraints . . . . . . . . . . . . . . . . . . 38 4.5.4 Maximum Separation/Range/Close-to-boundary Constraints . . . 38 4.5.5 Boundary Constraints . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5.6 Variant Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.6 Cost Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Chapter 5. Experimental Results 42 5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2 Experimental Results and Comparisons . . . . . . . . . . . . . . . . . . 43 Chapter 6. Conclusions and Future Work 51 Bibliography 55 Publication List 59 | |
| dc.language.iso | en | |
| dc.subject | 類比積體電路 | zh_TW |
| dc.subject | 電路擺置 | zh_TW |
| dc.subject | 實體設計 | zh_TW |
| dc.subject | Physical Design | en |
| dc.subject | Placement | en |
| dc.subject | Analog ICs | en |
| dc.title | QB 樹: 一個趨向最佳之拓樸表示法及其於類比佈局設計之應用 | zh_TW |
| dc.title | QB-Trees: Towards an Optimal Topological Representation and Its Applications to Analog Layout Designs | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王廷基(Ting-Chi Wang),陳宏明(Hung-Ming Chen),方劭云(Shao-Yun Fang) | |
| dc.subject.keyword | 實體設計,電路擺置,類比積體電路, | zh_TW |
| dc.subject.keyword | Physical Design,Placement,Analog ICs, | en |
| dc.relation.page | 59 | |
| dc.identifier.doi | 10.6342/NTU201600580 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-07-05 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| Appears in Collections: | 電子工程學研究所 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-105-R03943092-1.pdf Restricted Access | 2.52 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.