請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65292
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Sheng Chou | en |
dc.contributor.author | 周昇 | zh_TW |
dc.date.accessioned | 2021-06-16T23:34:54Z | - |
dc.date.available | 2017-08-01 | |
dc.date.copyright | 2012-08-01 | |
dc.date.issued | 2012 | |
dc.date.submitted | 2012-07-27 | |
dc.identifier.citation | [1] coalesCgrip: A Tool for Routing Congestion Analysis, http://homepages.cae.wisc.edu/∼adavoodi/gr/cgrip.htm.
[2] ISPD 2006 Placement Contest, http://archive.sigda.org/ispd2006/contest.html. [3] Structured Placement Benchmark Suite, http://www.cerc.utexas.edu/utda/download/DP/. [4] A. R. Agnihotri, S. Ono, and P. H. Madden, “Recursive bisection placement: Feng Shui 5.0 implementation details,” in Proc. ACM Int. Symp. Physical Design, pp. 230–232, San Francisco, CA, Apr. 2005. [5] S. R. Arikati and R. Varadarajan, “A signature based approach to regularity extraction,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 542–545, San Jose, CA, Nov. 1997. [6] H. Cai, S. Note, P. Six, and H. D. Man, “A data path layout assembler for high performance DSP circuits,” in Proc. ACM/IEEE Design Automation Conf., pp. 306–311, Orlando, FL, Jun. 1990. [7] T. Chan, A. Chowdhary, B. Krishna, A. Levin, G. Meeker, and N. Sehgal, “Challenges of CAD development for datapath design,” Intel Technology Journal, vol. Q1, no. 17, Feb. 1999. [8] T. F. Chan, J. Cong, J. R. Shinnerl, K. Sze, and M. Xie, “mPL6: Enhanced multilevel mixed-size placement,” in Proc. ACM/IEEE Design Automation Conf., pp. 212–214, San Jose, CA, Apr. 2006. [9] Y.-W. Chang, Z.-W. Jiang, and T.-C. Chen, “Essential issues in analytical placement algorithms,” IPSJ Trans. System LSI Design Methodology, vol. 2, pp. 145–166, 2007. [10] H. Chen, C. Qiao, F. Zhou, and C.-K. Cheng, “Refined single trunk tree: a rectilinear Steiner tree generator for interconnect prediction,” in Proc. Int. Workshop on System-level Interconnect Prediction, pp. 85–89, San Diego, CA, Apr. 2002. [11] T.-C. Chen, T.-C. Hsu, Z.-W. Jiang, and Y.-W. Chang, “NTUplace: A ratio partitioning based placement algorithm for large-scale mixed-size designs,” in Proc. ACM Int. Symp. Physical Design, pp. 236–238, San Francisco, CA, Apr. 2005. [12] 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 preplaced blocks and density constraints,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 7, pp. 1228–1240, Jul. 2008. [13] A. Chowdhary, S. Kale, P. Saripella, N. Sehgal, and R. Gupta, “A general approach for regularity extraction in datapath circuits,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 332–339, San Jose, CA, Nov. 1998. [14] C. Chu and Y.-C. Wong, “FLUTE: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 1, pp. 70–83, Jan. 2008. [15] M. R. Corazao, M. A. Khalaf, L. M. Guerra, M. Potkonjak, and J. M. Rabaey, “Performance optimization using template mapping for datapath-intensive high-level synthesis,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 8, pp. 877–888, Aug. 1996. [16] M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified NP-complete graph problems,” Theoretical Computer Science, vol. 1, no. 3, pp. 237–267, Feb. 1976. [17] S. Hassoun and C. McCreary, “Regularity extraction via clan-based structural circuit decomposition,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 414–418, San Jose, CA, Nov. 1999. [18] D. Hill, “Method and system for high speed detailed placement of cells within an integrated circuit design,” U.S. Patent 6370673, 2002. [19] M. Hirsch and D. Siewiorek, “Automatically extracting structure from a logical design,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 456–459, Santa Clara, CA, Nov. 1988. [20] M.-K. Hsu, Y.-W. Chang, and V. Balabanov, “TSV-aware analytical placement for 3D IC designs,” in Proc. ACM/IEEE Design Automation Conf., pp. 664–669, San Diego, CA, Jun. 2011. [21] M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang, “Routability-driven analytical placement for mixed-size circuit designs,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 80–84, San Jose, CA, Nov. 2011. [22] E. O. Hwang, Digital Logic and Microprocessor Design with VHDL. Thomson, 2006. [23] A. B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 5, pp. 734–747, May 2005. [24] J. Kim and S. M. Kang, “A timing-driven data path layout synthesis with integer programming,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 716–719, San Jose, CA, Nov. 1995. [25] W. K. Luk and A. A. Dean, “Multi-stack optimization for datapath chip (microprocessor) layout,” in Proc. ACM/IEEE Design Automation Conf., pp. 110–115, Las Vegas, NV, Jun. 1989. [26] M.‥Munch, N. Wehn, and M. Glesner, “Optimum simultaneous placement and binding for bit-slice architectures,” in Proc. IEEE/ACM Asia and South Pacific Design Automation Conf., pp. 735–740, Chiba, Japan, Aug. 1995. [27] H. Nakao, O. Kitada, M. Hayashikoshi, K. Okazaki, and Y. Tsujihashi, “A high density datapath layout generation method under path delay constraints,” in Proc. IEEE Custom Integrated Circuits Conf., pp. 9.5.1–9.5.5, San Diego, CA, May 1993. [28] G.-J. Nam, “ISPD 2006 placement contest: Benchmark suite and results,” in Proc. ACM Int. Symp. Physical Design, p. 167, San Jose, CA, Apr. 2006. [29] W. C. Naylor, R. Donelly, and L. Sha, “Non-linear optimization system and method for wire length and delay optimization for an automatic electronic circuit placer,” U.S. Patent 6671859, 2003. [30] R. X. Nijssen and J. A. Jess, “Two-dimensional datapath regularity extraction,”in Proc. ACM/SIGDA Physical Design Workshop, pp. 110–117, Reston, VA, Apr. 1996. [31] G. Odawara, T. Hiraide, and O. Nishina, “Partitioning and placement technique for CMOS gate arrays,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 6, no. 3, pp. 355–363, May 1987. [32] M. Pan, N. Viswanathan, and C. Chu, “An efficient and effective detailed placement algorithm,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 48–55, San Jose, CA, Nov. 2005. [33] J. A. Roy, D. A. Papa, A. N. Ng, and I. L. Markov, “Satisfying whitespace requirements in top-down placement,” in Proc. ACM Int. Symp. Physical Design, pp. 206–208, San Jose, CA, Apr. 2006. [34] C. Sechen and A. Sangiovanni-Vincentelli, “The TimberWolf placement and routing package,” IEEE J. Solid-State Circuits, vol. 20, no. 2, pp. 510–522, Apr. 1985. [35] J. Soukup, “Circuit layout,” Proc. IEEE, vol. 69, no. 10, pp. 1281–1304, Oct. 1981. [36] P. Spindler, U. Schlichtmann, and F. M. Johannes, “Abacus: Fast legalization of standard cell circuits with minimal movement,” in Proc. ACM Int. Symp. Physical Design, pp. 47–53, Portland, OR, Apr. 2008. [37] N. Viswanathan, M. Pan, and C. Chu, “FastPlace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control,” in Proc. IEEE/ACM Asia and South Pacific Design Automation Conf., pp. 135–140, Yokohama, Japan, Jan. 2007. [38] M. Wang, X. Yang, and M. Sarrafzadeh, “Dragon2000: Standard-cell placement tool for large industry circuits,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 260–263, San Jose, CA, Nov. 2000. 39] S. I. Ward, D. Ding, and D. Z. Pan, “PADE: A high-performance placer with automatic datapath extraction and evaluation through high-dimensional data learning,” in Proc. ACM/IEEE Design Automation Conf., pp. 756–761, San Francisco, CA, Jun. 2012. [40] S. I. Ward, D. A. Papa, Z. Li, C. Sze, C. Alpert, and E. Swartzlander, “Quantifying academic placer performance on custom designs,” in Proc. ACM Int. Symp. Physical Design, pp. 91–98, Santa Barbara, CA, Mar. 2011. [41] S. I. Ward, N. Viswanathan, Z. Li, C. Alpert, E. E. Swartzlander, and D. Z. Pan, “Keep it straight: Teaching placement how to better handle designs with datapaths,” in Proc. ACM Int. Symp. Physical Design, pp. 79–86, Napa, CA, Mar. 2012. [42] T. T. Ye and G. D. Micheli, “Data path placement with regularity,” in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 264–270, San Jose, CA, Nov. 2000. [43] J.-S. Yim and C.-M. Kyung, “Datapath layout optimisation using genetic algorithm and simulated annealing,” IEE Proc. Computers and Digital Techniques, vol. 145, no. 2, pp. 135–141, Mar. 1998. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65292 | - |
dc.description.abstract | 資料路徑是在高性能的電路設計中,用於資料運算最為重要的部分之一。為了對抗現今極速高升的計算複雜度,考慮資料路徑之電路擺置愈來愈為重要。在電路的實體設計中,資料路徑電路規律化及密集化的擺置,有助於提升電路效能。在過去,雖然電路擺置的問題已被廣泛研究,資料路徑電路在電路擺置上的考量卻大多被忽視。在這個論文中,我們提出了一個考慮密集資料路徑結構的擺置演算法。不同於過去的研究,我們以S型(Sigmoid)函數為基礎,提出全新的密度模型,並以非線性最佳化的方式降低線長並獲得高品質的擺置。實驗結果顯示出,我們所提出的方法相較於先前的研究,可以有效地得到最好的電路擺置結果。 | zh_TW |
dc.description.abstract | Datapath is one of the most important components in high performance circuit designs, such as microprocessors, as it is used to manipulate all data. For better performance, a datapath is usually placed with high regularity and compactness. Although cell placement has been studied extensively, not much work addresses the optimization of datapaths, which are often treated as big macros. In this thesis, we propose a structure-aware placement algorithm that can exploit the regular structures of datapath circuits and meanwhile leverage effective techniques to achieve high quality and scalability. Our algorithm applies a nonlinear optimization for wirelength minimization and a sigmoid-based density model for density control during datapath placement. Compared with state-of-the-art works, our algorithm can achieve the best structure-aware placement results efficiently. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T23:34:54Z (GMT). No. of bitstreams: 1 ntu-101-R99943078-1.pdf: 2651741 bytes, checksum: c745db25aa47b48945f76e1ba2e5ce85 (MD5) Previous issue date: 2012 | 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 Datapath Circuit Design 1 1.2 VLSI Circuit Placement 4 1.2.1 Global placement 6 1.2.2 Legalization 8 1.2.3 Detailed Placement 8 1.3 Related Work 9 1.3.1 Regularity Extraction 9 1.3.2 Datapath Placement 10 1.3.3 Hybrid Placement 11 1.4 Motivation 13 1.5 Our Contributions 14 1.6 Thesis Organization 15 Chapter 2. Preliminaries 16 2.1 Analytical Placement 16 2.2 Wirelength Model 18 2.3 Density Model 19 2.4 Problem Formulation 21 Chapter 3. The Structure-Aware Placement Algorithm 22 3.1 Algorithm Overview 22 3.2 Regularity Extraction 25 3.2.1 Hierarchy of Datapath-Intensive Circuit Designs 25 3.2.2 The Queue-Based Regularity Extraction Algorithm 26 3.3 Structure-Aware Global Placement 30 3.3.1 Clustering and Mixed-Size Prototyping 30 3.3.2 Declustering and Datapath Placement 31 3.3.2.1 Inter-Stage Placement (Horizontal Optimization) 31 3.3.2.2 Intra-Stage Placement (Vertical Optimization) 35 3.3.2.3 Multilevel Density Optimization 37 3.3.3 Random-Logic Refinement 37 3.4 Structure-Aware Legalization and Detailed Placement 37 3.4.1 Legalization 38 3.4.2 Wirelength-Driven Refinement 39 Chapter 4. Experimental Results 40 Chapter 5. Conclusions and Future Work 45 Bibliography 48 Publication List 54 | |
dc.language.iso | en | |
dc.title | 考慮密集資料路徑結構之電路擺置 | zh_TW |
dc.title | Structure-Aware Placement for Datapath-Intensive Circuit Designs | en |
dc.type | Thesis | |
dc.date.schoolyear | 100-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王廷基(Ting-Chi Wang),李毅郎(Yih-Lang Li),郭斯彥(Sy-Yen Kuo),陳宏明(Hung-Ming Chen),麥偉基(Wai-Kei Mak) | |
dc.subject.keyword | 實體設計,資料路徑,電路擺置,規律性萃取,密度模型, | zh_TW |
dc.subject.keyword | physical design,datapath,placement,regularity extraction,density model, | en |
dc.relation.page | 54 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2012-07-27 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 2.59 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。