Relocate White Space in Floorplanning

Most existing floorplanning algorithms compact blocks to the left and bottom. Although the compacting obtains an optimal area, it may not be good to meet other objectives such as minimizing total wire length, routing congestion or buffer allocation. In this paper, we propose a new method to allocate white space in floorplanning for minimizing total wire length. Our method is based on min-cost flow implementation, and guarantees to obtain the minimum of total wire length for a given floorplan representation. We also show that the method can be easily extended to handle constraints such as fixed-frame (fixed area), boundary pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay, without lose of optimality. The algorithm is so efficient in that it finishes in less than 0.5 seconds for all MCNC benchmarks of block placement. Thus it can be either integrated into each step in simulated annealing or applied to post-floorplanning (refine floorplanning). It is also very effective. Experimental results show we can further improve 4.8% of wire length even on very compact floorplans.