A profile-driven statistical analysis framework for the design optimization of soft real-time applications

ABSTRACT

Soft real-time applications lack a formal methodology for their design optimization. Well-established techniques from hard real-time systems cannot be directly applied to soft real-time applications, without losing key benefits of the soft real-time paradigm. We introduce a statistical analysis framework that is well-suited for discovering opportunities for optimization of soft real-time applications. We demonstrate how programmers can use the analysis provided by our framework to perform aggressive soft real-time design optimizations on their applications. The paper introduces the Context Execution Tree (CET) representation for capturing the statistical properties of function calls in the context of their execution in the program. The CET is constructed from an offline-profile of the application. Statistical measures are coupled with techniques that extract runtime distinguishable call-chains. This combination of techniques is applied to the CET to find statistically significant patterns of activity that i) expose slack in the execution of the application with respect to its soft real-time requirements, and ii) can be predicted with low overhead and high reliability during the normal execution of the application.

REFERENCES

• 1: Matthew Arnold , Michael Hind , Barbara G. Ryder, Online feedback-directed optimization of Java, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 2: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 3: Guillem Bernat , Antoine Colin , Stefan M. Petters, WCET Analysis of Probabilistic Hard Real-Time Systems, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.279, December 03-05, 2002
• 4: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 5: John E Freund , Ronald E Walpole, Mathematical statistics (4th ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 6: Robert J. Hall, Call path profiling, Proceedings of the 14th international conference on Software engineering, p.296-306, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143147]
• 7: Kavi, K. M., Youn, H. Y., Shirazi, B., and Hurson, A. R. A performability model for soft real-time systems. In 27th Hawaii International Conference on System Sciences (1994), pp. 571--580.
• 8: 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
• 9: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

General Terms:
Design, Measurement, Performance

Keywords:
behavior prediction, pattern detection, profiling, signatures, soft real-time, statistical analysis