A channel/switchbox definition algorithm for building-block layout

Yang Cai, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

5 Citations (Scopus)


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 languageEnglish
Title of host publication27th ACM/IEEE Design Automation Conference - Proceedings 1990
PublisherAssociation for Computing Machinery (ACM)
Number of pages4
ISBN (Print)081869650X, 9780897913638, 0897913639
Publication statusPublished - Jan 1991
Event27th ACM/IEEE Design Automation Conference, DAC 1990 - Orlando, United States
Duration: 24 Jun 199027 Jun 1990

Publication series

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


Conference27th ACM/IEEE Design Automation Conference, DAC 1990
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Engineering(all)


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

Cite this