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. S. Chatterjee, E. Parker, P. J. Hanlon, and A. R. Lebeck. Exact analysis of the cache behavior of nested loops. In PLDI, pages 286--297, New York, NY, USA, 2001. ACM Press.
6. P. Cousot and R. Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In POPL, pages 238--252, New York, NY, USA, 1977. ACM Press.
7. C. Ferdinand and R. Wilhelm. On Predicting Data Cache Behavior for Real-Time Systems. In LCTES, pages 16--30, London, UK, 1998. Springer-Verlag.
8. C. Ferdinand and R. Wilhelm. Fast and Efficient Cache Behavior Prediction for Real-Time Systems. Real-Time Systems, 17((2/3)), 1999.
9. S. Ghosh, M. Martonosi, and S. Malik. Cache Miss Equations: An Analytical Representation of Cache Misses. In ICS, pages 317--324, New York, NY, USA, 1997. ACM Press.
10. T. Lundqvist and P. Stenström. Timing Anomalies in Dynamically Scheduled Microprocessors. In IEEE Real-Time Systems Symposium, pages 12--21, 1999.
11. H. Ramaprasad and F. Mueller. Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns. In RTAS, pages 148--157, Washington, DC, USA, 2005. IEEE Computer Society.
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. R. Sen and Y. N. Srikant. Executable Analysis using Abstract Interpretation with Circular Linear Progressions. In MEMOCODE, pages 39--48, 2007.
14. R. T. White, C. A. Healy, D. B. Whalley, F. Mueller, and M. G. Harmon. Timing Analysis for Data Caches and Set-Associative Caches. In RTAS, page 192, Washington, DC, USA, 1997. IEEE Computer Society.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software selection and adaptation

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Formal software verification

  • Software organization and properties

    • Extra-functional properties

      • Software performance

    • Software functional properties

      • Formal methods

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis

    • Program semantics