Efficient and Precise Cache Behavior Prediction for Real-Time Systems | Real-Time Systems Skip to main content
Springer Nature Link
Log in

Efficient and Precise Cache Behavior Prediction for Real-Time Systems

  • Published:
Real-Time Systems Aims and scope Submit manuscript

Abstract

Abstract interpretation is a technique for the static detection of dynamic properties of programs. It is semantics based, that is, it computes approximative properties of the semantics of programs. On this basis, it supports correctness proofs of analyses. It replaces commonly used ad hoc techniques by systematic, provable ones, and it allows for the automatic generation of analyzers from specifications by existing tools. In this work, abstract interpretation is applied to the problem of predicting the cache behavior of programs. Abstract semantics of machine programs are defined which determine the contents of caches. For interprocedural analysis, existing methods are examined and a new approach that is especially tailored for the cache analysis is presented. This allows for a static classification of the cache behavior of memory references of programs. The calculated information can be used to improve worst case execution time estimations. It is possible to analyze instruction, data, and combined instruction/data caches for common (re)placement and write strategies. Experimental results are presented that demonstrate the applicability of the analyses.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alt, M., Ferdinand, C., Martin, F., and Wilhelm, R. 1996. Cache behavior prediction by abstract interpretation. Proc.SAS'96, Static Analysis Symposium. LNCS 1145, Springer, pp. 52–66.

  • Alt, M., and Martin, F. 1995. Generation of efficient interprocedural analyzers with PAG. Proc.SAS'95, Static Analysis Symposium. LNCS 983, Springer, pp. 33–50.

  • Alt, M., Martin, F., and Wilhelm, R. 1995. Generating dataflow analyzers with PAG. Technical Report A10-95, Universit¨ at des Saarlandes.

  • Arnold, R., Mueller, F., Whalley, D. B., and Harmon, M. 1994. Bounding worst-case instruction cache perfor-mance. Proc.IEEE Real-Time Systems Symposium, pp. 172–181.

  • Ball, T., and Larus, J. 1992. Optimally profiling and tracing programs. Proc.19th ACM Symposium on Principles of Programming Languages, pp. 59–70.

  • Basumallick, S., and Nilsen, K. 1994. Cache issues in real-time systems. Proc.ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.

  • Boehm, H. 1996. Performance measurement and caches. 1996. Article in the Usenet newsgroup comp.compilers.

  • Busquets-Mataix, J. V., Serrano, J. J., Ors, R., Gil, P., and Wellings, A. J. 1996. Adding instruction cache effects to schedulability analysis of preemptive real-time systems. Proc.1996 IEEE Real-Time Technology and Applications Symposium, pp. 204–212.

  • Chapman, R., Burns, A., and Wellings, A. J. 1994. Integrated program proof and worst-case timing analysis of SPARC ADA. Proc.ACMSIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.

  • Cousot, P., and Cousot, R. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. Proc.4th ACM Symposium on Principles of Programming Languages, pp. 238–252.

  • Ferdinand, C. 1997. A fast and efficient cache persistence analysis. Technical Report 10/97, Universit¨ at des Saarlandes, Sonderforschungsbereich 124.

    Google Scholar 

  • Ferdinand, C. 1997. Cache behavior prediction for real-time systems. Dissertation, Universit¨ at des Saarlandes.

  • Ferdinand, C., Martin, F., and Wilhelm, R. 1997. Applying compiler techniques to cache behavior prediction. Proc.ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems, pp. 37–46.

  • Ferdinand, C., Martin, F., and Wilhelm, R. 1998. Cache behavior prediction by abstract interpretation. Science of Computer Programming. Selected for SAS'96 special issue.

  • Ferdinand, C., Martin, F., Wilhelm, R., and Alt, M. 1997. Cache behavior prediction by abstract interpretation. Technical Report 05/97, Universit¨ at des Saarlandes, Sonderforschungsbereich 124.

    Google Scholar 

  • Ferdinand, C., and Wilhelm, R. 1998. On predicting data cache behavior for real-time systems. Proc.ACM SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems, Montreal, Canada.

  • Flynn, M. J. 1995. Computer Architecture: Pipelined and Parallel Processor Design. Jones and Bartlett Publish-ers.

  • Garey, M. R., Johnson, D. S. 1979. Computers and Intractability.A Guide to the Theory of NP-Completeness. Freemann and Company.

  • Haase, M. 1999. Beruecksichtigung der Hierarchie und Schreibstrategie von Caches fuer eine exakte Analyse des Cacheverhaltens von Programmen. Diplomarbeit, Universit¨ at des Saarlandes. (To appear).

  • Harmon, M. G., Baker, T. P., and Whalley, D. B. 1994. A retargetable technique for predicting execution time of code segments. Real-Time Systems 7: 159–182.

    Google Scholar 

  • Hennessy, J. L., and Patterson, D. A. 1996. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, second edition.

  • Hur, Y., Bea, Y. H., Lim, S.-S, Rhee, B.-D., Min, S. L., Park, Y. C., Lee, M., Shin, H., and Kim, C. S. 1995. Worst case timing analysis of RISC processors: R3000/R3010 case study. Proc.IEEE Real-Time Systems Symposium, pp. 308–319.

  • Jones, N. D., and Nielson, F. 1995. Abstract interpretation: a semantics-based tool for program analysis. Handbook of Logic in Computer Science. Oxford University Press.

  • Kam, J. B., and Ullman, J. D. 1977. Monotone data flow analysis frameworks. Acta Informatica 7(3): 305–318.

    Google Scholar 

  • Kim, S., Min, S., and Ha, R. 1996. Efficient worst case timing analysis of data caching. Proc.1996 IEEE Real-Time Technology and Applications Symposium, pp. 230–240.

  • Larus, J. 1990. Abstract execution: a technique for efficiently tracing programs. Software Practice and Experience 20(12): 1241–1258.

    Google Scholar 

  • Larus, J. 1996. EEL Guts: Using the EEL Executable Editing Library. Computer Sciences Department, University of Wisconsin-Madison.

    Google Scholar 

  • Larus, J. R., and Schnarr, E. 1995. EEL: machine-independent executable editing. Proc.ACM SIGPLAN Confer-ence on Programming Language Design and Implementation, pp. 291–300.

  • Lee, C., Han, J., Seo, Y., Min, S., Ha, R., Hong, S., Park, C., Lee, M., and Kim, C. 1996. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. Proc.IEEE Real-Time Systems Symposium.

  • Li, Y.-T. S., and Malik, S. 1995. Performance analysis of embedded software using implicit path enumeration. Proc.32nd ACM/IEEE Design Automation Conference, pp. 456–461.

  • Li, Y.-T. S., Malik, S., and Wolfe, A. 1995. Efficient microarchitecture modeling and path analysis for real-time software. Proc.IEEE Real-Time Systems Symposium, pp. 298–307.

  • Li, Y.-T. S, Malik, S., and Wolfe, A. 1996. Cache modeling for real-time software: beyond direct mapped instruction caches. Proc.IEEE REal-Time Systems Symposium.

  • Lim, S.-S., Bae, Y. H., Jang, G. T., Rhee, B.-D., Min, S. L., Park, C. Y, Shin, H., Park, K., Moon, S.-M., and Kim, C. S. 1995. An accurate worst case timing analysis for RISC processors. IEEE Transactions on Software Engineering, 21(7): 593–604.

    Google Scholar 

  • Liu, J.-C., and Lee, H.-J. 1994. Deterministic upperbounds of the worst-case execution time of cached programs. Proc.IEEE Real-Time Systems Symposium, pp. 182–191.

  • Martin, F. 1995. Die Generierung von Datenflußanalysatoren. Diplomarbeit, Universit¨ at des Saarlandes.

  • Martin, F. 1998. PAG — an efficient program analyzer generator. International Journal on Software Tools for Technology Transfer 2(1).

  • McFarling, S. 1989. Program optimization for instruction caches. Proc.Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 183–191.

  • Mendlson, A., Pinter, S. S., and Shtokhamer, R. 1994. Compile time instruction cache optimizations. Computer Architecture News 22(1): 44–51.

    Google Scholar 

  • Mueller, F., 1994. Static cache simulation and its applications. PhD Thesis, Florida State University.

  • Mueller, F. 1996. Generalizing timing predictions to set-associative caches. Technical Report TR 96-66, Institut f¨ ur Informatik, Humboldt-University.

    Google Scholar 

  • Mueller, F., Whalley, D. B., and Harmon, M. 1994. Predicting instruction cache behavior. Proc.ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.

  • Narasimham, K., and Nilsen, K. D. 1994. Portable execution time analysis for RISC processors. Proc.ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.

  • Nilsen, K. D., and Rygg, B. 1995. Worst-case execution time analysis on modern processors. Proc.ACMSIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.

  • Ottoson, G., and Sjödin, M. 1997. Worst-case execution time analysis for modern hardware architectures. Proc. ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems, pp. 47–55.

  • Park, C. Y., and Shaw, A. C. 1991. Experiments with program timing tool based on source-level timing schema. IEEE Computer 24(5): 48–57.

    Google Scholar 

  • Pettis, K., and Hansen, R. C. 1990. Profile guided code positioning. Proc.ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 16–27.

  • Puschner, P., and Koza, C. 1995. Computing maximum task execution times with linear programming techniques. Technical Report, Technische Universit¨ at Wien, Institut f ¨ ur Technische Informatik, Vienna.

    Google Scholar 

  • Puschner, P., and Koza, C. 1989. Calculating the maximum execution time of real-time programs. Real-Time Systems 1: 159–176.

    Google Scholar 

  • Puschner, P., and Schedl, A. 1993. A toll for the computation of worst case execution times. Proc.Euromicro Workshop on Real-Time Systems, pp. 224–229.

  • Ramrath, T. 1997. Entwurf und Implementierung eines Frontends f ¨ ur Analysen Zur Vorhersage des Cache-und Pipelining-Verhaltens. Diplomarbeit, Universit¨ at des Saarlandes.

  • Rawat, J. 1993. Static analysis of cache performance for real-time programming. Masters Thesis, Iowa State University.

  • Rieder, H. 1996.Personal communication. Fraunhofer Institut f¨ ur Zerst¨ orungsfreie Pr¨ ufverfahren, Saarbr¨ ucken.

  • Schneider, J. J. 1998. Statische pipeline-analyse f¨ ur echtzeitsysteme. Diplomarbeit, Universit¨ at des Saarlandes.

  • Sharir, M., and Pnueli, A. 1981. Two approaches to interprocedural data flow analysis. In S. S. Muchnick and N. D. Jones (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, pp. 189–233.

  • Smith, A. J. 1983. Cache memories. ACM Computing Surveys 14(3): 473–530.

    Google Scholar 

  • Stankovic, J. A. 1996. Real-Time and Embedded Systems. ACM 50th Anniversary Report on Real-Time Com-puting Research. http://www-ccs.cs.umass.edu/sdcr/rt.ps.

  • Theiling, H., and Ferdinand, C. 1998. Combining abstract interpretation and ILP for microarchitecture modelling and program path analysis. Proc.19th IEEE Real-Time Systems Symposium, Madrid, Spain, pp. 144–153.

  • Thesing, S., Martin, F., and Alt, M. 1997. PAG Manual. Fachbereich 14, Universit¨ at des Saarlandes.

  • Vrchoticky, A. 1994. Compilation support for fine-grained execution time analysis. Proc.ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.

  • White, R., Mueller, F., Healy, C., Whalley, D., and Harmon, M. 1997. Timing analysis for data caches and set-associative caches. IEEE Real-Time Technology and Applications Symposium, pp. 192–202.

  • Wilhelm, R., and Maurer, D. 1995. Compiler Design. International Computer Science Series. Addison–Wesley, second printing.

  • Zhang, N., Burns, A., and Nicholson, M. 1993. Pipelined processors and worst case execution times. Real-Time Systems 5: 319–343.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Informatik, Universität des Saarlandes, Postfach 15 11 50, D-66041, Saarbrücken

    Christian Ferdinand & Reinhard Wilhelm

Authors
  1. Christian Ferdinand
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Reinhard Wilhelm
    View author publications

    You can also search for this author inPubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ferdinand, C., Wilhelm, R. Efficient and Precise Cache Behavior Prediction for Real-Time Systems. Real-Time Systems 17, 131–181 (1999). https://doi.org/10.1023/A:1008186323068

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008186323068