Efficient height reduction over-the-cell channel router

Abstract: 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 approach exploits vacant terminals on the channel boundary effectively. It considers the fol-lowing factors simultaneously to select net seg-ments for routing over the cells: density distribution in the channel, the longest path in the vertical constraint graph, elimination of cycles in the vertical constraint graph and reduction in maximum cliques in the horizontal constraint graph. With respect to the PRIMARY 1 bench-mark examples, the router achieved a 41.3% improvement over the Greedy channel router (one without using over-thecell area) for a two-laye