Multilevel full-chip routing for the X-based architecture.
Journal
Proceedings of the 42nd Design Automation Conference, DAC 2005, San Diego, CA, USA, June 13-17, 2005
Pages
597-602
Date Issued
2005
Author(s)
Abstract
As technology advances into the nanometer territory, 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. 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 of IC routing is also a great challenge to existing routing algorithms. In this paper, 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 X-Steiner tree algorithm based on the delaunay triangulation approach for the X-architecture. 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 wirelength reduction. Compared with the state-of-the-art multilevel routing for the Manhattan architecture, experimental results show that our approach reduced wirelength by 18.7% and average delay by 8.8% with similar routing completion rates and via counts. Copyright 2005 ACM.
Subjects
Multilevel optimization; Physical design; Routing; X-architecture
Other Subjects
Algorithms; Integrated circuits; Routers; Full-chip routing; Multilevel optimization; X-arhitecture; Microprocessor chips
Type
conference paper