Channel/Switchbox Definition for VLSI Building-Block Layout

Yang Cai; D. F. Wong

doi:10.1109/43.103498

Channel/Switchbox Definition for VLSI Building-Block Layout

Yang Cai, D. F. Wong

Office of the Provost

Research output: Contribution to journal › Journal article › peer-review

5 Citations (Scopus)

Abstract

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

Original language	English
Pages (from-to)	1485-1493
Number of pages	9
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	10
Issue number	12
DOIs	https://doi.org/10.1109/43.103498
Publication status	Published - Dec 1991

Scopus Subject Areas

Software
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1109/43.103498

Cite this

@article{c91679fe8f124314af754cfd016a87f2,

title = "Channel/Switchbox Definition for VLSI Building-Block Layout",

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

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

note = "Funding Information: Manuscript received September 24, 1990. This work was 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. This paper was recommended by Associate Editor M. Marek-Sadowska.",

year = "1991",

month = dec,

doi = "10.1109/43.103498",

language = "English",

volume = "10",

pages = "1485--1493",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "IEEE",

number = "12",

}

TY - JOUR

T1 - Channel/Switchbox Definition for VLSI Building-Block Layout

AU - Cai, Yang

AU - Wong, D. F.

N1 - Funding Information: Manuscript received September 24, 1990. This work was 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. This paper was recommended by Associate Editor M. Marek-Sadowska.

PY - 1991/12

Y1 - 1991/12

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

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

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

U2 - 10.1109/43.103498

DO - 10.1109/43.103498

M3 - Journal article

AN - SCOPUS:0026389599

SN - 0278-0070

VL - 10

SP - 1485

EP - 1493

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 12

ER -

Channel/Switchbox Definition for VLSI Building-Block Layout

Abstract

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this