Timing-Constrained Flexibility-Driven Routing Tree Construction

Jin-Tai YAN  Yen-Hsiang CHEN  Chia-Fang LEE  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.7   pp.1360-1368
Publication Date: 2005/07/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.7.1360
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Recent Advances in Circuits and Systems--Part 1)
Category: Programmable Logic, VLSI, CAD and Layout
global routing,  routing flexibility,  Steiner tree,  timing constraint,  

Full Text: PDF>>
Buy this Article

As the complexity of VLSI circuits increases, the routability problem becomes more and more important in modern VLSI design. In general, the flexibility improvement of the edges in a routing tree has been exploited to release the routing congestion and increase the routability in the routing stage. Given an initial rectilinear Steiner tree, the rectilinear Steiner tree can be transformed into a Steiner routing tree by deleting all the corner points in the rectilinear Steiner tree. Based on the definition of the routing flexibility in a Steiner routing tree and the timing-constrained location flexibility of the Steiner-point in any Y-type wire, the simulated-annealing-based approach is proposed to construct a better timing-constrained flexibility-driven Steiner routing tree by reassigning the feasible locations of the Steiner points in all the Y-type wires. The experimental results show that our proposed algorithm, STFSRT, can increase about 0.005-0.020% wire length to improve about 43-173% routing flexibility for the tested benchmark circuits.