Optimal Channel Pin Assignment

Yang Cai, D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

18 Citations (Scopus)


The authors study the channel pin assignment (CPA) problem subject to position constraints, order constraints, and separation constraints. The problem is to assign two sets of terminals to the top and the bottom of a channel to minimize channel density. It is shown that the problem is NP-hard in general and polynomial time-optimal algorithms are presented for a case where the relative orderings of the terminals on the top and the bottom of the channel are completely fixed. The problem of channel routing with movable modules is introduced, and it is shown that it is a special case of the CPA problem under the formulation, and can be solved optimally in polynomial time. How the algorithms can be incorporated into standard-cell and building-block layout systems is discussed. Experimental results indicate that substantial reduction in channel density can be obtained by allowing movable terminals.

Original languageEnglish
Pages (from-to)1413-1424
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number11
Publication statusPublished - Nov 1991

Scopus Subject Areas

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


Dive into the research topics of 'Optimal Channel Pin Assignment'. Together they form a unique fingerprint.

Cite this