EFFICIENT HEIGHT REDUCTION OVER-THE-CELL CHANNEL ROUTER

The authors present a new algorithm for both two-layer and three-layer over-the-cell channel routing in the standard cell VLSI design. The a pproach exploits vacant terminals on the channel boundary effectively. It considers the following factors simultaneously to select net segme nts for routing over the cells: density distribution in the channel, t he longest path in the vertical constraint graph, elimination of cycle s in the vertical constraint graph and reduction in maximum cliques in the horizontal constraint graph. With respect to the PRIMARY 1 benchm ark examples, the router achieved a 41.3% improvement over the Greedy channel router (one without using over-the-cell area) for a two-layer routing model and a 61.0% improvement for a three-layer routing model. This outperforms all previous algorithms.