GLOBAL OPTIMIZATION ALGORITHMS FOR CHIP LAYOUT AND COMPACTION

被引：71

作者：

DORNEICH, MC ^{[1
]}

SAHINIDIS, NV ^{[1
]}

机构：

[1] UNIV ILLINOIS, DEPT MECH & IND ENGN, URBANA, IL 61801 USA

来源：

ENGINEERING OPTIMIZATION | 1995年 / 25卷 / 02期

关键词：

CHIP LAYOUT AND COMPACTION; PACKAGE PLANNING; BRANCH-AND-REDUCE; MIXED-INTEGER NONLINEAR PROGRAMMING;

D O I：

10.1080/03052159508941259

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

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.

引用

页码：131 / 154

页数：24

共 35 条

[21]

Otten R. H. J. M., 1983, Proceedings IEEE International Conference on Computer Design: VLSI in Computers (ICCD '83), P499

[22]

OTTEN RHJ, 1981, 18TH P ACM IEEE DES, P261

[23]

PARDALOS PM, 1994, HDB GLOBAL OPTIMIZAT

[24] GLOBAL OPTIMIZATION OF NONCONVEX NLPS AND MINLPS WITH APPLICATIONS IN-PROCESS DESIGN [J].

RYOO, HS ;

SAHINIDIS, NV .

COMPUTERS & CHEMICAL ENGINEERING, 1995, 19 (05) :551-566

[25]

RYOO HS, 1994, UNPUB J GLOBAL OPTIM

[26]

SAHINIDIS NV, 1994, BRANCH REDUCE OPTIMI

[27]

Sherali H, 1992, J GLOBAL OPTIM, V2, P379, DOI DOI 10.1007/BF00122429

[28] CIRCUIT LAYOUT [J].

SOUKUP, J .

PROCEEDINGS OF THE IEEE, 1981, 69 (10) :1281-1304

[29] OPTIMAL ORIENTATIONS OF CELLS IN SLICING FLOORPLAN DESIGNS [J].

STOCKMEYER, L .

INFORMATION AND CONTROL, 1983, 57 (2-3) :91-101

[30] AN ANALYTICAL APPROACH TO FLOORPLAN DESIGN AND OPTIMIZATION [J].

SUTANTHAVIBUL, S ;

SHRAGOWITZ, E .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1991, 10 (06) :761-769

← 1 2 3 4 →