An Optimal Channel Pin Assignment Algorithm for Hierarchical Building-Block Layout Design

Tetsushi KOIDE; Shin'ichi WAKABAYASHI; Noriyoshi YOSHIDA

An Optimal Channel Pin Assignment Algorithm for Hierarchical Building-Block Layout Design

Tetsushi KOIDE, Shin'ichi WAKABAYASHI, Noriyoshi YOSHIDA

Full Text Views

0

Cite this

Summary :

This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.10 pp.1636-1644

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

Tetsushi KOIDE, Shin'ichi WAKABAYASHI, Noriyoshi YOSHIDA, "An Optimal Channel Pin Assignment Algorithm for Hierarchical Building-Block Layout Design" in IEICE TRANSACTIONS on Fundamentals, vol. E76-A, no. 10, pp. 1636-1644, October 1993, doi: .
Abstract: This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_10_1636/_p

Copy

@ARTICLE{e76-a_10_1636,
author={Tetsushi KOIDE, Shin'ichi WAKABAYASHI, Noriyoshi YOSHIDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Optimal Channel Pin Assignment Algorithm for Hierarchical Building-Block Layout Design},
year={1993},
volume={E76-A},
number={10},
pages={1636-1644},
abstract={This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - An Optimal Channel Pin Assignment Algorithm for Hierarchical Building-Block Layout Design
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1636
EP - 1644
AU - Tetsushi KOIDE
AU - Shin'ichi WAKABAYASHI
AU - Noriyoshi YOSHIDA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1993
AB - This paper presents a linear time optimal algorithm to a channel pin assignment problem for hierarchical building-block layout design. The channel pin assignment problem is to determine positions of the pins of nets on the top and the bottom sides of a channel, which are partitioned into several intervals, and the pins are permutable within their associated intervals. The channel pin assignment problem has been shown NP-hard in general. We present a linear time optimal algorithm for an important special case of the problem, in which there is at most one pin of a net within each interval in the channel. The proposed algorithm is optimal in a sense that it can minimize both the channel density and the total wire length of the channel. We also disscuss how to apply our algorithm to the pin assignment in the L-shaped and staircase channels. Experimental results indicate that substantial reduction in both channel density and estimated total wire length can be obtained by permuting pins in each interval. Combining the proposed algorithm with a conventional channel router, results of channel routing also achieve large amount of reduction of the number of tracks, total wire length, and the number of vias.
ER -