A5: Scheduling Invasive Multicore Programs Under Uncertainty

Principal Investigators:

Prof. N. Megow

Scientific Researchers:

Dr. B. Simon


Project A5 is a new project joining the CRC/Transregio for the third funding period. It complements the project area A, Fundamentals, Language and Algorithm Research, with methods for coping with uncertainty, a central theme in Phase 3. Project A5 explores algorithms and analytical techniques for scheduling and resource management with uncertain input.


Scheduling and resource management are central tasks in many parts of invasive computing. Such problems are particularly challenging when real-time constraints are present, in the form of hard or soft deadlines that have to be met. Respecting deadlines is, however, not enough. Typically, precedence constraints among specific subtasks must be obeyed. In addition, hardware and software requirements as well as performance considerations impose further constraints on the compatibility between tasks and processors. Scheduling algorithms must handle various resources such as energy, bandwidth, and other resources. On top of that, in typical applications parts of the input data are uncertain. This can be uncertain tasks sets, unknown arrival times, fluctuations in task execution times, work load or power consumption, or uncertainty about the processor state.

The goal of this project is to develop algorithms that can handle uncertain input data. We design and mathematically analyse algorithms for scheduling and resource management using the invasive computing paradigm. Our methods shall give performance guarantees concerning the predictability and also quantify how hardware and software requirements affect the performance and predictability. This may reveal also optimisation potential in the systems architecture or algorithms.


We consider complex multiprocessor scheduling tasks with real-time constraints, in the form of hard or soft deadlines, with precedence constraints among specific subtasks, and various kinds of resources such as energy, bandwidth, and other resources. We investigate primarily the following kinds of uncertainty that are typical in practical applications:

  • fluctuations in task execution times, modelled as random variables with distributional information or by uncertainty intervals
  • uncertain task sets and arrival times modelled as online information
  • uncertain arrival times that follow some periodic pattern (periodic real-time scheduling).

The proposed project is of foundational character and aims for theoretical guarantees by building on methods from combinatorial optimisation, mathematical programming, scheduling theory, approximation and online algorithms. Our main focus lies on provable worst-case guarantees. When predictability is crucial, e.g. in safety-critical applications, multicore systems still rely on single-core usage. The reason is that the current state-of-the-art approaches in real-time scheduling do not capture the difficulties in scheduling parallel workloads in a predictable way. However, to fully unfold the power of multicore technology, it must include safety-critical functionalities. For safety-critical functionalities it is indispensable to reliably predict whether a given task will be computed in time, that is, we ask for reliability even in a worst case.

In this project we develop algorithms with worst-case guarantees regarding non-functional properties such as timing, resource utilisation, adaptivity, speed-factors and power consumption. We advance the theoretical foundations to exploit the power of parallel computing and particularly the benefits of invasive computing also for safety-critical applications. We expect to develop algorithms that are not only efficient from a theoretical standpoint but can be efficiently implemented in practice.


F. Eberle, F. Fischer, J. Matuschke, N. Megow: On Index Policies for Stochastic Minsum Scheduling. Operations Research Letters, 2019.
J.J. Chen, R. Hoeksma, T. Hahn, N. Megow and G. von der Brueggen: Scheduling Self-Suspending Tasks: New and Old Results. In Proc. of 31st Euromicro Conference on Real-Time Systems (ECRTS), 2019.
N. Megow, J. Verschae: Dual techniques for scheduling on a machine with varying speed. SIAM Journal on Discrete Mathematics 32(3): 1541-1571, 2018.
Loris Marchal, Hanna Nagy, Bertrand Simon and Frédéric Vivien. Parallel scheduling of DAGs under memory constraints. In Proc. of the 32st IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2018.
Loris Marchal, Samuel McCauley, Bertrand Simon and Frédéric Vivien. Minimizing I/Os in Out-of-Core Task Tree Scheduling. In Proc. of the 19th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), 2017.
L. Chen, N. Megow, K. Schewior: An O(log m)-Competitive Algorithm for Online Machine Minimization. Accepted for publication in SIAM Journal on Computing, 2018. Extended abstract published at SODA 2016.
L. Chen, N. Megow, K. Schewior: The Power of Migration in Online Machine Minimization. In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pp. 175-184, 2016.
Abdou Guermouche, Loris Marchal, Bertrand Simon and Frédéric Vivien. Scheduling Trees of Malleable Tasks for Sparse Linear Algebra. In Proc. of the European Conference on Parallel Processing (Euro-Par), 2015.

[1] Bertrand Simon, Joachim Falk, Nicole Megow, and Jürgen Teich. Energy minimization in DAG scheduling on MPSoCs at run-time: Theory and practice. In Workshop on Next Generation Real-Time Embedded Systems, 2020.
[2] Alberto Marchetti-Spaccamela, Nicole Megow, Jens Schlöter, Martin Skutella, and Leen Stougie. On the complexity of conditional dag scheduling in multiprocessor systems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2020.
[3] Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling self-suspending tasks: New and old results. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019), 2019.