Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation

Chung-Ping Chen; Yao-Wen Chang; D. F. Wong

doi:10.1145/240518.240596

Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation

Chung-Ping Chen, Yao-Wen Chang, D. F. Wong

Office of the Provost

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

24 Citations (Scopus)

Abstract

Delay, power, skew, area, and sensitivity are the most important concerns in current clock-tree design. We present in this paper an algorithm for simultaneously optimizing the above objectives by sizing wires and buffers in clock trees. Our algorithm, based on Lagrangian relaxation method, can optimally minimize delay, power, and area simultaneously with very low skew and sensitivity. With linear storage overall and linear runtime per iteration, our algorithm is extremely economical, fast, and accurate; for example, our algorithm can solve a 6201-wire-segment clock-tree problem using about 1-minute runtime and 1.3-MB memory and still achieve pico-second precision on an IBM RS/6000 workstation.

Original language	English
Title of host publication	33rd ACM/IEEE Design Automation Conference - Proceedings 1996
Publisher	Association for Computing Machinery (ACM)
Pages	405-408
Number of pages	4
ISBN (Print)	9780897917797, 0780332946
DOIs	https://doi.org/10.1145/240518.240596
Publication status	Published - Jun 1996
Event	33rd ACM/IEEE Design Automation Conference, DAC 1996 - Las Vegas, United States Duration: 3 Jun 1996 → 7 Jun 1996 https://dl.acm.org/doi/proceedings/10.1145/240518 (Link to conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/3826/proceeding

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	33rd ACM/IEEE Design Automation Conference, DAC 1996
Country/Territory	United States
City	Las Vegas
Period	3/06/96 → 7/06/96
Internet address	https://dl.acm.org/doi/proceedings/10.1145/240518 (Link to conference proceedings) https://ieeexplore.ieee.org/xpl/conhome/3826/proceeding

Scopus Subject Areas

Hardware and Architecture
Control and Systems Engineering

Access to Document

10.1145/240518.240596

Cite this

@inbook{5f84126a79594a6296198da0aeb9f880,

title = "Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation",

abstract = "Delay, power, skew, area, and sensitivity are the most important concerns in current clock-tree design. We present in this paper an algorithm for simultaneously optimizing the above objectives by sizing wires and buffers in clock trees. Our algorithm, based on Lagrangian relaxation method, can optimally minimize delay, power, and area simultaneously with very low skew and sensitivity. With linear storage overall and linear runtime per iteration, our algorithm is extremely economical, fast, and accurate; for example, our algorithm can solve a 6201-wire-segment clock-tree problem using about 1-minute runtime and 1.3-MB memory and still achieve pico-second precision on an IBM RS/6000 workstation.",

author = "Chung-Ping Chen and Yao-Wen Chang and Wong, {D. F.}",

note = "Funding Information: This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459. Publisher Copyright: {\textcopyright} 1997 ACM ; 33rd ACM/IEEE Design Automation Conference, DAC 1996 ; Conference date: 03-06-1996 Through 07-06-1996",

year = "1996",

month = jun,

doi = "10.1145/240518.240596",

language = "English",

isbn = "9780897917797",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "405--408",

booktitle = "33rd ACM/IEEE Design Automation Conference - Proceedings 1996",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/240518, https://ieeexplore.ieee.org/xpl/conhome/3826/proceeding",

}

Chen, C-P, Chang, Y-W & Wong, DF 1996, Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation. in 33rd ACM/IEEE Design Automation Conference - Proceedings 1996. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 405-408, 33rd ACM/IEEE Design Automation Conference, DAC 1996, Las Vegas, Nevada, United States, 3/06/96. https://doi.org/10.1145/240518.240596

Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation. / Chen, Chung-Ping; Chang, Yao-Wen; Wong, D. F.
33rd ACM/IEEE Design Automation Conference - Proceedings 1996. Association for Computing Machinery (ACM), 1996. p. 405-408 (ACM/IEEE Design Automation Conference - Proceedings).

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

TY - CHAP

T1 - Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation

AU - Chen, Chung-Ping

AU - Chang, Yao-Wen

AU - Wong, D. F.

PY - 1996/6

Y1 - 1996/6

N2 - Delay, power, skew, area, and sensitivity are the most important concerns in current clock-tree design. We present in this paper an algorithm for simultaneously optimizing the above objectives by sizing wires and buffers in clock trees. Our algorithm, based on Lagrangian relaxation method, can optimally minimize delay, power, and area simultaneously with very low skew and sensitivity. With linear storage overall and linear runtime per iteration, our algorithm is extremely economical, fast, and accurate; for example, our algorithm can solve a 6201-wire-segment clock-tree problem using about 1-minute runtime and 1.3-MB memory and still achieve pico-second precision on an IBM RS/6000 workstation.

AB - Delay, power, skew, area, and sensitivity are the most important concerns in current clock-tree design. We present in this paper an algorithm for simultaneously optimizing the above objectives by sizing wires and buffers in clock trees. Our algorithm, based on Lagrangian relaxation method, can optimally minimize delay, power, and area simultaneously with very low skew and sensitivity. With linear storage overall and linear runtime per iteration, our algorithm is extremely economical, fast, and accurate; for example, our algorithm can solve a 6201-wire-segment clock-tree problem using about 1-minute runtime and 1.3-MB memory and still achieve pico-second precision on an IBM RS/6000 workstation.

UR - https://dl.acm.org/doi/10.1145/240518.240596

UR - https://ieeexplore.ieee.org/document/545610

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

U2 - 10.1145/240518.240596

DO - 10.1145/240518.240596

M3 - Chapter

AN - SCOPUS:0029712265

SN - 9780897917797

SN - 0780332946

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 405

EP - 408

BT - 33rd ACM/IEEE Design Automation Conference - Proceedings 1996

PB - Association for Computing Machinery (ACM)

T2 - 33rd ACM/IEEE Design Automation Conference, DAC 1996

Y2 - 3 June 1996 through 7 June 1996

ER -

Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this