Optimal non-uniform wire-sizing under the Elmore delay model

Chung Ping Chen, Hai Zhou, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


We consider non-uniform wire-sizing for general routing trees under the Elmore delay model. Three minimization objectives are studied: 1) total weighted sink-delay; 2) total area subject to sink-delay bounds; and 3) maximum sink-delay. We first present an algorithm NWSA-wd for minimizing total weighted sink-delays based on iteratively applying the wire-sizing formula in [1]. We show that NWSA-wd always converges to an optimal wire-sizing solution. Based on NWSA-wd and the Lagrangian relaxation technique, we obtained two algorithms NWSA-db and NWSA-md which can optimally solve the other two minimization objectives. Experimental results show that our algorithms are efficient both in terms of runtime and storage. For example, NWSA-wd, with linear runtime and storage, can solve a 6201-wire-segment routing-tree problem using about 1.5-second runtime and 1.3-MB memory on an IBM RS/6000 workstation.

Original languageEnglish (US)
Pages (from-to)38-43
Number of pages6
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design - San Jose, CA, USA
Duration: Nov 10 1996Nov 14 1996

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Optimal non-uniform wire-sizing under the Elmore delay model'. Together they form a unique fingerprint.

Cite this