Clock routing for high-performance ICs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Clock routing for high-performance ICs

Full text

Pdf (877 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 27th ACM/IEEE Design Automation Conference table of contents

Orlando, Florida, United States

Pages: 573 - 579

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Michael A. B. Jackson	Electronics Research Laboratory, University of California, Berkeley, CA
Arvind Srinivasan	Electronics Research Laboratory, University of California, Berkeley, CA
E. S. Kuh	Electronics Research Laboratory, University of California, Berkeley, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 68, Citation Count: 42

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/123186.123406 What is a DOI?

ABSTRACT

In this paper we focus on routing techniques for optimizing clock signals in small-cell (e.g., standard-cell, sea-of gate, etc.…) ASICs. In previously reported work, the routing of the clock net has been performed using ordinary global routing techniques based on a minimum spanning or minimal Steiner tree that have little understanding of clock routing problems. We present a novel approach to clock routing that all but eliminates clock skew and yields excellent phase delay results for a wide range of chip sizes, net sizes (pin count), minimum feature sizes, and pin distributions on both randomly created and standard industrial benchmarks. For certain classes of pin distributions we have proven theoretically and observed experimentally a decrease in skew with an increase in net size. In practice, we have observed a two to three order magnitude reduction in skew when compared to a minimum rectilinear spanning tree.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BBB+89	S. Boon, S. Butler, R. Byrne, B. Setering, M. Casalanda, and Al Scherf. High performance clock distribution for cmos amc's. IEEE Custom late#rated Circuit Conference, pages 15.4.1-15.4.4, 1989.
	BWM86	H. B. Bakoglu, 3. T. Walker, and J. D. Meindl. A symmetric clock-distribution tree and optimized high-speed interconnectiorts for reduced clock skew in ulsi and wsi circuits. IEEE Int. Conference on Computer Design: VLSI in Computers and Processors (ICCD-86), pages 118-122, October 1986.
	DFW84	S. Dhar, M. A. Franklin, and D. F. Wann. Reduction of clock delays in vlsi structures. IEEE Int. Conference on Computer Design: V1,S1 in computers (1CCD), pages 778-783, 1984.
	DS80	R.L.M. Dang and N. Shigyo. A twodimensional simulation of lsi interconnect ca- ~3 citance. IEEE Electron Device Letters, L-2:196-197, August 1980.
	Elm48	W.C. Elmore. The transient response of damped linear networks with particular regard to wideband amplifiers. Journal of Applied Physics, 19(1):55-63, January 1948.
	Fis89	:I.P. Fishburn. 1989. Private Communication.
	FK82	A.L. Fisher and H. T. Kung. Synchronizing large systolic arrays. Proceedings of SPIE, 341:44-52, May 1982.
	FP86	E.G. Friedman and S. Powell. Design and analysis of a hierarchical clock distribution system for synchronous standard cell/macrocell vlsi. IEEE Journal of Solid- State Circuits, SC-21(2):240-246, 1986.
	Han66	M. Hanan. On steiner's problem with rectilinear distances. SIAM Journal of Applied Math, 14:255-265, 1966.
	JSK90	Michael Jackson, Arvind Srinivasan, and E.S. Kuh. Clock routing methodologies. Technical report, University of California at Berkeley, 1990. Memo ERL.
	KGE82	S.Y. Kung and R. J. Gal-Ezer. Synchronous versus asynchronous computation in vlsi array processors. Proceedings of SPIE, pages 53-65, May 1982.
	MC80	Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
	Mij87	D. Mijuskovic. Clock distribution in application specific integrated circuits. Microelectronics Journal, 18(4):15-27, 1987.
	Nag75	W. N agel. Spice2, a computer program to simulate semiconductor circuits. University of California, Berkeley, Memo No. ERL- M520, May 1975.
	RPH83	Jorge Rubinstein, Paul Penfield, and Mark A. ttorowitz Signal delays in rc tree networks. IEEE Trans. Computer-Aided Design, CAD-2:202-211, July 1983.
	RS89	P. Ramanathan and K. G. Shin. A clock distribution scheme for non-symmetric vlsi circuits. IEEE inl. Conference on Computer- Aided Design (ICCAD.89}, pages 398-401, November 1989.
	TKH88	Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, PROUD: A Sea-Of-Gates Placement Algorithm, IEEE Design & Test, v.5 n.6, p.44-56, November 1988 [doi>10.1109/54.9271]
	WF83	D.F. Warm and M. A. Franklin. Asynchronous and clocked control structures for vlsi based interconnection networks. IEEE Transactions on Computers, C-32(3):284- 293, March 1983.

CITED BY 42

	Weixiang Shen , Yici Cai , Xianlong Hong , Jiang Hu , Bing Lu, Zero skew clock routing in X-architecture based on an improved greedy matching algorithm, Integration, the VLSI Journal, v.41 n.3, p.426-438, May, 2008
	Jun Dong Cho , Majid Sarrafzadeh, A buffer distribution algorithm for high-speed clock routing, Proceedings of the 30th international conference on Design automation, p.537-543, June 14-18, 1993, Dallas, Texas, United States
	Masahiko Toyonaga , Keiichi Kurokawa , Takuya Yasui , Atsushi Takahashi, A practical clock tree synthesis for semi-synchronous circuits, Proceedings of the 2000 international symposium on Physical design, p.159-164, May 2000, San Diego, California, United States
	Gary Ellis , Lawrence T. Pileggi , Rob A. Rutenbar, A hierarchical decomposition methodology for multistage clock circuits, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.266-273, November 09-13, 1997, San Jose, California, United States
	Joe G. Xi , Wayne W. M. Dai, Buffer insertion and sizing under process variations for low power clock distribution, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.491-496, June 12-16, 1995, San Francisco, California, United States
	Yu-Min Lee , Hing Yin Lai , Charlie Chung-Ping Chen, Optimal spacing and capacitance padding for general clock structures, Proceedings of the 2001 conference on Asia South Pacific design automation, p.115-119, January 2001, Yokohama, Japan
	T.-H. Chao , J.-M. Ho , Y.-C. Hsu, Zero skew clock net routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.518-523, June 08-12, 1992, Anaheim, California, United States
	Chung-Ping Chen , Yao-Wen Chang , D. F. Wong, Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation, Proceedings of the 33rd annual conference on Design automation, p.405-408, June 03-07, 1996, Las Vegas, Nevada, United States
	Ashok Vittal , Malgorzata Marek-Sadowska, Power optimal buffered clock tree design, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.497-502, June 12-16, 1995, San Francisco, California, United States
	X. Zeng , D. Zhou , Wei Li, Buffer insertion for clock delay and skew minimization, Proceedings of the 1999 international symposium on Physical design, p.36-41, April 12-14, 1999, Monterey, California, United States
	Jatuchai Pangjun , Sachin S. Sapatnekar, Clock distribution using multiple voltages, Proceedings of the 1999 international symposium on Low power electronics and design, p.145-150, August 16-17, 1999, San Diego, California, United States
	Chung-Wen Albert Tsao , Andrew B. Kahng, Planar-DME: improved planar zero-skew clock routing with minimum pathlength delay, Proceedings of the conference on European design automation, p.440-445, September 19-23, 1994, Grenoble, France
	Qing Zhu , Wayne W.-M. Dai , Joe G. Xi, Optimal sizing of high-speed clock networks based on distributed RC and lossy transmission line models, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.628-633, November 07-11, 1993, Santa Clara, California, United States
	Jae Chung , Chung-Kuan Cheng, Skew sensitivity minimization of buffered clock tree, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.280-283, November 06-10, 1994, San Jose, California, United States
	Jae W. Chung , De-Yu Kao , Chung-Kuan Cheng , Ting-Ting Lin, Optimization of power dissipation and skew sensitivity in clock buffer synthesis, Proceedings of the 1995 international symposium on Low power design, p.179-184, April 23-26, 1995, Dana Point, California, United States
	Masato Edahiro, An efficient zero-skew routing algorithm, Proceedings of the 31st annual conference on Design automation, p.375-380, June 06-10, 1994, San Diego, California, United States
	Qing Zhu , Wayne Wei-Ming Dai, Perfect-balance planar clock routing with minimal path-length, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.473-476, November 1992, Santa Clara, California, United States
	Andrew Kahng , Jason Cong , Gabriel Robins, High-performance clock routing based on recursive geometric matching, Proceedings of the 28th conference on ACM/IEEE design automation, p.322-327, June 17-22, 1991, San Francisco, California, United States
	David Garrett , Mircea Stan , Alvar Dean, Challenges in clockgating for a low power ASIC methodology, Proceedings of the 1999 international symposium on Low power electronics and design, p.176-181, August 16-17, 1999, San Diego, California, United States
	Ikuo Harada , Hitoshi Kitazawa, A global router optimizing timing and area for high-speed bipolar LSI's, Proceedings of the 31st annual conference on Design automation, p.177-181, June 06-10, 1994, San Diego, California, United States
	Jaewon Oh , Iksoo Pyo , Massoud Pedram, Constructing lower and upper bounded delay routing trees using linear programming, Proceedings of the 33rd annual conference on Design automation, p.401-404, June 03-07, 1996, Las Vegas, Nevada, United States
	Shen Lin , C. K. Wong, Process-variation-tolerant clock skew minimization, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.284-288, November 06-10, 1994, San Jose, California, United States
	Andrew B. Kahng , Chung-Wen Albert Tsao, Low-cost single-layer clock trees with exact zero Elmore delay skew, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.213-218, November 06-10, 1994, San Jose, California, United States
	Satyamurthy Pullela , Noel Menezes , Lawrence T. Pillage, Reliable non-zero skew clock trees using wire width optimization, Proceedings of the 30th international conference on Design automation, p.165-170, June 14-18, 1993, Dallas, Texas, United States
	Masato Edahiro, A clustering-based optimization algorithm in zero-skew routings, Proceedings of the 30th international conference on Design automation, p.612-616, June 14-18, 1993, Dallas, Texas, United States
	Ying-Meng Li , Marwan A. Jabri, A zero-skew clock routing scheme for VLSI circuits, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.458-463, November 1992, Santa Clara, California, United States
	Shigetoshi Nakatake , Yukiko Kubo , Yoji Kajitani, Consistent floorplanning with super hierarchical constraints, Proceedings of the 2001 international symposium on Physical design, p.144-149, April 01-04, 2001, Sonoma, California, United States
	Jatuchai Pangjun , Sachin S. Sapatnekar, Low-power clock distribution using multiple voltages and reduced swings, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.309-318, June 2002
	Alexander Z. Zelikovsky , Ion I. Măndoiu, Practical approximation algorithms for zero- and bounded-skew trees, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.407-416, January 07-09, 2001, Washington, D.C., United States
	Shantanu Ganguly , Shervin Hojat, Clock distribution design and verification for PowerPC microprocessors, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.58-61, November 05-09, 1995, San Jose, California, United States
	Moses Charikar , Jon Kleinberg , Ravi Kumar , Sridhar Rajagopalan , Amit Sahai , Andrew Tomkins, Minimizing wirelength in zero and bounded skew clock trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.177-184, January 17-19, 1999, Baltimore, Maryland, United States
	Yongseok Cheon , Pei-Hsin Ho , Andrew B. Kahng , Sherief Reda , Qinke Wang, Power-aware placement, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Chung-Seok (Andy) Seo , Abhijit Chatterjee , Sang-Yeon Cho , Nan M. Jokerst, Design and optimization of board-level optical clock distribution network for high-performance optoelectronic system-on-a-packages, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Nan Guofang , Li Minqiang , Kou Jisong, Multi-level genetic algorithm (MLGA) for the construction of clock binary tree, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Joe Gufeng Xi , Wayne Wei-Ming Dai, Useful-Skew Clock Routing with Gate Sizing for Low Power Design, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.163-179, June/July 1997
	C. Yeh , G. Wilke , H. Chen , S. Reddy , H. Nguyen , T. Miyoshi , W. Walker , R. Murgai, Clock Distribution Architectures: A Comparative Study, Proceedings of the 7th International Symposium on Quality Electronic Design, p.85-91, March 27-29, 2006
	A. Balboni , C. Costi , A. Pellencin , M. Quadrini , D. Sciuto, Automatic clock tree generation in ASIC designs, Proceedings of the 1995 European conference on Design and Test, p.351, March 06-09, 1995
	Y. P. Chen , D. F. Wong, An Algorithm for Zero-Skew Clock Tree Routing with Buffer Insertion, Proceedings of the 1996 European conference on Design and Test, p.230, March 11-14, 1996
	Hidenori Sato , Akira Onozawa , Hiroaki Matsuda, A Balanced-Mesh Clock Routing Technique Using Circuit Partitioning, Proceedings of the 1996 European conference on Design and Test, p.237, March 11-14, 1996
	Iksoo Pyo , Jaewon Oh , Massoud Pedram, Constructing Minimal Spanning/Steiner Trees with Bounded Path Length, Proceedings of the 1996 European conference on Design and Test, p.244, March 11-14, 1996
	Jacob Minz , Xin Zhao , Sung Kyu Lim, Buffered clock tree synthesis for 3D ICs under thermal variations, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Chia-Chun Tsai , Jan-Ou Wu , Trong-Yen Lee, GDME: Grey Relational Clustering Applied to a Clock Tree Construction with Zero Skew and Minimal Delay, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.365-374, January 2008