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

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

Abstract

The problem of routing region definition in the VLSI building-block layout design style is addressed. An algorithm is presented to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. The 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. The algorithm was compared with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems considered, the new algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.

Original language	English (US)
Title of host publication	27th ACM/IEEE Design Automation Conference. Proceedings 1990
Publisher	Publ by IEEE
Pages	638-641
Number of pages	4
ISBN (Print)	081869650X
DOIs	https://doi.org/10.1145/123186.123425
State	Published - 1990
Externally published	Yes
Event	27th ACM/IEEE Design Automation Conference - Orlando, FL, USA Duration: Jun 24 1990 → Jun 28 1990

Publication series

Name	27th ACM/IEEE Design Automation Conference. Proceedings 1990

Other

Other	27th ACM/IEEE Design Automation Conference
City	Orlando, FL, USA
Period	6/24/90 → 6/28/90

ASJC Scopus subject areas

Engineering(all)

Access to Document

10.1145/123186.123425

Fingerprint Dive into the research topics of 'A channel/switchbox definition algorithm for building-block layout'. Together they form a unique fingerprint.

Cite this

Cai, Y., & Wong, D. F. (1990). A channel/switchbox definition algorithm for building-block layout. In 27th ACM/IEEE Design Automation Conference. Proceedings 1990 (pp. 638-641). (27th ACM/IEEE Design Automation Conference. Proceedings 1990). Publ by IEEE. https://doi.org/10.1145/123186.123425

@inproceedings{34c3f84ad2cb48dda413c1b18bb00ecc,

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

abstract = "The problem of routing region definition in the VLSI building-block layout design style is addressed. An algorithm is presented to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. The 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. The algorithm was compared with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems considered, the new algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.",

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

year = "1990",

doi = "10.1145/123186.123425",

language = "English (US)",

isbn = "081869650X",

series = "27th ACM/IEEE Design Automation Conference. Proceedings 1990",

publisher = "Publ by IEEE",

pages = "638--641",

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

note = "27th ACM/IEEE Design Automation Conference ; Conference date: 24-06-1990 Through 28-06-1990",

}

TY - GEN

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

AU - Cai, Yang

AU - Wong, D. F.

PY - 1990

Y1 - 1990

N2 - The problem of routing region definition in the VLSI building-block layout design style is addressed. An algorithm is presented to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. The 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. The algorithm was compared with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems considered, the new algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.

AB - The problem of routing region definition in the VLSI building-block layout design style is addressed. An algorithm is presented to decompose the routing area into a set of straight channels and switchboxes such that the number of switchboxes in the decomposition is minimized. The 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. The algorithm was compared with a previously known greedy approach and an exhaustive search optimal algorithm. For all the test problems considered, the new algorithm consistently outperformed the greedy algorithm, and it produced optimal solutions in almost all cases.

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

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

U2 - 10.1145/123186.123425

DO - 10.1145/123186.123425

M3 - Conference contribution

AN - SCOPUS:0025550663

SN - 081869650X

T3 - 27th ACM/IEEE Design Automation Conference. Proceedings 1990

SP - 638

EP - 641

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

PB - Publ by IEEE

T2 - 27th ACM/IEEE Design Automation Conference

Y2 - 24 June 1990 through 28 June 1990

ER -