Neural computation network for global routing

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

doi:10.1016/0010-4485(91)90054-Z

Neural computation network for global routing

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

^*Corresponding author for this work

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

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 language	English
Pages (from-to)	539-547
Number of pages	9
Journal	Computer-Aided Design
Volume	23
Issue number	8
DOIs	https://doi.org/10.1016/0010-4485(91)90054-Z
Publication status	Published - 1991 Oct

ASJC Scopus subject areas

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

Access to Document

10.1016/0010-4485(91)90054-Z

Cite this

@article{013cfed4e21f4575b7c0410e903493b5,

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 = oct,

doi = "10.1016/0010-4485(91)90054-Z",

language = "English",

volume = "23",

pages = "539--547",

journal = "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

SN - 0010-4485

VL - 23

SP - 539

EP - 547

JO - Computer-Aided Design

JF - Computer-Aided Design

IS - 8

ER -

Neural computation network for global routing

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this