Projects


A5: Scheduling Invasive Multicore Programs Under Uncertainty

Principal Investigators:

Prof. N. Megow

Scientific Researchers:

Dr. B. Simon




Abstract

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.

Synopsis

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.

Approach

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.

Publications

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.