Search

Worst-case execution time (WCET) analysis is crucial for designing real-time systems. While the WCET of tasks in a single core system can be upper bounded in isolation, the tasks in a manycore system are subject to shared memory interferences which impose high overestimation of the WCET bounds. However, manycore-based massively parallel applications will enter the area of real-time systems in the years ahead. Explicit message-passing and a clear separation of computation and communication facilitates WCET analysis for those programs. Thereby, the separation is especially ensured if applying collective communication.We propose a process of analysing state-of-the-art communication patterns with respect to worst case timing. As MPI is the standard for performing collective communication, we use it to show how to evaluate the timing behaviour in detail. We compare different communication patterns and show the tremendous impact of choosing an appropriate one.

Parallelization of AUTOSAR legacy software is a fundamental step to exploit the performance of multi-core electronic control units (ECUs). However, communication between runnables causes serialization and intra-task parallelization can therefore introduce large idle intervals, if a task contains a long critical path. Distributing the instructions of a runnable over cores (fine-grained parallelism) can reduce the serialization to a shorter time, but this requires an efficient and timing analyzable implementation. This paper investigates the efficiency of fine-grained parallelism for reducing the worst-case execution time in automotive applications. A pattern-supported parallelization approach is applied to extract parallelism of runnables in a structured way. Algorithmic skeletons are used to implement fine-grained parallelism in a dynamic (assignment at runtime) and in a static (a priori assignment) way. The performance evaluation showed that the static assignment is as efficient as a state-of-the-art barrier. Thereby, parallelism is explicitly expressed in a model and implemented in a timing analyzable way.

Bufferless deflection routing is a serious alternative to wormhole flow control and packet switching. It is based on the principle of deflecting a flit to a non-optimal route instead of buffering it, when two flits compete for the same link. The major weakness of deflection is the exploding number of misrouted flits at high network load, which increases the duration of flits within the network and requires to reassemble the flits at the receiver. These deflections can be reduced significantly by adding a small side buffer instead of always deflecting flits. In the presented approach, the side buffer is complemented by a restricted deflection policy that preserves the flit order: x-y-routing in an unidirectional 2D-torus ensures that collisions are impossible, as long as a flit is transported in the same direction. Only at the transition from x- to y-direction, collisions may happen and are avoided by controlled in-order deflection in x-direction. In-order delivery not only simplifies the arbitration logic, but avoids costly mechanisms for livelock-prevention and reassembly of flits at the receiver.

International audience; The EC project parMERASA (Multicore Execution of Parallelized Hard Real-Time Applications Supporting Analyzability) investigated timing-analyzable parallel hard real-time applications running on a predictable multicore processor. A pattern-supported parallelization approach was developed to ease sequential to parallel program transformation based on parallel design patterns that are timing analyzable. The parallelization approach was applied to parallelize the following industrial hard real-time programs: 3D path planning and stereo navigation algorithms (Honeywell International s.r.o.), control algorithm for a dynamic compaction machine (BAUER Maschinen GmbH), and a diesel engine management system (DENSO AUTOMOTIVE Deutschland GmbH). This article focuses on the parallelization approach, experiences during parallelization with the applications, and quantitative results reached by simulation, by static WCET analysis with the OTAWA tool, and by measurement-based WCET analysis with the RapiTime tool.