Multilevel Full-Chip Routing For The X-Based Architecture

As technology advances into the nanometer territory, the interconnect delay has become a first-order factor on chip performance. To handle this effect, the X-architecture has been proposed for high-performance integrated circuits. The X-architecture presents a new way of orienting a chip’s microscopic interconnect wires with the pervasive use of diagonal routes. It can reduce the wire length and via count, and thus improve performance and routability. Furthermore, the continuous increase of the problem size in IC routing is also a great challenge to existing routing algorithms. In this chapter, we present the first multilevel framework for full-chip routing using the X-architecture. To take full advantage of the X-architecture, we explore the optimal routing for three-terminal nets on the X-architecture and develop a general XST algorithm based on the Delaunay triangulation approach for the X-architecture [55]. The multilevel routing framework adopts a two-stage technique of coarsening followed by uncoarsening, with a trapezoid-shaped track assignment embedded between the two stages to assign long, straight diagonal segments for wire length reduction.