Practical Aspects of Multiscale Optimization Methods for VLSICAD

VLSICAD gives rise to large nonlinear optimization problems with integer constraints.  Traditional optimization methods are not able to find solutions in a reasonable length of time.  One approach to dealing with the sheer size of these problems is to use multiscale methods, that is, methods that solve a sequence of optimization problems of varying size and complexity.  In this paper we consider the application of a multiscale optimization method to problems in VLSICAD.  The multiscale method was originally developed in the context of engineering design, applied to optimization problems with differential equation constraints.  In that setting, each design problem represents a family of optimization problems, each corresponding to a particular discretization of the differential equations.  In the context of VLSICAD, a family of optimization problems is obtained by using clustering algorithms to group components of the circuit.

The focus of this paper is on practical issues: Is it possible to apply the multiscale algorithm to VLSICAD? Will the multiscale algorithm converge? How quickly?  Can the multiscale algorithm take into account integer constraints?  What are the implementation issues?  How does the multiscale algorithm perform on sample problems?  We believe that the answers to these questions are encouraging, and we suggest that further investigation of multiscale algorithms is called for.

“Practical Aspects of Multiscale Optimization Methods for VLSICAD”, in Multiscale Optimization and VLSI/CAD, Jason Cong and Joseph R. Shinnerl (editors), Kluwer Academic Publishers (Boston), pp. 265-291 (2002).

• Systems Engineering & Operations Research Dept.
• School of Information Technology and Engineering
• George Mason University

(snash@gmu.edu)