Accurate and efficient predicate analysis with binary decision diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Accurate and efficient predicate analysis with binary decision diagrams

Full text

Publisher Site , Pdf

Pdf (337 KB),

Ps (6.25 MB)

Source

International Symposium on Microarchitecture archive
Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture table of contents

Monterey, California, United States

Pages: 112 - 123

Year of Publication: 2000

ISBN:1-58113-196-8

Authors

John W. Sias	Center for Reliable and High-Performance Computing, Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, IL
Wen-Mei W. Hwu	Center for Reliable and High-Performance Computing, Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, IL
David I. August	Department of Computer Science, Princeton University, Princeton, NJ

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
IEEE TC - MICRO : IEEE TC - MICRO

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 34, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/360128.360141 What is a DOI?

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	Intel Corporation, IA-64 Application Developer's Architecture Guide, May 1999.
	2	J. C. Park and M. S. Schlansker, On predicated execution, Tech. Rep. HPL-91-58, Hewlett Packard Laboratories, Palo Alto, CA, May 1991.
	3	Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
	4	Alexandre E. Eichenberger , Edward S. Davidson, Register allocation for predicated code, Proceedings of the 28th annual international symposium on Microarchitecture, p.180-191, November 29-December 01, 1995, Ann Arbor, Michigan, United States
	5	David M. Gillies , Dz-ching Roy Ju , Richard Johnson , Michael Schlansker, Global predicate analysis and its application to register allocation, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.114-125, December 02-04, 1996, Paris, France
	6	David I. August , Wen-mei W. Hwu , Scott A. Mahlke, A framework for balancing control flow and predication, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.92-103, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	7	David I. August , Daniel A. Connors , Scott A. Mahlke , John W. Sias , Kevin M. Crozier , Ben-Chung Cheng , Patrick R. Eaton , Qudus B. Olaniran , Wen-mei W. Hwu, Integrated predicated and speculative execution in the IMPACT EPIC architecture, Proceedings of the 25th annual international symposium on Computer architecture, p.227-237, June 27-July 02, 1998, Barcelona, Spain
	8	Lori Carter , Beth Simon , Brad Calder , Larry Carter , Jeanne Ferrante, Predicated Static Single Assignment, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.245, October 12-16, 1999
	9	Richard Johnson , Michael Schlansker, Analysis techniques for predicated code, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.100-113, December 02-04, 1996, Paris, France
	10	David I. August , John W. Sias , Jean-Michel Puiatti , Scott A. Mahlke , Daniel A. Connors , Kevin M. Crozier , Wen-mei W. Hwu, The program decision logic approach to predicated execution, Proceedings of the 26th annual international symposium on Computer architecture, p.208-219, May 01-04, 1999, Atlanta, Georgia, United States
	11	A. Srivastava, Vulcan, Tech. Rep. TR-99-76, Microsoft Research, September 1999.
	12	V. Kathail, M. S. Schlansker, and B. R. Rau, HPL PlayDoh architecture specification: Version 1.0, Tech. Rep. HPL-93-80, Hewlett- Packard Laboratories, Palo Alto, CA, February 1994.
	13	Michael Schlansker , Scott Mahlke , Richard Johnson, Control CPR: a branch height reduction optimization for EPIC architectures, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.155-168, May 01-04, 1999, Atlanta, Georgia, United States
	14	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	15	Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
	16	F. Somenzi, CUDD: Colorado University Decision Diagram package, release 2.30, University of Colorado at Boulder, http://vlsi.colorado.edu/fabio/CUDD/, 1998.
	17	Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
	18	J. W. Sias, Condition awareness support for predicate analysis and optimization, Master's thesis, University of Illinois, Urbana, IL, 1999.
	19	Randal E. Bryant, Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams, Carnegie Mellon University, Pittsburgh, PA, 1992
	20	Peng Tu , David Padua, Gated SSA-based demand-driven symbolic analysis for parallelizing compilers, Proceedings of the 9th international conference on Supercomputing, p.414-423, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224648]
	21	S. B. Akers, Binary decision diagrams, IEEE Transaction on Computers, ol. C-27, pp. 509-516, June 1978.
	22	S. J. Friedman , K. J. Supowit, Finding the optimal variable ordering for binary decision diagrams, Proceedings of the 24th ACM/IEEE conference on Design automation, p.348-356, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37941]
	23	C. L. Berman, Circuit width, register allocation, and ordered binary decision diagrams, IEEE Transactions on Computer-Aided Design, vol. 10, pp. 1059-1066, August 1991.
	24	Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States

CITED BY 7

	Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Kaiyu Chen , Sharad Malik , David I. August, Retargetable static timing analysis for embedded software, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	Lori Carter , Brad Calder, Using predicate path information in hardware to determine true dependences, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Mikhail Smelyanskiy , Scott A. Mahlke , Edward S. Davidson , Hsien-Hsin S. Lee, Predicate-aware scheduling: a technique for reducing resource constraints, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	Noah Snavely , Saumya Debray , Gregory R. Andrews, Unpredication, Unscheduling, Unspeculation: Reverse Engineering Itanium Executables, IEEE Transactions on Software Engineering, v.31 n.2, p.99-115, February 2005
	John W. Sias , Sain-zee Ueng , Geoff A. Kent , Ian M. Steiner , Erik M. Nystrom , Wen-mei W. Hwu, Field-testing IMPACT EPIC research results in Itanium 2, ACM SIGARCH Computer Architecture News, v.32 n.2, p.26, March 2004
	Alexandru Nicolau , Guangqiang Li , Alexander V. Veidenbaum , Arun Kejariwal, Synchronization optimizations for efficient execution on multi-cores, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA