### Inhalt des Dokuments

# Algorithm Engineering for Real-time Scheduling and Routing

Project directors: | Prof. Dr. Friedrich Eisenbrand Prof. Dr. Martin Skutella |
---|---|

Researcher: | Jannik Matuschke |

Associated researchers: | Andreas Karrenbauer Martin Niemeier Britta Peis Thomas Rothvoß Andreas Wiese |

Support: | DFG Priority Programme 1307 "Algorithm Engineering" |

Since: | 2007 |

## Project Overview

**Problem Description**

While 20 years ago microprocessors have mostly been used in desktop computer workstations and large-scale computers, they have meanwhile become ubiquitous. They are used in nearly all areas of technology and specifically in safety and mission critical applications. The future vision of the automotive and avionics industry is complete, safe and reliable drive-by-wire and fly-by-wire respectively. Such industrial applications gave rise to the field of computer science which is called real-time scheduling and routing. Whereas classical scheduling deals with the distribution of a finite set of tasks to a set of machines, real-time scheduling deals with recurring tasks which are often periodic and thus appear infinitely often. Since the processors in a real-time system communicate by passing messages, the messages have to be routed through the architecture (modelled as a directed graph) additionally.

The goal of the project is to develop, implement, analyse and test algorithms for real-time scheduling and routing problems using methods of linear and integer programming as well as various scheduling and routing techniques from discrete optimization.

### Real-time scheduling under hard periodicity constraints

Hard periodic real-time scheduling problems are motivated by special requirements of real-time systems arising in safety critical environments, e. g. the avionics or automotive industry. Here, system designers need to schedule highly critical periodic control tasks with a predictable and static scheduling policy such that preemption and dynamic effects are avoided. For that reason, a hard periodic execution schedule is required. Here each task t_{i}=(c(t_{i}),p(t_{i})) releases a job of running time c(t_{i}) periodically exactly every p(t_{i}) timeunits. The problem is to find stating offsets that ensure that no collision of different jobs occurs.

Our research led to a characterization of the complexity landscape of the problem both in terms of approximation algorithms and inapproximability results (see *Eisenbrand et al., ICALP 2010*). Based on insights gained in the theoretical analysis, we also designed an algorithm and a solver that can tackle, for the first time, large previously unsolved instances from the avionics industry (see *Eisenbrand et al., ESA 2010*).

Although we made significant progress both in understanding the theoretical nature of the problem and solving it in practice, still there are important questions left open that we address in further research.

### Deadline constrained real-time scheduling

In deadline constrained real-time scheduling we have more relaxed feasibility requirements as in the case of hard periodic scheduling. Instead of requiring perfect periodic execution of the tasks, the jobs released periodically by the tasks have to be executed within a certain given time span after their release, specified by its relative deadline d_{i}. In the important special case of implicit deadlines the relative deadlines match the task periods, i. e. we have _{p}_{i} = d_{i} for all tasks, this means that a job of a task should be finished before the next one is released.

We studied two scheduling policies. For static-priority systems, the rate-monotonic scheduling policy is considered. Here, whenever two unfinished jobs are available at the same time, the one with the lower period is prioritized. For dynamic priority systems, the earliest-deadline-first policy is studied. Here, whenever two unfinished jobs are available at the same time, the one with the closer deadline is prioritized. The reason to consider these policies is that they are provably optimal, i.e., whenever an instance is feasible under any static/dynamic priority policy, it is also feasible under rate-monotonic/earliest-deadline-first policy (see *Liu and Layland, 1973*). We contributed significantly to a better theoretical understanding of these problems by providing, amongst other things, an average case analyis (*Karrenbauer and Rothvoß, ESA 2009; Davis et al., Real Time Systems 2009*), approximation algorithms (*Karrenbauer and Rothvoß, WAOA 2010*) and hardness results (*Eisenbrand and Rothvoß, APPROX 2009; Eisenbrand and Rothvoß, SODA 2010*).

### Scheduling jobs with shared memory

Embedded real-time systems are often implemented upon heterogeneous hard-

ware, consisting of several distinct processors, each with its own instruction set.

This trend towards platform heterogeneity is becoming more pronounced as real-time systems increasingly come to be implemented upon multicore platforms. Specialized hardware components are used that accelerate certain computations—examples include multicore CPUs with specialized graphics processing cores, signal-processing cores, floating-point units, customizable FPGAs etc. The heterogeneous multiprocessor platforms upon which embedded real-time systems are implemented often possess a shared pool of memory in addition to the computing cores (*see Hady et al., 2009*).

Therefore, we want to investigate real-time scheduling problems under the additional constraint that the jobs need to share a common pool of memory. The jobs which are active at any time must not exceed the total available memory of the system.

As a first step to understand the shared memory constraint, we investigated classical static offline scheduling problems where we additionally impose this constraint. We developed approximation algorithms for several variants of the offline scheduling problem (see *Niemeier et al., ECRTS 2011; Niemeier and Wiese, WAOA 2012*). While the offline variant is, to some extent, well understood, fundamental questions in the online and real-time scheduling variant are still open. Our next step is to contribute to a better understanding of these variants of the shared memory scheduling problem.

### Routing real-time messages

The problem to send a given set of messages through a communication network on time is a very involved problem of high practical relevance, even the special case in which all messages have unit size (i.e., the packet routing problem). We distinguish between the packet routing and the more general message routing problem, consider these problems on simple network topologies, with and without restrictions on the number of sources and sinks, release times, deadlines, travel times and capacities. Moreover, since packet routing is strongly related to dynamic flows, we aim to develop and translate techniques and ideas from the theory of dynamic flows to design efficient algorithms for the packet and message routing problem on the one hand, and on the other hand, contribute with our results to a better understanding of dynamic flows.

### Scheduling and routing dependent periodic tasks

While in the above we investigate real-time scheduling of periodic task systems and real-time routing of messages separately, the goal here is to develop algorithmic methods which can deal with the combination of the two problems: imagine a periodic task system with dependencies among the tasks in the sense that the successful execution of the jobs of one task might require the information of the jobs of another task. Thus, in case two dependent tasks are assigned to different processors, the corresponding information needs to be routed through the communication network linking the processors. This ambitious goal involves critical routing and scheduling decisions which affect each other. Before we approach this goal, we investigate the problem to schedule periodic task systems with dependencies but without any routing decisions. Also, we study the problem to route periodic messages through a network given that the tasks are already scheduled.

## References

Liu, C. L. and Layland, James W.**Scheduling algorithms for multiprogramming in a hard-real-time environment.**

J. Assoc. Comput. Mach., 20:46–61, 1973.

Hady, F. T. and Cabot, M. B. and Beck, J. and Rosenbluth, M.**Heterogeneous processors sharing a common cache.**

United States Patent 7,577,792. Assignee: Intel Corporation, 2009.

## Publications

Citation key | EisenbrandRothvoss2010 |
---|---|

Author | Eisenbrand, Friedrich and Rothvoß, Thomas |

Title of Book | Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010) |

Pages | 1029–1034 |

Year | 2010 |

Abstract | In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d_i <= p_i, the EDF-schedule is feasible if and only if for all Q >= 0: \sum_i=1^n (floor(Q-d_i)/p_i) + 1) * c_i <= Q. Though an enormous amount of literature deals with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is (weakly) coNP-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation. |