Embedded program timing analysis based on path clustering and architecture classification

ABSTRACT

Formal Program running time verification is an important issue in system design required for performance optimization under "first-time-right" design constraints and for real-time system verification. Simulation based approaches or simple instruction counting are not appropriate and risky for more complex architectures in particular with data dependent execution paths. Formal analysis techniques have suffered from loose timing bounds leading to significant performance penalties when strictly adhered to. We present an approach which combines simulation and formal techniques in a safe way to improve analysis precision and tighten the timing bounds. Using a set of processor parameters, it is adaptable to arbitrary processor architectures. The results show an unprecedented analysis precision allowing to reduce performance overhead for provably correct system or interface timing.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Charles E. Gimarc , Thomas M. Conte, Fast Simulation of Computer Architectures, Kluwer Academic Publishers, Norwell, MA, 1995
• 3: M. Johnson, Superscalar Microprocessor Design, Prentice Hall, Englewood Cliffs, NJ, 1991.
• 4: Jie Gong , Daniel D. Gajski , Sanjiv Narayan, Software estimation from executable specifications, Journal of Computer and Software Engineering, v.2 n.3, p.239-258, 1994
• 5: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 6: David B. Kirk, Predictable cache design for real-time systems, Carnegie Mellon University, Pittsburgh, PA, 1991
• 7: S. Malik, W. Wolf, A. Wolfe, Y. S. Li, T. Yen, Performance Analysis of Embedded Systems, NATO ASI, Workshop on Hardware-Software Co-Design, Tremezzo, Italy, 1995.
• 8: F. Mueller, R. Arnold, D. Whalley, Bounding Worst-Case Instruction Cache Performance, in Real-Time Systems Symposium. 1994 . Krithi, A., Editor. Puerto-Rico: IEEE Press. p. 172-181.
• 9: A. Mok et al. Evaluating Tight Execution Time Bounds of Programs by Annotations, Proc. IEEE WS Real-Time Operating Systems and Software, May 89, pp. 74-80.
• 10: Chang Yun Park, Predicting deterministic execution times of real-time programs, University of Washington, Seattle, WA, 1992
• 11: C.Y. Park, A.C. Shaw, Experiments with a program timing tool based on source-level timing schema. Proc llth IEEE Real-Time system Symp., pp. 72-81,1990
• 12: 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]
• 13: W. Ye, R. Ernst, Th. Benner, J. Henkel, Fast Timing Analysis for Harware-Software Cosynthesis, Proc. of ICCD 1993. IEEE Society Press, pp. 452-457, 1993
• 14: W. Ye, R. Ernst, Worst Case Timing Estimation based on Symbolic Execution, COBRA report, Institute of Computer Engineering, Technical University Braunschweig, Oct. 1995.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Experimentation, Measurement, Performance, Theory, Verification