An improved approach for set-associative instruction cache partial analysis

ABSTRACT

The current Worst Case Execution Time (WCET) computation methods are usually applied to whole programs, this may drive to scalability limitations as the program size becomes bigger. A solution could be to split programs into components that could support separated partial analyses to decrease the computation time. The componentization is also consistent with the more and more frequent use of Component Off The Shelf (COTS). Consequently, we need algorithms to perform analyses on component-wise applications. In this paper, we focus on the partial analysis of set-associative instruction caches, based on the categorization method described by M. Alt et al. We have first evaluated A. Rakib et al.'s approach to this problem and we have shown that, while correct, this approach can be greatly improved by a better estimation of the component effect on the cache. The version we have developed addresses the identified shortcomings and the experimentation results have been evaluated according to two criteria: (1) overestimation of the WCET and (2) computation time gain against the whole program analysis approach.

REFERENCES

• 1: Martin Alt , Christian Ferdinand , Florian Martin , Reinhard Wilhelm, Cache Behavior Prediction by Abstract Interpretation, Proceedings of the Third International Symposium on Static Analysis, p.52-66, September 24-26, 1996
• 2: Ballabriga, C., Cassé, H., and Sainrat, P. WCET computation on software components by partial static analysis. In Junior Researcher Workshop on Real-Time Computing, Nancy, 29/03/2007-30/03/2007 (http://www.loria.fr, March 2007), LORIA, pp. 15--18.
• 3: Cassé, H., and Sainrat, P. OTAWA, a framework for experimenting WCET computations. In 3rd European Congress on Embedded Real-Time Software, Toulouse (25--27 December 2005).
• 4: Cousot, P., and Cousot, R. Static determination of dynamic properties of programs. In Proceedings of the Second International Symposium on Programming (1976), Dunod, Paris, France, pp. 106--130.
• 5: 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]
• 6: Jakob Engblom , Andreas Ermedahl, Pipeline Timing Analysis Using a Trace-Driven Simulator, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.88, December 13-15, 1999
• 7: Ferdinand, C. A fast and efficient cache persistence analysis. Technical report, Universitat des Saarlandes (Sept. 1997).
• 8: Ferdinand, C., Martin, F., and Wilhelm, R. Applying compiler techniques to cache behavior prediction. In Proceedings of the ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems (1997), pp. 37--46.
• 9: Y.-T. S. Li , S. Malik , A. Wolfe, Efficient microarchitecture modeling and path analysis for real-time software, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.298, December 05-07, 1995
• 10: Frank Mueller, Timing Analysis for Instruction Caches, Real-Time Systems, v.18 n.2-3, p.217-247, May 2000 [doi>10.1023/A:1008145215849]
• 11: Mueller, F., and Whalley, D. Fast instruction cache analysis via static cache simulation. TR 94042, Dept. of CS, Florida State University (April 1994).
• 12: Kaustubh Patil , Kiran Seth , Frank Mueller, Compositional static instruction cache simulation, ACM SIGPLAN Notices, v.39 n.7, July 2004
• 13: Rakib, A., Parshin, O., Thesing, S., and Wilhelm, R. Component-wise instruction-cache behavior prediction. In Automated Technology for Verification and Analysis (2004), pp. 211--229.
• 14: Henrik Theiling , Christian Ferdinand , Reinhard Wilhelm, Fast and Precise WCET Prediction by Separated Cache andPath Analyses, Real-Time Systems, v.18 n.2-3, p.157-179, May 2000 [doi>10.1023/A:1008141130870]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design

Keywords:
COTS, WCET computation, abstract interpretation, instruction cache, partial cache analysis, partial static analysis