A polynomial time optimal algorithm for simultaneous buffer and wire sizing

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

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

5 Citations (Scopus)

Abstract

An interconnect joining a source and a sink is divided into fixed-length uniform-width wire segments, and some adjacent segments have buffers in between. The problem we considered is to simultaneously size the buffers and the segments so that the Elmore delay from the source to the sink is minimized. Previously, no polynomial time algorithm for the problem has been reported in the literature. In this paper, we present a polynomial time algorithm SBWS for the simultaneous buffer and wire sizing problem. SBWS is an iterative algorithm with guaranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Also, 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.127 s.

Original languageEnglish
Title of host publicationProceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 1998
PublisherIEEE
Pages479-485
Number of pages7
ISBN (Print)0818683597
DOIs
Publication statusPublished - 23 Feb 1998
Event1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998 - Paris, France
Duration: 23 Feb 199826 Feb 1998
https://ieeexplore.ieee.org/xpl/conhome/5270/proceeding (Conference proceedings)

Publication series

NameProceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE
ISSN (Print)1530-1591

Conference

Conference1998 Design, Automation and Test in Europe Conference and Exhibition, DATE 1998
Country/TerritoryFrance
CityParis
Period23/02/9826/02/98
Internet address

Scopus Subject Areas

  • Engineering(all)

Fingerprint

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

Cite this