A graph based algorithm for optimal buffer insertion under accurate delay models

Youxin Gao, D. F. Wong

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

19 Citations (Scopus)

Abstract

Buffer insertion is an efficient technique in interconnect optimization. This paper presents a graph based algorithm for optimal buffer insertion under accurate delay models. In our algorithm, a signal is accurately represented by a finite ramp which is characterized by two parameters, shift time and transition time. Any accurate delay model, such as delay models based on the transmission line model and SPICE simulations, can be incorporated into our algorithm. The algorithm determines the optimal number of buffers and their locations on a wire such that some optimization objective is satisfied. Two typical examples of such optimization objectives are minimizing the 50% threshold delay and minimizing the transition time. Both can be easily determined in our algorithm. We show that the buffer insertion problem can be reduced to a shortest path problem. The algorithm can be easily extended for simultaneous buffer insertion and wire-sizing, and complexity is still polynomial. The algorithm can also be extended to deal with problems such as buffer insertion subject to transition time constraints at any position along the wire.
Original languageEnglish
Title of host publicationProceedings of The Design, Automation and Test in Europe Conference and Exhibition, DATE 2001
EditorsWolfgang Nebel, Ahmed Jerraya
PublisherIEEE
Pages535-539
Number of pages5
DOIs
Publication statusPublished - Mar 2001
Event2001 Design, Automation and Test in Europe Conference and Exhibition, DATE 2001 - Munich, Germany
Duration: 13 Mar 200116 Mar 2001
https://past.date-conference.com/proceedings-archive/2001/YEAR.HTM (Conference proceedings)

Publication series

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

Conference

Conference2001 Design, Automation and Test in Europe Conference and Exhibition, DATE 2001
Country/TerritoryGermany
CityMunich
Period13/03/0116/03/01
Internet address

Scopus Subject Areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'A graph based algorithm for optimal buffer insertion under accurate delay models'. Together they form a unique fingerprint.

Cite this