Technische Universität Berlin

This workshop aims at bringing together young researchers from different scheduling communities in computer science, mathematics and operations research and discussing common research interests. The focus of this workshop are broadly theory, algorithms and complexity for realtime systems which appears to be a fruitful field for interdisciplinary collaboration on important problems. The workshop program contains talks, open problem sessions, and discussion rounds on general future research developments of this area. The goal is to discuss relevant research directions, identify particular research questions and potential collaborations, and to establish a longlasting research network.
This workshop is supported by the Mathematics Department at TU Berlin, and the DFG Research Center MATHEON.
Location: The workshop will take place in the BMS conference room at the second floor of the Mathematics Department at TU Berlin. Please see this page for travel information.
Organizing committee: Marko Bertogna (University of Modena, Italy), Nicole Megow (MPI für Informatik, Saarbrücken, and TU Darmstadt), Sebastian Stiller (TU Berlin).
Registration: Please send an email to Sebastian. There is a registration fee of 40 Euro.
Monday (Feb. 27)
12:0013:00 Welcome buffet
13:0016:00 Introductory round and presentation of general research interests
16:0016:30 Coffee
16:3017:00 Marko Bertogna: Future funding opportunities, energy scheduling and multiprocessor systems [slides]
17:0017:30 Vincenzo Bonifaci: Scheduling a Few Different Types of Unrelated Machines [slides]
17:3018:00 Ahlem Mifdaoui: System level worstcase performance evaluation of embedded Networks [slides]
Tuesday (Feb. 28)
09:3010:00 JianJia Chen: Timing predictability in resourcesharing systems [slides]
10:0010:30 Suzanne van der Ster: Mixedcriticality scheduling of implicitdeadline task systems on a single machine [slides]
10:3011:00 Rob Davis: Optimal Priority Assignment Algorithms for Probabilistic RealTime Systems [slides1, slides2]
11:0011:30 Coffee
11:3012:30 Collaboration and discussion
12:3013:30 Lunch
13:3015:30 Collaboration and discussion
15:3016:00 Cyriel Rutten: Feasibility tests for sporadic task systems on unrelated parallel machines [slides]
16:0016:30 Enrico Bini: Optimal assignment of periods and deadlines to EDFscheduled tasks [slides]
16:3017:00 Nikhil Bansal: The Geometry of Scheduling [slides]
17:0018:00+ Discussion on future research topics
Wednesday (Feb. 29)
09:3010:00 Rene Sitters: Efficient algorithms for average completion time scheduling [slides]
10:0010:30 Thomas Nolte: Predictability and resource reservation [slides]
10:3011:00 Coffee
11:0011:30 Andreas Wiese: The periodic maintenance problem [slides]
11:0012:00 Nicole Megow: Scheduling to meet deadlines: online algorithms and feasibility tests [slides]
12:00 Review and closing
Marko Bertogna: Future funding opportunities, Energy scheduling and Multiprocessor systems
The seventh Framework Programme for Research and Innovation of the
European Community is coming to a conclusion, and will be replaced in
2014 by Horizon 2020, the new research funding programme that will
allocate around 80 billion Euro through three broad lines of action.
This talk will briefly show the remaining opportuitites for joint
project proposals in the remaining calls of FP7, and the more
promising research directions of Horizon 2020, with a particular focus
on ICT topics that are of interest to our communities (realtime
systems, embedded systems, algorithms, scheduling). The intention is
to stimulate the discussion for establishing meaningful collaborations
and connections for future joint project proposals. Two very generic
examples are given for possible research directions: the management of
realtime electrical loads, and the scheduling problem for
massivelyparallel multiprocessor platforms.
Vincenzo Bonifaci: Scheduling a Few Different Types of Unrelated Machines
We give a polynomial time approximation scheme (PTAS) for the problem of
scheduling a set of jobs on a set of unrelated machines in the case that each
machine belongs to one of a fixed number of types, and the processing time of
each job depends only on the job and the type of the machine it is assigned
to. This generalizes existing PTASs for identical machines and for a constant
number of unrelated machines. The result more generally holds for
multidimensional jobs with a fixed number of dimensions. One application is
the assignment of sporadic implicitdeadline tasks to a set of heterogeneous
processors in the presence of, e.g., memory constraints.
Ahlem Mifdaoui: System level worstcase performance evaluation of embedded Networks
With the increasing complexity of embedded networks and the expansion of
exchanged data quantity, making the right design decisions to guarantee the
systems requirements becomes a difficult task for designer. Hence, it
becomes one of the major challenges in the design process to analyze the
systems characteristics till the first steps of the development cycle.
Simulations are commonly used for exploring the design space and validating
the functional and timing behaviors of the embedded networks. However, these
approaches are feasible for only small parts of the system and cannot cover
the entire domain of the model applicability and especially rare events that
represent worstcase functioning of the system. So, clearly, simulations
cannot provide the deterministic guarantees required by critical embedded
networks with hard certification requirements to respect like in civil and
military avionics, automotive and satellites, where a failure might have a
disastrous consequence on the system. With a formal specification language
like StateCharts or Specification and Description Language (SDL), it is
possible to verify the functional behavior of the network. However, for big
networks with an important number of nodes, this approach leads to a space
explosion problem inherent to the reachability analysis techniques
implemented by the formal verification tools. In order to overcome these
limitations, integrating an aideddecision tool till the first steps of the
design process becomes necessary to choose the right systems parameters to
respect the required constraints before investing too much time in detailed
implementations. WOPANets (Worst Case Performance Analysis of embedded
Networks) is a new tool that embodies an analytical approach based on the
Network Calculus formalism to perform a system level worstcase performance
evaluation and includes optimization analysis to find the optimal design
solution that guarantees the system's requirements. This approach would
enhance the design process time and costs. Some avionics and space networks
are already implemented in WOPANets like AFDX and Spacewire and new models
for applications based on multicluster embedded networks and wireless
technologies are in progress.
JianJia Chen: Timing predictability in resourcesharing systems
Designing systems with predictable timing behavior is an important task for safetycritical systems, such as automotive and avionic applications. This requires joint considerations from both software and hardware sides to certify the timing properties. The hardware should be timing predictable, i.e., timing accidents, including cache misses, pipeline stalls, branch mispredictions, bus collisions, memory refresh of DRAM, and TLB misses, should have bounded delay. The software should also be timing predictable from a single task's perspective (e.g., bounded loops, program depth, stack size, etc.) to multiple tasks' perspective (e.g., bounded number of preemptions, restarts, resource contentions, etc.).
Typically, when a predictable hardware platform is given, the timing behavior of a program may be analyzed approximately by using static analysis. The worstcase execution time (WCET) is then used for analyzing whether a set of programs can meet their timing constraints, i.e., the its response time should not exceed its relative deadline. This works well when uniprocessor systems or multiprocessor systems without hardware sharing are considered.
However, to reduce the cost and power consumption, resource sharing has been widely adopted in modern multicore system designs. That is, several cores have shared memory, shared communication fabric, etc. The drawback for resource sharing is mainly on the performance penalty. Therefore, how to share the resources will affect the timing behavior significantly. Timing anomalies usually happen when we consider resource sharing. Constructing tight analysis is usually nontrivial.
I would like to talk a little bit about what we have done for worstcase
timing analysis when resource sharing is considered. We have tried to model
the fundamental problem and solved it with overapproximation with high
time/space complexity. Tighter and more efficient analysis are needed to make
sure that resource sharing in multicore systems does not make the system
timing unpredictable.
Suzanne van der Ster: Mixedcriticality scheduling of implicitdeadline task systems
We consider scheduling an implicitdeadline sporadic task system on a single machine in a mixedcriticality setting. Each task of such a system generates a (possibly infinite) string of jobs, released one by one, with an interarrival separation bounded from below by a certain taskdependent period. Each job has a relative deadline equal to the length of that period.
In a mixedcriticality setting, each task has multiple levels of worstcase execution time estimates and each task has its own criticality level. By executing the tasks, we learn what level the system is in (which may change over time). When the system is in level $\ell$, all jobs of tasks of level larger or equal to $\ell$ should be scheduled for their level$\ell$ execution requirement, to meet their deadline.
Mixedcriticality systems arise when multiple functionalities are scheduled upon a single shared computing platform. This can force tasks of different importance (i.e. criticality) to share a processor.
We give a scheduling algorithm for scheduling a mixedcriticality task
system, called EDFVD (Earliest Deadline First with Virtual
Deadlines). We give sufficient conditions to check feasibility
efficiently for $K$ levels. For 2 levels we also analyze the
effectiveness of our scheduling algorithm using the processor speedup
metric. We show that if a 2level task system is schedulable on a
unitspeed processor, then it is correctly scheduled by EDFVD on a
processor of speed 4/3.
Rob Davis: Optimal Priority Assignment Algorithms for Probabilistic RealTime Systems
We present the problem of optimal priority assignment in fixed
priority preemptive single processor systems where tasks have
probabilistic execution times. We identify three subproblems which
optimize different metrics related to the probability of deadline
failures.
Cyriel Rutten: Feasibility tests for sporadic task systems on unrelated parallel machines
In modern hardware architectures it has become a very common feature to contain several types of processors with possibly completely different characteristics. In (realtime) scheduling, this feature is modeled by assuming the machines of a system to be unrelated. We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled.
We develop a polynomialtime algorithm which approximates the problem with a constant speedup factor of $2\cdot(4 + \sqrt{6})=12.9$ when the number of machines is arbitrary. Further, we show that any polynomialtime algorithm needs a speedup factor of at least 2, unless P = NP. Also, if the number of machines is constant, we approximate the problem to a factor of $1+ \epsilon$.
In this talk, we will provide an overview of the techniques used to derive
our results. Key is a better understanding of the demand bound function which
yields a sufficient and necessary condition for a task system on a single
machine to be feasible. In particular, we evaluate function only at a
constant number of time moments. Additionally, we approximate the demand
bound function of a task by the task's utilization whenever the task's
deadline sufficiently smaller than the time moment at which the function is
being evaluated. In case the number of machines is arbitrary, we continue
with formulating a linear program for which an integer solution (implying a
schedule) is derived using a result of Karp et al. (1987). On the other hand,
if the number of machines is constant, we formulate a dynamic program.
Enrico Bini: Optimal assignment of periods and deadlines to EDFscheduled tasks
In many application domains (such as in control systems), periods and
deadlines are not known parameters. They are rather variables that
need to be optimally assigned by the designer or (better) by a solver.
For this purpose, suitable representations of the feasibility
condition is needed. In the talk, the problem and some preliminary
results are presented.
Nikhil Bansal: The Geometry of Scheduling
We consider the following general scheduling problem: There are~$n$ jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives in both traditional scheduling setting and real time scheduling.
Our main result is a randomized polynomialtime algorithm with an
approximation ratio O(log log P), which substantially improves the
previous results even for very special cases. The key insight is to
relate this problem to certain natural geometric problems in 2d and
3d, and use recent techniques developed for geometric set cover
problems with low union complexity.
Thomas Nolte: Predictability and resource reservation
Resource reservation techniques provide a way to guarantee a supply of
resources from the resource to the user. Over the years several approaches
have been developed, stretching from purely theoretical models (e.g., linear
approximation) to models more reflecting the implementation (e.g., periodic
resource model) and real implementations (e.g., hierarchical scheduling).
However, these resource reservation techniques typically only cater for a
particular kind of resource, such as the CPU, on a particular kind of
computer architecture, e.g., a single CPU. We would like to take a broader
scope of resource reservation. Multiple resources could be taken into
consideration together to deal with effects such as a memory access affecting
the time needed to execute a particular piece of software. Allocation of
where and when a particular piece of software is executing will impact
performance, hence also impact the price to be paid for achieving
predictability. In order for resource reservation techniques to be practical,
more care needs to be taken into the way, e.g., hardware is catered for. Here
we believe in a combination of traditional resource reservation techniques
used together with more advanced modeling and analysis techniques including
statistics and probabilities.
Rene Sitters: Efficient algorithms for average completion time scheduling
We analyze the competitive ratio of online algorithms for minimizing
(weighted) average completion time on identical parallel machines and
prove that the wellknown shortest remaining processing time algorithm
(SRPT) is $5/4$competitive w.r.t. the average completion time
objective. The SRPT algorithm has a natural generalization to the case
where jobs have given weights. Unfortunately, our proof does not carry
over to this case. For weighted completion times, no algorithm is known
to have a competitive ratio less than 2. Remarkably, even for the
offline problem, the only ratio less than 2 results from the
approximation scheme given by Afrati et al. We give a deterministic
online algorithm with competitive ratio $1.791+o(m)$. This ratio holds
for preemptive and nonpreemptive scheduling. The two algorithms show
that approximation ratios less than 2 can be obtained for parallel
machines by simple and efficient online algorithms. The known lower
bounds indicate that competitive ratios close to 1 are possible for
randomized algorithms, especially when preemption is allowed.
Andreas Wiese: The periodic maintenance problem
The periodic maintenance problem is a realtime scheduling problem
which arises in the avionics industry. A set of tasks has to be
distributed on a minimum number of machines and offsets of the tasks
have to be computed. The tasks emit jobs strictly periodically
starting at their offset and then need to be executed on the machines
without any delay. We present a thorough theoretical characterization
of this problem in terms of approximation algorithms and complexity
results. One important special case that we study is the case of
harmonic period lengths, which very often arises in realworld
instances. Then we present computational results for different
IPformulations of the problem. In particular, we present a
formulation especially tailored to the harmonic case which clearly
outperforms standard textbook approaches to model the problem.
Nicole Megow: Scheduling to meet deadlines: online algorithms and feasibility tests In this talk I will present recent results and open questions in the context of scheduling realtime jobs with hard deadlines on m identical parallel machines. Each job has a processing time and a deadline, and the objective is to schedule jobs so that they complete before their deadline. It is known that even when the instance is feasible it may not be possible to meet all deadlines when jobs arrive online over time. Therefore, we consider settings in which the online algorithm has additional resources, such as higher speed or more machines, than the optimal offline algorithm that knows all jobs in advance. We give a new online algorithm improving on previous speedup results. And we show how our new insights relate to demand bound functions for periodic task systems and lead to improved feasibility tests.