Search

The requirements for today's embedded hard real-time systems are high: They should deliver high performance, be energy-efficient and always react in time. This leads to the use of processors with several cores. However, when the cores are connected via a shared memory, static timing analysis suffers from high pessimism. We see distributed memory many-core processors as a solution where cores communicate via messages. One of them is the Reduced Complexity Many-Core (RC/MC) architecture. It was developed with the goal of high timing predictability. In our thesis, we present an approach to estimate the Worst-Case Execution Time (WCET) of programs running on this platform. Furthermore, we extend the RC/MC to improve its timing predictability and its worst-case performance. Our first step is the introduction of ready synchronization, which avoids buffer overflows. Second, we design hardware support for broadcasts and multicasts. Third, the RC/MC is extended with hardware supported barriers. Each of these techniques is evaluated for its impact. We carry out timing analyses of the hardware operations for broadcasts/multicasts and barriers and compare them with their variants without hardware support. Finally, we present three case studies, where we analyze benchmarks taken from the NAS parallel benchmark suite to evaluate the worst-case performance of our extensions in the context of real use cases.

International audience; Applications in industry often have grown and improved over many years. Since their performance demands increase, they also need to benefit from the availability of multi-core processors. However, a reimplementation from scratch and even a restructuring of these industrial applications is very expensive, often due to high certification efforts. Therefore, a strategy for a systematic parallelization of legacy code is needed. We present a parallelization approach for hard real-time systems, which ensures a high reusage of legacy code and preserves timing analysability. To show its applicability, we apply it on the core algorithm of an avionics application as well as on the control program of a large construction machine. We create models of the legacy programs showing the potential of parallelism, optimize them and change the source codes accordingly. The parallelized applications are placed on a predictable multi-core processor with up to 18 cores. For evaluation, we compare the worst case execution times and their speedups. Furthermore, we analyse limitations coming up at the parallelization process.

Static WCET analysis of parallel programs running on shared-memory multicores suffers from high pessimism. Instead, distributed memory platforms which communicate via messages may be one solution for manycore systems. Message Passing Interface (MPI) is a standard for communication on these platforms. We show how its concept of collective operations can be employed for timing analysis. The idea is that the worst-case execution time (WCET) of a parallel program may be estimated by adding the WCET estimates of sequential program parts to the WCET estimates of communication parts. Therefore, we first analyse the two MPI operations MPI_Allreduce and MPI_Sendrecv. Employing these results, we make a timing analysis of the conjugate gradient (CG) benchmark from the NAS parallel benchmark suite.

International audience; The EC FP-7 project parMERASA (Multi-Core Execution of Parallelised Hard Real-Time Applications Supporting Analysability, Oct. 1, 2011 until Sept. 30, 2014) provides a timing analysable system of parallel hard real-time applications running on a scalable multi-core processor. parMERASA goes one step beyond mixed criticality demands: It targets future complex control algorithms by parallelising hard real-time programs to run on predictable multi-/many-core processors. A software engineering approach was developed to ease sequential to parallel program transformation by developing and supporting suitable parallel design patterns that are analysable. The following sequential hard real-time programs were parallelised by applying the pattern-oriented parallelisation approach: 3D path planning and stereo navigation algorithms (Honeywell International s.r.o.), diesel engine management system (DENSO AUTOMOTIVE Deutschland GmbH), and the control algorithm for a dynamic compaction machine (BAUER Maschinen GmbH). The paper reports on parallelisation approach, experiences made during parallelisation with applications, tools and multi-core architecture, scalability of applications and quantitative results reached.

We recently presented a parallelization approach based on parallel design patterns and leading to structured parallelism. The approach is applicable for the parallelization of sequential code parts of embedded hard real-time software. To reduce work effort it is necessary to rely on tool support. In this context, we here present software for the model-based and multi-objective optimization of a software model with a high degree of parallelism. In addition, we introduce the timing analyzable algorithmic skeletons (TAS) for the fast implementation of the optimized software model. To support the static WCET analysis with the OTAWA toolset, we developed a compact XML format to describe software with TAS instances. Such a model can then easily be translated into the OTAWA XML format representing parallel flow-facts. All software described in this technical report is available under an open source license.