GLOBAL OPTIMIZATION ALGORITHMS FOR CHIP LAYOUT AND COMPACTION
- 1 October 1995
- journal article
- research article
- Published by Taylor & Francis in Engineering Optimization
- Vol. 25 (2) , 131-154
Abstract
The package planning (chip layout and compaction) problem can be stated in terms of an optimization problem. The goal is to find the relative placement and shapes of the chips in a way that minimizes the total chip area subject to linear and nonlinear constraints. The constraints arise from geometric design rules, distance and connectivity requirements between various components, area and communication costs and other designer-specified requirements. The problem has been addressed in various settings. It is of unusual computational difficulty due to the nonconvexities- involved. This paper presents a new mixed-integer nonlinear programming formulation for simultaneous chip layout and two-dimensional compaction. Global optimization algorithms are developed for this model as well as for an existing formulation for the chip compaction problem. These algorithms are implemented with the global optimization software BARON and illustrated by solving several example problems.Keywords
This publication has 12 references indexed in Scilit:
- Global optimization of nonconvex NLPs and MINLPs with applications in process designComputers & Chemical Engineering, 1995
- A new reformulation-linearization technique for bilinear programming problemsJournal of Global Optimization, 1992
- An analytical approach to floorplan design and optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Branch-and-bound placement for building block layout1991
- A Collection of Test Problems for Constrained Global Optimization Algorithms1990
- Combinatorial Algorithms for Integrated Circuit Layout1990
- GAMS, a user's guideACM SIGNUM Newsletter, 1988
- Algorithmic Aspects of One-Dimensional Layout CompactionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Optimal orientations of cells in slicing floorplan designsInformation and Control, 1983
- Circuit layoutProceedings of the IEEE, 1981