Efficiently counting program events with support for on-line queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficiently counting program events with support for on-line queries

Full text

Pdf (785 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 16 , Issue 5 (September 1994) table of contents

Pages: 1399 - 1410

Year of Publication: 1994

ISSN:0164-0925

Author

Thomas Ball

Univ. of Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 51, Citation Count: 8

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

ABSTRACT

The ability to count events in a program's execution is required by many program analysis applications. We represent an instrumentation method for efficiently counting events in a program's execution, with support for on-line queries of the event count. Event counting differs from basic block profiling in that an aggregate count of events is kept rather than a set of counters. Due to this difference, solutions to basic block profiling are not well suited to event counting. Our algorithm finds a subset of points in a program to instrument, while guaranteeing that accurate event counts can be obtained efficiently at every point in the execution.

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	Thomas Ball , James R. Larus, Optimally profiling and tracing programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1319-1360, July 1994 [doi>10.1145/183432.183527]
	2	GOLDBERG, A. 1991. Reducing overhead in counter-based execution profiling. Tech. Rep. CSL- TR-91-495, Computer Systems Laboratory, Stanford Univ., Stanford, Calif., (Oct.).
	3	GRAHAM, S. L., KESSLER, P. B., AND McKusIcK, M.K. 1983. An execution profiler for modular programs. Softw. Pract. Exper. 13, 671-685.
	4	HOLLINGSWORTH, J. Z. AND MILLER, B.P. 1993. Dynamic control of performance monitoring on large scale parallel systems. Tech. Rep. # 1133, Univ. of Wisconsin, Madison (Jan.).
	5	Peter B. Kessler, Fast breakpoints: design and implementation, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.78-84, June 1990, White Plains, New York, United States
	6	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	7	KNUTH, D. E. AND STEVENSON, F.R. 1973. Optimal measurement points for program frequency counts. BIT 13, 313-322.
	8	J. M. Mellor-Crummey , T. J. LeBlanc, A software instruction counter, ACM SIGARCH Computer Architecture News, v.17 n.2, p.78-86, April 1989
	9	PROBERT, R.L. 1975. Optimal insertion of software probes in well-delimited programs. IEEE Trans. Soflw. Eng. SE-8, 1 (Jan.), 34-42.
	10	Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.48-60, May 10-14, 1993, Santa Clara, California, United States
	11	Alan Dain Samples, Profile-driven compilation, University of California at Berkeley, Berkeley, CA, 1992
	12	V. Sarkar, Determining average program execution times and their variance, ACM SIGPLAN Notices, v.24 n.7, p.298-312, July 1989

CITED BY 8

	Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
	Thomas Reps , Thomas Ball , Manuvir Das , James Larus, The use of program profiling for software maintenance with applications to the year 2000 problem, ACM SIGSOFT Software Engineering Notes, v.22 n.6, p.432-449, Nov. 1997
	Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, ACM SIGPLAN Notices, v.32 n.5, p.85-96, May 1997
	Taweesup Apiwattanapong , Mary Jean Harrold, Selective path profiling, ACM SIGSOFT Software Engineering Notes, v.28 n.1, January 2003
	Rahul Joshi , Michael D. Bond , Craig Zilles, Targeted Path Profiling: Lower Overhead Path Profiling for Staged Dynamic Optimization Systems, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.239, March 20-24, 2004, Palo Alto, California
	Michael D. Bond , Kathryn S. McKinley, Practical Path Profiling for Dynamic Optimizers, Proceedings of the international symposium on Code generation and optimization, p.205-216, March 20-23, 2005
	Yun Liang , Tulika Mitra, Static analysis for fast and accurate design space exploration of caches, Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, October 19-24, 2008, Atlanta, GA, USA
	Subhajit Roy , Y. N. Srikant, Profiling k-Iteration Paths: A Generalization of the Ball-Larus Profiling Algorithm, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.70-80, March 22-25, 2009