Volume 15, Issue 3 784084 pp. 587-594
Article
Open Access

Simultaneous Buffer-sizing and Wire-sizing for Clock Trees Based on Lagrangian Relaxation

Yu-Min Lee

Yu-Min Lee

Department of Electrical and Computer Engineering University of Wisconsin Madison, WI 53706, USA , wisc.edu

Search for more papers by this author
Charlie Chung-Ping Chen

Corresponding Author

Charlie Chung-Ping Chen

Department of Electrical and Computer Engineering University of Wisconsin Madison, WI 53706, USA , wisc.edu

Search for more papers by this author
Yao-Wen Chang

Yao-Wen Chang

Department of Electrical Engineering National Taiwan University Taipei, Taiwan , ntu.edu.tw

Search for more papers by this author
D. F. Wong

D. F. Wong

Department of Computer Sciences University of Texas Austin, TX 78712, USA , utexas.edu

Search for more papers by this author
First published: 30 January 2002
Citations: 3

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.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.