Work package 3: coordination between tasks

In this work package, we will investigate how concurrency control mechanisms may affect the variability of task execution times and response times, and propose algorithms to make them more stable and predictable. Both offline and online methods will be considered.

Offline optimisation can be seen as a means for decreasing the cost of predictability by finding predictable and minimum-cost (e.g., power) solutions that meet timing constraints. Very often in the system design community, optimisation problem instances that could be solved through exact techniques are instead solved through hybrid incomplete approaches that on one hand need a tedious parameter setting and tuning and on the other do not guarantee optimality. Exact ways to tackle the mapping and configuration problem either incur overly large computation times already for medium-size task sets, or are inaccurate (e.g., use of heuristics and problem modelling with highly simplifying assumptions on system operation). Therefore, design technology for MPSoCs strongly needs accurate, scalable and composable modelling and solving frameworks. When fed with accurate task graph characterisations (e.g., accurate worst-case execution times) exact techniques result in highly predictable task executions. However, when task characteristics are not precisely known or subject to dynamic changes, offline methods can lead to resource waste or overload conditions.

Online algorithms for task scheduling and resource management are necessary to cope with activities having a highly variable (and unpredictable) execution behaviour. Among the online approaches, preemptive scheduling significantly affects the execution time predictability, because it reduces program locality, increasing the number of cache misses and hence increasing the variability of worst-case computation times. On the other hand, however, pure non-preemptive scheduling introduces additional synchronisation delays in task executions, and thus decreases schedulability with respect to preemptive scheduling. As a consequence, the benefits of applying non-preemptive scheduling algorithms in real-time systems must be carefully evaluated under several aspects. A detailed comparison between preemptive and non-preemptive scheduling is missing in the real-time literature, hence it will be considered as a key research objective in this work package.

Main tasks

Key players