RECTANGLE PACKING BASED PLACEMENT

Abstract

The first and the most critical stage in VLSI physical design is placement, the background of which is the rectangle packing problem: Given a set of rectangular modules of arbitrary sizes, place them without overlap on a plane within a rectangle of minimum area. Since the variety of the packing is uncountably infinite, the key issue for discrete optimization is the introduction of a finite solution space which includes an optimal solution and excludes infeasible solutions.

The main contribution of this work is in the introduction of such a solution space where each packing is represented by a pair of module name sequences, called sequence-pair. Using the solution space, simulated annealing method is carried out with a conventional wiring estimation formula to solve building block placement problems. The biggest MCNC benchmark example ami49 is placed promisingly in about 30 minutes on a Sun-SS2.

Relevant Papers