Maximizing pin alignment in vlsi routing with movable terminals

Wu Shiung Feng

doi:10.1080/02533839.1990.9677236

Maximizing pin alignment in vlsi routing with movable terminals

Wu Shiung Feng^*

^*Corresponding author for this work

National Taiwan University

Research output: Contribution to journal › Journal Article › peer-review

Abstract

This paper addresses a new problem of aligning two rows of movable terminals in order to minimize the channel width and via usage in the channel. The alignment problem of movable terminals is subject to the constraint that the number of vertical tracks used is not increased in the process. This constraint is not considerated in the paper referred to [6] which first considered the alignment problem of movable terminals. This problem is first shown to be NP-complete, therefore, we present a heuristic algorithm. All examples presented in [2] including Deutsch’s difficult example are used as the test routing problems. The programs were coded in C and implemented on SUN 3/110 workstation.

Original language	English
Pages (from-to)	103-114
Number of pages	12
Journal	Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume	13
Issue number	1
DOIs	https://doi.org/10.1080/02533839.1990.9677236
State	Published - 01 1990
Externally published	Yes

Keywords

Channel routing
Movable terminal
Pin alignment

Access to Document

10.1080/02533839.1990.9677236

Cite this

@article{2687e0b983e54864b423e6f93996bffa,

title = "Maximizing pin alignment in vlsi routing with movable terminals",

abstract = "This paper addresses a new problem of aligning two rows of movable terminals in order to minimize the channel width and via usage in the channel. The alignment problem of movable terminals is subject to the constraint that the number of vertical tracks used is not increased in the process. This constraint is not considerated in the paper referred to [6] which first considered the alignment problem of movable terminals. This problem is first shown to be NP-complete, therefore, we present a heuristic algorithm. All examples presented in [2] including Deutsch{\textquoteright}s difficult example are used as the test routing problems. The programs were coded in C and implemented on SUN 3/110 workstation.",

keywords = "Channel routing, Movable terminal, Pin alignment",

author = "Feng, {Wu Shiung}",

year = "1990",

month = jan,

doi = "10.1080/02533839.1990.9677236",

language = "英语",

volume = "13",

pages = "103--114",

journal = "Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an",

issn = "0253-3839",

publisher = "Taylor and Francis Ltd.",

number = "1",

}

TY - JOUR

T1 - Maximizing pin alignment in vlsi routing with movable terminals

AU - Feng, Wu Shiung

PY - 1990/1

Y1 - 1990/1

N2 - This paper addresses a new problem of aligning two rows of movable terminals in order to minimize the channel width and via usage in the channel. The alignment problem of movable terminals is subject to the constraint that the number of vertical tracks used is not increased in the process. This constraint is not considerated in the paper referred to [6] which first considered the alignment problem of movable terminals. This problem is first shown to be NP-complete, therefore, we present a heuristic algorithm. All examples presented in [2] including Deutsch’s difficult example are used as the test routing problems. The programs were coded in C and implemented on SUN 3/110 workstation.

AB - This paper addresses a new problem of aligning two rows of movable terminals in order to minimize the channel width and via usage in the channel. The alignment problem of movable terminals is subject to the constraint that the number of vertical tracks used is not increased in the process. This constraint is not considerated in the paper referred to [6] which first considered the alignment problem of movable terminals. This problem is first shown to be NP-complete, therefore, we present a heuristic algorithm. All examples presented in [2] including Deutsch’s difficult example are used as the test routing problems. The programs were coded in C and implemented on SUN 3/110 workstation.

KW - Channel routing

KW - Movable terminal

KW - Pin alignment

UR - http://www.scopus.com/inward/record.url?scp=0025211972&partnerID=8YFLogxK

U2 - 10.1080/02533839.1990.9677236

DO - 10.1080/02533839.1990.9677236

M3 - 文章

AN - SCOPUS:0025211972

SN - 0253-3839

VL - 13

SP - 103

EP - 114

JO - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

JF - Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an

IS - 1

ER -

Maximizing pin alignment in vlsi routing with movable terminals

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this