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.

《Full Text》