Sprungmarken

Servicenavigation

Hauptnavigation


You are here:

Home Research WCET-aware Compilation Tutorial

Bereichsnavigation

Hauptinhalt

Reconciling Compilers and Timing Analysis for Safety-Critical Real-Time Systems - the WCET-aware C Compiler WCC

Tutorial at the International Symposium on Code Generation and Optimization (CGO 2012)

Heiko Falk, Jan C. Kleinsorge


Summary

Timing constraints must be respected for safety-critical real-time applications. Traditionally, compilers are unable to use precise estimates of execution times for optimization, and timing properties of code are derived after compilation. A number of design iterations are required if timing constraints are not met. We propose to reconcile compilers and timing analysis and to create a worst-case execution time (WCET) aware compiler in this way. Such WCET-aware compilers can exploit precise WCET information during compilation. This way, they are able to improve the code quality. Also, they may help to avoid some of the design iterations and thereby save development time.

In this tutorial, we present the integration of a compiler and a WCET analyzer, yielding our WCET-aware compiler WCC. We are then considering compiler optimizations for their potential to reduce the WCET, assuming that the WCET is now used as the cost function. Considered optimizations include register allocation, scratchpad memory allocation, memory content selection and cache partitioning for multi-task systems. For large benchmark sets, average WCET reductions of up to 40% were achieved. Thus, this new area of research has the potential of achieving worthwhile execution time reductions for safety-critical real-time code.


Agenda

Location: Hilton San Jose, Room "San Carlos 1"

Schedule: Saturday March 31, 2012

  • 08.30 - 09.50 AM
    Session 1: Welcome and Introduction, WCC Compiler Infrastructure
    (Download Presentation Slides of Session 1)
  • 09.50 - 10.00 AM
    Discussion
  • 10.00 - 10.30 AM
    Coffee break
  • 10.30 - 11.50 AM
    Session 2: WCET-aware Optimizations, Conclusions and Outlook
    (Download Presentation Slides of Session 2)
  • 11.50 - 12.00 AM
    Discussion
  • 12.00 - 13.00 PM
    Lunch break


Target audience

  • Engineers and researchers interested in code generation for hard real-time systems.
  • Practitioners and researchers interested in compilation and optimization using formal timing models within compilers.


Outline

  • Introduction and motivation
    • Safety-critical real-time systems and worst-case execution times
    • Current state of the art in the industrial design of safety-critical real-time systems
    • Current state of the art in compiler construction
    • Static WCET analysis
  • Structure of the WCET-aware C Compiler WCC (incl. live demos of WCC's key features)
    • Integration of a WCET timing model into the compiler
    • Specification of memory hierarchies
    • Annotation and transformation of Flow Facts for WCET analysis
    • Automatic polyhedral loop bound analysis
  • Systematic WCET minimization by compiler optimizations
    • The Worst-Case Execution Path (WCEP)
    • Challenges imposed to WCET-aware compilers due to the WCEP
  • WCET-aware optimizations included in WCC (incl. few live demos of some optimizations)
    • Graph coloring register allocation
    • Scratchpad memory allocation
    • Cache-aware memory content selection
    • Cache partitioning for multi-task real-time systems
    • Combination of scratchpad allocation, memory content selection and cache partitioning
    • Optimization on an industrial code base
  • Conclusions and outlook on future work


Special requirements

None. Attendees do not need to bring own laptops etc. in order to follow this tutorial.


Presenters

  • Heiko Falk

    Heiko Falk is full professor at the Institute of Embedded Systems/Real-Time Systems at Ulm University (Germany) since 2011. He received his Ph.D. in Computer Science from the University of Dortmund (Germany) in 2004. From 2004 on until 2011, he worked as assistant professor in the embedded systems group at Dortmund. During his Ph.D., he concentrated on high-level source code optimizations. In the last years, the focus of his work is on code generation and optimization for performance and predictability, which is also the subject of the EC FP7 project PREDATOR. The WCC compiler developed by the research team lead by Heiko is the currently only known compiler which is able to minimize the WCET of programs by tightly integrating static timing analyses into the code generation and optimization stage.

  • Jan C. Kleinsorge

    Jan C. Kleinsorge received his diploma degree in Computer Science from the University of Dortmund (Germany) in 2008. Since 2009, he is Ph.D. student in the Design Automation for Embedded Systems Group (DAES) of Prof. Marwedel at Dortmund. In his diploma thesis, he investigated WCET-aware allocation techniques in memory hierarchies. He is now actively concerned with the investigation of multitask models and applications thereof for WCET-aware code optimizations. As part of the WCC compiler development team, his work contributes to the substantial pool of WCC's WCET-directed optimizations.


Acknowledgments

The work on the WCC compiler and on this tutorial received funding by the European IST FP7 NoE ArtistDesign, by the European IST FP7 NoE HiPEAC under contract no. 217068, by the European FP7 Framework Programme under grant agreement no. 216008 (PREDATOR), and by Deutsche Forschungsgemeinschaft (DFG) under grant FA 1017/1-1.


Links and Further Reading