Abstract
In this paper, we propose an algorithm for a nonsmooth convex optimization problem arising in very large-scale integrated circuit placement. The objective function is the sum of a large number of Half-Perimeter Wire Length (HPWL) functions and a strongly convex function. The algorithm is based on Nesterov’s smoothing and excessive gap techniques. The main advantage of the algorithm is that it can capture the HPWL information in the process of optimization, and every subproblem has an explicit solution in the process of optimization. The convergence rate of the algorithm is \(O(1/k^{2}),\) where k is the iteration counter, which is optimal. We also present preliminary experiments on nine placement contest benchmarks. Numerical examples confirm the theoretical results.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In 2005, Nesterov presented the smoothing [16] and excessive gap techniques [17] to solve nonsmooth convex minimization problems. Specifically, he solved the following minimization problem,
where X is a bounded closed convex set in the n-dimensional Euclidean space \({\mathbb{R}}^{n};\,\widehat{f}(x)\) is a convex and Lipschitz continuous differentiable function with some constant \(M\geqslant 0\) on X; the linear operator A maps X to Q; Q is a simple bounded closed convex set in the m-dimensional Euclidean space \({\mathbb{R}}^{m};\) and \(\widehat{\phi }(u)\) is a simple continuous convex function on Q, such that the maximum function in (1.1) has a closed-form solution. The iteration complexity of Nesterov’s smoothing technique is \(O(1/{\varepsilon }),\) where \(\varepsilon \) is a user-defined absolute accuracy of approximate optimal value. The convergence rate of the excessive gap technique for the problem is \(O(1/k)\) if \(\widehat{f}(x)\) is a non-strongly convex function, and can reach \(O(1/k^{2})\) if \(\widehat{f}(x)\) is a strongly convex function, where k is the iteration counter. The two methods have been widely used in applications, e.g., sparse recovery [2], resource allocation [8], risk measures for portfolio optimization [7], and multi-commodity flow and fractional packing [19].
In this paper, we aim at using the smoothing [16] and excessive gap techniques [17] to solve a convex optimization problem in the placement of a very large-scale integrated (VLSI) circuit. Placement is one of the most important steps in VLSI computer aided design, since chip performance depends heavily on the circuit placement results [1]. A modern chip often contains millions of circuit cells and nets, which must be placed in a design region legally and the objective is optimized. This has to be done using high-performance optimization techniques.
A VLSI circuit can be modeled as a hypergraph \(\mathcal {N}=(V,\,E),\) where V denotes the set of circuit cells with possibly different widths and heights and E denotes the set of nets specifying interconnections between the circuit cells. Note that a net may contain more than two cells, i.e., a net may be a hyperedge. Given a rectangular \([0,\,W]\times [0,\,H],\) VLSI placement seeks a placement of circuit cells such that no cell overlaps with the other, and the total wirelength is minimized [1, 4, 14]. This problem is NP-complete [6], and is rather difficult to solve due to the very large scale and NP-completeness. However, up to now, there are a number of packages for the VLSI placement problem using different optimization methods [1, 4, 14].
Given the location \((x^{(i)},\,y^{(i)})\in [0,\,W]\times [0,\,H]\) of circuit cell \(i\in V,\) the total wirelength of the circuit is defined as the Half-Perimeter Wirelength (HPWL), i.e., \(\mathrm{HPWL}_{\mathcal {N}}(x,\,y)=\mathrm{HPWL}_{\mathcal {N}}(x)+\mathrm{HPWL}_{\mathcal {N}}(y),\) where
Since the HPWL function (1.2) is continuous and convex, but not differentiable, it is usually approximated by the Bound-2-Bound (B2B) net model [21]. The B2B model is a convex quadratic function and has been widely used in VLSI placement research [1, 4, 13]. SimPL [10, 12], ComPLx [9], and Mapple [11] are among the best state-of-the-art placers in modern VLSI Computer Aided Design. They also approximate the HPWL function by the B2B net model [21], and solve the following problem as a subproblem,
where \(X=[0,\,W]^{n},\,\mathrm{HPWL}_{\mathcal {N}}^\mathrm{B2B}(x)\) is the B2B convex quadratic approximation of the function \(\mathrm{HPWL}_{\mathcal {N}}(x)\) in Eq. (1.2), \(\lambda >0,\) and \(x_{0}^{+}\) is the feasible solution of the VLSI placement problem.
The problem (1.3) is a key subproblem in VLSI placers SimPL, ComPLx, and Mapple, which was solved by the conjugate gradient method. In the problem, the B2B net model is a rough approximation of the HPWL function, which cannot capture the HPWL information exactly in the process of optimization. Moreover, the \(\Vert \cdot \Vert _{1}\) norm is not Lipschitz continuously differentiable, which makes the conjugate gradient method for solving the problem (1.3) not theoretically sound.
In this paper, we do not use the B2B net model to approximate the function \(\mathrm{HPWL}_{\mathcal {N}}(x)\) but use the HPWL function directly. The \(l_{1}\)-norm \(||\cdot ||_{1}\) is changed to the square of \(l_{2}\)-norm, i.e., \(||\cdot ||^{2}_{2}.\) Hence, the problem we consider in this paper is
where \(\lambda >0.\) The function \(\mathrm{HPWL}_{\mathcal {N}}(x)\) is a non-differentiable convex function, so we will adopt Nesterov’s smoothing and excessive gap techniques [16, 17] to solve problem (1.4).
Several approaches in the previous literature can be used to solve the minimization problem (1.4). The LSE net model and the \(L_{P}\)-norm net model [1, 4] approximate the function \(\mathrm{HPWL}_{\mathcal {N}}(x)\) by the LSE and \(L_{P}\)-norm functions. Subgradient methods [3] can be used to solve the problem (1.4) directly. But it has been recognized in practice that subgradient methods are usually slow and numerically sensitive to the choice of step sizes. Recently, Nesterov [18] proposed a subgradient method to optimize huge-scale problems with sparse subgradients. This method is based on a recursive update of the results of matrix/vector products and the values of symmetric functions. The convergence rate of the algorithm is \(O(1/\sqrt{k}),\) where k is the iteration counter. Dinh et al. [5] proposed an algorithm which combines Lagrangian decomposition with excessive gap smoothing techniques to solve large-scale separable convex optimization problems. The convergence rate is \(O(1/k).\) However, our problem is not separable, so we cannot use their technique directly. Schmidt et al. [20] proposed an algorithm to optimize the sum of a finite number of smooth convex functions by the stochastic average gradient method. The convergence rate is \(O(1/k).\)
In this paper, we propose an algorithm basing on the smoothing and excessive gap techniques by Nesterov [16, 17] to solve problem (1.4). Comparing problem (1.4) with the problem (1.1) in Nesterov [16, 17], we can find that our considered problem is a direct generalization of problem (1.1) on the summation of a large number of maximum functions. Moreover, every maximum function in (1.4) contains only the cells in a net, and the number of cells in a net is almost not too big according to the characteristic of the VLSI circuit. Hence, we use Nesterov’s smoothing technique on every maximum function directly. The proposed algorithm has a convergence rate \(O(1/k^{2}),\) where k is the iteration counter. According to the complexity theory for convex optimization by Nemirovski and Yudin [15], the proposed algorithm is optimal.
The paper is organized as follows. In Sect. 2, some notations and basic results are quoted. In Sect. 3.1, we introduce the technique of smoothing the HPWL function of every net \(e_{k}.\) The excessive gap condition (EGC) and some lemmas are given in Sect. 3.2. Section 4 introduces the algorithm. In this section, the theorems of convergence rate and efficiency estimate are also specified. In Sect. 5, we give a scheme to speed up the convergence of the algorithm. Finally, preliminary computational experiments are put in Sect. 6.
2 Notations and Basic Results
In this section, we review some notations and basic results proposed in Nesterov’s smoothing and excessive gap techniques [16, 17]. They will be used in our paper.
Let X be a finite dimensional space. In this paper, we define X as
where W is the width of the placement region in the VLSI placement problem.
The space of linear functions on X is denoted by \(X^{*}.\) For \(s\in X^{*},\,x\in X,\) the value of s at x is denoted by \(\langle s,\,x\rangle ,\) where \(\langle \cdot ,\,\cdot \rangle \) denotes the regular inner product. Denote \(s,\,z\in S,\) where S is a finite dimensional space equipped with the \(l_{p}\)-norm. The dual norm of s is defined as
Let A be a linear operator which maps X to Q, i.e., \(X\longrightarrow Q.\) We use \(A_{i}\) to denote the ith row of A, and use \(A^{j}\) to denote the jth column of A. In this paper, we set the space Q be equipped with the \(l_{1}\)-norm, and \(Q=\left\{ u{\text {:}}\,\sum \nolimits _{i=1}^{p} |u^{(i)}|\leqslant 1\right\} .\)
For \(x\in X,\,u\in Q,\,X\) is equipped with the \(l_{2}\)-norm, and the norm of A is defined as
Clearly,
It is easy to verify that
and
It is easy to prove that the norm of A satisfies
where p is the number of rows in A.
Furthermore, we define a strongly convex function \(d_{Q}(u)\) on the convex set Q, which satisfies that
and for all \(u,\,v\in Q,\)
where \(\sigma _{Q} >0\) is the strong convexity parameter of the function \(d_{Q}(u),\) and \(u^{*}=\arg \!\min _{u\in Q}d_{Q}(u).\) Without loss of generality, we assume that \(d_{Q}(u^{*})=0.\)
3 Objective and Dual Functions
In this section, we present the smoothing technique for the VLSI placement problem in detail. And then, the EGC is given for the objective function and its dual form.
3.1 Smoothing the Objective Function
Let \({a}_{i,j}(e_{k})\) be an n-dimensional vector corresponding to net \(e_{k}\) and cells i and j, where n is the dimension of the vector x. And for any \(i,\,j\in e_{k},\,i\ne j,\) the ith component of \( {a}_{i,j}(e_{k})\) is 1, the jth component of \({a}_{i,j}(e_{k})\) is \(-\)1, and the other components are zeros. Let \(A(e_{k})\) be a matrix with respect to \(e_{k}\) with all possible vectors \(a_{i,j}(e_{k})\) as rows. To make it clear, we give the following example.
Consider a hypergraph \(\mathcal {N}=(V,\,E),\) where \(V=\{1,\,2,\,3\},\) \(E=\{e_{1},\,e_{2}\},\) and the cells \(1,\,2\in e_{1},\,1,\,2,\,3\in e_{2}.\) By the notation, for the net \(e_{1},\,a_{1, 2}(e_{1})=(1,\,-1,\,0),\,a_{2, 1}(e_{1})=(-1,\,1,\,0);\) and for the net \(e_{2},\) we have \(a_{1, 2}(e_{2})=(1,\,-1,\,0),\,a_{1, 3}(e_{2})=(1,\,0,\,-1),\,a_{2, 1}(e_{2})=(-1,\,1,\,0),\,a_{2, 3}(e_{2})=(0,\,1,\,-1),\,a_{3, 1}(e_{2})=(-1,\,0,\,1),\,a_{3, 2}(e_{2})=(0,\,-1,\,1).\) Thus, the matrices \(A(e_{1})\) and \(A(e_{2})\) have the following forms:
Obviously, the dimension of \(A(e_{k})\) is \((n_{k}^{2}-n_{k})\times n,\) where \(n_{k}\) is the number of cells on the net \(e_{k}.\) Moreover, any row of the matrix \(A(e_{k})\) has only two non-zero components. The one is 1 and the other one is \(-\)1. So by (2.3), we can get
Lemma 3.1
By the above notations, for any net \(e_{k}\) with \(n_{k}\) cells, we have
Proof
For cells \(i,\,j\in e_{k},\) it holds that \(x^{(i)}-x^{(j)}=\langle a_{i,j}(e_{k}),\,x \rangle .\) Thus,
Furthermore, there exist \(i^{\prime },\,j^{\prime }\in e_{k}\) such that
So for \(u_{k}\) such that \(\sum \nolimits _{i=1}^{n_{k}(n_{k}-1)} |u^{(i)}_{k}|\leqslant 1,\)
Furthermore, suppose that in Eq. (3.2), \(a_{i^{\prime },j^{\prime }}(e_{k})\) is the pth row of \(A(e_{k}).\) Take \(u_{k}\) such that the pth component of \(u_{k}\) is \(\mathrm{sgn}(\langle a_{i^{\prime },j^{\prime }}(e_{k}),\,x \rangle ),\) and the other components of \(u_{k}\) are 0. Then
which implies that
Hence, Lemma 3.1 holds.
As shown in Lemma 3.1, in this paper, we define the set
where \(n_{k}\) is the number of cells on the net \(e_{k}.\) Furthermore, by Lemma 3.1, for any net \(e_{k},\) we write the function \(\mathrm{HPWL}_{e_{k}}(x)\) of \(e_{k}\) as
Let
By Lemma 3.1, the problem in (1.4) can be written as
where \(\lambda > 0,\,m=|\mathcal {N}|,\) which is obviously a direct generalization of problem (1.1).
For every net \(e_{k},\) the HPWL function (1.2) is convex but not Lipschitz continuously differentiable. Hence, the problem (3.6) is not easy to solve directly. We use the idea of smoothing technique [16] to transform the problem such that it is smooth.
Recall that \(d_{Q_{k}}(u_{k})\) is a strongly convex function on \(Q_{k}\) with a strongly convexity parameter \(\sigma _{Q_{k}}>0.\) Let \(u_{k}^{*}\) be the optimal solution of \(d_{Q_{k}}(u_{k}),\) i.e.,
Let \(\mu \) be a positive smoothness parameter. Consider the following function
Since \(d_{Q_{k}}(u_{k})\) is strongly convex, the optimal solution of the above maximization problem is unique and we let it be \(u^{*}_{k}(x).\) Thus, the smoothness function of the objective function in (3.6) is in the following form,
By Theorem 1 of [16], \(f_{\mu }(x)\) is a continuously differentiable convex function, and its gradient
is Lipschitz-continuous on X.
The dual problem of (3.6) can be formulated as
where \(\lambda >0.\) Denote \(x^{*}(u)\) as the optimal solution of the minimization problem in the dual problem (3.10), where \(u=(u_{1},\,u_{2}, \cdots ,u_{m})^{\rm T}.\) Since \(\widehat{f}(x)\) is strongly convex with strongly convex parameter 2, \(x^{*}(u)\) is unique. Moreover, by Theorem 1 of [16], \(\Phi (u_{1},\cdots ,u_{m})\) is a continuously differentiable concave function.
Therefore, for any \(\widehat{x}\in X\) and \(\overline{u}_{k} \in Q_{k},\) where \(k=1,\cdots ,m\), we have
Obviously, suppose \(\widehat{x}=x^{*}(\overline{u}),\) then we have
Since \(u_{1},\cdots ,u_{m}\) are independent and they have different dimensions, the partial gradient of the function \(\Phi (u_{1},\cdots ,u_{m})\) with respect to \(u_{k}\) is denoted by
Since \(x^{*}(u)\) is the unique optimal solution of (3.10), the gradient of the function \(\Phi (u_{1},\cdots ,u_{m})\) with respect to \(x^{*}(u)\) satisfies the following equality:
Hence,
By the way, the gradient of \(\Phi (u_{1},\cdots ,u_{m})\) is defined as follows:
By the properties of the norms, we can get the following inequality:
Lemma 3.2
The function \(\Phi (u_{1},\cdots ,u_{m})\) is Lipschitz-continuous differentiable with a Lipschitz constant
Proof
From the assumption that \(\widehat{f}(x)\) is strongly convex, the function \(\Phi (u_{1},\cdots ,u_{m})\) has the unique minimal solution \(x^{*}(u).\) Consider \(u_{k},\,{v}_{k}\in Q_{k},\,k=1,\cdots ,m.\) By the first-order optimality condition, we have
Adding the above inequalities and using the strong convexity of \(\widehat{f}(x),\) we have
By (2.1) and (3.15), we can get the following inequalities:
Thus, by (3.1) and \(\widehat{\sigma }=2,\) we can get the following inequality:
Moreover, by (3.13), (3.14), and the above inequality, we have
Hence, the lemma holds.
3.2 Excessive Gap Condition
Similar to [17], for some \(\overline{x}\in X\) and \(\overline{u}_{k}\in Q_{k},\) where \(k=1,\cdots ,m,\) the EGC is given as follows:
Lemma 3.3
Let vectors \(\overline{x}\in X\) and \(\overline{u}_{k}\in Q_{k}\) satisfying (3.16), where \(k=1,\cdots ,m.\) Then
where \(D_{k}=\max _{u_{k}\in Q_{k}}d_{Q_{k}}(u_{k}).\)
Proof
Clearly,
So we have
Hence, we can easily get
and Lemma 3.3 holds.
For \(u_{k},\,v_{k}\in Q_{k},\) denote the Bregman distance between \(u_{k}\) and \(v_{k}\) by
By (2.5), we have
Define the Bregman projection of g on the set \(Q_{k}\) as follows:
Lemma 3.4
The EGC holds for
where \(u^{*}_{k}\) is the minimal solution of \(d_{Q_{k}}(u_{k})\) and \(k=1,\cdots ,m.\)
Proof
Indeed, for any \(x \in X\) and \(u_{k}\in Q_{k},\,k=1,\cdots ,m,\) by setting \(g_{k}=\nabla _{u_{k}}\Phi (u^{*}_{1},\cdots ,u^{*}_{m}),\) we can get the equation
By Lemma 3.3, the function \(\Phi (u_{1},\cdots ,u_{m})\) is Lipschitz-continuous differentiable, we have
In review of [12] (Sect. 2.1), from the fact that the function \(\Phi (u_{1},\cdots ,u_{m})\) is concave, we have
Thus,
Hence, the EGC (3.16) is satisfied.
4 Algorithm
From Lemma 3.4, we know that the EGC holds for \(\mu =\max _{1\leqslant k \leqslant m}\frac{1}{\sigma _{Q_{k}}}L(\Phi ),\,\overline{x}=x^{*}(u^{*})\) and \(\overline{u}_{k}=u^{*}_{k},\,k=1,\cdots ,m.\) The following theorem develops a scheme to choose \(\mu ,\,\overline{x},\,\overline{u}=(\overline{u}_{1},\cdots ,\overline{u}_{m}),\) and makes sure that the EGC (3.16) holds in each iteration.
Theorem 4.1
Let vectors \(\overline{x}\in X\) and \(\overline{u}_{k}\in Q_{k},\,k=1,\cdots ,m,\) satisfying EGC for some positive parameters \(\mu .\) Fix a parameter \(\tau \in (0,\,1)\) and choose \(\mu _{+}=(1-\tau )\mu .\) Let
Then \(\overline{x}_{+}\) and \(\overline{u}_{+}=(\overline{u}_{1+},\cdots ,\overline{u}_{m+})\) satisfy EGC with smoothness parameters \(\mu _{+},\) provided that \(\tau \) is chosen in accordance with the following relation:
Proof
Denote \(\widehat{x}=x^{*}(\widehat{u})\) and \(v_{k}=u_{k}^{*}(\overline{x}).\) By line 2 of (4.1) and the convexity of \(\widehat{f}(x),\) we have
Since \(v_{k}=u_{k}^{*}(\overline{x})\) is an optimal solution of (3.8), by the first-order condition, we have
Hence,
By the above inequalities, (3.19) and (4.1), we can get the following relations:
Moreover, according to lines 1 and 4 of (4.1), we have
The proof is completed.
According to the above theorem and lemmas, the following algorithm is given. Denote \(u^{i}\) as the ith iteration value of \(u,\,x_{i}\) as the ith iteration value of x, and \(u_{k}\) as the kth component of u.
Theorem 4.2
Let the pairs \(\overline{x}_{i}\) and \(\overline{u}^{i}=\{\overline{u}_{1}^{i},\cdots ,\overline{u}_{m}^{i}\}\) be generated by the above algorithm. Then the following inequality holds:
Proof
According to Theorem 4.1 and Lemma 3.4, we have that the sequences \(\{\mu _{1}^{i},\cdots ,\mu _{m}^{i}\}_{i=0}^{\infty }\) and \(\{\tau _{i}\}_{i=0}^{\infty }\) satisfy the EGC (3.16), and
From Lemma 3.3, we have
This completes the proof.
By Theorem 4.2, we can see that the convergence rate of our algorithm is \(O(1/i^{2}),\) where i is the iteration counter.
Next we will introduce some implementation details of the algorithm. Choose the smoothness function \(d_{Q_{k}}(u_{k})\) as the following form:
It is easy to verify that
and the strong convexity parameter \(\sigma _{Q_{k}}=1.\)
We also need to compute the following objects at each iteration.
-
(1)
Computation of \(u_{k}^{*}(\overline{x}),\,k=1,\cdots ,m.\) \(\,u_{k}^{*}(\overline{x})\) is the solution of the following problem:
The solution of the above problem is
-
(2)
Computation of \(x^{*}(u).\,x^{*}(u)\) is the solution of the problem as follows:
The solution of the above problem can be written as
-
(3)
Computation of \(V_{k}(u_{k},\,g),\,k=1,\cdots ,m.\) \(\,V_{k}(u_{k},\,g)\) is the solution of the following problem:
The solution of the above problem can be written as
Thus, all variables of the algorithm can be computed directly.
5 Speeding Up the Convergence
By the above lemmas and theorems, we have found that the Lipschitz constant \(L(\Phi )\) may be too large. So we want to take the following strategies to reduce the constant and speed up the convergence.
For any \(x\in X,\) denote \(x_{e_{k}}\) as an n-dimensional vector, and for any \(i\in e_{k},\) the ith component of \(x_{e_{k}}\) is \(x^{(i)},\) and the other components are 0.
Obviously, for every net \(e_{k},\,x_{e_{k}}\) can be generated by the information of \(e_{k},\) and we have the equalities as follows:
Let \(\mathcal {A}\) be a matrix corresponding to a net with all the n cells. Then it is obvious that
By denoting \(\mathcal {X}^{*}(u)=(x_{1}^{*}(u),\,x_{2}^{*}(u),\cdots ,x_{m}^{*}(u)),\) and \(g_{k}(u)=A(e_{k})x^{*}(u),\) we can get
Denote \(\mathrm{deg}_i\) as the degree of the vertex i in the hypergraph. The following relations hold:
Note that the function \(\Phi (u_{1},\cdots ,u_{m})\) defined by (3.10) is concave and differentiable, and \(x^{*}(u)\) is its minimal solution. Moreover, the function \(\widehat{f}(x)\) is strongly convex with strong convexity parameter \(\widehat{\sigma }=2.\) Thus, we have the following lemma.
Lemma 5.1
The function \(\Phi (u_{1},\cdots ,u_{m})\) is Lipschitz-continuous differentiable with a constant
Proof
From the function \(\Phi (u_{1},\cdots ,u_{m})\) defined by (3.10) and the fact that \(\widehat{f}(x)\) is strongly convex, the minimization problem in (3.10) has the unique solution \(x^{*}(u).\) Consider \(u_{k},\,{v}_{k}\in Q_{k},\,k=1,\cdots ,m.\) We have
Hence, we have
and the lemma holds.
6 Experiments
In this section, we test the algorithm on nine benchmarks of the 2004 International Symposium on Physical Design (ISPD04) placement contest benchmark suites. Our implementation is written in Matlab 7.0, and is run on a personal computer with Intel Core2 Duo CPU E7500 (2.9 GHZ) and 2 GB internal memory, under Windows XP. The information of the nine benchmarks are put in Table 1. In the experiments, we take different values \(\lambda =0.1,\,0.5,\) and 1, and we take the value \(\varepsilon =200\) for every benchmark.
In Fig. 1, we plot the primal function value and the dual function value of the algorithm on the benchmark ibm01 with \(\lambda =1.0\) at each iteration.
From Fig. 1, we can find that the objective function value decreases very fast in the first 10 iterations, and then the value changes very small. Hence, we terminate our algorithm in the experiments when the dual gap is less than 200. The results of the algorithm on the nine benchmarks are put in Table 2.
Table 2 shows the runtime and the final value of \(f(x)\) for different \(\lambda \) and benchmark. In general, the computation of \(u_{k}^{*}(x)\) takes 25 % of the total runtime, the computation of \(V_{k}(u_{k},\,g)\) takes 27 % the computation of \(x^{*}(u)\) takes 14 % the computation of dual function \(\Phi (u_{1},\cdots ,u_{m})\) spends 26 % the computation of primal function \(f(x)\) takes 5 % and the others take 3 % of the total runtime, respectively.
The runtime of our algorithm is not only related to the scale of the benchmark, but also related to \(\lambda \) and the number of cells on the nets. From Fig. 1 and Table 2, we can find that with the increase of the value of \(\lambda ,\) the algorithm costs less time. This is because L is inversely proportional to \(\lambda ,\) and with the increase of L, the improvement of each iteration will be smaller. From the experiments, we also find that computations of \(u_{k}^{*}(x),\,V_{k}(u_{k},\,g),\) and \(\Phi (u_{1},\cdots ,u_{m})\) take most of the runtime, and these computations depend on the number of cells on the nets. When the number of cells on a net is larger, the more runtime of these computations will cost.
Finally, it must be remarked that the problem considered in this paper is only a subproblem in the software packages SimPL [10, 12], ComPLx [9], and Mapple [11], for VLSI placement. Our future research will improve the performance of the algorithm, and implement it for real VLSI placement.
References
Alpert, C.J., Mehta, D.P.: Handbook of Algorithm for Physical Design Automation. Auerbach Publications, New York (2008)
Becker, S., Bobin, J., Candes, E.J.: NESTA: a fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4(1), 1–39 (2011)
Boyd, S., Xiao, L., Mutapcic, A.: Subgradient Methods. Lecture notes for EE364b. Stanford University (2007)
Chu, C.: In: Wang, L.T., Chang, Y.W., Cheng, K.T. (eds.) Chapter 11: Placement in Electronic Design Automation: Synthesis, Verification, and Testing. Elsevier/Morgan, Kaufmann, San Francisco (2008)
Dinh, Q.T., Savorgnan, C., Diehl, M.: Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems. Comput. Optim. Appl. 55, 75–111 (2013)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Hans-Jakob, L., Jörg, D.: Convex risk measures for portfolio optimization and concepts of flexibility. Math. Program. 104(2–3), 541–559 (2005)
Hariharan, L., Pucci, F.D.: Decentralized resource allocation in dynamic networks of agents. SIAM J. Imaging Sci. 19(2), 911–940 (2008)
Kim, M.C., Markov, I.L.: ComPLx: a competitive primal–dual Lagrange optimization for global placement. In: Design Automation Conference, pp. 747–752, 2012
Kim, M.C., Lee, D.J., Markov, I.L.: SimPL: an effective placement algorithm. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 31(1), 50–60 (2012a)
Kim, M.C., Viswanathan, N., Alpert, C.J., Markov, I.L., Ramji, S.: MAPLE: multilevel adaptive placement for mixed-size Designs. In: International Symposium on Physical Design, pp. 193–200, 2012b
Kim, M.C., Lee, D.J., Markov, I.L.: SimPL: an effective placement algorithm. Commun. ACM 55(6), 105–113 (2013)
Lin, T., Chu, C., Shinnerl, J.R., Bustany, I., Nedelchev, I.: POLAR: placement based on novel rough legalization and refinement. In: International Conference on Computer-Aided Design, pp. 357–362, 2013
Markov, I.L., Hu, J., Kim, M.C.: Progress and challenges in VLSI placement research. In: International Conference on Computer-Aided Design, pp. 275–282, 2011
Nemirovski, A.S., Yudin, D.: Problem complexity and method efficiency in optimization. In: Wiley-Interscience Series in Discrete Mathematics, vol. XV. Wiley, New York (1983)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127–152 (2005a)
Nesterov, Y.: Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16(1), 235–249 (2005b)
Nesterov, Y.: Subgradient methods for huge-scale optimization problems. Math. Program. 146(1–2), 275–297 (2014)
Neveen, G., Jochen, K.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Imaging Sci. 37(2), 630–652 (2007)
Schmidt, M., Roux, N.L., Bach, F.: Minimizing finite sums with the stochastic average gradient. Technical report, HAL 00860051 (2013)
Spindler, P., Schlichtmann, U., Johannes, F.M.: Kraftwerk2—a fast force-directed quadratic placement approach using an accurate net model. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27(8), 1398–1411 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported partially by National Natural Science Foundation of China (Nos. 61170308 and 11331003) and National Key Basic Research Science Foundation of China (No. 2011CB808003).
Rights and permissions
About this article
Cite this article
Chen, JL., Cui, Y. & Zhu, WX. Nesterov’s Smoothing and Excessive Gap Methods for an Optimization Problem in VLSI Placement. J. Oper. Res. Soc. China 2, 423–443 (2014). https://doi.org/10.1007/s40305-014-0065-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40305-014-0065-8