An efficient and optimal algorithm for simultaneous buffer and wire sizing

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

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

38 Citations (Scopus)


In this paper, we consider the problem of interconnect delay minimization by simultaneous buffer and wire sizing under the Elmore delay model. We first present a polynomial time algorithm SBWS to minimize the delay of an interconnect wire. Previously, no polynomial time algorithm for the problem has been reported in the literature. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Experimental results show that SBWS is extremely efficient in practice. For example, for an interconnect of 10 000 segments and buffers, the CPU time is only 0.255 s. We then extend our result to handle interconnect trees. We present an algorithm SBWS-T which always gives the optimal solution. Experimental results show that SBWS-T is faster than the greedy wire sizing algorithm [2] in practice.

Original languageEnglish
Pages (from-to)1297-1304
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
Publication statusPublished - Sept 1999

Scopus Subject Areas

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


Dive into the research topics of 'An efficient and optimal algorithm for simultaneous buffer and wire sizing'. Together they form a unique fingerprint.

Cite this