IEICE TRANSACTIONS on Fundamentals
A Length Matching Routing Algorithm for Set-Pair Routing Problem
Summary :
In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.12 pp.2565-2571
- Publication Date
- 2015/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E98.A.2565
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Physical Level Design
Authors
Yuta NAKATANI
Tokyo Institute of Technology
Atsushi TAKAHASHI
Tokyo Institute of Technology
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
Yuta NAKATANI, Atsushi TAKAHASHI, "A Length Matching Routing Algorithm for Set-Pair Routing Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 12, pp. 2565-2571, December 2015, doi: 10.1587/transfun.E98.A.2565.
Abstract: In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.2565/_p
Copy
@ARTICLE{e98-a_12_2565,
author={Yuta NAKATANI, Atsushi TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Length Matching Routing Algorithm for Set-Pair Routing Problem},
year={2015},
volume={E98-A},
number={12},
pages={2565-2571},
abstract={In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.},
keywords={},
doi={10.1587/transfun.E98.A.2565},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - A Length Matching Routing Algorithm for Set-Pair Routing Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2565
EP - 2571
AU - Yuta NAKATANI
AU - Atsushi TAKAHASHI
PY - 2015
DO - 10.1587/transfun.E98.A.2565
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2015
AB - In the routing design of interposer and etc., the combination of a pin pair to be connected by wire is often flexible, and the reductions of the total wire length and the length difference are pursued to keep the circuit performance. Even though the total wire length can be minimized by finding a minimum cost maximum flow in set pair routing problems, the length difference is often large, and the reduction of it is not easy. In this paper, an algorithm that reduces the length difference while keeping the total wire length small is proposed. In the proposed algorithm, an initial routing first obtained by a minimum cost maximum flow. Then it is modified to reduce the maximum length while keeping the minimum total wire length, and a connection of the minimum length is detoured to reduce the length difference. The effectiveness of the proposed algorithm is confirmed by experiments.
ER -
English
