A Length Matching Routing Algorithm for Set-Pair Routing Problem

Yuta NAKATANI; Atsushi TAKAHASHI

doi:10.1587/transfun.E98.A.2565

A Length Matching Routing Algorithm for Set-Pair Routing Problem

Yuta NAKATANI, Atsushi TAKAHASHI

Full Text Views

1

Share
Cite this

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

set-pair routing, interposer, PCB, routing algorithm

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://globals.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 -