Method and system to redistribute white space for minimizing wire length

Abstract

Disclosed are a method and a system for redistributing white space on an integrated circuit. The method comprises the steps of providing a series of circuit blocks for the integrated circuit, and placing the blocks on the integrated circuit to obtain a predefined optimal wire length. In accordance with the preferred embodiment of the invention, we first show that the problem of placing the blocks to obtain an optimal wire length, can be formulated as linear programming. Then, we find it can be solved by efficient min-cost flow implementation instead of general and slow linear programming. The approach guarantees to obtain the minimum total wire length for a given floorplan topology. We also show that the approach is capable of handling various constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, cluster placement, and bounded net delay, without loss of optimality.