Redistribute White Space for Minimizing Wire Length

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 study the problem of distributing white space in floorplanning for minimizing total wire length. The problem can be formulated as linear programming. We propose an efficient min-cost flow based approach to solve it. Our approach guarantees to obtain the minimum of total wire length and meanwhile keep the minimum area for a given floorplan representation. We also show that the approach 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 loss of optimality. The algorithm is so efficient in that it finishes in less than 0.4 seconds for all MCNC benchmarks of block placement. It is also very effective. Experimental results show we can further improve 4.2% of wire length even on very compact floorplans. Thus it provides an ideal way of post-floorplanning (refine floorplanning).

By: Xiaoping Tang, Martin D. F. Wong

Published in: RC23323 in 2004

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

rc23323.pdf

Questions about this service can be mailed to reports@us.ibm.com .