High-performance clock routing based on recursive geometric matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

High-performance clock routing based on recursive geometric matching

Full text

Pdf (651 KB)

Source

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

San Francisco, California, United States

Pages: 322 - 327

Year of Publication: 1991

ISBN:0-89791-395-7

Authors

Andrew Kahng	UCLA Department of Computer Science, Los Angeles, California
Jason Cong	UCLA Department of Computer Science, Los Angeles, California
Gabriel Robins	UCLA Department of Computer Science, Los Angeles, California

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 26, Citation Count: 26

Additional Information:

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/127601.127688 What is a DOI?

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.

	1	D. Avis, "Worst Case Bounds for the Euclidean Matching Problem", International J. CompuL Math. Appl. 7 (1981), pp. 251-257.
	2	H. Bakoglu, J. T. Walker and J. D. Meindl, "A Symmetric Clock-Distribution Tree and Optimized High- Speed Interconnections for Reduced Clock Skew in ULSI and WSI Circuits", Proc. IEEE ICCD, Port Chester, Oct. 1986, pp. 118-122.
	3	H. Bakoglu, Circuits, Interconnections and Packaging for VLS1, Addison-Wesley, 1990.
	4	J. J. Bartholdi and L. K. Platzman, "A Fast Heuristic Based on Spacefilling Curves for Minimum-Weight Matching in the Plane", Inf. Proc. Letters 17 (1983), pp. 17%180.
	5	S. Dhar, M. A. Franklin and D. F. Warm, "Reduction of Clock Delays in VLSI Structures", Proc. 1EEE ICCD, Port Chester, Oct. 1984, pp. 778-783.
	6	A. L. Fisher and It. T. Kung, "Synchronizing Large Systolic Arrays", Proc. SPIE 341, May 1982, pp. 44-52.
	7	Michael A. B. Jackson , Arvind Srinivasan , E. S. Kuh, Clock routing for high-performance ICs, Proceedings of the 27th ACM/IEEE conference on Design automation, p.573-579, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123406]
	8	A. Kahng, J. Cong and G. Robins, "High- Performance Clock Routing Based on Recursive Geometric Matching", UCLA CSD TR-900045, Nov. 1990.
	9	A. Kahng and G. Robins, "A New Family of Steiner Tree Heuristics With Good Performance" The Iterated 1-Steiner Approach", Proc. IEEE ICCAD, Nov. 1990, pp. 428-431.
	10	E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt Rinehart and Winston, New York, 1976.
	11	Ichiang Lin , David H. C. Du, Performance-driven constructive placement, Proceedings of the 27th ACM/IEEE conference on Design automation, p.103-106, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123235]
	12	T. M. Lin and C. A. Mead, "Signal Delay in General RC Networks", IEEE Trans. on CAD CAD- 3(4) (1984), pp. 331-349.
	13	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	14	P. Ramanathan and K. G. Shin, "A Clock Distribution Scheme for Non-Symmetric VLSI Circuits", Proc. IEEE ICCAD, November 1989, pp. 398-401.
	15	J. R.ubinstein, P. Penfield and M. A. Horowitz, "Signal Delay in RC Tree Networks", IEEE Trans. on CAD CAD-2(3) (1983), pp. 202-211.
	16	T. L. Snyder and J. M. Steele, "Worst-Case Greedy Matchings in the Unit d-Cube", Networks 20 (1990), pp. 779-800.
	17	A. Srinivasan, private communication, Oct. 1990.
	18	J. M. Steele, "Growth Rates of Euclidean Minimal Spanning Trees With Power Weighted Edges", The Annals of Probability 16(4) (1988), pp. 1767-1787.
	19	K. J. Supowit and E. M. Reingold, "Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching", SIAM J. Computing 12(1) (1983), pp. 118-143.
	20	K.J. Supowit, E. M. Reingold, and D. A. Plaisted, "The Travelling Salesman Problem and Minimum Matching in the Unit Square", SIAM J. Computing 12(1) (1983), pp. 144-156.
	21	Pravin Vaidya, Geometry helps in matching, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.422-425, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62253]
	22	D. F. Wann and M. A. Franklin, "Asynchronous and Clocked Control Structure for VLSI Based Interconnection Networks", IEEE Trans. on Compute~ 21(3) (1983), pp. 284-293.

CITED BY 26

	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
	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
	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
	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
	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
	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
	Wasim Khan , Moazzem Hossain , Naveed Sherwani, Zero skew clock routing in multiple-clock synchronous systems, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.464-467, November 1992, Santa Clara, California, United States
	Zhaoyun Xing , Prithviraj Banerjee, A parallel algorithm for zero skew clock tree routing, Proceedings of the 1998 international symposium on Physical design, p.118-123, April 06-08, 1998, Monterey, 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
	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
	Mitsuho Seki , Kenji Inoue , Kazuo Kato , Kouki Tsurusaki , Shin'ichi Fukasawa , Hitoshi Sasaki , Mutsuhito Aizawa, A specified delay accomplishing clock router using multiple layers, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.289-292, November 06-10, 1994, San Jose, California, 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
	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
	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
	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
	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
	Xinjie Wei , Yici Cai , Meng Zhao , Xianlong Hong, Legitimate Skew Clock Routing with Buffer Insertion, Journal of VLSI Signal Processing Systems, v.42 n.2, p.107-116, February 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