An application of preconditioned conjugate gradients to relative placement in chip design
| Autor: | Christian Zillober, Christian Kredler, Georg Sigl, Frank Johannes |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1993 |
| Předmět: |
Numerical Analysis
Mathematical optimization Optimization problem Applied Mathematics General Engineering Constrained optimization MathematicsofComputing_NUMERICALANALYSIS Quadratic function Optimal control Quadratic form Conjugate gradient method Quadratic programming ddc:510 Algorithm Mathematics Cholesky decomposition |
| Popis: | SUMMARY In distance geometry problems and many other applications, we are faced with the optimization of high-dimensional quadratic functions subject to linear equality constraints. A new approach is presented that projects the constraints, preserving sparsity properties of the original quadratic form such that well-known preconditioning techniques for the conjugate gradient method remain applicable. Very-Iarge scale cell placement problems in chip design have been solved successfully with diagonal and incomplete Cholesky preconditioning. Numerical results produced by a FORTRAN 77 program illustrate the good behaviour of the aJgorithm. Quadratic programming with either non-negativity or linear equality constraints is a standard model type in quite a large number of applications: we mention only discretization of certain optimal control problems or many kinds of distance geometry approaches. In this paper, we discuss preconditioned conjugate gradient (CO) methods for large·scaIc quadratic optimization problems with linear equality constraints. Our new algorithm has been developed for an initial global placement phase in chip design. The presented CO method enables a simultaneous treatment of all cells and is applicable to general-cell and standard·cell circuits of several thousand cells and nets. Now it is no longer necessary to partition the chip area and to solve stand·alone smaller optimization problems. This formerly used local strategy frequently neglects the connections between the subproblems, leading to models which are often unrealistic. In Section 2 we formulate the constrained problem. Section 3 discussses the various techniques of preconditioning. Further, a new CG method for preconditioning in an affine subspace is presented. Section 4 contains the model formulation for the chip placement problem and some numerical results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|