Greedy wire-sizing is linear time

Chris C.N. Chu, Martin D.F. Wong

Research output: Contribution to journalConference articlepeer-review

Abstract

The greedy wire-sizing algorithm (GWSA) has been experimentally shown to be very efficient, but no mathematical analysis on its convergence rate has ever been reported. In this paper, we consider GWSA for continuous wire sizing. We prove that GWSA converges linearly to the optimal solution, which implies that the run time of GWSA is linear with respect to the number of wire segments for any fixed precision of the solution. Moreover, we also prove that this is true for any starting solution. This is a surprising result because previously it was believed that in order to guarantee convergence, GWSA had to start from a solution in which every wire segment is set to the minimum (or maximum) possible width. Our result implies that GWSA can use a good starting solution to achieve faster convergence. We demonstrate this point by showing that the minimization of maximum delay and the minimization of area subject to maximum delay bound using Lagrangian relaxation can be sped up by more than 50%.

Original languageEnglish (US)
Pages (from-to)398-405
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume18
Issue number4
DOIs
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1998 International Symposium on Physical Design, ISPD-98 - Monterey, CA, United States
Duration: Apr 6 1998Apr 8 1998

Keywords

  • Interconnect
  • Performance optimization
  • Wiresizing

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Greedy wire-sizing is linear time'. Together they form a unique fingerprint.

Cite this