Rectangle-packing-based module placement

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.
Format: Conference Proceeding
Language:English
Subjects:
Circuit simulation
Design engineering
Information science
NP-hard problem
Production
Simulated annealing
Very large scale integration
Wiring
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1063-6757
1092-3152
1558-2434
DOI:10.1109/ICCAD.1995.480159