A channel/switchbox definition algorithm for building-block layout

Yang Cai, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publication27th ACM/IEEE Design Automation Conference. Proceedings 1990
PublisherPubl by IEEE
Pages638-641
Number of pages4
ISBN (Print)081869650X
DOIs
StatePublished - 1990
Externally publishedYes
Event27th ACM/IEEE Design Automation Conference - Orlando, FL, USA
Duration: Jun 24 1990Jun 28 1990

Publication series

Name27th ACM/IEEE Design Automation Conference. Proceedings 1990

Other

Other27th ACM/IEEE Design Automation Conference
CityOrlando, FL, USA
Period6/24/906/28/90

ASJC Scopus subject areas

  • Engineering(all)

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