Bounded-skew clock and Steiner routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounded-skew clock and Steiner routing

Full text

Pdf (687 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 3 , Issue 3 (July 1998) table of contents

Pages: 341 - 388

Year of Publication: 1998

ISSN:1084-4309

Authors

Jason Cong	University of California, Los Angeles
Andrew B. Kahng	University of California, Los Angeles
Cheng-Kok Koh	University of California, Los Angeles
C.-W. Albert Tsao	University of California, Los Angeles

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

We study the minimum-cost bounded-skew routing tree problem under the pathlength (linear) and Elmore delay models. This problem captures several engineering tradeoffs in the design of routing topologies with controlled skew. Our bounded-skew routing algorithm, called the BST/DME algorithm, extends the DME algorithm for exact zero-skew trees via the concept of a merging region. For a prescribed topology, BST/DME constructs a bounded-skew tree (BST) in two phases: (i) a bottom-up phase to construct a binary tree of merging regions which represent the loci of possible embedding points of the internal nodes, and (ii) a top-down phase to determine the exact locations of the internal nodes. We present two approaches to construct the merging regions: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and a dynamic programming-based selection technique to consider merging points that are interior to, as well as on the boundary of, the merging regions. When the topology is not prescribed, we propose a new Greedy-BST/DME algorithm which combines the merging region computation with topology generation. The Greedy-BST/DME algorithm very closely matches the best known heuristics for the zero-skew case and for the unbounded-skew case (i.e., the Steiner minimal tree problem). Experimental results show that our BST algorithms can produce a set of routing solutions with smooth skew and wire length tradeoffs.

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	BOESE, K. D., AND KAHNG, A.B. 1992. Zero-skew clock routing trees with minimum wirelength. In Proceedings of the IEEE International ASIC Conference (Sept.) 1.1.1-1.1.5.
	2	BOESE, K. D., KAHNG, A. B., McCoY, B. A., AND ROBINS, G. 1995. Near-optimal critical sink routing tree constructions. IEEE Trans. on Comput.-Aided Des. Int. Circ. and Syst. 14, 12 (Dec.) 1417-1436.
	3	BORAH, M., OWENS, R.M., AND IRWIN, M.J. 1994. An edge-based heuristic for Steiner routing. IEEE Trans. on Comput.-Aided Des. Int. Circ. and Syst. 13, 12 (Dec.) 1563-1568.
	4	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
	5	CHAO, T.-H., Hsu, Y.-C. H., Ho, J.-M., BOESE, K. D., AND KAHNG, A.B. 1992. Zero skew clock routing with minimum wirelength. IEEE Trans. on Circ. and Syst. 39, 11 (Nov.) 799-814.
	6	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
	7	Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
	8	Jason Cong , Andrew B. Kahng , Cheng-Kok Koh , C.-W. Albert Tsao, Bounded-skew clock and Steiner routing under Elmore delay, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.66-71, November 05-09, 1995, San Jose, California, United States
	9	CONG, J., KAHNG, A. B., KOH, C.-K., AND TSAO, C.-W. A. 1995b. Bounded-skew clock and steiner routing under Elmore delay. Tech. Rep. 950030 (Aug.), UCLA CS Dept.
	10	Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.408-425, Dec. 1994 [doi>10.1109/92.335010]
	11	CONG, J., AND KOH, C.-K. 1995. Minimum-cost bounded-skew clock routing. In Proceedings of the IEEE International Symposium on Circuits and Systems (April) 1.215-1.218.
	12	J. Cong , C. Koh , K. Leung, Simultaneous buffer and wire sizing for performance and power optimization, Proceedings of the 1996 international symposium on Low power electronics and design, p.271-276, August 12-14, 1996, Monterey, California, United States
	13	CONG, J., AND LEUNG, K.S. 1995. Optimal wiresizing under the distributed Elmore delay model. IEEE Trans. on Comput.-Aided Des. of Int. Circ. and Syst. 14, 3 (March) 321-336.
	14	EDAHIRO, M. 1991. Minimum skew and minimum path length routing in vlsi layout design. NEC Research and Development 32, 4 (Oct.) 569-575.
	15	EDAHIRO, M. 1992. Minimum path-length equi-distant routing. In Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems (Dec.) 41-46.
	16	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 [doi>10.1145/157485.165066]
	17	EDAHIRO, M. 1993b. Delay minimization for zero-skew routing. In Proceedings of the International Conference on Computer-Aided Design, 563-566.
	18	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 [doi>10.1145/196244.196426]
	19	ELMORE, W.C. 1948. The transient response of damped linear networks with particular regard to wide-band amplifiers. J. Applied Physics 19, 1 (Jan.) 55-63.
	20	FRIEDMAN, E. G., ED. 1995. Clock Distribution networks in VLSI Circuits and Systems: A Selected Reprint Volume. IEEE Circuits and Systems Society.
	21	Dennis J. H. Huang , Andrew B. Kahng , Chung-Wen Albert Tsao, On the bounded-skew clock and Steiner routing problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.508-513, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217579]
	22	KAHNG, A. B., AND ROBINS, G. 1992. A new class of iterative Steiner tree heuristics with good performance. IEEE Trans. on Comput. Aided Des. of Int. Circ. and Syst. 11, 7 (July) 893-902.
	23	KAHNG, n. B., AND ROBINS, G. 1994. On Optimal Interconnections for VLSI. Kluwer, Norwell, MA.
	24	KAHNG, A. B., AND TSAO, C.-W. A. 1996. Planar-DME: A single-layer zero-skew clock tree router. IEEE Trans. on Comput. Aided Des. of Int. Circ. and Syst. 15, 1 (Jan.) 8-19.
	25	Andrew B. Kahng , C.-W. Albert Tsao, More practical bounded-skew clock routing, Proceedings of the 34th annual conference on Design automation, p.594-599, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266292]
	26	Andrew B. Kahng , C.-W. Albert Tsao, Practical Bounded-Skew Clock Routing, Journal of VLSI Signal Processing Systems, v.16 n.2-3, p.199-215, June/July 1997 [doi>10.1023/A:1007995125716]
	27	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
	28	PULLELA, S., MENEZES, N., AND PILEGGI, L.T. 1996. Post-processing of clock trees via wiresizing and buffering for robust design. IEEE Trans. on Comput. Aided Des. of Int. Circ. and Syst. 15, 6 (June) 691-701.
	29	TSAY, R.-S. 1993. An exact zero-skew clock routing algorithm. IEEE Trans. on Comput.- Aided Des. of Int. Circ. and Syst. CAD-12, 2 (Feb.) 242-249.
	30	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 [doi>10.1145/217474.217577]
	31	T.-C. Wang , D. F. Wong, A graph theoretic technique to speed up floorplan area optimization, Proceedings of the 29th ACM/IEEE conference on Design automation, p.62-68, June 08-12, 1992, Anaheim, California, United States
	32	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 [doi>10.1145/217474.217576]
	33	Qing Zhu , Wayne Wei-Ming Dai, Planar clock routing for high performance chip and package co-design, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.2, p.210-226, June 1996 [doi>10.1109/92.502193]
	34	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

CITED BY 26

	I-Min Liu , Tan-Li Chou , Adnan Aziz , D. F. Wong, Zero-skew clock tree construction by simultaneous routing, wire sizing and buffer insertion, Proceedings of the 2000 international symposium on Physical design, p.33-38, May 2000, San Diego, California, United States
	Chung-wen Albert Tsao , Cheng-kok Koh, UST/DME: a clock tree router for general skew constraints, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.359-379, July 2002
	Chung-Wen Albert Tsao , Cheng-Kok Koh, UST/DME: a clock tree router for general skew constraints, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Yu Chen , Andrew B. Kahng , Gang Qu , Alexander Zelikovsky, The associative-skew clock routing problem, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.168-172, November 07-11, 1999, San Jose, California, United States
	Bing Lu , Jiang Hu , Gary Ellis , Haihua Su, Process variation aware clock tree routing, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Kai Wang , Malgorzata Marek-Sadowska, Clock network sizing via sequential linear programming with time-domain analysis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	Anand Rajaram , Jiang Hu , Rabi Mahapatra, Reducing clock skew variability via cross links, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Anand Rajaram , David Z. Pan , Jiang Hu, Improved algorithms for link-based non-tree clock networks for skew variability reduction, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Yongqiang Lu , C. N. Sze , Xianlong Hong , Qiang Zhou , Yici Cai , Liang Huang , Jiang Hu, Navigating registers in placement for clock network minimization, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Ganesh Venkataraman , C. N. Sze , Jiang Hu, Skew scheduling and clock routing for improved tolerance to process variations, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Yongqiang Lu , C. N. Sze , Xianlong Hong , Qiang Zhou , Yici Cai , Liang Huang , Jiang Hu, Register placement for low power clock network, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Wai-Ching Douglas Lam , Cheng-Kok Koh, Process variation robust clock tree routing, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Muhammet Mustafa Ozdal , Martin D. F. Wong, Two-layer bus routing for high-speed printed circuit boards, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.213-227, January 2006
	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
	Min-Seok Kim , Jiang Hu, Associative skew clock routing for difficult instances, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Hao Yu , Yu Hu , Chunchen Liu , Lei He, Minimal skew clock embedding considering time variant temperature gradient, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Saif Ali Butt , Stefan Schmermbeck , Jurij Rosenthal , Alexander Pratsch , Eike Schmidt, System level clock tree synthesis for power optimization, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Anand Rajaram , David Z. Pan, Fast Incremental Link Insertion in Clock Networks for Skew Variability Reduction, Proceedings of the 7th International Symposium on Quality Electronic Design, p.79-84, March 27-29, 2006
	Aseem Agarwal , David Blaauw , Vladimir Zolotov, Statistical Clock Skew Analysis Considering Intra-Die Process Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.914, November 09-13, 2003
	Stephan Held , Bernhard Korte , Jens Maβberg , Matthias Ringe , Jens Vygen, Clock Scheduling and Clocktree Construction for High Performance ASICS, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.232, November 09-13, 2003
	Yanfeng Wang , Qiang Zhou , Yici Cai , Jiang Hu , Xianlong Hong , Jinian Bian, Low power clock buffer planning methodology in F-D placement for large scale circuit design, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Wei-Chung Chao , Wai-Kei Mak, Low-power gated and buffered clock network construction, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.1, p.1-20, January 2008
	Hai Wang , Hao Yu , Sheldon X.-D. Tan, Fast analysis of nontree-clock network considering environmental uncertainty by parameterized and incremental macromodeling, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Yesin Ryu , Taewhan Kim, Clock buffer polarity assignment combined with clock tree generation for power/ground noise minimization, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	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