Timing-Constrained Flexibility-Driven Routing Tree Construction

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

doi:10.1093/ietisy/e88-d.7.1360

Timing-Constrained Flexibility-Driven Routing Tree Construction

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

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.7 pp.1360-1368

Publication Date: 2005/07/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.7.1360

Type of Manuscript: Special Section PAPER (Special Section on Recent Advances in Circuits and Systems--Part 1)

Category: Programmable Logic, VLSI, CAD and Layout

Cite this

Copy

Jin-Tai YAN, Yen-Hsiang CHEN, Chia-Fang LEE, "Timing-Constrained Flexibility-Driven Routing Tree Construction" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 7, pp. 1360-1368, July 2005, doi: 10.1093/ietisy/e88-d.7.1360.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.7.1360/_p

Copy

@ARTICLE{e88-d_7_1360,
author={Jin-Tai YAN, Yen-Hsiang CHEN, Chia-Fang LEE, },
journal={IEICE TRANSACTIONS on Information},
title={Timing-Constrained Flexibility-Driven Routing Tree Construction},
year={2005},
volume={E88-D},
number={7},
pages={1360-1368},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e88-d.7.1360},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - Timing-Constrained Flexibility-Driven Routing Tree Construction
T2 - IEICE TRANSACTIONS on Information
SP - 1360
EP - 1368
AU - Jin-Tai YAN
AU - Yen-Hsiang CHEN
AU - Chia-Fang LEE
PY - 2005
DO - 10.1093/ietisy/e88-d.7.1360
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2005
AB - 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.
ER -