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
StatePublished - Jun 1 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

Fingerprint

Routers
Decomposition

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Cai, Y., & Wong, D. F. (1991). On minimizing the number of L-shaped channels. In 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.

Proceedings - Design Automation Conference. Publ by IEEE, 1991. p. 328-334 (Proceedings - Design Automation Conference).

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

Cai, Y & Wong, DF 1991, On minimizing the number of L-shaped channels. in 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.
Cai Y, Wong DF. On minimizing the number of L-shaped channels. In Proceedings - Design Automation Conference. Publ by IEEE. 1991. p. 328-334. (Proceedings - Design Automation Conference).
Cai, Yang ; Wong, D. F. / On minimizing the number of L-shaped channels. Proceedings - Design Automation Conference. Publ by IEEE, 1991. pp. 328-334 (Proceedings - Design Automation Conference).
@inproceedings{d77da3f4df0948ccb37b623ad6d293b2,
title = "On minimizing the number of L-shaped channels",
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.",
author = "Yang Cai and Wong, {D. F.}",
year = "1991",
month = "6",
day = "1",
language = "English (US)",
isbn = "0818691492",
series = "Proceedings - Design Automation Conference",
publisher = "Publ by IEEE",
pages = "328--334",
booktitle = "Proceedings - Design Automation Conference",

}

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 -