Wire segmenting for improved buffer insertion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Wire segmenting for improved buffer insertion

Full text

Pdf (158 KB)

Source

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

Anaheim, California, United States

Pages: 588 - 593

Year of Publication: 1997

ISBN:0-89791-920-3

Authors

Charles Alpert	IBM Austin Research Laboratory, Austin, TX
Anirudh Devgan	IBM Austin Research Laboratory, Austin, TX

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 33, Citation Count: 57

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

ABSTRACT

Buffer insertion seeks to place buffers on the wires of a signal netto minimize delay. Van Ginneken [Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay] proposed an optimal dynamicprogramming solution (with extensions proposed by [7] [8][9] [12]) such that at most one buffer can be placed on a singlewire. This constraint can hurt solution quality, but it may be circumventedby dividing each wire into multiple smaller segments.This work studies the problem of finding the correct number of segmentsfor each wire in the routing tree. Too few segments yieldssub-par solutions, but too many segments can lead to excessive runtimes and memory loads. We derive new theoretical results forcomputing the appropriate number of buffers (and hence wire segments)which motivate our new wire segmenting algorithm. Weshow that using wire segmenting as a precursor to buffer insertionproduces solutions within a few percent of optimal, while usingonly seconds of 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. Leonard Berman , J. Lawrence Carter , Ken F. Day, The fanout problem: from theory to practice, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.69-99, June 1989, Cambridge, Massachusetts, United States
	2	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 [doi>10.1145/240518.240596]
	3	S. Dhar and M. A. Franklin, "Optimum Buffer Circuits for Driving Long Uniform Lines" IEEE Journal of Solid-State Circuits 26(1), 1991, pp. 32-40.
	4	W. C. Elmore, "The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifiers", J. Applied Physics 19, 1948, pp. 55-63.
	5	N. Hedenstierna and K. O. Jeppson, "CMOS Circuit Speed and Buffer Optimization", IEEE Trans. on Computer-Aided Design 6(2), 1987, pp. 270-281.
	6	Lalgudi N. Kannan , Peter R. Suaris , Hong-Gee Fang, A methodology and algorithms for post-placement delay optimization, Proceedings of the 31st annual conference on Design automation, p.327-332, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196399]
	7	J. Lillis, C.-K. Cheng and T.-T. Y. Lin "Optimal and Efficient Buffer Insertion and Wire Sizing", IEEE Custom Integrated Circuits Conference, 1995, pp. 259-262
	8	John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
	9	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 Journal of Solid-State Circuits, 31(3), 1996, pp. 437-447.
	10	Shen Lin , Malgorzata Marek-Sadowska, A fast and efficient algorithm for determining fanout trees in large networks, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	11	Kerry S. Lowe , P. Glenn Gulak, Gate sizing and buffer insertion for optimizing performance in power constrained BiCMOS circuits, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.216-219, November 07-11, 1993, Santa Clara, California, United States
	12	T. Okamoto and J. Cong, "Interconnect Layout Optimization by Simultaneous Steiner Tree Construction and Buffer Insertion", Fifth ACM/SIGDA Physical Design Workshop, 1996, pp. 1-6.
	13	Kanwar Jit Singh , Alberto Sangiovanni-Vincentelli, A heuristic algorithm for the fanout problem, Proceedings of the 27th ACM/IEEE conference on Design automation, p.357-360, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123303]
	14	L. E E E van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay", Proc. International Symposium on Circuits and Systems, 1990, pp. 865-868.

CITED BY 57

	Minghorng Lai , D. F. Wong, Memory-efficient interconnect optimization, Proceedings of the 2001 conference on Asia South Pacific design automation, p.198-202, January 2001, Yokohama, Japan
	Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States
	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
	Chris Chu , D. F. Wong, Closed form solutions to simultaneous buffer insertion/sizing and wire sizing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.343-371, July 2001
	Yu-Yen Mo , Chris Chu, A hybrid dynamic/quadratic programming algorithm for interconnect tree optimization, Proceedings of the 2000 international symposium on Physical design, p.134-139, May 2000, San Diego, California, United States
	I-Min Liu , Adnan Aziz , D. F. Wong, Meeting delay constraints in DSM by minimal repeater insertion, Proceedings of the conference on Design, automation and test in Europe, p.436-440, March 27-30, 2000, Paris, France
	Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion with accurate gate and interconnect delay computation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.479-484, June 21-25, 1999, New Orleans, Louisiana, United States
	Probir Sarkar , Vivek Sundararaman , Cheng-Kok Koh, Routability-driven repeater block planning for interconnect-centric floorplanning, Proceedings of the 2000 international symposium on Physical design, p.186-191, May 2000, San Diego, California, United States
	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
	Yehea I. Ismail , Eby G. Friedman , Jose L. Neves, Exploiting the on-chip inductance in high-speed clock distribution networks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.963-973, 12/1/2001
	Rajeev Murgai, Technology-based transformations, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Yehea I. Ismail , Eby G. Friedman , Jose L. Neves, Repeater insertion in tree structured inductive interconnect, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.420-424, November 07-11, 1999, San Jose, California, United States
	Jason Cong , Tianming Kong , David Zhigang Pan, Buffer block planning for interconnect-driven floorplanning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.358-363, November 07-11, 1999, San Jose, California, United States
	Yehea I. Ismail , Eby G. Friedman , Jose L. Neves, Equivalent Elmore delay for RLC trees, Proceedings of the 36th ACM/IEEE conference on Design automation, p.715-720, June 21-25, 1999, New Orleans, Louisiana, United States
	P. Sarkar , C. Koh, Repeater block planning under simultaneous delay and transition time constraints, Proceedings of the conference on Design, automation and test in Europe, p.540-545, March 2001, Munich, Germany
	Yuchun Ma , Xianlong Hong , Sheqin Dong , Song Chen , Yici Cai , C. K. Cheng , Jun Gu, Dynamic global buffer planning optimization based on detail block locating and congestion analysis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Amir H. Ajami , Kaustav Banerjee , Massoud Pedram, Analysis of substrate thermal gradient effects on optimal buffer insertion, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Charles Alpert , Andrew B. Kahng , Bao Liu , Ion Măndoiu , Alexander Zelikovsky, Minimum-buffered routing of non-critical nets for slew rate and reliability control, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Yi-Hui Cheng , Yao-Wen Chang, Integrating buffer planning with floorplanning for simultaneous multi-objective optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.624-627, 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
	Sebastian Vogel , Martin D. F. Wong, Closed form solution for optimal buffer sizing using the Weierstrass elliptic function, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, 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
	Song Chen , Xianlong Hong , Sheqin Dong , Yuchun Ma , Yici Cai , Chung-Kuan Cheng , Jun Gu, A buffer planning algorithm with congestion optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.615-620, January 27-30, 2004, Yokohama, Japan
	Jiang Hu , Charles J. Alpert , Stephen T. Quay , Gopal Gandham, Buffer insertion with adaptive blockage avoidance, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Jason Cong , Tianming Kong , Zhigang (David) Pan, Buffer block planning for interconnect planning and prediction, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.929-937, 12/1/2001
	Xiaoping Tang , Ruiqi Tian , Hua Xiang , D. F. Wong, A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Rongtian Zhang , Kaushik Roy , Cheng Kok Koh , David B. Janes, Stochastic wire-length and delay distributions of 3-dimensional circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Rajeev Murgai, Layout-driven area-constrained timing optimization by net buffering, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	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
	Rajeev R. Rao , David Blaauw , Dennis Sylvester , Charles J. Alpert , Sani Nassif, An efficient surface-based low-power buffer insertion algorithm, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Yuantao Peng , Xun Liu, Freeze: engineering a fast repeater insertion solver for power minimization using the ellipsoid method, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Yuantao Peng , Xun Liu, A sensitivity analysis of low-power repeater insertion, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Yuchun Ma , Xianlong Hong , Sheqin Dong , Song Chen , Yici Cai , C. K. Cheng , Jun Gu, An integrated floorplanning with an efficient buffer planning algorithm, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Keith W. C. Wong , Evangeline F. Y. Young, Fast buffer planning and congestion optimization in interconnect-driven floorplanning, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Weiping Shi , Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Song Chen , Xianlong Hong , Sheqin Dong , Yuchun Mal , Yici Cai , Chung-Kuan Cheng , Jun Gu, A buffer planning algorithm based on dead space redistribution, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Shu-Min Li , Yih-Huai Cherng , Yao-Wen Chang, Noise-aware buffer planning for interconnect-driven floorplanning, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	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
	Mandar Waghmode , Zhuo Li , Weiping Shi, Buffer insertion in large circuits with constructive solution search techniques, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Francisco-Javier Veredas , Michael Scheppler , Hans-Joerg Pfleiderer, Automated conversion from a LUT-based FPGA to a LUT-based MPGA with fast turnaround time, Proceedings of the conference on Design, automation and test in Europe: Designers' forum, March 06-10, 2006, Munich, Germany
	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
	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
	Xiaoping Tang , D. F. Wong, Planning buffer locations by network flows, Proceedings of the 2000 international symposium on Physical design, p.180-185, May 2000, San Diego, California, United States
	Christoph Bartoschek , Stephan Held , Dieter Rautenbach , Jens Vygen, Fast buffering for optimizing worst slack and resource consumption in repeater trees, Proceedings of the 2009 international symposium on Physical design, March 29-April 01, 2009, San Diego, California, USA
	Yanming Jia , Yici Cai , Xianlong Hong, Dummy fill aware buffer insertion during routing, Proceedings of the 17th great lakes symposium on Great lakes symposium on VLSI, March 11-13, 2007, Stresa-Lago Maggiore, Italy
	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
	J. L. Wong , A. Davoodi , V. Khandelwal , A. Srivastava , M. Potkonjak, Wire-length prediction using statistical techniques, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.702-705, November 07-11, 2004
	C. J. Alpert , Jiang Hu , S. S. Sapatnekar , C. N. Sze, Accurate estimation of global buffer delay within a floorplan, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.706-711, November 07-11, 2004
	Liang Deng , M. D. F. Wong, Buffer insertion under process variations for delay minimization, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.317-321, November 06-10, 2005, San Jose, CA
	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
	Ruiming Li , Dian Zhou , Jin Liu , Xuan Zeng, Power-Optimal Simultaneous Buffer Insertion/Sizing and Wire Sizing, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.581, November 09-13, 2003
	Supratik Chakraborty , Rajeev Murgai, Layout-driven Timing Optimization by Generalized De Morgan Transform, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.647, January 07-11, 2002
	Jinjun Xiong , Kingho Tam , Lei He, Buffer Insertion Considering Process Variation, Proceedings of the conference on Design, Automation and Test in Europe, p.970-975, 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
	Frank Huebbers , Ali Dasdan , Yehea Ismail, Multi-layer interconnect performance corners for variation-aware timing analysis, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Ruiming Chen , Hai Zhou, Fast min-cost buffer insertion under process variations, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Michael Moreinis , Arkadiy Morgenshtein , Israel A. Wagner , Avinoam Kolodny, Logic gates as repeaters (LGR) for area-efficient timing optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.11, p.1276-1281, November 2006