Minimizing channel density by shifting blocks and terminals

Yang Cai; D. F. Wong

Minimizing channel density by shifting blocks and terminals

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

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 language	English (US)
Title of host publication	1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers
Publisher	Publ by IEEE
Pages	524-527
Number of pages	4
ISBN (Print)	0818621575
State	Published - Dec 1 1992
Externally published	Yes
Event	1991 IEEE International Conference on Computer-Aided Design - ICCAD-91 - Santa Clara, CA, USA Duration: Nov 11 1991 → Nov 14 1991

Publication series

Name	1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers

Other

Other	1991 IEEE International Conference on Computer-Aided Design - ICCAD-91
City	Santa Clara, CA, USA
Period	11/11/91 → 11/14/91

ASJC Scopus subject areas

Engineering(all)

Access to Document

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

Cite this

Minimizing channel density by shifting blocks and terminals. / Cai, Yang; Wong, D. F.

1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers. Publ by IEEE, 1992. p. 524-527 (1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers).

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

Cai, Y & Wong, DF 1992, Minimizing channel density by shifting blocks and terminals. in 1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers. 1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers, Publ by IEEE, pp. 524-527, 1991 IEEE International Conference on Computer-Aided Design - ICCAD-91, Santa Clara, CA, USA, 11/11/91.

@inproceedings{7616c3c367434752980dec02b31c5ef5,

title = "Minimizing channel density by shifting blocks and terminals",

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.",

author = "Yang Cai and Wong, {D. F.}",

year = "1992",

month = dec,

day = "1",

language = "English (US)",

isbn = "0818621575",

series = "1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers",

publisher = "Publ by IEEE",

pages = "524--527",

booktitle = "1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers",

note = "1991 IEEE International Conference on Computer-Aided Design - ICCAD-91 ; Conference date: 11-11-1991 Through 14-11-1991",

}

TY - GEN

T1 - Minimizing channel density by shifting blocks and terminals

AU - Cai, Yang

AU - Wong, D. F.

PY - 1992/12/1

Y1 - 1992/12/1

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0027084974

SN - 0818621575

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

SP - 524

EP - 527

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

PB - Publ by IEEE

T2 - 1991 IEEE International Conference on Computer-Aided Design - ICCAD-91

Y2 - 11 November 1991 through 14 November 1991

ER -