UTILIZATION OF VACANT TERMINALS FOR IMPROVED OVER-THE-CELL CHANNEL ROUTING

In this paper, we present a new algorithm called WISER for over-the-ce ll channel routing in the standard cell design style using the two-lay er routing model. The novelty of our approach lies in the use of ''vac ant'' terminals for over-the-cell routing. Furthermore, we consider lo ngest paths in the vertical constraint graph, as well as channel densi ty as a basis for choosing nets to route over the rows of standard cel ls. Our approximation algorithm for net selection produces provably go od results. Algorithm WISER has been implemented and tested on several benchmarks, including PRIMARY1 and Deutsch's difficult example. The e xperimental results show that WISER reduces the channel height by an a verage of 29%, as compared to conventional channel routers, and 15%, a s compared to existing over-the-cell routers. In addition, it reduces the total number of vias per routing by 32%.