An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation

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

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

10 Citations (Scopus)

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
Title of host publicationProceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999
PublisherIEEE
Pages210-215
Number of pages6
ISBN (Print)076950406X
DOIs
Publication statusPublished - 10 Oct 1999
Event17th IEEE International Conference on Computer Design, ICCD 1999 - Austin, United States
Duration: 10 Oct 199913 Oct 1999
https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding (Conference proceedings)

Publication series

NameProceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors
Volume1999-October
ISSN (Print)1063-6404
ISSN (Electronic)2576-6996

Conference

Conference17th IEEE International Conference on Computer Design, ICCD 1999
Country/TerritoryUnited States
CityAustin
Period10/10/9913/10/99
Internet address

Scopus Subject Areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint

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

Cite this