A methodology of VLSI layout described by several authors first determines the relative positions of indivisible pieces, called cells, on the chip. Various optimizations are then performed on this initial layout to minimize some cost measure such as chip area or perimeter. If each cell is a rectangel with given dimensions, one optimization problem is to choose orientations of all the cells to minimize the cost measure. A polynomial time algorithm is given for this optimization problem for layouts of a special type called slicings. However, orientation optimization for more general layouts is shwon to be NP-complete (in the strong sense).

--Author’s Abstract

The abstract given above is a good description of the paper. Given an algorithmic point of view, the paper is interesting. The problem, called “optimal orientation of cells in slicing floorplan design,” has been solved, until now, by the use of greedy heuristics. In the paper, however, an efficient polynomial time algorithm is devised. In addition, a nontrivial proof of the NP-completeness of the problem for more general layouts is given:

From a practical point of view (that is, in VLSI layout design), the orientation problem must be considered in the context of the full design process. Hence, as the author points out in the Conclusion, the formulation of the real problem is much more complex.