An optimal channel pin assignment algorithm

Yang Cai, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A study is made of the channel pin assignment problem subject to both position and order constraints. The authors show that the problem is NP-hard in general and present a polynomial time optimal algorithm for an important case where the relative orderings of the terminals are completely fixed. They extend their algorithm to solve the problem for the case where there are also separation constraints between some pairs of consecutive terminals optimally in polynomial time. A discussion is presented of how the algorithm can be incorporated into standard cell and building-block layout design systems. Experimental results indicate that by allowing movable terminals, substantial reductions in channel density can be obtained.

Original languageEnglish (US)
Title of host publication1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers
PublisherPubl by IEEE
Pages10-13
Number of pages4
ISBN (Print)0818620552
StatePublished - Dec 1 1990
Externally publishedYes
Event1990 IEEE International Conference on Computer-Aided Design - ICCAD-90 - Santa Clara, CA, USA
Duration: Nov 11 1990Nov 15 1990

Publication series

Name1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers

Other

Other1990 IEEE International Conference on Computer-Aided Design - ICCAD-90
CitySanta Clara, CA, USA
Period11/11/9011/15/90

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'An optimal channel pin assignment algorithm'. Together they form a unique fingerprint.

  • Cite this

    Cai, Y., & Wong, D. F. (1990). An optimal channel pin assignment algorithm. In 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers (pp. 10-13). (1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers). Publ by IEEE.