Influence of procedure cloning on WCET prediction

ABSTRACT

For the worst-case execution time (WCET) analysis, especially loops are an inherent source of unpredictability and loss of precision. This is caused by the difficulty to obtain safe and tight information on the number of iterations executed by a loop in the worst case. In particular, data-dependent loops whose iteration counts depend on function parameters are extremely difficult to analyze precisely. Procedure cloning helps by making such data-dependent loops explicit within the source code, thus making them accessible for high-precision WCET analyses.

This paper presents the effect of procedure cloning applied at the source-code level on worst-case execution time. Theoptimization generates specialized versions of functionsbeing called with constant values as arguments. In standardliterature, it is used to enable further optimizations like constant propagation within functions and to reduce calling overhead.

We show that procedure cloning for WCET minimization leads to significant improvements. Reductions of the WCET from 12% up to 95% were measured for real-life benchmarks. These results demonstrate that procedure cloning improves analyzability and predictability of real-time applications dramatically. In contrast, average-case performance as the criterion procedure cloning was developed for is reduced by only 3% at most. Our results also show that these WCET reductions only implied small overhead during WCET analysis.

REFERENCES

• 1: AbsInt Angewandte Informatik GmbH. Worst-Case Execution Time Analyzer aiT for TriCore. 2007.
• 2: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 3: K. D. Cooper, M. W. Hall, and K. Kennedy. A Methodology for Procedure Cloning. Computer Languages, 19(2):105--117, 1993.
• 4: H. Falk , P. Lokuciejewski , H. Theiling, Design of a WCET-Aware C Compiler, Proceedings of the 2006 IEEE/ACM/IFIP Workshop on Embedded Systems for Real Time Multimedia, p.121-126, October 26-27, 2006 [doi>10.1109/ESTMED.2006.321284]
• 5: Heiko Falk , Peter Marwedel, Control Flow Driven Splitting of Loop Nests at the Source Code Level, Proceedings of the conference on Design, Automation and Test in Europe, p.10410, March 03-07, 2003
• 6: H. Falk , M. Schwarzer, Loop Nest Splitting for WCET-Optimization and Predictability Improvement, Proceedings of the 2006 IEEE/ACM/IFIP Workshop on Embedded Systems for Real Time Multimedia, p.115-120, October 26-27, 2006 [doi>10.1109/ESTMED.2006.321283]
• 7: 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, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 8: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 9: S. Thesing. Safe and Precise WCET Determinations by Abstract Interpretation of Pipeline Models. PhD thesis, Saarland University, 2004.
• 10: Wankang Zhao , David Whalley , Christopher Healy , Frank Mueller, Improving WCET by applying a WC code-positioning optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.4, p.335-365, December 2005 [doi>10.1145/1113841.1113842]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Performance

Keywords:
WCET minimization, compiler optimizations, context-sensitive WCET-analysis