Modeling the function cache for worst-case execution time analysis

ABSTRACT

Static worst-case execution time (WCET) analysis is done by modeling the hardware behavior. In this paper we describe a WCET analysis technique to analyze systems with function caches, a special kind of instruction cache that caches whole functions only. This cache was designed with the aim to be more predictable for the worst-case than existing instruction caches. Within this paper we developed a cache analysis technique for the function cache. One of the new concepts of this analysis technique is the local persistence analysis, which allows to precisely model the function cache.

References

1. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers, Principles, Techniques, and Tools. Addison-Wesley, June 1997. ISBN 0-201-10088-6.
2. R. D. Arnold, F. Mueller, D. Whalley, and M. Harmon. Bounding Worst-Case Instruction Cache Performance. In Proc. 15th Real-Time Systems Symposium (RTSS), pages 172--181, Brookline, Massachusetts, Dec. 1994.
3. Y.-T. S. Li, S. Malik, and A. Wolfe. Cache modeling for real-time software: Beyond direct mapped instruction caches. In Proc. 17th Real-Time Systems Symposium, pages 254--263. IEEE, Dec. 1996.
4. T. Lundqvist and P. Stenström. Timing anomalies in dynamically scheduled microprocessors. In RTSS '99: Proceedings of the 20th IEEE Real-Time Systems Symposium, page 12, Washington, DC, USA, 1999. IEEE Computer Society.
5. F. Martin, M. Alt, R. Wilhelm, and C. Ferdinand. Experimental comparison of call string and functional approaches to interprocedural analysis. In Proc. 7th International Conference on Compiler Construction, LNCS 1383. Springer, 1998.
6. E. E. Myers. A precise inter-procedural data flow algorithm. In Proc. 8th ACM Symposium on Principles of Programming Languages, pages 219--230, 1981.
7. P. Puschner and A. V. Schedl. Computing maximum task execution times - a graph-based approach. Journal of Real-Time Systems, 13:67--91, 1997.
8. M. Schoeberl. A time predictable instruction cache for a Java processor. In On the Move to Meaningful Internet Systems 2004: Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES 2004), volume 3292 of LNCS, pages 371--382, Agia Napa, Cyprus, October 2004. Springer.
9. M. Schoeberl. JOP: A Java Optimized Processor for Embedded Real-Time Systems. PhD thesis, Vienna University of Technology, 2005.
10. M. Schoeberl. A time predictable Java processor. In Proceedings of the Design, Automation and Test in Europe Conference (DATE 2006), pages 800--805, Munich, Germany, March 2006.
11. M. Schoeberl and R. Pedersen. WCET analysis for a Java processor. In Proceedings of the Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES 2006), Paris, France, October 2006.
12. M. Sharir and A. Pnueli. Program Flow Analysis: Theory and Application, chapter 7, Two approaches to interprocedural data flow analysis, pages 189--233. Prentice Hall, 1981.
13. H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET prediction by separate cache and path analyses. Real-Time Systems, 18(2/3), 2000.

Index Terms

• Hardware

  • Integrated circuits

    • Semiconductor memory

  • Robustness