Layout optimization with algebraic multigrid methods (AMG)

Hans Regler and Ulrich Ruede

Institut fuer Informatik, Technische Universitaet Muenchen, Arcisstr. 21, D-8000 Muenchen 2, Germany


Finding the optimal position for the individual cells (also called functional modules) on the chip surface is an important and difficult step in the design of integrated circuits. This paper deals with the problem of relative placement, that is the minimization of a quadratic functional with large, sparse, positive definite system matrix. The basic optimization problem must be augmented by constraints to inhibit solutions where cells overlap. This is particularly difficult, because the constraints are added incrementally as the iteration progresses. Besides classical iterative methods, based on conjugate gradients (CG), we show that algebraic multigrid methods (AMG) provide an interesting alternative. For moderately sized examples with about 10000 cells, AMG is already competitive with CG and is expected to be superior for larger problems. Besides the classical multiplicative AMG algorithm where the levels are visited sequentially, we propose an additive variant of AMG where levels may be treated in parallel and that is suitable as a preconditioner in the CG algorithm.