Abstract
In hard real-time systems, the worst-case execution times of programs must be known. Obtaining safe upper bounds for these times by measuring actual executions is rarely possible, since the worst case input is normally not known. We apply static program analysis methods to determine an upper bound for the WCET. While this approach is not new, we believe to be the first to have developed a tool that implements these techniques for all the features of a real-life, non-trivial processor, the Motorola ColdFire 5307. Our tool is, to the best of our knowledge, the first one that can determine a safe and rather precise WCET bound for a processor that has caches and pipelines and performs branch prediction and instruction prefetching.
Our approach to use a pipeline model in the analysis of the processor behavior opens up new perspectives towards a generative analysis approach and can prove helpful in investigating other processor properties. The emphasis of this paper is on the modeling of the pipeline behavior as input to the derivation of a pipeline analysis.
This work was partly supported by the RTD project IST-1999-20527 DAEDALUS of the European FP5 program.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Martin Alt and Florian Martin. Generation of Efficient Interprocedural Analyzers with PAG. In Proceedings of SAS’95, Static Analysis Symposium, volume 983 of Lecture Notes in Computer Science. Springer-Verlag, 1995.
David G. Bradlee, Robert R. Henry, and Susan J. Eggers. The Marion System for Retargetable Instruction Scheduling. In Brent Hailpern, editor, Proceedings of the ACM SIGPLAN’ 91 Conference on Programming Language Design and Implementation, pages 229–240, Toronto, ON, Canada, June 1991. ACM Press.
A. Colin and I. Puaut. Worst Case Execution Time Analysis for a Processor with Branch Prediction. Real-Time Systems, Special issue on worst-case execution time analysis, 18(2):249–274, 2000.
Patrick Cousot and Radhia Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Fourth ACM Symposium on Principles of Programming Languages, pages 238–252, Los Angeles, California, 1977. ACM Press, New York.
Christian Ferdinand. Cache Behavior Prediction for Real-Time Systems. PhD thesis, Universität des Saarlandes, 1997.
Christian Ferdinand, Reinhold Heckmann, Marc Langenbach, Florian Martin, Michael Schmidt, Henrik Theiling, Stephan Thesing, and Reinhard Wilhelm. Reliable and precise WCET determination for a real-life processor. In Proceedings of EMSOFT 2001, First Workshop on Embedded Software, volume 2211 of Lecture Notes in Computer Science, 2001.
Peter Grun, Ashok Halambi, Nikil Dutt, and Alex Nicolau. RTGEN: An Algorithm for Automatic Generation of Reservation Tables from Architectural Descriptions. In Proceedings on the 12th International Symposium on Systems Synthesis, 1999.
Ashok Halambi, Peter Grun, Vijay Ganesh, Asheesh Khare, Nikil Dutt, and Alex Nicolau. EXPRESSION: A Language for Architecture Exploration through Compiler/Simulator Retargetability. In DATE, 1999.
Christopher A. Healy, Robert D. Arnold, Frank Mueller, David B. Whalley, and Marion G. Harmon. Bounding Pipeline and Instruction Cache Performance. IEEE Transactions on Computers, 48(1):53–70, January 1999.
Christopher A. Healy, David B. Whalley, and Marion G. Harmon. Integrating the Timing Analysis of Pipelining and Instruction Caching. In Proceedings of the IEEE Real-Time Systems Symposium, pages 288–297, December 1995.
Reinhold Heckmann and Stephan Thesing. Cache and Pipeline Analysis for the ColdFire 5307. Technical report, Universität des Saarlandes, 2001.
http://www.aisee.com. aiSee Home Page.
Yerang Hur, Young Hyun Bae, Sung-Soo Lim, Sung-Kwan Kim, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Minsuk Lee, Heonshik Shin, and Chong Sang Kim. Worst Case Timing Analysis of RISC Processors: R3000/R3100 Case Study. In Proceedings of the IEEE Real-Time Systems Symposium, pages 308–319, December 1995.
Motorola Inc. MCF5307 ColdFire Integrated Microprocessor User’s Manual. Motorola Inc., August 2000. MCF5307UM/D, Rev. 2.0.
Y.-T. S. Li, S. Malik, and A. Wolfe. Cache Modeling for Real-Time Software: Beyond Direct Mapped Instruction Caches. IEEE Real-Time Systems Symposium, January 1997.
Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, and Chong Sang Kim. An Accurate Worst Case Timing Analysis Technique for RISC Processors. IEEE Transactions on Software Engineering, 21(7), July 1995.
Sung-Soo Lim, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, and Chong Sang Kim. Issues of Advanced Architectural Features in the Design of a Timing Tool. In Proceedings of the 11th IEEE Workshop on Real-time Operating Systems and Software, 1994.
Thomas Lundqvist and Per Stenström. Integrating Path and Timing Analysis Using Instruction-Level Simulation Techniques. In Frank Mueller and Azer Bestavros, editors, Proceedings of the ACM SIGPLAN Workshop Languages, Compilers and Tools for Embedded Systems (LCTES), volume 1474 of Lecture Notes in Computer Science, pages 1–15, 1998.
Thomas Lundqvist and Per Stenström. An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution. Real-Time Systems Journal, 17(2/3):183–207, November 1999.
K. Narasimhan and K. Nilsen. Portable Execution Time Analysis for RISC Processors. 1994.
S. Pees, V. Zivojnovic, A. Hoffmann, and H. Meyr. Retargetable Timed Instruction Set Simulation of Pipelined Processor Architectures. In Proceedings of the International Conference on Signal Processing Applications and Technology, September 1998.
P. Puschner and Ch. Koza. Calculating the maximum execution time of real-time programs. Real-Time Systems, 2(1):159–176, 1989.
Jörn Schneider and Christian Ferdinand. Pipeline Behavior Prediction for Superscalar Processors by Abstract Interpretation. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems, volume 34, pages 35–44, May 1999.
Alan C. Shaw. Reasoning About Time in Higher-Level Language Software. IEEE Transactions on Software Engineering, 15(7):875–889, July 1989.
Chuck Siska. A Processor Description Language Supporting Retargetable Multi-Pipeline DSP Program Development Tools. In Proceedings of the 11th International Symposium on System Synthesis, 1998.
Henrik Theiling. Extracting Safe and Precise Control Flow from Binaries. In Proceedings of the 7th Conference on Real-Time Computing Systems and Applications, Cheju Island, South Korea, 2000.
Henrik Theiling and Christian Ferdinand. Combining Abstract Interpretation and ILP for Microarchitecture Modelling and Program Path Analysis. In Proceedings of the 19th IEEE Real-Time Systems Symposium (RTSS), Madrid, Spain, 1998.
V. Zivojnovic, S. Pees, Ch. Schläger, Markus Willems, Rainer Schoenen, and H. Meyr. LISA-Machine Description Language and Generic Machine Model. In Proceedings of the International Conference on Signal Processing Applications and Technology, October 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Langenbach, M., Thesing, S., Heckmann, R. (2002). Pipeline Modeling for Timing Analysis. In: Hermenegildo, M.V., Puebla, G. (eds) Static Analysis. SAS 2002. Lecture Notes in Computer Science, vol 2477. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45789-5_22
Download citation
DOI: https://doi.org/10.1007/3-540-45789-5_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44235-6
Online ISBN: 978-3-540-45789-3
eBook Packages: Springer Book Archive