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

Fingerprint

Polynomials
Computational complexity

ASJC Scopus subject areas

  • Engineering(all)

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.

An optimal channel pin assignment algorithm. / Cai, Yang; Wong, D. F.

1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. Publ by IEEE, 1990. p. 10-13 (1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers).

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

Cai, Y & Wong, DF 1990, An optimal channel pin assignment algorithm. in 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers, Publ by IEEE, pp. 10-13, 1990 IEEE International Conference on Computer-Aided Design - ICCAD-90, Santa Clara, CA, USA, 11/11/90.
Cai Y, Wong DF. An optimal channel pin assignment algorithm. In 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. Publ by IEEE. 1990. p. 10-13. (1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers).
Cai, Yang ; Wong, D. F. / An optimal channel pin assignment algorithm. 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers. Publ by IEEE, 1990. pp. 10-13 (1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers).
@inproceedings{9832e8d6a3f74c959e78462125411a9f,
title = "An optimal channel pin assignment algorithm",
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.",
author = "Yang Cai and Wong, {D. F.}",
year = "1990",
month = "12",
day = "1",
language = "English (US)",
isbn = "0818620552",
series = "1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers",
publisher = "Publ by IEEE",
pages = "10--13",
booktitle = "1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers",

}

TY - GEN

T1 - An optimal channel pin assignment algorithm

AU - Cai, Yang

AU - Wong, D. F.

PY - 1990/12/1

Y1 - 1990/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025545068&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025545068&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0025545068

SN - 0818620552

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

SP - 10

EP - 13

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

PB - Publ by IEEE

ER -