### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - Design Automation Conference |

Publisher | Publ by IEEE |

Pages | 328-334 |

Number of pages | 7 |

ISBN (Print) | 0818691492 |

State | Published - Jun 1 1991 |

Externally published | Yes |

Event | Proceedings of the 28th ACM/IEEE Design Automation Conference - San Francisco, CA, USA Duration: Jun 17 1991 → Jun 21 1991 |

### Publication series

Name | Proceedings - Design Automation Conference |
---|---|

ISSN (Print) | 0146-7123 |

### Other

Other | Proceedings of the 28th ACM/IEEE Design Automation Conference |
---|---|

City | San Francisco, CA, USA |

Period | 6/17/91 → 6/21/91 |

### Fingerprint

### ASJC Scopus subject areas

- Engineering(all)

### Cite this

*Proceedings - Design Automation Conference*(pp. 328-334). (Proceedings - Design Automation Conference). Publ by IEEE.

**On minimizing the number of L-shaped channels.** / Cai, Yang; Wong, D. F.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Proceedings - Design Automation Conference.*Proceedings - Design Automation Conference, Publ by IEEE, pp. 328-334, Proceedings of the 28th ACM/IEEE Design Automation Conference, San Francisco, CA, USA, 6/17/91.

}

TY - GEN

T1 - On minimizing the number of L-shaped channels

AU - Cai, Yang

AU - Wong, D. F.

PY - 1991/6/1

Y1 - 1991/6/1

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

M3 - Conference contribution

AN - SCOPUS:0026175208

SN - 0818691492

T3 - Proceedings - Design Automation Conference

SP - 328

EP - 334

BT - Proceedings - Design Automation Conference

PB - Publ by IEEE

ER -