Performance data collection using a hybrid approach

ABSTRACT

Performance profiling consists of monitoring a software system during execution and then analyzing the obtained data. There are two ways to collect profiling data: event tracing through code instrumentation and statistical sampling. These two approaches have different advantages and drawbacks. This paper proposes a hybrid approach to data collection that combines the completeness of event tracing with the low cost of statistical sampling. We propose to maximize the weighted amount of information obtained during data collection, show that such maximization can be performed in linear time or is NP-hard depending on the data collected and the collection implementation. We propose an approximation algorithm for NP-hard case. Our paper also presents an application of the formal approach to an example use case.

REFERENCES

• 1: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
• 2: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 3: V. Chvatal, Linear Programming, Freeman, 1983.
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: J. Hollingsworth, B. Miller, J. Cargille, Dynamic Program Instrumentation for Scalable Performance Tools, Proceedings of the Scalable High Performance Computing Conference, 1994.
• 6: Jain, R., The Art of Computer Systems Performance Analysis, Wiley 1991.
• 7: R. Lencevicius, E. Metz, A. Ran; Software Validation using Power Profiles, Proceedings of the 20th IASTED International Conference on Applied Informatics (AI 2002), Feb 2002.
• 8: Linear Programming Frequently Asked Questions, 2004 http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
• 9: E. Metz, R. Lencevicius, Efficient Instrumentation for Performance Profiling, Proceedings of the 1st Workshop on Dynamic Analysis, 2003, pp. 143--148.
• 10: E. Metz, R. Lencevicius, Performance Data Collection: A Hybrid Approach, Proceedings of the 2nd International Workshop on Dynamic Analysis, 2004, pp. 48--51.
• 11: S. Sahni, Data Structures, Algorithms and Application in C++, p. 697., Silicon Press, 2005.
• 12: D. Stewart, Measuring Execution Time and Real-Time Performance, Embedded Systems Conference (ESC), 2001.
• 13: K. Subramaniam, M. Thazhuthaveetil, Effectiveness of Sampling Based Software Profilers, 1st International Conference on Reliability and Quality Assurance, 1994, pp. 1--5.
• 14: Jeffrey S. Vetter , Daniel A. Reed, Managing performance analysis with dynamic statistical projection pursuit, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.44-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331576]
• 15: Vtune Performance Analyzer, March 2004. http://www.intel.com/software/products/vtune/.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Algorithms, Measurement, Performance

Keywords:
profiling, sampling, tracing