Rectangle-packing-based module placement

TLDR

VLSI layout placement is a rectangle‑packing problem where many rectangular modules must be placed without overlap in the smallest bounding rectangle, and because the packing space is infinite, a finite P‑admissible solution space is needed to enable successful optimization. The paper proposes a finite solution space where each packing is represented by a pair of module name sequences. The solution space represents each packing as a pair of module name sequences. Simulated annealing over the proposed space successfully packed hundreds of modules, and when combined with a conventional wiring method, it challenged the largest MCNC benchmark ami49.

Abstract

The first and the most critical stage in VLSI layout design is the placement, the background of which is the rectangle packing problem: Given many rectangular modules of arbitrary site, place them without overlapping on a layer in the smallest bounding rectangle. Since the variety of the packing is infinite (two-dimensionally continuous) many, the key issue for successful optimization is in the introduction of a P-admissible solution space, which is a finite set of solutions at least one of which is optimal. This paper proposes such a solution space where each packing is represented by a pair of module name sequences. Searching this space by simulated annealing, hundreds of modules could be successfully packed as demonstrated. Combining a conventional wiring method, the biggest MCNC benchmark ami49 is challenged.