466Accesses
167Citations
3Altmetric
Abstract
Precise run-time prediction suffers from a complexity problem when doing an integrated analysis. This problem is characterised by the conflict between an optimal solution and the complexity of the computation of the solution.
The analysis of modern hardware consists of two parts: a) the analysis of the microarchitecture's behaviour (caches, pipelines) and b) the search for the longest program path. Because an integrated analysis has a significant computational complexity, we chose to separate these two steps. By this, an ordering problem arises, because the steps depend on each other.
In this paper we show how the microarchitecture analysis can be separated from the path analysis in order to make the overall analysis fast. Practical experiments will show that this separation, however, does not make the analysis more pessimistic than existing approaches. Furthermore, we show that the approach can be used to analyse executables created by a standard optimising compiler.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Aho, A., Sethi, R., and Ullman, J. 1986.Compilers: Principles, Techniques, and Tools. Addison Wesley.
Alt, M., Ferdinand, C., Martin, F., and Wilhelm, R. 1996. Cache behavior prediction by abstract interpretation.Proceedings of SAS'96, Static Analysis Symposium, Volume 1145 ofLecture Notes in Computer Science, pp. 52–66.
Alt, M., and Martin, F. 1995. Generation of efficient interprocedural analyzers with PAG.Proceedings of SAS'95, Static Analysis Symposium, Volume 983 ofLecture Notes in Computer Science, pp. 33–50.
Christian Ferdinand, R. W. 1998. On predicting data cache behavior for real-time systems.Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems. Montreal, Canada.
Cousot, P., and Cousot, R. 1977. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints.Proceedings of the 4th ACM Symposium on Principles of Programming Languages: 238–252.
Engblom, J., Ermedahl, A., and Altenbernd, P. 1998. Facilitating worst-case execution time analysis for optimized code.The 10th Euromicro Workshop on Real-Time Systems. Berlin, Germany.
Ermedahl, A., and Gustafsson, J. 1997. Deriving annotations for tight calculation of execution time.In Proceedings of Euro-Par '97,LNCS 1300. Passau, Germany, pp. 1298–1307.
Ferdinand, C. 1997. Cache Behavior Prediction for Real-Time Systems. PhD Thesis, Universität des Saarlandes.
Ferdinand, C., Martin, F., and Wilhelm, R. 1997. Applying compiler techniques to cache behavior prediction.Proceedings of the ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems: 37–46.
Ferdinand, C., Martin, F., Wilhelm, R., and Alt, M. 1998. Cache behavior prediction by abstract interpretation.Science of Computer Programming, Elsevier.
Li, Y.-T. S., and Malik, S. 1995. Performance analysis of embedded software using implicit path enumeration.Proceedings of the 32nd ACM/IEEE Design Automation Conference: 456–461.
Li, Y.-T. S., Malik, S., and Wolfe, A. 1995. Efficient microarchitecture modeling and path analysis for real-time software.Proceedings of the 16th IEEE Real-Time Systems Symposium: 298–307.
Li, Y.-T. S., Malik, S., and Wolfe, A. 1996. Cache modeling for real-time software: Beyond direct mapped instruction caches.Proceedings of the 17th 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.
Lim, S.-S., Han, J. H., Kim, J., and Min, S. L. 1998. A worst case timing analysis technique for multi-issue machines.Proceedings of the 19th IEEE Real-Time Systems Symposium. Madrid, Spain, pp. 334–345.
Martin, F. 1998. PAG-an efficient program analyzer generator.International Journal on Software Tools for Technology Transfer 2(1).
Martin, F. 1999. Generation of Program Analyzers. Ph.D. thesis, Universität des Saarlandes. to appear.
Martin, F., Alt, M., Wilhelm, R., and Ferdinand, C. 1998. Analysis of loops.Proceedings of the 7th International Conference on Compiler Construction. Koskimies, K., ed. Lecture Notes in Computer Science, Volume 1383.
Mueller, F., Whalley, D. B., and Harmon, M. 1994. Predicting instruction cache behavior.Proceedings of the ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems.
Nielson, F., Nielson, H. R., and Hankin, C. 1999.Principles of Program Analysis, Springer-Verlag.
Ottoson, G., and Sjödin, M. 1997. Worst-case execution time analysis for modern hardware architectures.Proceedings of the ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems: 47–55.
Schneider, J. 1998. Statische Pipeline-Analyse für Echtzeitsysteme. Diploma Thesis, Universität des Saarlandes.
Schneider, J., and Ferdinand, C. 1999. Pipeline behaviour prediction for superscalar processors by abstract interpretation.In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems.
Schrijver, A. 1996.Theory of Linear and Integer Programming. John Wiley & Sons Ltd.
Sicks, M.1997. Adreßbestimmung zur Vorhersage des Verhaltens von Daten-Caches. Diploma Thesis, Universität des Saarlandes.
Stankovic, J. A. 1996. Real-Time and Embedded Systems. ACM 50th Anniversary Report on Real-Time Computing 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.Proceedings of the 19th IEEE Real-Time Systems Symposium. Madrid, Spain, pp. 144–153.
Thesing, S., Martin, F., and Alt, M. 1997. PAG Manual. Fachbereich 14, Universität des Saarlandes.
Tice, C., and Graham, S. L. 1998. OPTVIEW: A new approach for examining optimized code.Proceedings of the 1998 Workshop on Program Analysis for Software Tools and Engineering, Montreal.
Wilhelm, R., and Maurer, D. 1995.Compiler Design, International Computer Science Series. Addison-Wesley. Second Printing.
Author information
Authors and Affiliations
Department of Computer Science, University of the Saarland, Germany
Henrik Theiling & Reinhard Wilhelm
AbsInt Angewandte Informatik GmbH, Saarbrücken, Germany
Christian Ferdinand
- Henrik Theiling
You can also search for this author inPubMed Google Scholar
- Christian Ferdinand
You can also search for this author inPubMed Google Scholar
- Reinhard Wilhelm
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Theiling, H., Ferdinand, C. & Wilhelm, R. Fast and Precise WCET Prediction by Separated Cache and Path Analyses.Real-Time Systems18, 157–179 (2000). https://doi.org/10.1023/A:1008141130870
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative