請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33578完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 張耀文 | |
| dc.contributor.author | Chen-Feng Chang | en |
| dc.contributor.author | 張宸峰 | zh_TW |
| dc.date.accessioned | 2021-06-13T04:48:24Z | - |
| dc.date.available | 2006-07-18 | |
| dc.date.copyright | 2006-07-18 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-07-16 | |
| dc.identifier.citation | [1] http://www.xinitiative.org/
[2] S. H. Batterywala, N. Shenoy, W. Nicholls, and H. Zhou, Track assignment: A desirable intermediate step between global routing and detailed routing,' Proc. of Int. Conf. Computer-Aided Design, pp. 59{66, 2002. [3] M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd Edition, Springer-Verlag 2000. [4] Y.-W. Chang, K. Zhu, and D. F. Wong, Timing-driven routing for symmetrical-array-based FPGAs,' Trans. on Design Automation of Electronic Systems, vol. 5, no. 3, pp. 433{450, 2000. [5] H. Chen, C. K. Cheng, A. B. Khang, I. I. Mandoiu, Q. Wang, and B. Yao, The Y-Architecture for on-chip interconnect: Analysis and methodology,' Proc. of Int. Conf. Computer-Aided Design, pp. 13{19, 2003. [6] H. Chen, B. Yao, F. Zhou, and C. K. Cheng, The Y-Architecture: Yet another on-chip interconnect solution,' Proc. of Asia and South Paci‾c Design Automation Conf., pp. 840{846, 2003. [7] B. Choi, C. Chiang, J. Kawa, and M. Sarrafzadeh, Routing resources consumption on M-arch and X-arch,' Proc. of Int. Symp. on Circuits and Systems, 2004. [8] J. Cong, J. Fang, and Y. Zhang, Multilevel approach to full-chip gridless routing,' Proc. of Int. Conf. Computer-Aided Design, pp. 396{403, 2001. [9] J. Cong, M. Xie, and Y. Zhang, An enhanced multilevel routing system,' Proc. of Int. Conf. Computer-Aided Design, pp. 51{58, 2002. [10] J. Cong and J. Shinnerl, Multilevel optimization in VLSICAD, Kluwer Academic Publishers, 2003. [11] C. S. Coulston, Constructing exact octagonal steiner minimal trees,' Proc. of Great Lake Symp. on VLSI, pp. 1{6, 2003. [12] Leo J. Guibas and Jorge Stol‾, On computing all north-east nearest neighbors in the L1 metric,' Information Processing Letters, 1983. [13] M. R. Garey, R. L. Graham, and D. S. Johnson, The complexity of computing steiner minimal trees,' SIAM Journal on Applied Mathematics, pp. 835{859, 1977. [14] A. Hashimoto and J. Stevens , Wire routing by optimizing channel assignment within large apertures,' Proc. of Design Automation Conf., pp. 155{169, 1971. [15] A. Hashimoto and J. Stevens , Wire routing by optimizing channel assignment within large apertures,' Proc. of Design Automation Conf., pp. 155{169, 1971. [16] T.-Y. Ho, Y.-W. Chang, S.-J. Chen, and D. T. Lee, A fast crosstalk- and performance-driven multilevel routing system,' Proc. of Int. Conf. Computer-Aided Design, pp. 382{387, 2003. [17] T.-Y. Ho, Y.-W. Chang, and S.-J. Chen, Multilevel routing with antenna avoidance,' Proc. of Int. Symp. on Physical Design, pp. 34{40, 2004. [18] T.-Y. Ho, C.-F. Chang, Y.-W. Chang, and S.-J. Chen, Multilevel full-chip routing for the X-based architecture,' Proc. of Design Automation Conf., 2005. [19] A. B. Kahng, I. Mandoiu, and A. Zelikovsky, High scalable algorithms for rectilinear and octilinear steiner trees,' Proc. of Asia and South Paci‾c Design Automation Conf., pp. 827{833, 2003. [20] A. B. Kahng and G. Robins, a new class iterative Steiner tree heuristics with good performance' IEEE Trans. Computer Aided Design, 1992. [21] C. K. Koh and P. H. Madden, Manhattan or Non-Manhattan? A study of alternative VLSI routing architectures,' Proc. of Great Lake Symp. on VLSI, pp. 47{52, 2000. [22] C. Y. Lee, An algorithm for path connection and its application,' IRE Trans.Electronic Computer, EC-10, 1961. [23] S.-P. Lin and Y.-W. Chang, A novel framework for multilevel routing considering routability and performance,' Proc. of Int. Conf. Computer-Aided Design, pp. 44{50, 2002. [24] M.Paluszewski, P. Winter, and M. Zachariasen, A new paradigm for general architecture routing,' Proc. of Great Lake Symp. on VLSI, pp. 202{207, 2004. [25] M. R. Stan, F. Hamzaoglu, and D. Garrett, Non-manhattan maze routing,'Proc. of Brazilian Symp. on Integrated Circuit Design, pp. 260{265, 2004. [26] S. Teig, The X Architecture: not your father's diagonal wiring,' Proc. of System Level Interconnect Predicition, pp. 33{37, 2002. [27] Andrew Chi-Chih Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems,' the Society for Industrial and Applied Journal on Computing, pp.721-736, 1982. [28] Y.-L. Lin, Y.-C. Hsu and F.-S. Tsai, Hybrid Routing,' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 151-157, 1990. [29] Q. Zhu, H. Zhou, T. Jing, X. Hong, and Y. Yang, cient octilinear steiner tree construction based on spanning graphs,' Proc. of Asia and South Paci‾c Design Automation Conf., pp. 687{690, 2004. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33578 | - |
| dc.description.abstract | As nanometer IC technologies advance, the interconnect delay has become a first order effect on chip performance. To handle this effect, the X-architecture has been proposed for high-performance integrated circuits. In this thesis, we present a novel multilevel full-chip routing system using the X-architecture, called XRoute. Unlike the traditional V-cycle multilevel framework that adopts bottom-up coarsening followed by top-down uncoarsening. Our novel multilevel framework works in the inversed V-cycle manner: top-down uncoarsening followed by bottom-up coarsening. The top-down uncoarsening stage performs octagonal global routing and X-detailed routing for local nets at each level and then refines the solution for the next level. Then, the bottom-up coarsening stage performs the X-detailed routing to reroute failed nets and refines the solution level by level. To take full advantage of the X-architecture, we also develop a progressive X-Steiner tree algorithm based on the delaunay triangulation approach for the X-architecture. Compared with the state-of-the-art V-cycle multilevel routing system for the X-architecture [18](DAC-05), experimental results show that our XRoute reduces the respective wirelength and average delay by about 14.05% and 30.62%, with better routing completion. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T04:48:24Z (GMT). No. of bitstreams: 1 ntu-95-R92921095-1.pdf: 619792 bytes, checksum: 42a1142da33123fe576afd933574d383 (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | Abstract ii
List of Tables iii List of Figures iv Chapter 1. Introduction 1 1.1 Introduction . . . . . . . . . . . . . . . . . . 1 1.2 Previous Work . . . . . . . . . . . . . . . . . 2 1.2.1 Multilevel Routing framework. . . . . . . . . . 3 1.2.2 The Octilinear Steiner Minimal Tree Construction 4 1.3 Our Contribution . . . . .. . . . . . . . . . . . 7 1.4 Organization of the Thesis . . . . . . . . .. . . 10 Chapter 2. Preliminaries 11 2.1 The X-Architecture . . . . . . . . . . . . . . . . . . . . . 11 2.2 The Multilevel Frameworks Based on the Manhattan Architecture . . . . . . . . . . . . . . . . . . . . . 11 2.3 The Multilevel Framework Based on the X-Architecture.13 Chapter 3. The X-Based Routing System 16 3.1 Multilevel Routing Model . . . . . . . . . . . . 18 3.2 Octagonal Global Pattern Routing and 1-bend Trial Routing . . . . . . . . . . . . . . . . . . . . . . . .19 3.3 Multilevel X-Routing Framework . . . . . . . . . . 22 3.4 Progressive X-Steiner Tree Construction . . . . . . 22 3.4.1 Three-Terminal Net Routing Based on X-Architecture . . . . . . . . . . . . . . . . . . . . . 22 3.4.2 Progressive X-Steiner Tree Algorithm Based On Delaunay Triangulation . . . . . . . . . . . . . . . . 26 3.5 X-Detailed Routing . . . . . . . . . . . . . . . . 28 Chapter 4. Experimental Results 31 Chapter 5. Conclusion and Future Work 34 Bibliography 36 | |
| dc.language.iso | en | |
| dc.subject | 多階層 | zh_TW |
| dc.subject | 繞線 | zh_TW |
| dc.subject | 架構 | zh_TW |
| dc.subject | X-Architecture | en |
| dc.subject | Routing | en |
| dc.subject | Router | en |
| dc.subject | Multilevel | en |
| dc.subject | XRoute | en |
| dc.title | X架構下的全晶片繞線框架 | zh_TW |
| dc.title | XROUTE: AN X-ARCHITECTURE FULL-CHIP ROUTER BASED ON A NOVEL MULTILEVEL FRAMEWORK | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林永隆,王志恆,黃世旭 | |
| dc.subject.keyword | 繞線,架構,多階層, | zh_TW |
| dc.subject.keyword | X-Architecture,XRoute,Multilevel,Router,Routing, | en |
| dc.relation.page | 38 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-07-17 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 未授權公開取用 | 605.27 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。