Algorithms For A Nonsmooth Convex Optimization Problem In VLSI Global Placement

Placement has to determine the positions of the cells in a given chip area. Place-ment is one of the most important steps in VLSI CAD, since chip performance is heavily depended on the circuit placement results. The objective function of place-ment is the sum of many Half Perimeter Wire Length functions and is a convex but not differentiable function. Therefore, some smooth approximation methods are usually adopted to approximate the HPWL function. However, no global place-ment algorithm can minimize the HPWL function directly up to now. To solve the convex but nondifferentiable problem, Subgradient methods have been recognized in practice that subgradient methods are usually slow and numerically sensitive to the choice of step sizes. Currently, Nesterov’s smoothing and excessive gap techniques have been developed to solve a class of nonsmooth convex optimization problem suc-cessfully, both in theory and in practice. In this thesis, we will use the techniques to solve a nonsmooth convex optimization problem arising in VLSI global placement.In this thesis, two global placement techniques are developed for dealing with the the HPWL net models which are based on the placer SimPL. These techniques are:(1) a global placement algorithm which is based on Nesterov’s Smoothing tech-nique, (2)a global placement algorithm which is based on Nesterov’s Excessive Gap technique. In chapter 2, we introduce the two algorithms. The main advantage of these algorithms is that they can capture the Half Perimeter Wire Length informa-tion in the process of optimization. Besides, in the two algorithms, every variant has an explicit solution in the process of optimization. The convergence rate of the algorithm which is based on Nesterov’s Smoothing technique is O(1/k), and the convergence rate of the algorithm which is based on Nesterov’s Excessive Gap technique technique is O(l/k2), where k is the iteration counter, which is optimal.Chapter 3 reports our experimental results on ISPD-2004 placement contest benchmarks and a comparison of the results are obtained by the two algorithms. We have found that the algorithm which is based on Nesterov’s Smoothing technique achieves 2.9×faster than the algorithm which is based on Nesterov’s Excessive Gap technique, and the qualities are almost the same.