A new over-the-cell channel router

A new over-the-cell channel router is presented. The authors solved the over-the-cell problem in two phases: (1) routing over cells, and (2) routing within the channel. The first phase reduces the channel density as far as possible by routing some critical nets over the cells. It was found that only the critical nets being routed over the cell may reduce the channel density. The maximum density segment (MDS) in the channel is defined, and the nets to be routed over the cells were chosen among the nets which cover the MDSs, so that the channel density was likely to be reduced. The second phase can be done by using a conventional channel router. The algorithm was coded in C and implemented on a SUN4/110 workstation. The experimental results are comparable to or better than previously published results