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

Youxin Gao, D. F. Wong

Research output: Contribution to journalConference articlepeer-review

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 (US)
Article number915075
Pages (from-to)535-539
Number of pages5
JournalProceedings -Design, Automation and Test in Europe, DATE
DOIs
StatePublished - Dec 1 2001
Externally publishedYes
EventDesign, Automation and Test in Europe Conference and Exhibition 2001, DATE 2001 - Munich, Germany
Duration: Mar 13 2001Mar 16 2001

ASJC 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