Reducing Channel Density by Routing Over the Cells
No Thumbnail Available
Date
1993-06-??
Authors
張國恩
Journal Title
Journal ISSN
Volume Title
Publisher
國立臺灣師範大學研究發展處
Office of Research and Development
Office of Research and Development
Abstract
本文提出一個線性時間之演算法以完成過晶元佈線，該佈線可以有效地減少最大通道密度。此演算法首先以新的通道表示方式描述問題，並建立二個交叉圖形模式。然後針對每一個交叉圖形各找出獨立集合以代表可以有效地完成過晶元佈線之部份網列連線。本文中之演算法已完成程式設計，並以著名的實例完成測試評估。和以前之研究成果比較，本演算法可以在較短之執行時間內得到良好的結果。
A linear time algorithm for greater reduction of maximum channel density by routing over the cells is presented. The algorithm first models theproblem as a new scheme of zone representation and two intersected graphsfor two sides of the channel. Then, a feasible independent set of each graphis found to represent the subnets that are efficient to be routed over the cellsat the corresponding side of channel. The algorithm is implemented andevaluated by the tests of famous benchmarks. In comparison with previous research, our results are satisfactory while the algorithm takes less CPU timethan those of previous works. For Deutsch's difficult example, the previousalgorithm takes about 29.25 seconds while we need only 5.6 seconds.
A linear time algorithm for greater reduction of maximum channel density by routing over the cells is presented. The algorithm first models theproblem as a new scheme of zone representation and two intersected graphsfor two sides of the channel. Then, a feasible independent set of each graphis found to represent the subnets that are efficient to be routed over the cellsat the corresponding side of channel. The algorithm is implemented andevaluated by the tests of famous benchmarks. In comparison with previous research, our results are satisfactory while the algorithm takes less CPU timethan those of previous works. For Deutsch's difficult example, the previousalgorithm takes about 29.25 seconds while we need only 5.6 seconds.