Efficient detection and exploitation of infeasible paths for software timing analysis

ABSTRACT

Accurate estimation of the worst-case execution time (WCET) of a program is important for real-time embedded software. Static WCET estimation involves program path analysis and architectural modeling. Path analysis is complex due to the inherent difficulty in detecting and exploiting infeasible paths in a program's control flow graph. In this paper, we propose an efficient method to exploit infeasible path information for WCET estimation without resorting to exhaustive path enumeration. We demonstrate the efficiency of our approach for some real-life control-intensive applications.

REFERENCES

• 1: AbsInt. aiT: Worst case execution time analyzer, 2004. http://www.absint.com/ait/.
• 2: P. Altenbernd. On the false path problem in hard real-time programs. In ECRTS, 1996.
• 3: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 4: A. Ermedahl and J. Engblom. Modeling complex flows for worst-case execution time analysis. In RTSS, 2000.
• 5: Andreas Ermedahl , Jan Gustafsson, Deriving Annotations for Tight Calculation of Execution Time, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.1298-1307, August 26-29, 1997
• 6: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 7: Christopher A. Healy , David B. Whalley, Automatic detection and exploitation of branch constraints for timing analysis, IEEE Transactions on Software Engineering, v.28 n.8, p.763-781, August 2002 [doi>10.1109/TSE.2002.1027799]
• 8: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar , Grégoire Sutre, Lazy abstraction, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.58-70, January 16-18, 2002, Portland, Oregon
• 9: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, p.88-98, November 1995, La Jolla, California, United States
• 11: Thomas Lundqvist , Per Stenström, Integrating Path and Timing Analysis Using Instruction-Level Simulation Techniques, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.1-15, June 01, 1998
• 12: Chang Yun Park, Predicting program execution times by analyzing static and dynamic program paths, Real-Time Systems, v.5 n.1, p.31-62, March 1993 [doi>10.1007/BF01088696]
• 13: Peter P. Puschner , Anton V. Schedl, Computing Maximum Task Execution Times — A Graph-BasedApproach, Real-Time Systems, v.13 n.1, p.67-91, July 1997 [doi>10.1023/A:1007905003094]
• 14: 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]
• 15: Friedhelm Stappert , Andreas Ermedahl , Jakob Engblom, Efficient longest executable path search for programs with complex flows and pipeline effects, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502240]
• 16: Vivy Suhendra , Tulika Mitra , Abhik Roychoudhury , Ting Chen, WCET Centric Data Allocation to Scratchpad Memory, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.223-232, December 05-08, 2005 [doi>10.1109/RTSS.2005.45]
• 17: WCET benchmarks, 2004. http://www.c-lab.de/home/en/download.html.
• 18: Wankang Zhao , David Whalley , Christopher Healy , Frank Mueller, WCET Code Positioning, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.81-91, December 05-08, 2004 [doi>10.1109/REAL.2004.55]

INDEX TERMS

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

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

General Terms:
Measurement, Performance

Keywords:
WCET analysis, infeasible path detection