Things that make real-time hard - parallelization

Previous posts have considered hardware acceleration features that improve the overall performance of a system but also make analysis of that system from a real-time perspective more difficult. Last time, we examined some of the difficulties encountered in determining the WCET when multicore processors are used. To fully benefit from the capabilities of a multicore architecture requires software that is able to execute on more than one core simultaneously, i.e. that software must be parallelised. This blog post explores some of the issues that arise when attempting to determine WCET of parallelised code.

The background to parallelization

As the number of cores contained in multicore devices increases, the need to exploit parallelism to improve performance becomes more significant. For existing systems, it may be necessary to modify already developed software to exploit parallelism present in the underlying task. In new systems, software can be designed to permit the exploitation of parallelism.

This is a subject that is actively being researched: at Rapita we are involved with parMERASA, an EU FP7 project to explore the parallelization of real-time software in avionics, automotive and industrial control applications.

How parallelism can be exploited

Depending on the desired application, the way in which parallelism is exploited may vary. For example, some software repeatedly performs the same sequence of operations across a number of items of data. The overall operation can be parallelised by splitting it into a number of smaller processes each of which can be performed on a separate processor core. This creates a pipeline where each stage of the execution occurs in parallel.

In some cases, the input data itself can be split up into a number of smaller units, each of which can be processed on a separate processor core and the output recombined to produce the final result. Such a technique is often used for image processing applications. Often, the most effective parallelization strategy for an application will use a mixture of different parallelization techniques.

Parallelization and WCET

The parallelization of software poses a number of difficulties, particularly when considering how to establish the WCET for a piece of software. A fundamental difference when software is executed in parallel is the need for the communication between different processing units, either to exchange data to be processed, perform synchronisation to ensure that the final results are consistent, or to control access to external resources when they must be accessed from multiple cores simultaneously.

Even an operation as straightforward as writing a value into a shared variable then reading it back introduces communication if the components reading and writing are executed on different cores. In future articles, we will consider in more detail the types of communication that can occur in a parallelised system, and consider how they can impact the determination of WCET for the system. We will also consider how the system designer can organize their system to reduce the need for communications.