DIMACS TR: 98-03
Optimal Cell Flipping to Minimize Channel Density in
VLSI Design and Pseudo-Boolean Optimization
Authors: Endre Boros, Peter L. Hammer, Michel Minoux and David Rader
ABSTRACT
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(\frac{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 multi-channel 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-03.ps.gz
DIMACS Home Page