WCET estimation for executables in the presence of data caches

ABSTRACT

This paper describes techniques to estimate the worst case execution time of executable code on architectures with data caches. The underlying mechanism is Abstract Interpretation, which is used for the dual purposes of tracking address computations and cache behavior. A simultaneous numeric and pointer analysis using an abstraction for discrete sets of values computes safe approximations of access addresses which are then used to predict cache behavior using Must Analysis. A heuristic is also proposed which generates likely worst case estimates. It can be used in soft real time systems and also for reasoning about the tightness of the safe estimate. The analysis methods can handle programs with non-affine access patterns, for which conventional Presburger Arithmetic formulations or Cache Miss Equations do not apply. The precision of the estimates is user-controlled and can be traded off against analysis time. Executables are analyzed directly, which, apart from enhancing precision, renders the method language independent.

REFERENCES

• 1: ARM7TDMI. Technical Reference Manual. "http://www.arm.com/pdfs/DDI0210B_7TDMI_R4.pdf".
• 2: Simplescalar/ARM. "http://www.simplescalar.com/v4test.html".
• 3: WCET Project/Benchmarks. "http://www.mrtc.mdh.se/projects/wcet/benchmarks.html".
• 4: G. Balakrishnan and T. W. Reps. Analyzing Memory Accesses in x86 Executables. In CC, pages 5--23, 2004.
• 5: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 6: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 7: Christian Ferdinand , Reinhard Wilhelm, On Predicting Data Cache Behavior for Real-Time Systems, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.16-30, June 01, 1998
• 8: Christian Ferdinand , Reinhard Wilhelm, Efficient and Precise Cache Behavior Prediction for Real-TimeSystems, Real-Time Systems, v.17 n.2-3, p.131-181, Nov. 1999 [doi>10.1023/A:1008186323068]
• 9: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
• 10: Thomas Lundqvist , Per Stenström, Timing Anomalies in Dynamically Scheduled Microprocessors, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.12, December 01-03, 1999
• 11: Harini Ramaprasad , Frank Mueller, Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.148-157, March 07-10, 2005 [doi>10.1109/RTAS.2005.12]
• 12: R. Sen and Y. N. Srikant. Estimating WCET in the presence of Data Caches. Technical Report. "http://archive.csa.iisc.ernet.in/TR/2007/5".
• 13: Rathijit Sen , Y. N. Srikant, Executable Analysis using Abstract Interpretation with Circular Linear Progressions, Proceedings of the 5th IEEE/ACM International Conference on Formal Methods and Models for Codesign, p.39-48, May 30-June 02, 2007 [doi>10.1109/MEMCOD.2007.371251]
• 14: Randall T. White , Christopher A. Healy , David B. Whalley , Frank Mueller , Marion G. Harmon, Timing Analysis for Data Caches and Set-Associative Caches, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.192, June 09-11, 1997

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Formal methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Performance, Verification