X-route: An x-architecture full-chip multilevel router
Journal
20th Anniversary IEEE International SOC Conference
Pages
229-232
Date Issued
2007
Author(s)
Chang, C.-F.
Abstract
In this paper, we present an X-architecture multilevel full-chip router, called X-Route. Unlike the traditional Λ-shaped multilevel framework that adopts bottom-up coarsening followed by top-down uncoarsening, our multilevel framework runs in the V-shaped 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. Since we perform top-down routing first, global long nets are routed earlier. To prevent a wrong decision from blocking the later nets, we keep a dynamic congestion map that records the updated routing congestion information based on the routed nets and the global-path prediction of the unrouted nets. 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 Λ-shaped multilevel routing for the X-architecture, experimental results show that our X-Route reduces the respective wirelength and average delay by about 14.05% and 30.62%, with better routing completion.
SDGs
Other Subjects
Architecture; Coarsening; Marine biology; Programmable logic controllers; Refining; Routing algorithms; X-architecture; Computer networks; Algorithms; Controllers; Fineness; Refining
Type
conference paper