張耀文臺灣大學：電機工程學研究所張宸峰Chang, Chen-FengChen-FengChang2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53288As 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.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 36619792 bytesapplication/pdfen-US繞線架構多階層X-ArchitectureXRouteMultilevelRouterRoutingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53288/1/ntu-95-R92921095-1.pdf