Timing-driven optimization using lookahead logic circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Timing-driven optimization using lookahead logic circuits

Full text

Pdf (139 KB)

Source

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

San Francisco, California

SESSION: Recent advances in timing, ECO and logic optimization table of contents

Pages 390-395

Year of Publication: 2009

ISBN:978-1-60558-497-3

Authors

Mihir Choudhury	Rice University, Houston
Kartik Mohanram	Rice University, Houston

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 0

Additional Information:

abstract references index terms

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

ABSTRACT

This paper describes a timing-driven optimization technique for the synthesis of multi-level logic circuits. Motivated by the parallel prefix problem, the proposed timing-driven optimization produces logic circuits with "lookahead" properties due to the inherent parallelism among the synthesized sub-circuits. Lookahead logic circuits are synthesized using global critical path sensitization information to decompose and reduce the Boolean functions of the nodes in the technology-independent representation of the logic circuit. Unlike prior timing-driven optimization techniques, where synthesis of the decomposition functions is potentially expensive, the proposed technique has the advantage that the decomposition functions are discovered in the synthesized form. On average, the proposed technique reduces the number of logic levels (mapped delay) of 15 benchmark circuits by 40%, 56%, and 22% (21%, 56% and 10%) over the best results of SIS, ABC, and an industry-standard synthesizer, respectively.

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. Singh et al., "Timing optimization of combinational logic," in Proc. Intl. Conference Computer-aided Design, pp. 282--285, 1988.
	2	C. Berman et al., "Efficient techniques for timing correction," in Proc. Intl. Symposium on Circuits and Systems, pp. 415--419, 1990.
	3	P. McGeer et al., "Performance enhancement through the generalized bypass transform," in Proc. Intl. Conference Computer-aided Design, pp. 184--187, 1991.
	4	K. Keutzer et al., "Is redundancy necessary to reduce delay?," IEEE Trans. Computer-aided Design, vol. 10, no. 4, pp. 427--435, 1991.
	5	H. Touati et al., "Delay optimization of combinational logic circuits by clustering and partial collapsing," in Proc. Intl. Conference Computer-aided Design, pp. 188--191, 1991.
	6	K. Chen et al., "Timing optimization for multi-level combinational networks," in Proc. Design Automation Conference, pp. 339--344, 1991.
	7	A. Saldanha et al., "Performance optimization using exact sensitization," in Proc. Design Automation Conference, pp. 425--429, 1994.
	8	G. de Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994.
	9	M. Fujita et al., "Multi-level logic optimization," in Logic synthesis and verification (S. Hassoun, T. Sasao, and R. K. Brayton, eds.), ch. 2, Kluwer Academic Publishers, Boston, MA, 2002.
	10	F. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, 1991.
	11	S. Lakshmivarahan and S. K. Dhall, Parallel Computing Using the Prefix Problem. Oxford University Press, 1994.
	12	Y.-T. Lai et al., "OBDD-based function decomposition: Algorithms and implementation," IEEE Trans. Computer-aided Design, vol. 15, no. 8, pp. 977--990, 1996.
	13	B. Becker et al., "On the expressive power of OKFDDs," Formal Methods in System Design, vol. 11, no. 1, pp. 5--21, 1997.
	14	C. Yang et al., "BDS: A BDD-based logic optimization system," IEEE Trans. Computer-aided Design, vol. 21, no. 7, pp. 866--876, 2000.
	15	D. Wu et al., "FBDD: A folded logic synthesis system," in Intl. Conference on ASIC, pp. 746--751, 2005.
	16	R. Ladner and M. Fischer, "Parallel prefix computation," Journal of the ACM, vol. 27, no. 4, pp. 831--838, 1980.
	17	"ABC Logic synthesis tool." Please visit the URL http://www.eecs.berkeley.edu/~alanmi/abc/ for further details.
	18	L. Benini et al., "Telescopic units: A new paradigm for performance optimization of vlsi designs," IEEE Trans. Computer-aided Design, vol. 17, no. 3, pp. 220--232, 1998.
	19	L. Benini et al., "Automatic synthesis of large telescopic units based on near-minimum timed supersetting," IEEE Trans. Computers, vol. 48, no. 8, pp. 769--779, 1999.
	20	Y.-S. Su et al., "An efficient mechanism for performance optimization of variable-latency designs," in Proc. Design Automation Conference, pp. 976--981, 2007.
	21	E. Sentovich et al., "SIS: A system for sequential circuit synthesis," Tech. Rep. UCB/ERL M92/41, EECS Department, University of California, Berkeley, 1992.