Projects

A5: Scheduling Invasive Multicore Programs Under Uncertainty

Principal Investigators:

Prof. Nicole Megow

Scientific Researchers:

Dr. Bertrand Simon (09/2018-09/2020)
Alexander Lindermayr (10/2020-now)

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).
• uncertain task suspension when waiting for instance for input data
• conditional task sets and dependencies revealed only at runtime based on execution results
• no certainty on the future is possible but predictions are available: the objective is then to design algorithms that perform well if these predictions are accurate but also provide guarantees regardless of the prediction quality.

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.

The main contributions of this project are summarized below.

Energy-Minimization in DAG Scheduling

Static (offline) techniques for mapping applications given by task graphs to MPSoC systems often deliver overly pessimistic and thus suboptimal results w.r.t. exploiting time slack in order to minimize the energy consumption. This holds true in particular in case computation times of tasks may be workload-dependent and becoming known only at runtime or in case of conditionally executed tasks or scenarios. We present and analyze algorithms for scheduling such periodic applications and provide provably optimal results as well as approximation algorithms with proven guarantees on the achieved energy savings.

Consumed energy of our approach in empirical experiments.

Designing Algorithms using Untrusted Predictions

A large disadvantage of machine-learned predictors is that we cannot expect correct predictions in all situations. Still, decision-making systems that are based on such predictors need not only to benefit from good predictions but also to achieve a decent performance when the predictions are inadequate. We propose a robust prediction setup for arbitrary metrical task systems (MTS) (e.g., caching, k-server and convex body chasing) and online matching on the line. Specifically for caching, we present an algorithm whose performance, as a function of the prediction's quality, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real world datasets, which suggests practicality.

Conditional DAG Scheduling

One of the main models for parallel applications is a DAG of tasks, where edges represent precedence constraints. The conditional DAG model allows the presence of control structures such as conditional (if-then-else) constructs. We perform a thorough analysis on the worst-case makespan (latest completion time) of a conditional DAG task under list scheduling (a.k.a. fixed-priority scheduling). We show several hardness results concerning the complexity of the optimization problem on multiple processors. Complementing these negative results, we show that certain practice-relevant DAG structures are very well tractable.

Example source code and its representation as a conditional DAG.

Scheduling Self-Suspending Tasks

In computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. Such self-suspension behavior has been shown to induce performance degradation in real-time systems. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art.

Scheduling on Heteregoneous Processors

Modern platforms are using accelerators in conjunction with standard processing units in order to reduce the running time of specific operations, such as matrix operations. We consider the problem of scheduling a set of tasks subject to precedence constraints on hybrid platforms, composed of two types of processing units. We improve the best known approximation algorithm and propose the first conditional lower bounds specific to this setting. In a separate work, we have conducted a survey classifying the main algorithms existing to handle different settings of hybrid platform scheduling and propose unified implementations to evaluate them on a large set of benchmarks.

Prediction-clairvoyant scheduling

In many realistic scheduling scenarios, the precise processing times of the jobs are uncertain. Hence, it is often assumed that they are completely unknown. The classic preemptive approach for this problem is the famous Round-Robin algorithm, which distributes the resources fairly among all unfinished jobs. However, this setting often is overly pessimistic, as in many applications we have a rough estimate of a job's length, e.g. using simple statistics or machine learning. We consider using such untrusted predictions to design algorithms that improve over long-standing lower bounds given sufficiently good predictions, and also demonstrate their applicability and improvements on real world data in empirical experiments.

Preemptive robustification of following a predicted schedule (A) by using Round-Robin (B).

News

• May 20, 2021: Alexander Lindermayr's Master's Thesis "Learning-Augmented Online Algorithms for the 2-Server Problem on the Line and Generalizations" was nominated for the Bremer Studienpreis award by the Faculty of Mathematics and Computer Science of the University of Bremen.
• Sept 30, 2020: Bertrand Simon joins as a CNRS researcher the IN2P3 Computing Center in Villeurbanne/Lyon.