TY - GEN
T1 - On minimizing the number of L-shaped channels
AU - Cai, Yang
AU - Wong, D. F.
PY - 1991/6
Y1 - 1991/6
N2 - The problem of minimizing the number of L-shaped channels in the routing region definition and ordering for building-block layouts is studied. Given a building-block layout of rectangular modules, the routing region is to be decomposed into straight and L-shaped channels and routed in a certain order. Since channel routers usually produce superior results, it is desirable to minimize the number of L-shaped channels used in such a decomposition. A fast algorithm that can produce provably better results than a previously proposed algorithm is presented. This algorithm is based on a study of the structure of such layouts, 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 to finish the computation, and it obtained up to 29% reduction in the number of L-shaped channels over the results produced by another algorithm.
AB - The problem of minimizing the number of L-shaped channels in the routing region definition and ordering for building-block layouts is studied. Given a building-block layout of rectangular modules, the routing region is to be decomposed into straight and L-shaped channels and routed in a certain order. Since channel routers usually produce superior results, it is desirable to minimize the number of L-shaped channels used in such a decomposition. A fast algorithm that can produce provably better results than a previously proposed algorithm is presented. This algorithm is based on a study of the structure of such layouts, 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 to finish the computation, and it obtained up to 29% reduction in the number of L-shaped channels over the results produced by another algorithm.
UR - http://www.scopus.com/inward/record.url?scp=0026175208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026175208&partnerID=8YFLogxK
U2 - 10.1145/127601.127689
DO - 10.1145/127601.127689
M3 - Conference contribution
AN - SCOPUS:0026175208
SN - 0818691492
SN - 9780818691492
T3 - Proceedings - Design Automation Conference
SP - 328
EP - 334
BT - Proceedings - Design Automation Conference
PB - Publ by IEEE
T2 - Proceedings of the 28th ACM/IEEE Design Automation Conference
Y2 - 17 June 1991 through 21 June 1991
ER -