A fast floor planning algorithm for architectural evaluation

A method for producing a chip floor plan from a list of blocks and their interconnections is presented. 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 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 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 high-level behavioral specification