Memory-based optimization techniques for real-time systems

Abstract

Embedded/Cyber-physical systems, have become popular in a wide range of application scenarios. Such systems are called real-time systems if they underlie strict timing constraints. To verify if such systems can meet their deadlines, the knowledge of an upper bound for a program's execution time is mandatory. This upper bound is also called worst-case execution time (WCET) and is estimated by static timing analyzers.

Established optimizing compilers are not aware of the WCET as objective since they focus on the minimization of the average-case execution time (ACET). To overcome this obstacle, this thesis presents memory-based optimization techniques which focus on the reduction of the WCET of programs. All presented optimizations are integrated into the WCET-aware C Compiler (WCC) framework.

Since the memory interface of a system often turns out to be a bottleneck which limits the performance of a system, the presented optimizations are applied to different levels of the memory hierarchy of a system. Starting within a CPU core, the instruction fetch buffer is the most tightly coupled memory which tries to provide the next few instructions to be executed. Optimization techniques are presented improving the efficiency of this buffer w.r.t. the WCET of a system. Instruction caches placed between the CPU core and the main memory try to speed up accesses to the main memory by storing local copies in fast small cache memories. In order to improve the efficiency of this part of the memory hierarchy, a memory content selection approach is introduced which improves the WCET of a program by improving the cache performance.

Due to the fact that multi-task systems are employed in almost all domains, this thesis presents elaborate extensions to a compiler supporting the compilation and WCET-aware optimization of multi-task systems. These extensions exploited to develop a number of novel optimizations for systems running multiple tasks. As first optimization, a WCET-driven software-based cache partitioning demonstrates the effectiveness of considering the WCET for the optimization of a set of tasks. Furthermore, many embedded systems integrate so-called scratchpad memories (SPM) as tightly coupled memories. An optimization approach for SPM allocation in a multi-task scenario is proposed. Besides, a holistic view of memory architecture compilation considers a number of memory-based WCET optimizations and presents approaches for a combined application.

Existing compiler frameworks which are able to consider the WCET during optimization are limited to a particular hardware platform. In order to support multiple platforms, this thesis presents techniques to extend an existing WCET-aware compiler framework. Based on these extensions, a novel static cache locking optimization selects memory blocks which are statically locked into the instruction cache driven by WCET reductions.

Applying these optimizations, the WCET of real-time applications can be reduced by about 35% to 48%. These results underline the need for specialized WCET-driven optimization techniques integrated into a sophisticated compiler framework. Otherwise, immense optimization potential would remain unused resulting in oversized and thus costly Embedded/Cyber-physical systems.