On minimizing the number of L-shaped channels

Yang Cai; D. F. Wong

doi:10.1145/127601.127689

On minimizing the number of L-shaped channels

Yang Cai, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

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
Title of host publication	28th ACM/IEEE Design Automation Conference - Proceedings 1991
Publisher	Association for Computing Machinery (ACM)
Pages	328-334
Number of pages	7
ISBN (Electronic)	0818661496
ISBN (Print)	0818691492, 9780818691492, 9780897913959, 0897913957
DOIs	https://doi.org/10.1145/127601.127689
Publication status	Published - Jun 1991
Event	28th ACM/IEEE Design Automation Conference, DAC 1991 - San Francisco, United States Duration: 17 Jun 1991 → 21 Jun 1991 https://dl.acm.org/doi/proceedings/10.1145/127601 https://ieeexplore.ieee.org/xpl/conhome/7708/proceeding

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0146-7123

Conference

Conference	28th ACM/IEEE Design Automation Conference, DAC 1991
Country/Territory	United States
City	San Francisco
Period	17/06/91 → 21/06/91
Internet address	https://dl.acm.org/doi/proceedings/10.1145/127601 https://ieeexplore.ieee.org/xpl/conhome/7708/proceeding

Scopus Subject Areas

Engineering(all)

Access to Document

10.1145/127601.127689

Cite this

@inproceedings{721c7c37e3644e8c974dc899a0eb5626,

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.}",

note = "The work was partially supported by the National Science Foundation under grant MIP-8909586, by the Texas Advanced Research Program under grant 4096, and by an IBM Faculty Development Award.; 28th ACM/IEEE Design Automation Conference, DAC 1991 ; Conference date: 17-06-1991 Through 21-06-1991",

year = "1991",

month = jun,

doi = "10.1145/127601.127689",

language = "English",

isbn = "0818691492",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "328--334",

booktitle = "28th ACM/IEEE Design Automation Conference - Proceedings 1991",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/127601, https://ieeexplore.ieee.org/xpl/conhome/7708/proceeding",

}

Cai, Y & Wong, DF 1991, On minimizing the number of L-shaped channels. in 28th ACM/IEEE Design Automation Conference - Proceedings 1991. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 328-334, 28th ACM/IEEE Design Automation Conference, DAC 1991, San Francisco, California, United States, 17/06/91. https://doi.org/10.1145/127601.127689

TY - GEN

T1 - On minimizing the number of L-shaped channels

AU - Cai, Yang

AU - Wong, D. F.

N1 - The work was partially supported by the National Science Foundation under grant MIP-8909586, by the Texas Advanced Research Program under grant 4096, and by an IBM Faculty Development Award.

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 - https://dl.acm.org/doi/10.1145/127601.127689

UR - https://ieeexplore.ieee.org/document/979737

UR - http://www.scopus.com/inward/record.url?scp=0026175208&partnerID=8YFLogxK

U2 - 10.1145/127601.127689

DO - 10.1145/127601.127689

M3 - Conference proceeding

AN - SCOPUS:0026175208

SN - 0818691492

SN - 9780818691492

SN - 9780897913959

SN - 0897913957

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 328

EP - 334

BT - 28th ACM/IEEE Design Automation Conference - Proceedings 1991

PB - Association for Computing Machinery (ACM)

T2 - 28th ACM/IEEE Design Automation Conference, DAC 1991

Y2 - 17 June 1991 through 21 June 1991

ER -

On minimizing the number of L-shaped channels

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this