Retargetable static timing analysis for embedded software

ABSTRACT

This paper presents a novel approach for retargetable static software timing analysis. Specifically, we target the problem of determining bounds on the execution time of a program on modern processors, and solve this problem in a retargetable software development environment. Another contribution of this paper is the modeling of important features in contemporary architectures, such as branch prediction, predication, and instruction pre-fetching, which have great impact on system performance, and have been rarely handled thus far. These ideas allow to build a timing analysis tool that is efficient, accurate, modular and retargetable. We present preliminary results for sample embedded programs to demonstrate the applicability of the proposed approach.

REFERENCES

• 1: John A. StankovicThis work was done while the , Marco Spuri , Marco Di Natale , Giorgio C. Buttazzo, Implications of Classical Scheduling Results for Real-Time Systems, Computer, v.28 n.6, p.16-25, June 1995 [doi>10.1109/2.386982]
• 2: K. Keutzer, S. Malik, A. R. Newton, J. Rabaey and A. Sangiovanni- Vincentelli. "System Level Design: Orthogonolization of Concerns and Platform-Based Design". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(12), December 2000.
• 3: P. Gopinath and R. Gupta. "Applying compiler techniques to scheduling in Real-time systems". In Proceedings of 1990 IEEE Real-Time Systems Symposium, pages 247--256, 1990.
• 4: S. Lim, Y. H. Bae, G. Tae Jang, B. Rhee, S. Lyul Min, C. Y. Park, H. Shin, K. Park, S. Moon, C. S. Kim, "An Accurate Worst Case Timing Analysis Technique for RISC Processors," In Proceedings of the 15th Real-Time Systems Symposium, 1994.
• 5: Randall T. White , Christopher A. Healy , David B. Whalley , Frank Mueller , Marion G. Harmon, Timing Analysis for Data Caches and Set-Associative Caches, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.192, June 09-11, 1997
• 6: F. Mueller. "Timing predictions for multi-level caches". In ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, pages 29--36, 1997.
• 7: Thomas Lundqvist , Per Stenström, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999 [doi>10.1023/A:1008138407139]
• 8: Friedhelm Stappert , Peter Altenbernd, Complete worst-case execution time analysis of straight-line hard real-time programs, Journal of Systems Architecture: the EUROMICRO Journal, v.46 n.4, p.339-355, Feb. 2000 [doi>10.1016/S1383-7621(99)00010-7]
• 9: J. Engblom, A. Ermedahl, M. Sjodin, J. Gustafsson, and H. Hansson, "Worst-Case Execution-Time Analysis for Embedded Real-Time Systems". Unpublished technique report, Department of Computer Systems, Uppsala University, Sweden, 2000.
• 10: Y.-T. S. Li , S. Malik , A. Wolfe, Cache modeling for real-time software: beyond direct mapped instruction caches, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.254, December 04-06, 1996
• 11: Antoine Colin , Isabelle Puaut, Worst Case Execution Time Analysis for a Processor withBranch Prediction, Real-Time Systems, v.18 n.2-3, p.249-274, May 2000 [doi>10.1023/A:1008149332687]
• 12: "The IMPACT Research Group", http://www.crhc.uiuc.edu/IMPACT
• 13: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 14: Itanium TM Processor Microarchitecture Reference. Technical report, Intel Corp., August 2000. http://developer.intel.com/design/ia-64/
• 15: John W. Sias , Wen-Mei W. Hwu , David I. August, Accurate and efficient predicate analysis with binary decision diagrams, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.112-123, December 2000, Monterey, California, United States [doi>10.1145/360128.360141]
• 16: "The Liberty Computer Architecture Research Group", http://liberty.cs.princeton.edu
• 17: Chi-Keung Luk , Todd C. Mowry, Cooperative prefetching: compiler and hardware support for effective instruction prefetching in modern processors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.182-194, November 1998, Dallas, Texas, United States

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software development

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Design, Experimentation, Performance