Minimizing channel density by shifting blocks and terminals

Yang Cai, D.F. Wong

Research output: Chapter in book/report/conference proceedingConference proceeding

Abstract

The authors study the problem of minimizing channel density by shifting the blocks that form the sides of the channel and the terminals on the boundary of each block. Several special cases of this problem have been investigated, but no polynomial time algorithm was known for the general case. The authors present a polynomial time optimal algorithm for solving this problem. For long channels, they propose heuristic approaches to speed up the algorithm. Extensions as well as applications of the algorithm to detailed routing in building-block layout design are also discussed. Preliminary experimental results are very promising. Substantial reductions in routing area were obtained in moderate computation time.
Original languageEnglish
Title of host publication1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers
PublisherIEEE
Pages524-527
Number of pages4
ISBN (Print)0818621575
DOIs
Publication statusPublished - 14 Nov 1991
Event1991 IEEE International Conference on Computer-Aided Design, ICCAD 1991 - Santa Clara, United States
Duration: 11 Nov 199114 Nov 1991
https://ieeexplore.ieee.org/xpl/conhome/345/proceeding

Publication series

NameIEEE International Conference on Computer-Aided Design

Conference

Conference1991 IEEE International Conference on Computer-Aided Design, ICCAD 1991
Country/TerritoryUnited States
CitySanta Clara
Period11/11/9114/11/91
Internet address

User-Defined Keywords

  • Routing
  • Polynomials
  • Algorithm design and analysis
  • Physics computing
  • Very large scale integration
  • Circuits
  • Pins
  • Scholarships

Fingerprint

Dive into the research topics of 'Minimizing channel density by shifting blocks and terminals'. Together they form a unique fingerprint.

Cite this