IEICE TRANSACTIONS on Fundamentals
A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound
Summary :
In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.12 pp.2971-2978
- Publication Date
- 2009/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.2971
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Physical Level Desing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yukihide KOHIRA, Suguru SUEHIRO, Atsushi TAKAHASHI, "A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 12, pp. 2971-2978, December 2009, doi: 10.1587/transfun.E92.A.2971.
Abstract: In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2971/_p
Copy
@ARTICLE{e92-a_12_2971,
author={Yukihide KOHIRA, Suguru SUEHIRO, Atsushi TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound},
year={2009},
volume={E92-A},
number={12},
pages={2971-2978},
abstract={In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.},
keywords={},
doi={10.1587/transfun.E92.A.2971},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - A Fast Longer Path Algorithm for Routing Grid with Obstacles Using Biconnectivity Based Length Upper Bound
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2971
EP - 2978
AU - Yukihide KOHIRA
AU - Suguru SUEHIRO
AU - Atsushi TAKAHASHI
PY - 2009
DO - 10.1587/transfun.E92.A.2971
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2009
AB - In recent VLSI systems, signal propagation delays are requested to achieve the specifications with very high accuracy. In order to meet the specifications, the routing of a net often needs to be detoured in order to increase the routing delay. A routing method should utilize a routing area with obstacles as much as possible in order to realize the specifications of nets simultaneously. In this paper, a fast longer path algorithm that generates a path of a net in routing grid so that the length is increased as much as possible is proposed. In the proposed algorithm, an upper bound for the length in which the structure of a routing area is taken into account is used. Experiments show that our algorithm utilizes a routing area with obstacles efficiently.
ER -
English
