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

TLDR

VLSI placement is a critical early stage that reduces to a rectangle‑packing problem, where modules must be placed without overlap in a minimum‑area rectangle, and the challenge is to define a finite solution space that contains an optimal packing. The authors introduce a finite solution space for placement by encoding each packing as a sequence‑pair of module names. They explore the sequence‑pair space using simulated annealing to find efficient packings. The method successfully packed hundreds of modules and produced a highly promising placement for the MCNC ami49 benchmark using conventional wiring‑area estimation.

Abstract

The earliest and the most critical stage in VLSI layout design is the placement. The background 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 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.