Simultaneous buffer-sizing and wire-sizing for clock trees based on lagrangian relaxation

Yu Min Lee, Charlie Chung Ping Chen, Yao Wen Chang, D. F. Wong

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)587-594
Number of pages8
JournalVLSI Design
Volume15
Issue number3
DOIs
StatePublished - 2002
Externally publishedYes

Keywords

  • Buffer-sizing
  • Clock trees
  • Interconnect optimization
  • Lagrangian relaxation
  • VLSI CAD
  • Wire-sizing

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Simultaneous buffer-sizing and wire-sizing for clock trees based on lagrangian relaxation'. Together they form a unique fingerprint.

Cite this