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

H. Murata, K.Fujiyoshi, S.Nakatake, and Y.Kajitani, "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair" , IEEE Trans. on CAD, Vol. 15, No. 12, pp.1518--1524, Dec. 1996.

©2002-2018 U.C. Regents