S-Tree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

S-Tree: a technique for buffered routing tree synthesis

Full text

Pdf (172 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 39th annual Design Automation Conference table of contents

New Orleans, Louisiana, USA

SESSION: Routing and buffering table of contents

Pages: 578 - 583

Year of Publication: 2002

ISBN ~ ISSN:0738-100X , 1-58113-461-4

Authors

Miloš Hrkić	University of Illinois at Chicago, Chicago, IL
John Lillis	University of Illinois at Chicago, Chicago, IL

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 23, Citation Count: 13

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

ABSTRACT

We present the S-Tree algorithm for synthesis of buffered interconnects. The approach incorporates a unique combination of real-world issues (handling of routing and buffer blockages, cost minimization, critical sink isolation, sink polarities), robustness and scalability. The algorithm is able to achieve the slack comparable to that of buffered P-Tree [7] using less resources (wire and buffers) in an order of magnitude less cpu time.

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	C. J. Alpert , Miloš Hrkić , J. Hu , A. B. Kahng , J. Lillis , B. Liu , S. T. Quay , S. S. Sapatnekar , A. J. Sullivan , P. Villarrubia, Buffered Steiner trees for difficult instances, Proceedings of the 2001 international symposium on Physical design, p.4-9, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369699]
	2	J. Cong, "Challenges and Opportunities for Design Innovations in Nanometer Technologies," Frontiers in Semiconductor Research: A Collection of SRC Working Papers. SRC, 1997
	3	Jason Cong , Xin Yuan, Routing tree construction under fixed buffer locations, Proceedings of the 37th conference on Design automation, p.379-384, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337502]
	4	S.-W. Hur, A. Jagannathan, J. Lillis, "Timing-Driven Maze Routing," IEEE Transactions on Computer Aided Design Feb. 2000, vol. 19, no. 2, pp. 234--241
	5	Ashok Jagannathan , Sung-Woo Hur , John Lillis, A fast algorithm for context-aware buffer insertion, Proceedings of the 37th conference on Design automation, p.368-373, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337496]
	6	J. Lillis, C.-K. Cheng, T.-T. Y Lin, "Optimal Wire Sizing and Buffer insertion for Low Power and a Generalized Delay Model," IEEE Journal of Solid State Circuits, 31 (3): pp. 437--447, March 1996
	7	John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Simultaneous Routing and Buffer Insertion for High Performance Interconnect, Proceedings of the 6th Great Lakes Symposium on VLSI, p.148, March 22-23, 1996
	8	John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
	9	Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
	10	L.P.P.P. van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay," ISCAS-90, pp. 865--868, 1990
	11	Hai Zhou , D. F. Wong , I-Min Liu , Adnan Aziz, Simultaneous routing and buffer insertion with restrictions on buffer locations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.96-99, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309885]

CITED BY 13

	Miloš Hrkić , John Lillis, Buffer tree synthesis with consideration of temporal locality, sink polarity requirements, solution cost and blockages, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006
	Charles J. Alpert , Gopal Gandham , Miloš Hrkić , Jiang Hu , Stephen T. Quay, Porosity aware buffered steiner tree construction, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Xiaoping Tang , Martin D. F. Wong, Tradeoff routing resource, runtime and quality in buffered routing, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.430-433, January 27-30, 2004, Yokohama, Japan
	Sampath Dechu , Zion Cien Shen , Chris C. N. Chu, An efficient routing tree construction algorithm with buffer insertion, wire sizing and obstacle considerations, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.361-366, January 27-30, 2004, Yokohama, Japan
	Weiping Shi , Zhuo Li , Charles J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.609-614, January 27-30, 2004, Yokohama, Japan
	C. N. Sze , Jiang Hu , Charles J. Alpert, A place and route aware buffered Steiner tree construction, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.355-360, January 27-30, 2004, Yokohama, Japan
	Charles J. Alpert , Miloš Hrkić , Jiang Hu , Stephen T. Quay, Fast and flexible buffer trees that navigate the physical layout environment, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Miloš Hrkić , Miloš Hrkić , John Lillis , Giancarlo Beraudo, An approach to placement-coupled logic replication, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Zhuo Li , C. N. Sze , Charles J. Alpert , Jiang Hu , Weiping Shi, Making fast buffer insertion even faster via approximation techniques, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Zhuo (Robert) Li , Weiping Shi, An O(mn) time algorithm for optimal buffer insertion of nets with m sinks, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Hosung (Leo) Kim , John Lillis , Miloš Hrkić , Miloš Hrkić, Techniques for improved placement-coupled logic replication, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Zhuo Li , Weiping Shi, An O(bn^2) Time Algorithm for Optimal Buffer Insertion with b Buffer Types, Proceedings of the conference on Design, Automation and Test in Europe, p.1324-1329, March 07-11, 2005