A channel/switchbox definition algorithm for building-block layout

Yang Cai; D. F. Wong

doi:10.1145/123186.123425

A channel/switchbox definition algorithm for building-block layout

Yang Cai, D. F. Wong

Office of the Provost

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

5 Citations (Scopus)

Abstract

In this paper we study the problem of routing region definition in the VLSI building-block layout design style. We present an algorithm to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. Our algorithm is based on a graph-theoretic approach that makes use of an efficient polynomial time optimal algorithm for computing minimum clique covers of triangulated graphs. Experimental results indicate our algorithm performs well. We compared our algorithm with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems we considered, our algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.

Original language	English
Title of host publication	27th ACM/IEEE Design Automation Conference - Proceedings 1990
Publisher	Association for Computing Machinery (ACM)
Pages	638-641
Number of pages	4
ISBN (Print)	081869650X, 9780897913638, 0897913639
DOIs	https://doi.org/10.1145/123186.123425
Publication status	Published - Jan 1991
Event	27th ACM/IEEE Design Automation Conference, DAC 1990 - Orlando, United States Duration: 24 Jun 1990 → 27 Jun 1990 https://dl.acm.org/doi/proceedings/10.1145/123186 https://ieeexplore.ieee.org/xpl/conhome/790/proceeding

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	27th ACM/IEEE Design Automation Conference, DAC 1990
Country/Territory	United States
City	Orlando
Period	24/06/90 → 27/06/90
Internet address	https://dl.acm.org/doi/proceedings/10.1145/123186 https://ieeexplore.ieee.org/xpl/conhome/790/proceeding

Scopus Subject Areas

General Engineering

Access to Document

10.1145/123186.123425

Cite this

@inproceedings{4065e907bd8a48a68a6685d748064144,

title = "A channel/switchbox definition algorithm for building-block layout",

abstract = "In this paper we study the problem of routing region definition in the VLSI building-block layout design style. We present an algorithm to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. Our algorithm is based on a graph-theoretic approach that makes use of an efficient polynomial time optimal algorithm for computing minimum clique covers of triangulated graphs. Experimental results indicate our algorithm performs well. We compared our algorithm with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems we considered, our algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.",

author = "Yang Cai and Wong, {D. F.}",

note = "This 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.; 27th ACM/IEEE Design Automation Conference, DAC 1990 ; Conference date: 24-06-1990 Through 27-06-1990",

year = "1991",

month = jan,

doi = "10.1145/123186.123425",

language = "English",

isbn = "081869650X",

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

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

pages = "638--641",

booktitle = "27th ACM/IEEE Design Automation Conference - Proceedings 1990",

address = "United States",

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

}

Cai, Y & Wong, DF 1991, A channel/switchbox definition algorithm for building-block layout. in 27th ACM/IEEE Design Automation Conference - Proceedings 1990. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 638-641, 27th ACM/IEEE Design Automation Conference, DAC 1990, Orlando, Florida, United States, 24/06/90. https://doi.org/10.1145/123186.123425

A channel/switchbox definition algorithm for building-block layout. / Cai, Yang; Wong, D. F.
27th ACM/IEEE Design Automation Conference - Proceedings 1990. Association for Computing Machinery (ACM), 1991. p. 638-641 (ACM/IEEE Design Automation Conference - Proceedings).

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

TY - GEN

T1 - A channel/switchbox definition algorithm for building-block layout

AU - Cai, Yang

AU - Wong, D. F.

N1 - This 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/1

Y1 - 1991/1

N2 - In this paper we study the problem of routing region definition in the VLSI building-block layout design style. We present an algorithm to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. Our algorithm is based on a graph-theoretic approach that makes use of an efficient polynomial time optimal algorithm for computing minimum clique covers of triangulated graphs. Experimental results indicate our algorithm performs well. We compared our algorithm with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems we considered, our algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.

AB - In this paper we study the problem of routing region definition in the VLSI building-block layout design style. We present an algorithm to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. Our algorithm is based on a graph-theoretic approach that makes use of an efficient polynomial time optimal algorithm for computing minimum clique covers of triangulated graphs. Experimental results indicate our algorithm performs well. We compared our algorithm with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems we considered, our algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.

UR - https://dl.acm.org/doi/10.1145/123186.123425

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

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

U2 - 10.1145/123186.123425

DO - 10.1145/123186.123425

M3 - Conference proceeding

AN - SCOPUS:0025550663

SN - 081869650X

SN - 9780897913638

SN - 0897913639

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 638

EP - 641

BT - 27th ACM/IEEE Design Automation Conference - Proceedings 1990

PB - Association for Computing Machinery (ACM)

T2 - 27th ACM/IEEE Design Automation Conference, DAC 1990

Y2 - 24 June 1990 through 27 June 1990

ER -

A channel/switchbox definition algorithm for building-block layout

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this