Greedy wire-sizing is linear time

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

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

6 Citations (Scopus)

Abstract

In interconnect optimization by wire-sizing, minimizing weighted sink delay has been shown to be the key problem. Wire-sizing with many important objectives such as minimizing total area subject to delay bounds or minimizing maximum delay can all be reduced to solving a sequence of weighted sink delay problems by Lagrangian relaxation. GWSA, first introduced in [10] for discrete wire-sizing and later extended in [2] to continuous wire-sizing, is a greedy wire-sizing algorithm for the weighted sink delay problem. Although GWSA has been experimentally shown to be very efficient, 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 using Lagrangian relaxation can be speed up by 57.7%.

Original languageEnglish
Title of host publicationISPD '98
Subtitle of host publicationProceedings of the 1998 International Symposium on Physical Design
PublisherAssociation for Computing Machinery (ACM)
Pages39-44
Number of pages6
ISBN (Print)9781581130218
DOIs
Publication statusPublished - 6 Apr 1998
Event1998 International Symposium on Physical Design, ISPD 1998 - Monterey, United States
Duration: 6 Apr 19988 Apr 1998
https://dl.acm.org/doi/proceedings/10.1145/274535 (Conference proceedings)

Publication series

NameProceedings of The international Symposium on Physical Design, ISPD

Symposium

Symposium1998 International Symposium on Physical Design, ISPD 1998
Country/TerritoryUnited States
CityMonterey
Period6/04/988/04/98
Internet address

Scopus Subject Areas

  • 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