A depth-decreasing heuristic for combinational logic

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A depth-decreasing heuristic for combinational logic: or how to convert a ripple-carry adder into a carry-lookahead adder or anything in-between

Full text

Pdf (509 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: 361 - 364

Year of Publication: 1991

ISBN:0-89791-363-9

Author

John P. Fishburn

AT&T Bell Laboratories, Murray Hill, New Jersey

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 24, Citation Count: 16

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.123305 What is a DOI?

ABSTRACT

This paper describes a heuristic for speeding up combinational logic by decreasing the logic depth, at the expense of a minimal increase in circuit size. The heuristic iteratively speeds up sections of the critical path by the use of Shannon factorization on the late input. This procedure is empirically found to be capable of reproducing or even beating several classic global optimizations: a chain of an associative operator is transformed into a tree, a ripple prefix circuit into a parallel prefix circuit, and a ripple-carry adder into a slightly smaller and faster circuit than the carry-lookahead adder.

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	K. Bartlett, W. Cohen, A. DeGeus, and G. Hachtel. Synthesis and optimization of multilevel logic unck.'r timing constraints. IEEE Trans. CAD, 5:582-596, 1986.
	2	G. Bilardi , F. P. Preparata, Size-time complexity of Boolean networks for prefix computations, Journal of the ACM (JACM), v.36 n.2, p.362-382, April 1989 [doi>10.1145/62044.62052]
	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	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	5	Y. Ofman. On the algorithmic compleydty of discrete functions. Soviet Physics - Doklady, 7:58%-591, 1963.
	6	C. E. Shannon. A symbolic analysis of relay and switching circuits. AIEE Transactions, 57:713-723, 1938.
	7	K.J. $ingh, A. R. Wang, R. K. Brayton, and A. Sangiovanni- Vincentelli. Timing optimization of combinational logic. In ICCAD, pages 282--285, 1988.
	8	I. Sklansky. Conditional sum logic. IRE Transactions on Electronic Computers, 9:226-231, 1960.
	9	Marc Snir, Depth-size trade-offs for parallel prefix computation, Journal of Algorithms, v.7 n.2, p.185-201, June 1986 [doi>10.1016/0196-6774(86)90003-9]
	10	C. S. Wallace. A suggestion for a fast multiplier. IEEE Transactions on Electronic Computers, 13:14-17, 1964.
	11	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987

CITED BY 16

	Kerry S. Lowe , P. Glenn Gulak, A unified discrete gate sizing/cell library optimization method for design and analysis of delay minimized CMOS and BiCMOS circuits, Proceedings of the conference on European design automation, p.42-47, September 19-23, 1994, Grenoble, France
	Narendra V. Shenoy , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Minimum padding to satisfy short path constraints, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.156-161, November 07-11, 1993, Santa Clara, California, United States
	B. Gregory , D. MacMillen , D. Fogg, ISIS: a system for performance driven resource sharing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.285-290, June 08-12, 1992, Anaheim, California, United States
	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
	Dimitrios Kagaris , Spyros Tragoudas, Partial scan with retiming, Proceedings of the 30th international conference on Design automation, p.249-254, June 14-18, 1993, Dallas, Texas, United States
	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
	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
	Rajeev Murgai, Technology-based transformations, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Soha Hassoun , Carl Ebeling, Using precomputation in architecture and logic resynthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.316-323, November 08-12, 1998, San Jose, California, United States
	Luc Rijnders , Zohair Sahraoui , Paul Six , Hugo De Man, Timing optimization by bit-level arithmetic transformations, Proceedings of the conference on European design automation, p.48-53, September 18-22, 1995, Brighton, England
	M. Crastes , K. Sakouti , G. Saucier, A technology mapping method based on perfect and semi-perfect matchings, Proceedings of the 28th conference on ACM/IEEE design automation, p.93-98, June 17-22, 1991, San Francisco, California, United States
	S. Gavrilov , A. Glebov , S. Pullela , S. C. Moore , A. Dharchoudhury , R. Panda , G. Vijayan , D. T. Blaauw, Library-less synthesis for static CMOS combinational logic circuits, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.658-662, November 09-13, 1997, San Jose, California, United States
	Dimitrios Kagaris , Spyros Tragoudas, Retiming-Based Partial Scan, IEEE Transactions on Computers, v.45 n.1, p.74-87, January 1996
	Rajesh Garg , Mario Sanchez , Kanupriya Gulati , Nikhil Jayakumar , Anshul Gupta , Sunil P. Khatri, A design flow to optimize circuit delay by using standard cells and PLAs, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	Jianhua Liu , Shuo Zhou , Haikun Zhu , Chung-Kuan Cheng, An Algorithmic Approach for Generic Parallel Adders, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.734, November 09-13, 2003
	Shih-Hsu Huang , Yow-Tyng Nieh, Clock skew scheduling with race conditions considered, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.45-es, September 2007