On minimizing the number of L-shaped channels

Yang Cai, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
PublisherPubl by IEEE
Pages328-334
Number of pages7
ISBN (Print)0818691492, 9780818691492
DOIs
StatePublished - Jun 1991
Externally publishedYes
EventProceedings of the 28th ACM/IEEE Design Automation Conference - San Francisco, CA, USA
Duration: Jun 17 1991Jun 21 1991

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0146-7123

Other

OtherProceedings of the 28th ACM/IEEE Design Automation Conference
CitySan Francisco, CA, USA
Period6/17/916/21/91

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'On minimizing the number of L-shaped channels'. Together they form a unique fingerprint.

Cite this