Skip to main content
main-content

Über dieses Buch

For real-time systems, the worst-case execution time (WCET) is the key objective to be considered. Traditionally, code for real-time systems is generated without taking this objective into account and the WCET is computed only after code generation. Worst-Case Execution Time Aware Compilation Techniques for Real-Time Systems presents the first comprehensive approach integrating WCET considerations into the code generation process. Based on the proposed reconciliation between a compiler and a timing analyzer, a wide range of novel optimization techniques is provided. Among others, the techniques cover source code and assembly level optimizations, exploit machine learning techniques and address the design of modern systems that have to meet multiple objectives.

Using these optimizations, the WCET of real-time applications can be reduced by about 30% to 45% on the average. This opens opportunities for decreasing clock speeds, costs and energy consumption of embedded processors. The proposed techniques can be used for all types real-time systems, including automotive and avionics IT systems.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

The first chapter introduces the topics discussed in this book. Due to the vital importance of embedded real-time systems in today’s industrial applications, the need for their effective optimization is becoming more and more important. The common practice is typically based on a trial-and-error procedure including several time-consuming software generation attempts. In this book, it is demonstrated how the integration of timing analysis into a compiler framework for an automotive processor can provide a systematic path toward optimized worst-case execution times (WCET), enabling to cut down costs. Following the motivation, the contributions of this work and the outline of the book is provided.
Paul Lokuciejewski, Peter Marwedel

Chapter 2. WCET Analysis Techniques

Besides functional correctness, hard real-time systems have to satisfy timing constraints. The key parameter for timing constraints is the worst-case execution time. In this chapter, common timing analysis techniques found in academia and industry are discussed and the three main classes of approaches for a WCET analysis are presented. The static timing analysis is the only method that guarantees safe WCET estimates. It does not rely on the execution of the code under analysis but derives its timing information from the program code combined with abstract models of the hardware architecture. Next, basic terms involved in the static analysis are discussed. The chapter is concluded with a description of the workflow of the leading static WCET analyzer aiT which is also exploited in this work.
Paul Lokuciejewski, Peter Marwedel

Chapter 3. WCC—WCET-Aware C Compiler

In this chapter, the utilized compiler framework is discussed. The chapter begins with an overview of work to existing frameworks that integrate WCET analyses into the compilation process. The basic workflow of the utilized WCET-aware C compiler WCC, which is similar to standard optimizing compilers, is presented to provide the reader with an overall overview of the WCET-aware compilation flow. Moreover, the integration of a static WCET analyzer into the compiler framework is discussed. In addition, a static loop analysis, which was developed in this work to enable an automatic WCET analysis, is presented. To exploit optimization potential for WCET minimization at source code level, WCET timing data has to be translated from the compiler’s backend into its frontend. This technique, which was developed in this work, is called back-annotation and will be introduced in this chapter. Finally, an overview of WCC’s target architecture, the Infineon TriCore processor, concludes this chapter.
Paul Lokuciejewski, Peter Marwedel

Chapter 4. WCET-Aware Source Code Level Optimizations

High-performance embedded systems can only be developed when efficiency requirements are pursued at different levels of the system design. A predominant role is associated with compilers which are responsible for the generation of efficient machine code. To accomplish this goal, compilers have to feature advanced optimizations. The class of source code optimizations provides a number of benefits compared to optimizations applied at lower abstraction levels of the code. The most important issues are portability, early application in the optimization sequence to enable subsequent optimizations, and availability of more details about the program structure due to the high level of abstraction. In this chapter, novel WCET-aware source code level optimizations are presented, including procedure cloning, superblock optimizations, loop unrolling, and loop unswitching. Moreover, a technique called invariant path is presented to accelerate WCET-aware optimizations.
Paul Lokuciejewski, Peter Marwedel

Chapter 5. WCET-Aware Assembly Level Optimizations

The major shortcoming of source code optimizations is their lack of intrinsic knowledge about the underlying architecture. Hence, the development of transformations that exploit processor-specific features is limited or even infeasible at all. As a result, a maximal optimization potential can not be explored. In contrast, assembly level optimizations operate on a code representation that reflects the finally executed code. Thus, the compiler is fully aware of numerous critical details about the utilized resources during execution. In this chapter, novel WCET-aware assembly level optimizations are discussed. In detail, the optimizations WCET-aware procedure positioning and WCET-aware trace scheduling are presented.
Paul Lokuciejewski, Peter Marwedel

Chapter 6. Machine Learning Techniques in Compiler Design

The manual generation of heuristics for compiler optimizations is a tedious task which requires both a high amount of expertise and an extensive trial-and-error tuning. The consequence is that many optimizations operate inefficiently. In this chapter, an automatic generation of machine learning based (MLB) heuristics for WCET-aware compiler optimizations is presented. A feasibility study for the generation of WCET-aware heuristics for the source code optimization function inlining is presented. Moreover, this chapter shows that on the one hand MLB WCET-aware heuristics can also be easily constructed at other abstraction levels of the code, namely at assembly level as demonstrated for the optimization loop-invariant code motion. On the other hand, this chapter indicates that an automatic selection of appropriate machine learning algorithms and their parameters can significantly improve the performance of the generated heuristics. To demonstrate the effectiveness of the MLB heuristics, evaluations on real-life benchmarks were performed, showing that the novel heuristics outperform traditional, hand-crafted heuristics.
Paul Lokuciejewski, Peter Marwedel

Chapter 7. Multi-objective Optimizations

The development of high-performance optimizing compilers is an inherently hard problem for many reasons. Besides the complex task of generating efficient compiler heuristics, optimizations that are performed in a sequence may exhibit non-trivial interactions with other optimizations as well as with the underlying hardware. For modern systems, the situation becomes even worse. In addition to the challenges of finding promising optimization sequences, modern systems have to meet different requirements. In case of embedded real-time systems, not only the WCET but also the average-case execution time or the code size are critical. This chapter provides a complementary solution for the construction of high-performance compilers. It begins with a discussion of the general structure of an adaptive compiler and shows how the WCC is accordingly extended. To cope with the huge search space of compiler optimizations, an automatic approach for compiler optimization sequence exploration based on evolutionary multi-objective search algorithms is presented. The effectiveness of this approach is demonstrated on real-life benchmarks.
Paul Lokuciejewski, Peter Marwedel

Chapter 8. Summary and Future Work

This chapter summarizes the contributions of the techniques proposed in this book. To demonstrate the high performance of the WCC framework for an automatic WCET reduction, an overall evaluation of the developed optimization techniques is presented by applying these optimizations in sequence for a representative real-life benchmark. Finally, a discussion on directions for future work is provided.
Paul Lokuciejewski, Peter Marwedel

Backmatter

Weitere Informationen

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Globales Erdungssystem in urbanen Kabelnetzen

Bedingt durch die Altersstruktur vieler Kabelverteilnetze mit der damit verbundenen verminderten Isolationsfestigkeit oder durch fortschreitenden Kabelausbau ist es immer häufiger erforderlich, anstelle der Resonanz-Sternpunktserdung alternative Konzepte für die Sternpunktsbehandlung umzusetzen. Die damit verbundenen Fehlerortungskonzepte bzw. die Erhöhung der Restströme im Erdschlussfall führen jedoch aufgrund der hohen Fehlerströme zu neuen Anforderungen an die Erdungs- und Fehlerstromrückleitungs-Systeme. Lesen Sie hier über die Auswirkung von leitfähigen Strukturen auf die Stromaufteilung sowie die Potentialverhältnisse in urbanen Kabelnetzen bei stromstarken Erdschlüssen. Jetzt gratis downloaden!

Bildnachweise