Channel Density Minimization by Pin Permutation

Yang Cai; D. F. Wong; Jason Cong

doi:10.1155/1994/68279

Channel Density Minimization by Pin Permutation

Yang Cai, D. F. Wong, Jason Cong

Office of the Provost

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

Abstract

We present in this paper a linear time optimal algorithm for minimizing the density of a channel (with exits) by permuting the terminals on the two sides of the channel. This compares favorably with the previously known near-optimal algorithm presented in [6] that runs in superlinear time. Our algorithm has important applications in hierarchical layout design of intergrated circuits. We also show that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.

Original language	English
Pages (from-to)	171-183
Number of pages	13
Journal	VLSI Design
Volume	2
Issue number	Special Issue
DOIs	https://doi.org/10.1155/1994/68279
Publication status	Published - Jan 1994

Scopus Subject Areas

Hardware and Architecture
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

User-Defined Keywords

VLSI
Circuit layout
Channel routing
Pin assignment
Pin permutation

Access to Document

10.1155/1994/68279

Cite this

@article{def19a8736b542a0a7f0a0be62d2f72f,

title = "Channel Density Minimization by Pin Permutation",

abstract = "We present in this paper a linear time optimal algorithm for minimizing the density of a channel (with exits) by permuting the terminals on the two sides of the channel. This compares favorably with the previously known near-optimal algorithm presented in [6] that runs in superlinear time. Our algorithm has important applications in hierarchical layout design of intergrated circuits. We also show that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.",

keywords = "VLSI, Circuit layout, Channel routing, Pin assignment, Pin permutation",

author = "Yang Cai and Wong, {D. F.} and Jason Cong",

note = "Funding Information: This work was partially supported by the National Science Foundation under grant MIP-8909586, by an IBM Faculty Development Award, and by an ACM SIGDA scholarship. Publisher Copyright: {\textcopyright} 1994 Hindawi Publishing Corporation. Distributed under the Creative Commons Attribution License.",

year = "1994",

month = jan,

doi = "10.1155/1994/68279",

language = "English",

volume = "2",

pages = "171--183",

journal = "VLSI Design",

issn = "1065-514X",

publisher = "Hindawi Publishing Corporation",

number = "Special Issue",

}

TY - JOUR

T1 - Channel Density Minimization by Pin Permutation

AU - Cai, Yang

AU - Wong, D. F.

AU - Cong, Jason

N1 - Funding Information: This work was partially supported by the National Science Foundation under grant MIP-8909586, by an IBM Faculty Development Award, and by an ACM SIGDA scholarship. Publisher Copyright: © 1994 Hindawi Publishing Corporation. Distributed under the Creative Commons Attribution License.

PY - 1994/1

Y1 - 1994/1

N2 - We present in this paper a linear time optimal algorithm for minimizing the density of a channel (with exits) by permuting the terminals on the two sides of the channel. This compares favorably with the previously known near-optimal algorithm presented in [6] that runs in superlinear time. Our algorithm has important applications in hierarchical layout design of intergrated circuits. We also show that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.

AB - We present in this paper a linear time optimal algorithm for minimizing the density of a channel (with exits) by permuting the terminals on the two sides of the channel. This compares favorably with the previously known near-optimal algorithm presented in [6] that runs in superlinear time. Our algorithm has important applications in hierarchical layout design of intergrated circuits. We also show that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.

KW - VLSI

KW - Circuit layout

KW - Channel routing

KW - Pin assignment

KW - Pin permutation

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

U2 - 10.1155/1994/68279

DO - 10.1155/1994/68279

M3 - Journal article

AN - SCOPUS:0028576299

SN - 1065-514X

VL - 2

SP - 171

EP - 183

JO - VLSI Design

JF - VLSI Design

IS - Special Issue

ER -

Channel Density Minimization by Pin Permutation

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this