Neural Network Approach To The Routing Problem

Pao Hsu Shih, Wu Shung Feng, Kuo En Chang

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The routing problem of VLSI layout is to realize the interconnection requirements of the given netlists. This problem is in the NP-complete class and most of the currently available algorithms are heuristic. This paper proposes a new architecture of neural network based on the Hopfield and Tank model for the routing problem. Our approach takes all interconnection requirements into consideration simultaneously. Using the massive parallelism of a neural network to solve NP-complete problems has been demonstrated to be an effective approach. However, applying this technique to the routing problem is still to be investigated. This network is constructed of two layers of neurons. One layer of neurons is used for minimizing the total path length and distributing interconnecting wires evenly among channels. The other layer of neurons is used for channel capacity enforcement. A set of randomly generated testing examples are used to verify the performance of our approach. About 15-20% reduction of total path length is achieved using this network.

Original languageEnglish
Pages (from-to)295-306
Number of pages12
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume14
Issue number3
DOIs
Publication statusPublished - 1991 Apr

Keywords

  • Circuit layout
  • Hopfield and Tank model
  • Neural network
  • Routing problem

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Neural Network Approach To The Routing Problem'. Together they form a unique fingerprint.

  • Cite this