An efficient hierarchical approach for general floorplan area minimization

In this paper, we formulate the general nonslicing floorplan area minimization for soft modules as a quadratic programming problem, and propose an efficient hierarchical approach to reduce the scale of the problem. For an arbitrary given initial floorplan, a new module clustering algorithm is first proposed to divide the modules into several clusters and to build the hierarchical structure of these clusters. After the clusters were generated, a constraint generator will automatically produce the mathematical programming constraints for each cluster. Then we solve these sets of constraints through a mathematical programming solver. Finally, we use a linear transformation algorithm to calculate the exact coordinates for each module. Experimental results on MCNC benchmarks show that our method is very efficient. In our experiment, we assume the aspect ratio of each module can range from 0.1 to 10.0 as used in most of the previous works and we can generate a zero dead space floorplan for every benchmark within 10 seconds even based on different initial floorplans. Because the final floorplan generated by our method will keep the similar topology of the initial floorplan, our method can be applied as a post-process of all existing floorplan algorithms having different major objectives (e.g. total wire length, delay of critical net) to further reduce the area.