Algorithms for three-layer over-the-cell channel routing

The authors present a novel algorithm for three-layer, over-the-cell channel routing of standard cell designs. The novelty of the proposed approach lies in the use of ´vacant´ terminals for over-the-cell routing. Furthermore, the authors consider both the maximum cliques in the horizontal constraint graph and the longest paths in the vertical constraint graph as a basis for choosing the nets to route over the cells. They prove that their net selection algorithm is guaranteed to produce a solution within 68% of the optimum. The proposed algorithm has been implemented and tested on several benchmark examples. For the entire PRIMARY 1 benchmark, they reduce the total routing height by 76% as compared to a two-layer channel router, which leads to a 7% reduction in chip height.<>