Please use this identifier to cite or link to this item:
Title: Reducing Channel Density by Routing Over the Cells
Other Titles: 以過晶元佈線方式減少通道密度
Authors: 張國恩
Issue Date: Jun-1993
Publisher: 國立臺灣師範大學研究發展處
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.
Other Identifiers: EA7E61BB-6FB1-FCFF-D7C3-CCD3AB909033
Appears in Collections:師大學報

Files in This Item:
File SizeFormat 
ntnulib_ja_L0801_0038_019.pdf399.41 kBAdobe PDFView/Open

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