## 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 [19] 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 [5], [6] of a 1937 algorithm due to Weiszfeld [22] 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.

Original language | English (US) |
---|---|

Pages (from-to) | 3-13 |

Number of pages | 11 |

Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |

Volume | 17 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1 1998 |

## Keywords

- Analytic placement, gordian-l, interconnect delay, linear placement, linear wirelength, newton, primal dual, quadratic placement, weiszfeld

## ASJC Scopus subject areas

- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering