Efficient optimization by modifying the objective function:applications to timing-driven VLSI layout

摘要

When minimizing a given objective function is challenging because of, for example, combinatorial complexity or points of nondifferentiability, one can apply more efficient and easier-to-implement algorithms to modified versions of the function. In the ideal case, one can employ known algorithms for the modified function that have a thorough theoretical and empirical record and for which public implementations are available. The main requirement here is that minimizers of the objective function do not change much through the modification, i.e., the modification must have a bounded effect on the quality of the solution. Review of classic and recent placement algorithms suggests a dichotomy between approaches that either: (a) heuristically minimize potentially irrelevant objective function (e.g., VLSI placement with quadratic wirelength) motivated by the simplicity and speed of a standard minimization algorithm; or (b) devise elaborate problem-specific minimization heuristics for more relevant objective functions (e.g., VLSI placement with linear wirelength). Smoothness and convexity of the objective functions typically enable efficient minimization. If either characteristic is not present in the objective function, one can modify and/or restrict the objective to special values of parameters to provide the missing properties. After the minimizers of the modified function are found, they can be further improved with respect to the original function by fast local search using only function evaluations. Thus, it is the modification step that deserves most attention. In this paper, we approximate convex nonsmooth continuous functions by convex differentiable functions which are parameterized by a scalar β>0 and have convenient limit behavior as β→0. This allows the use of Newton-type algorithms for minimization and, for standard numerical methods, translates into a tradeoff between solution quality and speed. We prove that our methods apply to arbitrary multivariate convex piecewise-linear functions that are widely used in synthesis and analysis of electrical networks. The utility of our approximations is particularly demonstrated for wirelength and nonlinear delay estimations used by analytical placers for VLSI layout, where they lead to more “solvable” problems than those resulting from earlier comparable approaches [29]. For a particular delay estimate, we show that, while convexity is not straightforward to prove, it holds for a certain range of parameters, which, luckily, are representative of “real-world” technologies