VLSI module placement based on rectangle-packing by the sequence-pair

The earliest and the most critical stage in VLSI layout design is the placement, The background of which is the rectangle packing problem: Given 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 successful optimization is the introduction of a finite solution space which includes an optimal solution, This paper proposes such a solution space where each packing is represented by a pair of module name sequences, called a sequence-pair, Searching this space by simulated annealing, hundreds of modules have been packed efficiently as demonstrated, For applications to VLSI layout, we attack the biggest MCNC benchmark ami49 with a conventional wiring area estimation method, and obtain a highly promising placement.