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.

[1] Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, and Bertrand Simon. Scheduling on hybrid platforms: Improved approximability window. In Proceedings of the Latin American Theoretical Informatics Symposium, 2020.
[2] Olivier Beaumont, Louis-Claude Canon, Lionel Eyraud-Dubois, Giorgio Lucarelli, Loris Marchal, Clément Mommessin, Bertrand Simon, and Denis Trystram. Scheduling on two types of resources: A survey. ACM Computing Surveys, 2020.
[3] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In Proceedings of the Thirty-Seventh International Conference on Machine Learning (ICML), 2020.
[4] Bertrand Simon, Joachim Falk, Nicole Megow, and Jürgen Teich. Energy minimization in DAG scheduling on MPSoCs at run-time: Theory and practice. In Proceedings of the Workshop on Next Generation Real-Time Embedded Systems (NG-RES), pages 2:1–2:13, 2020. [ DOI ]
[5] Alberto Marchetti-Spaccamela, Nicole Megow, Jens Schlöter, Martin Skutella, and Leen Stougie. On the complexity of conditional dag scheduling in multiprocessor systems. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2020.
[6] Franziska Eberle, Felix Fischer, Jannik Matuschke, and Nicole Megow. On index policies for stochastic minsum scheduling. Operations Research Letters, 47(3):213–218, 2019.
[7] Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling self-suspending tasks: New and old results. In Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019), 2019.