Channel/Switchbox Definition for VLSI Building-Block Layout

Yang Cai, D. F. Wong

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)1485-1493
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume10
Issue number12
DOIs
StatePublished - Dec 1991
Externally publishedYes

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Channel/Switchbox Definition for VLSI Building-Block Layout'. Together they form a unique fingerprint.

Cite this