A Fast Floorplanning Algorithm for Architectural Evaluation

This paper presents a method for producing a chip floor plan from a list of blocks and their interconnections. The blocks can be of different sizes, and each block can have several possible aspect ratios. The algorithm places the blocks and chooses the orientation and aspect ratio of each so as to produce a near-minimum area floor plan. The preliminary placement of the blocks is done using a standard min-cut placement algorithm, modified so that it can handle blocks of different sizes. The choice of aspect ratio and orientation is done using a new dynamic programming algorithm, along with a heuristic that limits the number of possible configurations explored. The algorithm is shown to give near-optimal results, yet it is faster than comparable placement algorithms, fast enough to be used in the inner loop of a program that generates and evaluates many alternative designs for a given-level behavioral specification.