A graph theoretic approach to feed-through pin assignment

Y.-P. Chen, D.F. Wong

Research output: Contribution to journalJournal articlepeer-review


We study in this paper the feed-through pin assignment problem for cell-based design that assigns global nets to feed-through cells or implicit feed-through ports. On a single row, for a restricted permutation of global nets, we develop a graph theoretic approach for optimally minimizing the density of the channel above (below) the row subject to the bound on the density of the channel below (above) the row. Based on this technique, an approach for iteratively improving multiple row feed-through pin assignment can be developed. We show that our approach is also applicable to the design style in which there is an over-the-cell feed-through layer.

Original languageEnglish
Pages (from-to)147-158
Number of pages12
JournalIntegration, the VLSI Journal
Issue number2
Publication statusPublished - Dec 1997

Scopus Subject Areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Feed-through pin
  • Graphy theory
  • Routing
  • Standard cell

Cite this