### 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 language | English (US) |
---|---|

Title of host publication | 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers |

Publisher | Publ by IEEE |

Pages | 10-13 |

Number of pages | 4 |

ISBN (Print) | 0818620552 |

State | Published - Dec 1 1990 |

Externally published | Yes |

Event | 1990 IEEE International Conference on Computer-Aided Design - ICCAD-90 - Santa Clara, CA, USA Duration: Nov 11 1990 → Nov 15 1990 |

### Publication series

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

### Other

Other | 1990 IEEE International Conference on Computer-Aided Design - ICCAD-90 |
---|---|

City | Santa Clara, CA, USA |

Period | 11/11/90 → 11/15/90 |

### Fingerprint

### ASJC Scopus subject areas

- Engineering(all)

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

}

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 -