A heuristic algorithm for the fanout problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A heuristic algorithm for the fanout problem

Full text

Pdf (652 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 27th ACM/IEEE Design Automation Conference table of contents

Orlando, Florida, United States

Pages: 357 - 360

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Kanwar Jit Singh	DEC, SGS-Thomson, Texas Instruments, Philips and Intel. and University of California, Berkeley, CA
Alberto Sangiovanni-Vincentelli	University of California, Berkeley, CA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 24, Citation Count: 28

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

ABSTRACT

We present an algorithm to optimally distribute a signal to its required destinations. The choice of the buffers and the topology of the distribution tree depends on the availability of different strength gates and on the load and the required times at the destinations. The general problem is to construct a fanout-tree for a signal so that the required time constraint at the source node is met and the fanout-tree has a minimum area. Since the area constrained fanout problem is NP-complete and area is not a major consideration in present high density designs, we restrict our attention to the simpler problem of designing fast fanout circuits without any area constraint. The proposed algorithm builds the fanout tree by partitioning the fanout signals into subsets and then recursively solving each sub-problem. At each stage the algorithm generates a fanout tree that is an improvement over the previous stage. This feature allows the user to specify the improvement desired by the fanout correction process. The performance of the algorithm, when run on randomly generated distributions of required times and on real design examples, is very promising.

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	G. De Micheli. Performance-Oriented Synthesis of Large-Scale Domino CMOS Circuits. IEEE Transactions on CAD, CAD- 6(5): 751-765, 1987.
	3	H. J. Hoover , M. M. Klawe , N. J. Pippenger, Bounding Fan-out in Logical Networks, Journal of the ACM (JACM), v.31 n.1, p.13-18, Jan. 1984 [doi>10.1145/2422.322412]
	4	K. Keutzer and M. Vancura. Timing Cq3tlmization in a Logic Synthesis System. In G. Saucier, editor, ,Proceedings of International Workshop on Logic and Arch. Synthesis for Silicon Compil. ers, pages 1-13, Grenoble, France, May 1988. Inst. Nat. Polytechnique.
	5	E.L. Lawler. Combinatorial Optinu'zation: Networks and Matroids. Holt, Rinehart and Winston, 1976.
	6	P. G. Paulin and F. Poirot. Logic Decomposition Algorithms for the Timing Optimization of Multi-Level l~gic. In Proceedings of ICCD 89, pages 329-333, 1989.
	7	K. J. Singh, A. R. Wang, R. K. Brayton, and A. Sangiovanni- Vincentelli. Timing Optimization of Combinational Logic. In lCCAD-88, pages 282-285. IEEE, 1988.

CITED BY 29

	Koichi Sato , Masamichi Kawarabayashi , Hideyuki Emura , Naotaka Maeda, Post-layout optimization for deep submicron design, Proceedings of the 33rd annual conference on Design automation, p.740-745, June 03-07, 1996, Las Vegas, Nevada, United States
	Victor N. Kravets , Karem A. Sakallah, M32: a constructive multilevel logic synthesis system, Proceedings of the 35th annual conference on Design automation, p.336-341, June 15-19, 1998, San Francisco, California, United States
	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
	Narendra V. Shenoy , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Resynthesis of multi-phase pipelines, Proceedings of the 30th international conference on Design automation, p.490-496, June 14-18, 1993, Dallas, Texas, 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
	J. P. Fishburn, LATTIS: an iterative speedup heuristic for mapped logic, Proceedings of the 29th ACM/IEEE conference on Design automation, p.488-491, June 08-12, 1992, Anaheim, California, United States
	T. Mitsuhashi , M. Murakata , K. Yoshida , T. Aoki, Physical design CAD in deep sub-micron era, Proceedings of the conference on European design automation, p.350-355, September 1996, Geneva, Switzerland
	Juho Kim , Cyrus Bamji , Yanbin Jiang , Sachin Sapatnekar, Concurrent transistor sizing and buffer insertion by considering cost-delay tradeoffs, Proceedings of the 1997 international symposium on Physical design, p.130-135, April 14-16, 1997, Napa Valley, California, United States
	Rajeev Murgai, On the global fanout optimization problem, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.511-515, November 07-11, 1999, San Jose, California, United States
	Hirendu Vaishnav , Massoud Pedram, Routability-driven fanout optimization, Proceedings of the 30th international conference on Design automation, p.230-235, June 14-18, 1993, Dallas, Texas, United States
	Rajeev Murgai, Efficient global fanout optimization algorithms, Proceedings of the 2001 conference on Asia South Pacific design automation, p.571-576, January 2001, Yokohama, Japan
	G. Saucier , D. Brasen , J. P. Hiol, Partitioning with cone structures, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.236-239, November 07-11, 1993, Santa Clara, California, United States
	P. Cocchini , M. Pedram , G. Piccinini , M. Zamboni, Fanout optimization under a submicron transistor-level delay model, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.551-556, November 08-12, 1998, San Jose, California, United States
	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
	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
	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
	Kurt Keutzer , A. Richard Newton , Narendra Shenoy, The future of logic synthesis and physical design in deep-submicron process geometries, Proceedings of the 1997 international symposium on Physical design, p.218-224, April 14-16, 1997, Napa Valley, California, United States
	David S. Kung, A fast fanout optimization algorithm for near-continuous buffer libraries, Proceedings of the 35th annual conference on Design automation, p.352-355, June 15-19, 1998, San Francisco, California, United States
	Ko Yoshikawa , Hiroshi Ichiryu , Hisato Tanishita , Sigenobu Suzuki , Nobuyoshi Nomizu , Akira Kondoh, Timing optimization on mapped circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.112-117, June 17-22, 1991, San Francisco, California, United States
	Rajeev Murgai, Technology-based transformations, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	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
	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
	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
	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
	Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
	Qinghua Liu , Malgorzata Marek-Sadowska, Wire length prediction-based technology mapping and fanout optimization, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, 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
	D. Bañeres , J. Cortadella , M. Kishinevsky, Layout-aware gate duplication and buffer insertion, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	Behnam Amelifard , Farzan Fallah , Massoud Pedram, Low-power fanout optimization using multi threshold voltages and multi channel lengths, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.4, p.478-489, April 2009