Efficient algorithms for two and three-layer over-the-cell channel routing

We present a new efficient algorithm for both two and three-layer over-the-cell channel routing in the standard cell design technology. Our approach considers both density distribution in the channel and longest path in vertical constraint graph. Besides, we use vacant terminals to eliminate cycles in the vertical constraint graph as well as to reduce the maximum cliques in the horizontal constraint graph for selecting net segments to be routed over the cells. For the PRIMARY 1 benchmark examples, our router reduced the total channel height by 39.1% and 61.0% for two-layer and three-layer routing model, respectively