Efficient Via Shifting Algorithms in Channel Compaction

Yang Cai, D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


We consider in this paper the problem of shifting vias to obtain more compactable channel routing solutions. Let S be a grid-based two-layer channel routing solution. Let vc, wcbe the number of grid points on column c that are occupied by vias, horizontal wires in S, respectively. We define the expected height of columns c in S to be hc = Avc + Bwc + C, where A, B, C are some design rule dependent constants. A column in S is said to be a critical column if it has maximum expected height among all columns in S. Let Hs= maxchcbe the expected height of the critical column(s) of S. Hsis an estimation of the height of S after compaction. We show that the problem of shifting vias to minimize Hscan be solved optimally in polynomial time.

Original languageEnglish
Pages (from-to)1848-1857
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number12
Publication statusPublished - Dec 1993

Scopus Subject Areas

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


Dive into the research topics of 'Efficient Via Shifting Algorithms in Channel Compaction'. Together they form a unique fingerprint.

Cite this