Performance estimation of embedded software with instruction cache modeling

ABSTRACT

Embedded systems generally interact in some way with the outside world. This may involve measuring sensors and controlling actuators, communicating with other systems, or interacting with users. These functions impose real-time constraints on system design. Verification of these specifications requires computing an upper bound on the worst-case execution time (WCET) of a hardware/software system. Furthermore, it is critical to derive a tight upper bound on WCET in order to make efficient use of system resources. The problem of bounding WCET is particularly difficult on modern processors. These processors use cache-based memory systems that vary memory access time based on the dynamic memory access pattern of the program. This must be accurately modeled in order to tightly bound WCET. Several analysis methods have been proposed to bound WCET on processors with instruction caches. Existing approaches either search all possible program paths, an intractable problem, or they use highly pessimistic assumptions to limit the search space. In this paper we present a more effective method for modeling instruction cache activity and computing a tight bound on WCET. The method uses an integer linear programming formulation and does not require explicit enumeration of program paths. The method is implemented in the program cinderella and we present some experimental results of this implementation.

REFERENCES

• 1: ARNOLD, R., MUELLER, F., WHALLEY, D., AND HARMON, M. 1994. Bounding worst-case instruction cache performance. In Proceedings of the 15th IEEE Symposium on Real-Time Systems (Dec.). IEEE Computer Society Press, Los Alamitos, CA, 172-181.
• 2: George S. Avrunin , James C. Corbett , Laura K. Dillon , Jack C. Wileden, Automated Derivation of Time Bounds in Uniprocessor Concurrent Systems, IEEE Transactions on Software Engineering, v.20 n.9, p.708-719, September 1994 [doi>10.1109/32.317429]
• 3: Rajesh Kumar Gupta, Co-synthesis of hardware and software for digital embedded systems, Stanford University, Stanford, CA, 1994
• 4: INTEL CORPORATION, 1990. QT960 User Manual. Intel Corp., Santa Clara, CA.
• 5: Corporate Intel Corp., i860 microprocessor family programmer's reference manual, Intel Corporation, Santa Clara, CA, 1992
• 6: 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
• 7: 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]
• 8: LIM, S., BAE, Y. H., JANG, G. T., RHEE, B., MIN, S. L., PARK, C. Y., SHIN, H., PARK, K., AND KIM, C.S. 1994. An accurate worst case timing analysis technique for RISC processors. In Proceedings of the 15th IEEE Symposium on Real-Time Systems (Dec.). IEEE Computer Society Press, Los Alamitos, CA, 97-108.
• 9: LIU, J. AND LEE, H. 1994. Deterministic upperbounds of the worst-case execution times of cached programs. In Proceedings of the 15th IEEE Symposium on Real-Time Systems (Dec.). IEEE Computer Society Press, Los Alamitos, CA, 182-191.
• 10: MOK, A. K., AMERASINGHE, P., CHEN, M., AND TANTISIRIVAT, K. 1989. Evaluating tight execution time bounds of programs by annotations. In Proceedings of the Sixth IEEE Workshop on Real-Time Operating Systems and Software (May). IEEE Computer Society Press, Los Alamitos, CA, 74-80.
• 11: Glenford J. Myers , David L. Budde, The 80960 microprocessor architecture, John Wiley & Sons, Inc., New York, NY, 1988
• 12: Chang Yun Park, Predicting deterministic execution times of real-time programs, University of Washington, Seattle, WA, 1992
• 13: P. Puschner , Ch. Koza, Calculating the maximum, execution time of real-time programs, Real-Time Systems, v.1 n.2, p.159-176, Sep. 1989 [doi>10.1007/BF00571421]
• 14: RAWAT, J. 1993. Static analysis of cache performance for real-time programming. Master's Thesis. Iowa State Univ., Ames, IA.
• 15: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

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

General Terms:
Design, Experimentation, Performance, Theory