Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/77345300/34308
Title: 以神經網路處理佈線問題
Neural Network Approach to the Routing Problem
Authors: 國立臺灣師範大學資訊教育研究所
施保旭
馮武雄
張國恩
Shih, P. H.
Feng, W. S.
Chang, K. E.
Issue Date: 1-May-1991
Publisher: 中國工程師學會
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.
URI: http://rportal.lib.ntnu.edu.tw/handle/77345300/34308
ISSN: 0253-3839
Other Identifiers: ntnulib_tp_A0904_01_007
Appears in Collections:教師著作

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.