以神經網路處理佈線問題
No Thumbnail Available
Date
1991-05-01
Authors
施保旭
馮武雄
張國恩
Shih, P. H.
Feng, W. S.
Chang, K. E.
Journal Title
Journal ISSN
Volume Title
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.
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.