The partitioning of floorplans is an important topic in the field of very large-scale integration (VLSI) physical design automation. Proper partitioning of floorplans can lead to not only efficient insertion of repeaters, but also efficient global and channel routing. As a result, the quality of physical layouts can be improved and the design time can be reduced.
In this paper, a floorplan is defined to contain a number of rectangular blocks, and each of those blocks may have associated nets. An ms-cut is a monotone staircase that partitions rectangular blocks of a floorplan into two groups, and the monotone staircase cuts those blocks from the floorplan’s bottom-left corner to the floorplan’s top-right corner; the staircase does not go down or go left when it cuts the floorplan. Since a floorplan can have many different ms-cuts, there are a variety of problems with regard to the partitioning of a floorplan with ms-cuts.
A number of floorplan partitioning problems are discussed in the paper. The min-cut problem Pc is to find an ms-cut that minimizes the number of nets crossing the two partitions. The number-balance problem Pn is to find an ms-cut that balances the numbers of rectangular blocks for the two partitions, whereas the area-balance problem PA is to find an ms-cut that balances the areas of the two partitions. Furthermore, there is the number-balanced min-cut problem Pnc and the area-balanced min-cut problem PAc; the two problems consider the number of crossing nets as well as one of the balancing factors.
Before this paper was published, it had already been proven that problems Pc and Pn are polynomial time solvable. The paper goes one step further and attacks other floorplan partitioning problems: it proves that PA and PAc are nondeterministic polynomial time (NP) hard, and conjectures that Pnc is also NP hard. Furthermore, the paper proposes a heuristic for solving these difficult problems. The heuristic is based on a max-flow min-cut method, and is capable of partitioning (or bi-partitioning) a floorplan hierarchically.
The paper discusses a number of floorplan partitioning problems. These problems are clearly presented and are interesting. The heuristic proposed for solving some of these problems is flexible and efficient. Moreover, partitioning a floorplan using monotone staircase cuts can be beneficial to other VLSI physical design processes.
