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. >
['Nancy D. Holmes', 'Naveed A. Sherwani', 'Majid Sarrafzadeh']
Algorithms for three-layer over-the-cell channel routing