Neural computation network for global routing

P. H. Shih, K. E. Chang, W. S. Feng

Research output: Contribution to journalArticle

Abstract

Global routing is a crucial step in circuit layout. Under the constraint of the relative positions of circuit blocks enforced by placement, the global routing develops an effective plan such that the interconnections of nets can be completed efficiently. This problem has been proven to be NP-complete, and most of the currently available algorithms are heuristic. The paper proposes a new neural-computation-network architecture based on the Hopfield and Tank model for the global-routing problem. This network is constructed using two layers of neurons. One layer is used for minimizing the total path length and distributing interconnecting wires evenly between channels. The other layer is used for channel-capacity enforcement. This network is proven to be able to converge to a stable state. A set of randomly generated testing examples are used to verify the performance of the approach. A reduction in total path length of about 20% is attained by this network.

Original languageEnglish
Pages (from-to)539-547
Number of pages9
JournalComputer-Aided Design
Volume23
Issue number8
DOIs
Publication statusPublished - 1991 Oct

Fingerprint

Integrated circuit layout
Channel capacity
Heuristic algorithms
Network architecture
Neurons
Routing
Wire
Path Length
Networks (circuits)
Testing
Channel Capacity
Routing Problem
Network Architecture
Interconnection
Placement
Layout
Neuron
NP-complete problem
Heuristics
Verify

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering

Cite this

Neural computation network for global routing. / Shih, P. H.; Chang, K. E.; Feng, W. S.

In: Computer-Aided Design, Vol. 23, No. 8, 10.1991, p. 539-547.

Research output: Contribution to journalArticle

Shih, P. H. ; Chang, K. E. ; Feng, W. S. / Neural computation network for global routing. In: Computer-Aided Design. 1991 ; Vol. 23, No. 8. pp. 539-547.
@article{9fc96aeefdc4499b93c20bd57d3eb240,
title = "Neural computation network for global routing",
abstract = "Global routing is a crucial step in circuit layout. Under the constraint of the relative positions of circuit blocks enforced by placement, the global routing develops an effective plan such that the interconnections of nets can be completed efficiently. This problem has been proven to be NP-complete, and most of the currently available algorithms are heuristic. The paper proposes a new neural-computation-network architecture based on the Hopfield and Tank model for the global-routing problem. This network is constructed using two layers of neurons. One layer is used for minimizing the total path length and distributing interconnecting wires evenly between channels. The other layer is used for channel-capacity enforcement. This network is proven to be able to converge to a stable state. A set of randomly generated testing examples are used to verify the performance of the approach. A reduction in total path length of about 20{\%} is attained by this network.",
author = "Shih, {P. H.} and Chang, {K. E.} and Feng, {W. S.}",
year = "1991",
month = "10",
doi = "10.1016/0010-4485(91)90054-Z",
language = "English",
volume = "23",
pages = "539--547",
journal = "CAD Computer Aided Design",
issn = "0010-4485",
publisher = "Elsevier Limited",
number = "8",

}

TY - JOUR

T1 - Neural computation network for global routing

AU - Shih, P. H.

AU - Chang, K. E.

AU - Feng, W. S.

PY - 1991/10

Y1 - 1991/10

N2 - Global routing is a crucial step in circuit layout. Under the constraint of the relative positions of circuit blocks enforced by placement, the global routing develops an effective plan such that the interconnections of nets can be completed efficiently. This problem has been proven to be NP-complete, and most of the currently available algorithms are heuristic. The paper proposes a new neural-computation-network architecture based on the Hopfield and Tank model for the global-routing problem. This network is constructed using two layers of neurons. One layer is used for minimizing the total path length and distributing interconnecting wires evenly between channels. The other layer is used for channel-capacity enforcement. This network is proven to be able to converge to a stable state. A set of randomly generated testing examples are used to verify the performance of the approach. A reduction in total path length of about 20% is attained by this network.

AB - Global routing is a crucial step in circuit layout. Under the constraint of the relative positions of circuit blocks enforced by placement, the global routing develops an effective plan such that the interconnections of nets can be completed efficiently. This problem has been proven to be NP-complete, and most of the currently available algorithms are heuristic. The paper proposes a new neural-computation-network architecture based on the Hopfield and Tank model for the global-routing problem. This network is constructed using two layers of neurons. One layer is used for minimizing the total path length and distributing interconnecting wires evenly between channels. The other layer is used for channel-capacity enforcement. This network is proven to be able to converge to a stable state. A set of randomly generated testing examples are used to verify the performance of the approach. A reduction in total path length of about 20% is attained by this network.

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

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

U2 - 10.1016/0010-4485(91)90054-Z

DO - 10.1016/0010-4485(91)90054-Z

M3 - Article

AN - SCOPUS:0026241074

VL - 23

SP - 539

EP - 547

JO - CAD Computer Aided Design

JF - CAD Computer Aided Design

SN - 0010-4485

IS - 8

ER -