Performance estimation of embedded software with instruction cache modeling

ABSTRACT

Embedded systems generally interact with the outside world. Thus, some real-time constraints may be imposed on the system design. Verification of these constraints requires computing a tight upper bound on the worst case execution time (WCET) of a hardware/software system. The problem of bounding WCET is particularly difficult on modern processors, which use cache-based memory systems that vary memory access time significantly. This must be accurately modeled in order to tightly bound WCET. Existing approaches either search all possible program paths, an intractable problem, or they use pessimistic assumptions to limit the search space. In this paper we present a far more effective and accurate method for modeling instruction cache activity and computing a tight bound on WCET. It is implemented in the program \texttt{cinderella}. We present some preliminary results of using this tool on sample embedded programs.

REFERENCES

• 1: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.456-461, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217570]
• 2: E Kligerman , A D Stoyenko, Real-time Euclid: a language for reliable real-time systems, IEEE Transactions on Software Engineering, v.12 n.9, p.941-949, Sept. 1986
• 3: Jyh-Charn Liu and Hung-Ju Lee, "Deterministic upperbounds of the worst-case execution times of cached programs", in Proceedings of the 15th IEEE Real-Time Systems Symposium, December 1994, pp. 182-191.
• 4: Sung-Soo Lira, 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", in Proceedings of the 15th IEEE Real-Time Systems Symposium, December 1994, pp. 97-108.
• 5: A. C. Shaw, Reasoning About Time in Higher-Level Language Software, IEEE Transactions on Software Engineering, v.15 n.7, p.875-889, July 1989 [doi>10.1109/32.29487]
• 6: Robert Arnold, Frank Mueller, David Whalley, and Marion Harmon, "Bounding worst-case instruction cache performance", in Proceedings of the 15th IEEE Real-Time Systems Symposium, December 1994, pp. 172-181.
• 7: Jai Rawat, "Static analysis of cache performance for realtime programming", Master's thesis, Iowa State University of Science and Technology, November 1993, TR93-19.
• 8: Intel Corporation, QT960 User Manual, 1990, Order Number 270875-001.
• 9: Intel Corporation, i960KA/KB Miclvprocessor Programmers's Reference Manual, 1991, ISBN 1-55512-137-3.
• 10: Glenford J. Myers , David L. Budde, The 80960 microprocessor architecture, John Wiley & Sons, Inc., New York, NY, 1988
• 11: Chang Yun Park, Predicting Deterministic Execution Times of Real-Time Programs, PhD thesis, University of Washington, Seattle 98195, August 1992.
• 12: Rajesh Kumar Gupta, Co-Synthesis of Hardware and Software for Digital Embedded Systems, PhD thesis, Stanford University, December 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Measurement, Performance, Theory