DEP: detailed execution profile

ABSTRACT

In many areas of computer architecture design and program development, the knowledge of dynamic program behavior can be very handy. Several challenges beset the accurate and complete collection of dynamic control flow and memory reference information. These include scalability issues, runtime-overhead, and code coverage. For example, while Tallam and Gupta's work on extending WPP (Whole Program Paths) showed good compressibility, their profile requires 500MBytes of intermediate memory space and an average of 23 times slowdown to be collected.To address these challenges, this paper presents DEP (Detailed Execution Profile). DEP captures the complete dynamic control flow, data dependency and memory reference of a whole program's execution. The profile size is significantly reduced due to the insight that most information can be recovered from a tightly coupled record of control flow and register value changes. DEP is collected in an infrastructure called Adept (A dynamic execution profiling tool), which uses the DynamoRIO binary instrumentation framework to insert profile-collecting instructions within the running application. DEP profiles user-level code execution in its entirety, including interprocedural paths and the execution of multiple threads.The framework for collecting DEP has been tested on real, large and commercial applications. Our experiments show that DEP of Linux SPECInt 2000 benchmarks and Windows SysMark benchmarks can be collected with an average of 5 times slowdown while maintaining competitive compressibility. DEP's profile sizes are about 60% that of traditional profiles.

REFERENCES

• 1: Standard Performance Evaluation Corporation. SPEC CPU2000 benchmark suite, 2000. http://www.spec.org/osg/cpu2000/.
• 2: Sysmark 2004 SE. SYSmark benchmark Second Edition, 2004. http://www.bapco.com/.
• 3: Glenn Ammons , James R. Larus, Improving data-flow analysis with path profiles, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.72-84, June 17-19, 1998, Montreal, Quebec, Canada
• 4: 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
• 5: Derek L. Bruening , Saman Amarasinghe, Efficient, transparent, and comprehensive runtime code manipulation, Massachusetts Institute of Technology, Cambridge, MA, 2004
• 6: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 7: James Law , Gregg Rothermel, Whole program Path-Based dynamic impact analysis, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 8: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 9: Nicholas Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, University of Cambridge, November 2004. http://valgrind.org/.
• 10: Craig G. Nevill-Manning and Ian H. Witten. Identifying hierarchical structure in sequences: A linear-time algorithm. Journal of Artificial Intelligence Research, 7:67--82, 1997.
• 11: Manos Renieris , Shashank Ramaprasad , Steven P. Reiss, Arithmetic program paths, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
• 12: Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.140-153, January 16-18, 2002, Portland, Oregon
• 13: Julian Seward. bzip2. http://www.bzip.org/.
• 14: Sriraman Tallam , Rajiv Gupta , Xiangyu Zhang, Extended Whole Program Paths, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.17-26, September 17-21, 2005 [doi>10.1109/PACT.2005.22]
• 15: Xiangyu Zhang , Rajiv Gupta, Whole Execution Traces, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.105-116, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.37]
• 16: Youtao Zhang , Rajiv Gupta, Timestamped whole program path representation and its applications, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.180-190, June 2001, Snowbird, Utah, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Measurement, Performance

Keywords:
control flow, dynamic instrumentation, memory reference, profile