以過晶元佈線方式減少通道密度 作者:張國恩(國立臺灣師範大學資訊教育研究所)

摘要：

本文提出一個線性時間之演算法以完成過晶元佈線，該佈線可以有效地減少最大通道密度。此演算法首先以新的通道表示方式描述問題，並建立二個交叉圖形模式。然後針對每一個交叉圖形各找出獨立集合以代表可以有效地完成過晶元佈線之部分網列連線。本文中之演算法已完成程式設計，並以著名的實例完成測試評估。和以 前之研究成果比較，本演算法可以在較短之執行時間內得到良好的結果。

《詳全文》

Reducing Channel Density by Routing Over The Cells Author: Kuo-En Chang(Department of Information and Computer Education, National Taiwan Normal University)

Abstract：

A linear time algorithm for greater reduction of maximum channel den-sity by routing over the cells is presented. The algorithm first models the problem as a new scheme of zone representation and two intersected graphs for two sides of the channel. Then, a feasible independent set of each graph is found to represent the subnets that are efficient to be routed over the cells at the corresponding side of channel. The algorithm is implemented and evaluated by the tests of famous benchmarks. In comparison with previous re-search, our results are satisfactory while the algorithm takes less CPU time than those of previous works. For Deutsch's difficult example, the previous algorithm takes about 29.25 seconds while we need only 5.6 seconds.