TY - JOUR

T1 - Optimal cell flipping to minimize channel density in VLSI design and pseudo-boolean optimization

AU - Boros, Endre

AU - Hammer, Peter L.

AU - Minoux, Michel

AU - Rader, David J.

N1 - Funding Information:
* Corresponding author. ’ Partially supported by the Office of Naval Research (Grants N000149310890). 2 Partially supported by the National Science Foundation (Grant CRG 931531).

PY - 1999/1/15

Y1 - 1999/1/15

N2 - Cell flipping in VLSI design is an operation in which some of the cells are replaced with their "mirror images" with respect to a vertical axis, while keeping them in the same slot. After the placement of all the cells, one can apply cell flipping in order to further decrease the total area, approximating this objective by minimizing total wire length, channel width, etc. However, finding an optimal set of cells to be flipped is usually a difficult problem. In this paper we show that cell flipping can be efficiently applied to minimize channel density in the standard cell technology. We show that an optimal flipping pattern can be found in O(p(n/c)c) time, where n, p and c denote the number of nets, pins and channels, respectively. Moreover, in the one channel case (i.e. when c = 1) the cell flipping problem can be solved in O(p log n) time. For the multichannel case we present both an exact enumeration scheme and a mixed-integer program that generates an approximate solution very quickly. We present computational results on examples up to 139 channels and 65 000 cells.

AB - Cell flipping in VLSI design is an operation in which some of the cells are replaced with their "mirror images" with respect to a vertical axis, while keeping them in the same slot. After the placement of all the cells, one can apply cell flipping in order to further decrease the total area, approximating this objective by minimizing total wire length, channel width, etc. However, finding an optimal set of cells to be flipped is usually a difficult problem. In this paper we show that cell flipping can be efficiently applied to minimize channel density in the standard cell technology. We show that an optimal flipping pattern can be found in O(p(n/c)c) time, where n, p and c denote the number of nets, pins and channels, respectively. Moreover, in the one channel case (i.e. when c = 1) the cell flipping problem can be solved in O(p log n) time. For the multichannel case we present both an exact enumeration scheme and a mixed-integer program that generates an approximate solution very quickly. We present computational results on examples up to 139 channels and 65 000 cells.

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

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

U2 - 10.1016/S0166-218X(98)00114-0

DO - 10.1016/S0166-218X(98)00114-0

M3 - Article

AN - SCOPUS:0041705409

VL - 90

SP - 69

EP - 88

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

ER -