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

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 1996-12, Vol.15 (12), p.1518-1524
• Main Authors: Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.
• Format: Article
• Language: English
• Subjects: Applied sciences; Circuits; Costs; Design. Technologies. Operation analysis. Testing; Electronics; Exact sciences and technology; Genetic algorithms; Information science; Integrated circuits; Polynomials; Production; Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices; Simulated annealing; Very large scale integration; Wiring
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/43.552084

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.