TY - GEN

T1 - Minimizing channel density by lateral shifting of components

AU - Johnson, D. S.

AU - LaPaugh, Andrea Suzanne

AU - Pinter, R. Y.

PY - 1994/1/1

Y1 - 1994/1/1

N2 - We consider a channel layout model in which we are free to change the spacing, but not the ordering, of the components on the top and bottom of a routing channel. The goal is to minimize channel density. Let N be the total number of terminals on top and bottom components. The main previous approach to this problem used dynamic programming and restricted the potential locations for components and their terminals to grid points along a one-dimensional line, yielding running times polynomial in L, where L is the length of the grid. To use such an algorithm in an environment where high-precision placement is possible, however, one must have a very fine grid, with L growing as Ω(N2) or worse. Consequently, the running time could grow very large as a function of N. We prove a key combinatorial lemma that implies that the run time for a grid-free dynamic programming algorithm can be polynomially bounded. Based on this lemma, a naive O(N5) algorithm is derived. We then show how this can be sped up to O(N3) by computing appropriately defined auxiliary functions. For certain instances of the problem in which all components are roughly the same size and have roughly √N terminals, we can further reduce the running time to O(N2.5).

AB - We consider a channel layout model in which we are free to change the spacing, but not the ordering, of the components on the top and bottom of a routing channel. The goal is to minimize channel density. Let N be the total number of terminals on top and bottom components. The main previous approach to this problem used dynamic programming and restricted the potential locations for components and their terminals to grid points along a one-dimensional line, yielding running times polynomial in L, where L is the length of the grid. To use such an algorithm in an environment where high-precision placement is possible, however, one must have a very fine grid, with L growing as Ω(N2) or worse. Consequently, the running time could grow very large as a function of N. We prove a key combinatorial lemma that implies that the run time for a grid-free dynamic programming algorithm can be polynomially bounded. Based on this lemma, a naive O(N5) algorithm is derived. We then show how this can be sped up to O(N3) by computing appropriately defined auxiliary functions. For certain instances of the problem in which all components are roughly the same size and have roughly √N terminals, we can further reduce the running time to O(N2.5).

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

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

M3 - Conference contribution

AN - SCOPUS:0028333507

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 122

EP - 131

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -