Graph-based techniques to speed up floorplan area optimization

A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [1-7]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. An effective method to reduce memory usage is as follows: During the computation, whenever the set of non-redundant implementations of a sub-floorplan exceeds a certain predefined size, we only retain a subset of the implementations that can best approximate the original set. In this paper, we present two algorithms to optimally select implementations for rectangular and L-shaped sub-floorplans. Our algorithms can be applied to existing floorplan area optimization algorithms such as [3-7] to improve their performances. The common key idea of our two algorithms is to reduce the problem of optimally selecting a subset of implementations to a constrained shortest path problem, which we can solve optimally in polynomial time. We have incorporated the two algorithms into [7] and obtained very encouraging experimental results.