Reducing Channel Density in Standard Cell Layout

The problem of global routing in standard cell layouts so as to minimize total channel density is considered. A sub-problem of this, called the linear net routing problem (LNRP), is defined and is argued to be the key to a successful solution to the general problem. A polynomial-time heuristic for LNRP is presented and its behavior analyzed. In particular, it is proven that the heuristic can produce results as bad as, but no worse than, 50% over the optimal.