VLSI module placement based on rectangle-packing by the sequence-pair
- 1 December 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 15 (12) , 1518-1524
- https://doi.org/10.1109/43.552084
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.Keywords
This publication has 12 references indexed in Scilit:
- Area Minimization For Hierarchical FloorplansPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- An MCM/IC timing-driven placement algorithm featuring explicit design space explorationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Branch-and-bound placement for building block layoutPublished by Association for Computing Machinery (ACM) ,1991
- An optimal algorithm for floorplan area optimizationPublished by Association for Computing Machinery (ACM) ,1990
- Model and solution strategy for placement of rectangular blocks in the Euclidean planeIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- A New Algorithm for Floorplan DesignPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- An Analytical Algorithm for Placement of Arbitrarily Sized Rectangular BlocksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Order of Channels for Safe Routing and Optimal Compaction of Routing AreaIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- Optimal orientations of cells in slicing floorplan designsInformation and Control, 1983
- Automatic Floorplan DesignPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982