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 |
| State | Published - Dec 1 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 |
Fingerprint
ASJC Scopus subject areas
- Engineering(all)
Cite this
A channel/switchbox definition algorithm for building-block layout. / Cai, Yang; Wong, D. F.
27th ACM/IEEE Design Automation Conference. Proceedings 1990. Publ by IEEE, 1990. p. 638-641 (27th ACM/IEEE Design Automation Conference. Proceedings 1990).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
}
TY - GEN
T1 - A channel/switchbox definition algorithm for building-block layout
AU - Cai, Yang
AU - Wong, D. F.
PY - 1990/12/1
Y1 - 1990/12/1
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
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
ER -