An optimum channel-routing algorithm for polycell layouts of integrated circuits

B. W. Kernighan; D. G. Schweikert; G. Persky

An optimum channel-routing algorithm for polycell layouts of integrated circuits

B. W. Kernighan
, D. G. Schweikert
, G. Persky

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

Abstract

This paper presents an algorithm for finding optimum routings for interconnection paths in a channel between two parallel rows of circuit cells. A routing algorithm thus need only avoid overlapping collinear horizontal segments of different nets, and avoid overlapping collinear vertical segments, to achieve a physically acceptable routing. The algorithm, although based on branch and bound, has provided optimum routings for circuits with 50 to 60 nets in a minute or two of computing.

Original language	English (US)
Article number	803997
Pages (from-to)	50-59
Number of pages	10
Journal	Proceedings - Design Automation Conference
State	Published - Jun 25 1973
Externally published	Yes
Event	10th Design Automation Workshop, DAC 1973 - Portland, United States Duration: Jun 25 1973 → Jun 27 1973

All Science Journal Classification (ASJC) codes

Computer Science Applications
Control and Systems Engineering
Electrical and Electronic Engineering
Modeling and Simulation

Cite this

@article{fd8366abc6bd482dab3ae20a9e557354,

title = "An optimum channel-routing algorithm for polycell layouts of integrated circuits",

abstract = "This paper presents an algorithm for finding optimum routings for interconnection paths in a channel between two parallel rows of circuit cells. A routing algorithm thus need only avoid overlapping collinear horizontal segments of different nets, and avoid overlapping collinear vertical segments, to achieve a physically acceptable routing. The algorithm, although based on branch and bound, has provided optimum routings for circuits with 50 to 60 nets in a minute or two of computing.",

author = "Kernighan, \{B. W.\} and Schweikert, \{D. G.\} and G. Persky",

note = "Publisher Copyright: {\textcopyright} 1973 Institute of Electrical and Electronics Engineers Inc..; 10th Design Automation Workshop, DAC 1973 ; Conference date: 25-06-1973 Through 27-06-1973",

year = "1973",

month = jun,

day = "25",

language = "English (US)",

pages = "50--59",

journal = "Proceedings - Design Automation Conference",

issn = "0738-100X",

}

TY - JOUR

T1 - An optimum channel-routing algorithm for polycell layouts of integrated circuits

AU - Kernighan, B. W.

AU - Schweikert, D. G.

AU - Persky, G.

PY - 1973/6/25

Y1 - 1973/6/25

N2 - This paper presents an algorithm for finding optimum routings for interconnection paths in a channel between two parallel rows of circuit cells. A routing algorithm thus need only avoid overlapping collinear horizontal segments of different nets, and avoid overlapping collinear vertical segments, to achieve a physically acceptable routing. The algorithm, although based on branch and bound, has provided optimum routings for circuits with 50 to 60 nets in a minute or two of computing.

AB - This paper presents an algorithm for finding optimum routings for interconnection paths in a channel between two parallel rows of circuit cells. A routing algorithm thus need only avoid overlapping collinear horizontal segments of different nets, and avoid overlapping collinear vertical segments, to achieve a physically acceptable routing. The algorithm, although based on branch and bound, has provided optimum routings for circuits with 50 to 60 nets in a minute or two of computing.

UR - https://www.scopus.com/pages/publications/84987006716

UR - https://www.scopus.com/pages/publications/84987006716#tab=citedBy

M3 - Conference article

AN - SCOPUS:84987006716

SN - 0738-100X

SP - 50

EP - 59

JO - Proceedings - Design Automation Conference

JF - Proceedings - Design Automation Conference

M1 - 803997

T2 - 10th Design Automation Workshop, DAC 1973

Y2 - 25 June 1973 through 27 June 1973

ER -

An optimum channel-routing algorithm for polycell layouts of integrated circuits

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this