On minimizing the number of L-shaped channels in building-block layout [VLSI]

Given a building-block layout of rectangular modules, the routing area is to be decomposed into straight and L-shaped channels and routed in a certain order. Since straight channels are easier to route and channel routers usually produce near-optimal results, it is desirable to minimize the number of L-shaped channels used in such a decomposition. An algorithm for minimizing the number of L-shaped channels used in the routing area decomposition is presented. The algorithm is based on a careful study of the structure of layouts of rectangular modules and a transformation of the original problem to a graph theoretical problem. For examples of up to 136 channels, the algorithm took less than one tenth of a second on a SUN SPARC station 1 to finish the computation and obtained up to 29% reduction in the mumber of L-shaped channels over the results produced by the algorithm of W.M. Dai et al. (1985)