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 .
|Number of pages||13|
|Journal||IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems|
|Publication status||Published - Jun 1993|
Scopus Subject Areas
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering