A fast algorithm for optimal via-shifting in channel compaction

Yang Cai, D. F. Wong

Research output: Contribution to journalConference articlepeer-review

Abstract

The authors consider the problem of shifting vias to obtain more compactable channel routing solutions. Given a grid-based two-layer channel routing solution S, one can obtain a new routing solution S' by simply shifting the vias in S. In this case, S' is said to be derivable from S. The authors address the problem of how to obtain a routing solution S' from S by shifting vias so that S' would achieve minimum channel height after compaction. They present some necessary preliminary material and give the boolean procedure which forms the backbone of the algorithm. They present the optimal algorithm for shifting for the channel routing solution. The worst-case time complexity of the algorithm is considered. The algorithm uses a technique which is similar to the greedy algorithm for computing a maximum matching for a special class of bipartite graphs called convex bipartite graphs.

Original languageEnglish (US)
Pages (from-to)1940-1943
Number of pages4
JournalProceedings - IEEE International Symposium on Circuits and Systems
Volume4
StatePublished - Dec 1 1991
Externally publishedYes
Event1991 IEEE International Symposium on Circuits and Systems Part 4 (of 5) - Singapore, Singapore
Duration: Jun 11 1991Jun 14 1991

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A fast algorithm for optimal via-shifting in channel compaction'. Together they form a unique fingerprint.

Cite this