Static timing analysis of embedded software

ABSTRACT

This paper examines the problem of statically analyzing the performance of embedded software. This problem is motivated by the increasing growth of embedded systems and a lack of appropriate analysis tools.We study different performance metrics that need tobe considered in this context and examine a range oftechniques that have been proposed for analysis. Verybroadly these can be classified into path analysis andsystem utilization analysis techniques. It is observedthat these are interdependent, and thus need to beconsidered together in any analysis framework.

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: Shaun Bharrat , Kevin Jeffay, Predicting Worst Case Execution Times on a Pipelined RISC Processor, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1995
• 3: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: an analytical representation of cache misses, Proceedings of the 11th international conference on Supercomputing, p.317-324, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263657]
• 4: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 5: Marion Goode Harmon, Predicting execution time on contemporary computer architectures, Florida State University, Tallahassee, FL, 1991
• 6: C. A. Healy , D. B. Whalley , M. G. Harmon, Integrating the timing analysis of pipelining and instruction caching, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.288, December 05-07, 1995
• 7: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 8: Yerang Hur , Young Hyun Bae , Sung-Soo Lim , Sung-Kwan Kim , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Minsuk Lee , Heonshik Shin , Chong Sang Kim, Worst case timing analysis of RISC processors: R3000/R3010 case study, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.308, December 05-07, 1995
• 9: Alvin R. Lebeck , David A. Wood, Cache Profiling and the SPEC Benchmarks: A Case Study, Computer, v.27 n.10, p.15-26, October 1994 [doi>10.1109/2.318580]
• 10: Chang-Gun Lee , J. Hahn , Sang Lyul Min , R. Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Analysis of cache-related preemption delay in fixed-priority preemptive scheduling, Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96), p.264, December 04-06, 1996
• 11: Y.-T. S. Li. P~fo~,~~ A~O,~, of E,~b~dd~d Software. PhD thesis, Princeton University, 1997. In preparation.
• 12: Y.-T. S. Li , S. Malik , A. Wolfe, Efficient microarchitecture modeling and path analysis for real-time software, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.298, December 05-07, 1995
• 13: 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
• 14: Margaret Martonosi , Anoop Gupta , Thomas E. Anderson, Tuning Memory Performance of Sequential and Parallel Programs, Computer, v.28 n.4, p.32-40, April 1995 [doi>10.1109/2.375175]
• 15: A. K. Mok, P. Amerasinghe, M. Chen, and K. Tantisirivat. Evaluating tight execution time bounds of programs by annotations. In Proceedings of the 6th IEEE Workshop on Real-Time Operating Systems and Software, pages 74-80, May 1989.
• 16: Todd C. Mowry , Monica S. Lam , Anoop Gupta, Design and evaluation of a compiler algorithm for prefetching, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.62-73, October 12-15, 1992, Boston, Massachusetts, United States
• 17: K. Narasimhan and K. Nilsen. Portable execution time analysis for RISC processors. In Proceedings of ACM PLDI Workshop on Language, Compiler, and Tool Support for Real-Time Systems, pages L1-L10, June 1994.
• 18: Chang Yun Park, Predicting deterministic execution times of real-time programs, University of Washington, Seattle, WA, 1992
• 19: 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]
• 20: K. Ramamritham , J. A. Stankovic , P. F. Shiah, Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.184-194, April 1990 [doi>10.1109/71.80146]
• 21: V. Rustagi and D. B. Whalley. Calculating minimum and maximum loop iterations. Technical report, Computer Science Department, Florida State University, May 1994.
• 22: L. Sha, R. Rajkumar, and S. S. Sathaye. Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. In Proceedings of the IEEE, pages 68-82, January 1994.
• 23: 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]
• 24: K. G. Shin and P. Ramanathan. Real-time computing: A new discipline of computer science and engineering. In Proceedings of the IEEE, pages 6-24, January 1994.
• 25: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 26: David A. Wood , Mark D. Hill , R. E. Kessler, A model for estimating trace-sample miss ratios, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.79-89, May 21-24, 1991, San Diego, California, United States
• 27: N. Zhang , A. Burns , M. Nicholson, Pipelined processors and worst case execution times, Real-Time Systems, v.5 n.4, p.319-343, Oct. 1993 [doi>10.1007/BF01088834]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

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

General Terms:
Design, Measurement, Performance, Theory