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

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

doi:10.1109/ICCD.1999.808427

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

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

11 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 language	English
Title of host publication	Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999
Publisher	IEEE
Pages	210-215
Number of pages	6
ISBN (Print)	076950406X
DOIs	https://doi.org/10.1109/ICCD.1999.808427
Publication status	Published - 10 Oct 1999
Event	17th IEEE International Conference on Computer Design, ICCD 1999 - Austin, United States Duration: 10 Oct 1999 → 13 Oct 1999 https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding (Conference proceedings)

Publication series

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

Conference

Conference	17th IEEE International Conference on Computer Design, ICCD 1999
Country/Territory	United States
City	Austin
Period	10/10/99 → 13/10/99
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding (Conference proceedings)

Access to Document

10.1109/ICCD.1999.808427

Cite this

Liu, I.-M., Aziz, A., Wong, D. F., & Zhou, H. (1999). An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation. In Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999 (pp. 210-215). (Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors; Vol. 1999-October). IEEE. https://doi.org/10.1109/ICCD.1999.808427

@inproceedings{f6c5a399e35349debf1c4cfc322252f6,

title = "An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation",

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.",

author = "I-Min Liu and Adnan Aziz and Wong, {D. F.} and Hai Zhou",

year = "1999",

month = oct,

day = "10",

doi = "10.1109/ICCD.1999.808427",

language = "English",

isbn = "076950406X",

series = "Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors",

publisher = "IEEE",

pages = "210--215",

booktitle = "Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999",

address = "United States",

note = "17th IEEE International Conference on Computer Design, ICCD 1999 ; Conference date: 10-10-1999 Through 13-10-1999",

url = "https://ieeexplore.ieee.org/xpl/conhome/6554/proceeding",

}

Liu, I-M, Aziz, A, Wong, DF & Zhou, H 1999, An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation. in Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999. Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors, vol. 1999-October, IEEE, pp. 210-215, 17th IEEE International Conference on Computer Design, ICCD 1999, Austin, Texas, United States, 10/10/99. https://doi.org/10.1109/ICCD.1999.808427

An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation. / Liu, I-Min; Aziz, Adnan; Wong, D. F. et al.
Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999. IEEE, 1999. p. 210-215 (Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors; Vol. 1999-October).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

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

AU - Liu, I-Min

AU - Aziz, Adnan

AU - Wong, D. F.

AU - Zhou, Hai

PY - 1999/10/10

Y1 - 1999/10/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033297643&partnerID=8YFLogxK

U2 - 10.1109/ICCD.1999.808427

DO - 10.1109/ICCD.1999.808427

M3 - Conference proceeding

AN - SCOPUS:0033297643

SN - 076950406X

T3 - Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors

SP - 210

EP - 215

BT - Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999

PB - IEEE

T2 - 17th IEEE International Conference on Computer Design, ICCD 1999

Y2 - 10 October 1999 through 13 October 1999

ER -

Liu IM, Aziz A, Wong DF, Zhou H. An efficient buffer insertion algorithm for large networks based on Lagrangian relaxation. In Proceedings of The 17th IEEE International Conference on Computer Design, ICCD 1999. IEEE. 1999. p. 210-215. (Proceedings - IEEE International Conference on Computer Design (ICCD): VLSI in Computers and Processors). doi: 10.1109/ICCD.1999.808427

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this