A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method

Yoichi SHIRAISHI; Jun'ya SAKEMI; Kazuyuki FUKUDA

A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method

Yoichi SHIRAISHI, Jun'ya SAKEMI, Kazuyuki FUKUDA

Full Text Views

0

Share
Cite this

Summary :

A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.10 pp.1746-1754

Publication Date: 1993/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category

Cite this

Copy

Yoichi SHIRAISHI, Jun'ya SAKEMI, Kazuyuki FUKUDA, "A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method" in IEICE TRANSACTIONS on Fundamentals, vol. E76-A, no. 10, pp. 1746-1754, October 1993, doi: .
Abstract: A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e76-a_10_1746/_p

Copy

@ARTICLE{e76-a_10_1746,
author={Yoichi SHIRAISHI, Jun'ya SAKEMI, Kazuyuki FUKUDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method},
year={1993},
volume={E76-A},
number={10},
pages={1746-1754},
abstract={A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - A Global Routing Algorithm Based on the Multi-Commodity Network Flow Method
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1746
EP - 1754
AU - Yoichi SHIRAISHI
AU - Jun'ya SAKEMI
AU - Kazuyuki FUKUDA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1993
AB - A global routing problem is formulated as a multi-commodity network flow problem. The formulation gives no restriction over the shape of a routing pattern and makes it possible to obtain the optimal solution by using a mathematical programming method. Moreover, it can be naturally extended to the problem even optimizing routing length objectives for net delay and clock skew perfomances by using the goal programming method. An approximation algorithm solving the multi-commodity network flow problem is proposed by adding a merge step of wires whose source-sink pairs are exactly the same and a step restricting an area for searching routes. Experimental results show that this global routing algorithm connected with a line-search detailed router can generate a complete routing for interblock routing problems with more than 2400 wires in two industrial chips. The total amount of procassing time for both problems is about 90 minutes on a mainframe computer.
ER -