Channel density minimization by pin permutation

Yang Cai; D.F. Wong

doi:10.1109/ICCD.1992.276294

Channel density minimization by pin permutation

Yang Cai, D.F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding

Abstract

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 is presented. It compares favorably with the near-optimal algorithm of J. Cong and K.-Y. Khoo (1991) that runs in superlinear time. The present algorithm has important applications in hierarchical layout design of integrated circuits. In addition, it is shown that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.

Original language	English
Title of host publication	Proceedings of 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors
Publisher	IEEE
Pages	378-382
Number of pages	5
ISBN (Print)	0818631104
DOIs	https://doi.org/10.1109/ICCD.1992.276294
Publication status	Published - 14 Oct 1992
Event	1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors - Cambridge, MA, United States Duration: 11 Oct 1992 → 14 Oct 1992 https://ieeexplore.ieee.org/xpl/conhome/442/proceeding

Publication series

Name	IEEE International Conference on Computer Design: VLSI in Computers and Processors, ICCD

Conference

Conference	1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors
Country/Territory	United States
City	Cambridge, MA
Period	11/10/92 → 14/10/92
Internet address	https://ieeexplore.ieee.org/xpl/conhome/442/proceeding

User-Defined Keywords

Routing
Polynomials
Wire
Delta modulation
Minimization
Algorithm design and analysis
Circuits
Very large scale integration
Scholarships

Access to Document

10.1109/ICCD.1992.276294

Cite this

@inproceedings{8c97a4f916cc47cba8c19bb8057f91e4,

title = "Channel density minimization by pin permutation",

abstract = "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 is presented. It compares favorably with the near-optimal algorithm of J. Cong and K.-Y. Khoo (1991) that runs in superlinear time. The present algorithm has important applications in hierarchical layout design of integrated circuits. In addition, it is shown that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.",

keywords = "Routing, Polynomials, Wire, Delta modulation, Minimization, Algorithm design and analysis, Circuits, Very large scale integration, Scholarships",

author = "Yang Cai and D.F. Wong",

note = "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.; 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors ; Conference date: 11-10-1992 Through 14-10-1992",

year = "1992",

month = oct,

day = "14",

doi = "10.1109/ICCD.1992.276294",

language = "English",

isbn = "0818631104",

series = "IEEE International Conference on Computer Design: VLSI in Computers and Processors, ICCD",

publisher = "IEEE",

pages = "378--382",

booktitle = "Proceedings of 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/442/proceeding",

}

Cai, Y & Wong, DF 1992, Channel density minimization by pin permutation. in Proceedings of 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors. IEEE International Conference on Computer Design: VLSI in Computers and Processors, ICCD, IEEE, pp. 378-382, 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors, Cambridge, MA, United States, 11/10/92. https://doi.org/10.1109/ICCD.1992.276294

Channel density minimization by pin permutation. / Cai, Yang; Wong, D.F.
Proceedings of 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors. IEEE, 1992. p. 378-382 (IEEE International Conference on Computer Design: VLSI in Computers and Processors, ICCD).

Research output: Chapter in book/report/conference proceeding › Conference proceeding

TY - GEN

T1 - Channel density minimization by pin permutation

AU - Cai, Yang

AU - Wong, D.F.

N1 - 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.

PY - 1992/10/14

Y1 - 1992/10/14

N2 - 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 is presented. It compares favorably with the near-optimal algorithm of J. Cong and K.-Y. Khoo (1991) that runs in superlinear time. The present algorithm has important applications in hierarchical layout design of integrated circuits. In addition, it is shown that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.

AB - 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 is presented. It compares favorably with the near-optimal algorithm of J. Cong and K.-Y. Khoo (1991) that runs in superlinear time. The present algorithm has important applications in hierarchical layout design of integrated circuits. In addition, it is shown that the problem of minimizing wire length by permuting terminals is NP-hard in the strong sense.

KW - Routing

KW - Polynomials

KW - Wire

KW - Delta modulation

KW - Minimization

KW - Algorithm design and analysis

KW - Circuits

KW - Very large scale integration

KW - Scholarships

UR - https://ieeexplore.ieee.org/document/276294/

U2 - 10.1109/ICCD.1992.276294

DO - 10.1109/ICCD.1992.276294

M3 - Conference proceeding

SN - 0818631104

T3 - IEEE International Conference on Computer Design: VLSI in Computers and Processors, ICCD

SP - 378

EP - 382

BT - Proceedings of 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors

PB - IEEE

T2 - 1992 IEEE International Conference on Computer Design: VLSI in Computers & Processors

Y2 - 11 October 1992 through 14 October 1992

ER -

Channel density minimization by pin permutation

Abstract

Publication series

Conference

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this