An efficient and optimal algorithm for simultaneous buffer and wire sizing

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

Research output: Contribution to journalArticlepeer-review

Abstract

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 (US)
Pages (from-to)1297-1304
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume18
Issue number9
DOIs
StatePublished - 1999
Externally publishedYes

Keywords

  • Buffer sizing
  • Interconnect
  • Performance optimization
  • Physical design
  • Wire sizing

ASJC Scopus subject areas

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

Fingerprint 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