Efficient buffer insertion algorithm for large networks based on Lagrangian relaxation

I. Min Liu, Adnan Aziz, D. F. Wong, Hai Zhou

Research output: Contribution to conferencePaperpeer-review

Abstract

We propose a novel buffer insertion algorithm for handling more general networks, whose underlying topology is a directed acyclic graph rather than just a RC tree. The algorithm finds a global buffering which minimizes buffer area while meeting the timing constraints. We use Lagrangian relaxation to translate the timing constraints to a cost in the objective function, and simplify the resulting objective function using the special structure of the problem we are solving. The core of the algorithm is a local refinement procedure, which iteratively computes the optimal buffering for each edge so as to minimize a weighted area and delay objective. The resulting procedure is fast, and takes full advantage of the slack available on noncritical paths.

Original languageEnglish (US)
Pages210-215
Number of pages6
StatePublished - Dec 1 1999
Externally publishedYes
EventInternational Conference on Computer Design (ICCD'99) - Austin, TX, USA
Duration: Oct 10 1999Oct 13 1999

Other

OtherInternational Conference on Computer Design (ICCD'99)
CityAustin, TX, USA
Period10/10/9910/13/99

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Efficient buffer insertion algorithm for large networks based on Lagrangian relaxation'. Together they form a unique fingerprint.

Cite this