Name
Abstract | ||
|---|---|---|
A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool minimizes linear wirelength by first approximating the linear wirelength objective by a modified squared wirelength objective, then executing the following loop-(1) minimize the current objective to yield some approximate solution and (2) use the resulting solution to construct a more accurate objective-until the solution converges. This paper shows how to apply a generalization of an algorithm due to Weiszfeld (1937) to placement with a linear wirelength objective and that the main GORDIAN-L loop is actually a special case of this algorithm. We then propose applying a regularization parameter to the generalized Weiszfeld algorithm to control the tradeoff between convergence and solution accuracy; the GORDIAN-L iteration is equivalent to setting this regularization parameter to zero. We also apply novel numerical methods, such as the primal-Newton and primal-dual Newton iterations, to optimize the linear wirelength objective. Finally, we show both theoretically and empirically that the primal-dual Newton iteration stably attains quadratic convergence, while the generalized Weiszfeld iteration is linear convergent. Hence, primal-dual Newton is a superior choice for implementing a placer such as GORDIAN-L, or for any linear wirelength optimization |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/43.673628 | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Keywords | DocType | Volume |
wirelength objective,linear convergent,linear wirelength,global placement,linear wirelength optimization,faster minimization,current objective,regularization parameter,primal-dual newton iteration,linear wirelength objective,gordian-l cell placement tool,gordian-l iteration,numerical method,integrated circuit,newton method,integrated circuit layout,linear convergence,iterative methods,numerical methods,quadratic convergence,minimisation,helium,linear approximation,optimization,gravity,interconnection,computer aided design,implementation,indexing terms,newton iteration | Journal | 17 |
Issue | ISSN | ISBN |
1 | 0278-0070 | 0-89791-927-0 |
Citations | PageRank | References |
29 | 4.13 | 12 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. J. Alpert | 1 | 2445 | 226.04 |
| Tony F. Chan | 2 | 603 | 49.56 |
| Dennis J.-H. Huang | 3 | 58 | 8.25 |
| Dennis J.-H. Huang | 4 | 58 | 8.25 |
| Igor L. Markov | 5 | 3858 | 261.98 |
| P. Mulet | 6 | 407 | 37.69 |
| Kenneth Yan | 7 | 47 | 6.16 |