An O(nlogn) time algorithm for optimal buffer insertion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(nlogn) time algorithm for optimal buffer insertion

Full text

Pdf (207 KB)

Source

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

Anaheim, CA, USA

SESSION: Technology mapping, buffering, and bus design table of contents

Pages: 580 - 585

Year of Publication: 2003

ISBN:1-58113-688-9

Authors

Weiping Shi	Texas A&M University, College Station, TX
Zhuo Li	Texas A&M University, College Station, TX

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 37, Citation Count: 15

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

ABSTRACT

The classic algorithm for optimal buffer insertion due to van Ginneken has time and space complexity O(n²), where n is the number of possible buffer positions.

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	Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
	2	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	3	Maggie Kang , Wayne W.-M. Dai , Tom Dillinger , David LaPotin, Delay bounded buffered tree construction for timing driven floorplanning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.707-712, November 09-13, 1997, San Jose, California, United States
	4	J. Lillis, C. K. Cheng and T.-T. Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," IEEE Trans. Solid-State Circuits 31(3), 1996, 437--447.
	5	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]
	6	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
	7	"A fast algorithm for area minimization of slicing floorplans," IEEE Trans. CAD 15(6), 1996, 550--571.
	8	L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree network for minimal Elmore delay," ISCAS 1990, 865--868.
	9	H. Zhou, D. F. Wong, I. M. Liu and A. Aziz, "Simultaneous routing and buffer insertion with restrictions on buffer locations," IEEE Trans. CAD 19(7), 2000, 819--824.

CITED BY 15

	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 , Charles J. Alpert , Jiang Hu , Weiping Shi, Path based buffer insertion, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Christoph Bartoschek , Stephan Held , Dieter Rautenbach , Jens Vygen, Efficient generation of short and fast repeater tree topologies, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Jinjun Xiong , Lei He, Fast buffer insertion considering process variations, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, 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
	Charles J. Alpert , Miloš Hrkić , Stephen T. Quay, A fast algorithm for identifying good buffer insertion candidate locations, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Dian Zhou , Rui-Ming Li, Design and verification of high-speed VLSI physical design, Journal of Computer Science and Technology, v.20 n.2, p.147-165, March 2005
	Yu Hu , King Ho Tam , Tom Tong Jing , Lei He, Fast dual-vdd buffering based on interconnect prediction and sampling, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Hamid Reza Kheirabadi , Morteza Saheb Zamani, An efficient net ordering algorithm for buffer insertion, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	Yen-Pin Chen , Jia-Wei Fang , Yao-Wen Chang, ECO timing optimization using spare cells, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
	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
	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
	Xun Liu , Yuantao Peng , Marios C. Papaefthymiou, RIP: An Efficient Hybrid Repeater Insertion Scheme for Low Power, Proceedings of the conference on Design, Automation and Test in Europe, p.1330-1335, March 07-11, 2005
	Chien Pang Lu , Mango C.-T. Chao , Chen Hsing Lo , Chih Wei Chang, A metal-only-ECO solver for input-slew and output-loading violations, Proceedings of the 2009 international symposium on Physical design, March 29-April 01, 2009, San Diego, California, USA