### Inhalt des Dokuments

# Algorithm Engineering for Real-time Scheduling and Routing

Project
directors: | Prof. Dr. Friedrich Eisenbrand [1] Prof. Dr. Martin Skutella [2] |
---|---|

Researcher: | Jannik Matuschke
[3] |

Associated
researchers: | Andreas Karrenbauer [4] Martin Niemeier Britta Peis [5] Thomas Rothvoß [6] Andreas Wiese [7] |

Support: | DFG Priority Programme
1307 "Algorithm Engineering" [8] |

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

- [10]
- © COGA/EPFL

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 [11]*). 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 [12]*).

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

- [13]
- © COGA/EPFL

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 [14]; Davis et al., Real Time Systems 2009 [15]*),
approximation algorithms (*Karrenbauer and Rothvoß, WAOA 2010
[16]*) and hardness results (*Eisenbrand and Rothvoß, APPROX
2009 [17]; Eisenbrand and Rothvoß, SODA 2010
[18]*).

### 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 [19]; Niemeier and Wiese, WAOA 2012
[20]*). 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

Order by: Author [21] Year [22] Journal [23]

Skutella, Martin and Peis, Britta and
Wiese, Andreas

**Packet Routing on the Grid [24]**.

In **Lopez-Ortiz, Alejandro
(ed.)**, *Theoretical Informatics, 9th Latin American
Symposium, LATIn 2010, Oaxaca, Mexico*, Lecture Notes in Computer
Science, Springer, Vol. 6034, pp. 120-130, 2010.

Peis, Britta and Skutella, Martin and
Wiese, Andreas

**Packet Routing: Complexity and Algorithms [25]**.

In **Bampis, Evripidis and Jansen, Klaus
(ed.)**, *Approximation and Online Algorithms, 7th
International Workshop, WAOA 2009, Copenhagen, Denmark, September
2009. Revised Papers*, pp. 217–228, Springer, 2010.
[pdf] [26]

Peis, Britta and Stiller, Sebastian and
Wiese, Andreas

**Policies for Periodic Packet Routing [27]**.

In **Cheong, Otfried and Chwa Kyung-Yong and Park, Kunsoo
(ed.)**, *Algorithms and Computation - 21st International
Symposium, ISAAC 2010, Jeju Island, Korea*, Lecture Notes in
Computer Science, Springer, Vol. 6507, pp. 266–278, 2010.

Peis, Britta and Wiese,
Andreas

**Universal packet routing with arbitrary bandwidths and
transit times [28]**.

In *Integer Programming and Combinatorial Optimization
(IPCO 2011)*, pp. 362-375, Springer, 2011.

Peis, Britta and Wiese,
Andreas

**Throughput Maximization for Periodic Packet Routing on
Trees and Grids [29]**.

In *Approximation and Online Algorithms (WAOA 2010)*,
pp. 213–224, Springer, 2011.

Niemeier, Martin and Wiese,
Andreas

**Scheduling with an Orthogonal Resource Constraint
[30]**.

In *10th Workshop on Approximation and Online Algorithms
(WAOA2012)*, 2012.

Niemeier, Martin and Wiese, Andreas and
Baruah, Sanjoy

**Partitioned Real-Time Scheduling on Heterogeneous
Shared-Memory Multiprocessors [31]**.

In *Proceedings of the 23rd Euromicro Conference on
Real-Time Systems (ECRTS 2011)*, 2011.

to appear. [pdf] [32]

Koch, Ronald and Peis, Britta and
Skutella, Martin and Wiese, Andreas

**Real-Time Message Routing and Scheduling [33]**.

In **Jansen, Klaus and Naor, Joseph and Rolim, Jose
(ed.)**, *Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques, 12th International Workshop,
APPROX-RANDOM 2009, Berkeley, USA*, Lecture Notes in Computer
Science, Springer, Vol. 5687, pp. 217–230, 2009.

Karrenbauer, Andreas and Rothvoß,
Thomas

**An Average-Case Analysis for Rate-Monotonic
Multiprocessor Real-time Scheduling [34]**.

In *Proceedings of the 17th Annual European Symposium on
Algorithms (ESA 2009)*, Lecture Notes in Computer Science, Vol.
5757, pp. 432–443, Springer, 2009.
[pdf] [35]

Karrenbauer, Andreas and Rothvoß,
Thomas

**A 3/2-Approximation Algorithm for Rate-Monotonic
Multiprocessor Scheduling of Implicit-Deadline Tasks [36]**.

In *Proceedings of the 8th International Workshop on
Approximation and Online Algorithms (WAOA 2010)*, Lecture Notes in
Computer Science, Vol. 6534, pp. 166-177, Springer, 2011.

Eisenbrand, Friedrich and Rothvoß,
Thomas

**EDF-schedulability of synchronous periodic task systems
is coNP-hard [37]**.

In *Proceedings of the ACM-SIAM Symposium on Discrete
Algorithms (SODA 2010)*, pp. 1029–1034, 2010.
[pdf] [38]

Eisenbrand, Friedrich and Rothvoß,
Thomas

**New Hardness Results for Diophantine Approximation
[39]**.

In *Proceedings of the 12th Intl. Workshop on
Approximation Algorithms for Combinatorial Optimization Problems
(APPROX 2009)*, Lecture Notes in Computer Science, Vol. 5687, pp.
98–110, Springer, 2009.
[pdf] [40]

Eisenbrand, Friedrich and Rothvoß,
Thomas

**Static-priority Real-time Scheduling: Response Time
Computation is NP-hard [41]**.

In *IEEE Real-Time Systems Symposium (RTSS)*, 2008.
[pdf] [42]

Eisenbrand, Friedrich and Hähnle,
Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, José
and Wiese, Andreas

**Scheduling periodic tasks in a hard real-time
environment [43]**.

In **Abramsky, Samson and Gavoille, Cyril and Kirchner,
Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.
(ed.)**, *Automata, Languages and Programming (ICALP
2010)*, pp. 299–311, Springer, 2010.
[pdf] [44]

Eisenbrand, Friedrich and Kesavan,
Karthikeyan and Mattikalli, Raju S. and Niemeier, Martin and
Nordsieck, Arnold W. and Skutella, Martin and Verschae, José and
Wiese, Andreas

**Solving an Avionics Real-Time Scheduling Problem by
Advanced IP-Methods [45]**.

In **de Berg, Mark and Meyer, Ulrich
(ed.)**, *Algorithms – ESA '10*, pp. 11–22, Springer,
2010.
[pdf] [46]

Davis, Robert and Rothvoß, Thomas and
Baruah, Sanjoy and Burns, Alan

**Exact quantification of the sub-optimality of
uniprocessor fixed-priority preemptive scheduling [47]**.

*Kluwer Academic Publishers*, Vol. 43, pp.
211–258, 2009.

dr_martin_skutella/parameter/maxhilfe/

k_matuschke/jannik_matuschke/parameter/maxhilfe/

a_peis/britta_peis/parameter/maxhilfe/

as_wiese/jan_philipp_kappmeier/parameter/maxhilfe/

ebseite/AG_DiskAlg/FG_KombOptGraphAlg/logos/dfg-algorit

hm-engineering-long.jpg

Webseite/AG_DiskAlg/FG_KombOptGraphAlg/projects/SPP-RTS

_Routing/BinTree.png

nal.pdf

l.pdf

Webseite/AG_DiskAlg/FG_KombOptGraphAlg/projects/SPP-RTS

_Routing/RateMonotonic.png

ase-esa09.pdf

2n/

a2010.pdf

-approx-cameraready.pdf?version=2

&mode=best

eduling.pdf

meier-wiese-2012-scheduling-with-orthogonal-constraint.

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?cHash=a3d8c03afad5406c6844eb6042fe

eae3&tx_sibibtex_pi1%5Bsort%5D=author%3A0&type=

1

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?cHash=07b612e5f308006c4f4c53c9e076

75f4&tx_sibibtex_pi1%5Bsort%5D=year%3A0&type=1

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?cHash=ddec8ca926f4b951d4aae72fbff9

700f&tx_sibibtex_pi1%5Bsort%5D=journal%3A0&type

=1

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238270&cHash=4a2277d13c3f6ac6f8893f1b2c732f25

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238269&cHash=887ef2032f51131461fb836999459f6b

ncs.pdf

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238271&cHash=8a7185e3a187efa2d234fbc4a1d07a66

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238272&cHash=4dfce2d7e31fd254153bfb02d98b2154

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238273&cHash=621389542a898879f1bc408c258f3dca

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330815&cHash=6f3bdacf215fe69c96d8d0b7dac52c7e

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238268&cHash=61e164e698d865559f2e5d2886605f85

eduling.pdf

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238245&cHash=0570dfc901c6e146ce829bf15f9c5a3e

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330812&cHash=0073aff11473ebf06afe8f6d09c474d9

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330813&cHash=0badf7a4d51c0dac5ac2253dca139326

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330810&cHash=afcd94387c1cb4dd5cf9dea0fb30b0d2

&mode=best

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330811&cHash=c112f5dcc62f50690cd0e24b103d31b8

&mode=best

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330814&cHash=9b0207c20d7393c5ee8cb352057b3a33

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238179&cHash=f729227cc208a50f64e0e18db49428b7

final.pdf

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

238182&cHash=b9f57c32f5194a96b376f0644345066a

nal.pdf

orithm_engineering_for_real_time_scheduling_and_routing

/parameter/maxhilfe/?tx_sibibtex_pi1%5Bcontentelement%5

D=tt_content%3A478316&tx_sibibtex_pi1%5BshowUid%5D=

330809&cHash=c8804886b7810dde1618d06b20bbab95