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 |
Fingerprint
ASJC Scopus subject areas
- Engineering(all)
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
}
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
ER -