On Minimizing the Number of L-Shaped Channels in Building-Block Layout

We study in this Paper the problem of minimizing the number of L-shaped channels in routing area decomposition for building-block layouts. 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. We present an algorithm for minimizing the number of L-shaped channels used in the routing area decomposition. Our algorithm is based on a careful study of the structure of layouts of rectangular modeules and a transformation of the original problem to a graph theoretical problem. For examples of up to 136 channels, our algorithm took less than one tenth of a second on a SUN SPARCstation 1 to finish the computation and obtained up to 29% reduction in the number of L-shaped channels over the results produced by the algorithm in [9].