Neural Network Approach to the Routing Problem

施 保旭, Wu-Shiung Feng, 張 國恩

Research output: Contribution to journalJournal Article peer-review

Abstract

     在VLSI佈局中,佈線問題是一個很重要的部份,其工作在於將給定的連線要求予 以正確的完成。此問題已被證明為 NP -完全性問題。目前所見的方法大多是採用啟發式的 演算法。 本論文提出一套植基於 Hopfield and Tank 模型的新型神經網路架構來解決佈線 的問題。我們將所有的連線要求一次同時加以考慮。使用神經網路的平行架構來解 NP -完 全性問題已被證明為一有效的方法,然而,將此法使用於佈線問題,本文則是首創。這套架 構是由兩層的神經元所組成。第一層負責使連線的長度最小,以及分佈最平均。第二層則是 負責處理通道滿溢的問題。本文亦證明此網路可以收斂至一個穩定的狀態。我們使用一組隨 機產生的資料來加以測試的結果,本網路可以將連線的長度減少 20 %左右。 
     The routing problem of VLSI layout is to realize the interconnection requirements of the given netlists. This proplem 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 slove 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 languageAmerican English
Pages (from-to)295-305
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
StatePublished - 1991

Fingerprint

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

Cite this