DFG Algorithm Engineering for Real-time Scheduling and Routing

Project director: Prof. Dr. Fritz Eisenbrand, Prof. Dr. Martin Skutella,
Ecole Polytechnique Fédérale de Lausanne, Technische Universität Berlin
Researcher: Andreas Karrenbauer, Martin Niemeier, Britta Peis, Thomas Rothvoß, Andreas Wiese
Support: Deutsche Forschungsgemeinschaft (DFG)
within Priority Programme 1307 "Algorithm Engineering"

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.

Scheduling periodic real-time tasks systems

We study fundamental periodic scheduling problems that occur in real-time systems. In [5] we were able to solve a longstanding open problem, concerning the complexity of response-time computation of a periodic task. This paper revealed an intimate connection of real-time scheduling with the theory of integer programming, specifically the algorithmic geometry of numbers. We believe that this connection should be further elaborated to contribute with more fundamental results on the complexity of real-time scheduling as well as to develop algorithms to solve real-time scheduling problems efficiently. We consider periodic tasks t1,...,tn where each task ti=(c(ti),d(ti),p(ti)) releases a job of running time c(ti) at each integer multiple of the period p(ti) which has to be finished before the (relative) deadline d(ti). In the important special case of implicit-deadlines we have d(ti)=p(ti) for all tasks ti.

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.

Implementation and test of an algorithm library

This part is devoted to the further implementation and test of the algorithmic methods developed in what is described above. The empirical evaluation of the implemented algorithms will provide crucial information for the further development and redesign of algorithms. So far, we were mostly concerned with fundamental theoretical problems in scheduling and routing and did not test our ideas yet on real-world instances. This will be different in the coming period of our project, as we intensify our collaboration with the real-time systems group in Salzburg. This group around Christoph Kirsch has developed the programming language HTL [7] to model and program real-time systems for control and other safety-critical applications. HTL succeeds the well known Giotto [8] programming language and allows in particular for precedence relations between tasks of the same period and for mapping program modules to arbitrary communication networks. HTL is in use, for example, as a tool to implement control of autonomous helicopters. While the primary goal of HTL lies on safety and liveness of critical applications, the optimization of hardware resources was not yet in the focus of this project; optimal scheduling and routing of messages has so far not yet been considered.

Publications

[1]
R. Davis, T. Rothvoß, S. Baruah, and A. Burns. Exact Quantification of the Sub-optimality of Uniprocessor Fixed Priority Pre-emptive Scheduling. Real-Time Systems 43(3), pages 211-258. 2009.
[2]
F. Eisenbrand, N. Hähnle, M. Niemeier, M. Skutella, J. Verschae, and A. Wiese. Scheduling periodic tasks in a hard real-time environment. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), volume 6198 of LNCS, pages 299-311. Springer, 2010.

[3]
F. Eisenbrand and T. Rothvoß. A ptas for static priority real-time scheduling with resource augmentation. In Proceedings of the 35th international Colloquium on Automata, Languages and Programming (ICALP 2008), volume 5125 of LNCS, pages 246-257. Springer, 2008.
[4]
F. Eisenbrand and T. Rothvoß. Static-priority real-time scheduling: Response time computation is np-hard. In Proceedings of the 29th IEEE Real-Time Systems Symposium (RTSS 2008), pages 397-406, 2008.
[5]
F. Eisenbrand and T. Rothvoß. EDF-schedulability of synchronous periodic task systems is coNP-hard. In ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), 2010.
[9]
R. Koch, B. Peis, M. Skutella, and A. Wiese. Real-time message routing and scheduling. In S. Naor, editor, Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009), volume 5687 of LNCS, pages 217-230. Springer, 2009.

[10]
B. Peis, M. Skutella, and A. Wiese. Packet routing: Complexity and algorithms. In E. Bampis and K. Jansen, editors, Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009), volume 5893 of LNCS, pages 217-228. Springer, 2010.

[11]
B. Peis, M. Skutella, and A. Wiese. Packet routing on the grid. In Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN 2010), volume 6034 of LNCS, pages 120-130. Springer, 2010

[12]
A. Karrenbauer and T. Rothvoß. An average-case analysis for rate-monotonic multiprocessor real-time scheduling. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009), volume 5757 of LNCS, pages 432-443. Springer, 2009.
[13]
F. Eisenbrand, M. Niemeier, M. Skutella, J. Verschae, and A. Wiese. Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), volume 6346 of LNCS, pages 11-22. Springer, 2010.
[14]
B. Peis and A. Wiese. Throughput Maximization for Periodic Packet Routing on Trees and Grids. In Proceedings of the 8th Workshop on Approximation and Online Algorithms (WAOA 2010), volume 6534 of LNCS, pages 213-224. Springer, 2011.
[15]
B. Peis and A. Wiese. Universal packet routing with arbitrary bandwidths and transit times. In Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), to appear.
[16]
M. Niemeier, A. Wiese and S. Baruah. Partitioned real-time scheduling on heterogeneous shared-memory multiprocessors. In Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS 2011), to appear.

Other references

[6]
P. Sanders G. F. Italiano, P. Mutzel and M. Skutella. Algorithm engineering. Technical Report 25/2007, Mathematisches Forschungsinstitut Oberwolfach, 2007.

[7]
A. Ghosal, A. Sangiovanni-Vincentelli, C. Kirsch, T. Henzinger, and D. Iercan. A hierarchical coordination language for interacting real-time tasks. In Sang Lyul Min and Wang Yi, editors, EMSOFT, pages 132-141. ACM, 2006.

[8]
T. Henzinger, B. Horowitz, and C. Kirsch. Giotto: a time-triggered language for embedded programming. Proceedings of the IEEE, 91:84-99, 2003.