A fast fanout optimization algorithm for near-continuous buffer libraries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast fanout optimization algorithm for near-continuous buffer libraries

Full text

Pdf (186 KB)

Source

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

San Francisco, California, United States

Pages: 352 - 355

Year of Publication: 1998

ISBN:0-89791-964-5

Author

David S. Kung

IBM T. J. Watson Research Center, 33-115, P. O. Box 218, Yorktown Heights, NY

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, 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/277044.277143 What is a DOI?

ABSTRACT

This paper presents a gain-based fanout optimization algorithm for near-continuous buffer libraries. A near-continuous buffer library contains many buffers in a wide range of discrete sizes and each buffer of a specific type satisfies a size-independent delay equation. The new fanout algorithm is derived from an optimal algorithm to a special fanout optimization problem for continuous libraries. The gain-based technique constructs fanout trees which have better timing at similar area cost. Since no combinatorial search over buffer sizes or fanout tree topologies is used, our execution time is up to 1000 times faster when compared to conventional fanout algorithms.

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	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]
	3	K. Kodandapani , J. Grodstein , A. Domic , H. Touati, A simple algorithm for fanout optimization using high-performance buffer libraries, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.466-471, November 07-11, 1993, Santa Clara, California, United States
	4	L. Stok , D. S. Kung , D. Brand , A. D. Drumm , L. N. Reddy , N. Hieter , D. J. Geiger , H. H. Chao , P. J. Osler , A. J. Sullivan, BooleDozer: logic synthesis for ASICs, IBM Journal of Research and Development, v.40 n.4, p.407-430, July 1996
	5	Ivan E. Sutherland , Robert F. Sproull, Logical effort: designing for speed on the back of an envelope, Proceedings of the 1991 University of California/Santa Cruz conference on Advanced research in VLSI, p.1-16, April 1991
	6	K. L. Shepard , S. M. Carey , E. K. Cho , B. W. Curran , R. F. Hatch , D. E. Hoffman , S. A. McCabe , G. A. Northrop , R. Seigler, Design methodology for the S/390 parallel enterprise server G4 microprocessors, IBM Journal of Research and Development, v.41 n.4-5, p.515-547, July/Sept. 1997

CITED BY 13

	Peyman Rezvani , Amir H. Ajami , Massoud Pedram , Hamid Savoj, LEOPARD: a Logical Effort-based fanout OPtimizer for ARea and Delay, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.516-519, November 07-11, 1999, San Jose, California, United States
	Rajeev Murgai, Technology-based transformations, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Yiu-Hing Chan , Prabhakar Kudva , Lisa Lacey , Greg Northrop , Thomas Rosser, Physical synthesis methodology for high performance microprocessors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Rajeev Murgai, Performance optimization under rise and fall parameters, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.185-190, November 07-11, 1999, San Jose, California, United States
	Wei Chen , Cheng Ta Hsieh , Massoud Pedram, Simultaneous gate sizing and fanout optimization, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Haoxing Ren , David Z. Pan , David S. Kung, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Ting-Yuan Wang , Jeng-Liang Tsai , Charlie Chung-Ping Chen, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	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
	Behnam Amelifard , Farzan Fallah , Massoud Pedram, Low-power fanout optimization using multiple threshold voltage inverters, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
	Behnam Amelifard , Farzan Fallah , Massoud Pedarm, Low-power fanout optimization using MTCMOS and multi-Vt techniques, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany
	Wei Chen , Massoud Pedram , Premal Buch, Buffered Routing Tree Construction Under Buffer Placement Blockages, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.381, January 07-11, 2002
	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