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

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 c an apply cell flipping in order to further decrease the total area, approxi mating this objective by minimizing total wire length, channel width, etc. However, finding an optimal set of cells to be flipped is usually a difficu lt problem. In this paper we show that cell flipping can be efficiently app lied to minimize channel density in the standard cell technology. We show t hat 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. Moreov er, 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 multi channel case we present both a n exact enumeration scheme and a mixed-integer program that generates an ap proximate solution very quickly. We present computational results on exampl es up to 139 channels and 65 000 cells. (C) 1999 Elsevier Science B.V. All rights reserved.