Master
level course module on multiprocessor scheduling
Professor
Lars Lundberg
Blekinge Institute of Technology, Ronneby, Sweden
Course Overview
The course module consists of two major parts:
- Multiprocessor
scheduling for high performance supercomputing, 4 hours
- Multiprocessor
scheduling for real-time systems with guaranteed worst-case performance, 4
hours
The students are expected to prepare
themselves by reading some material (to be defined later). Reading this material
will take another 8 hours, i.e. for the student this course module requires 16 hours work.
Part 1:
Multiprocessor scheduling for high performance supercomputing
In this case there is one parallel program, consisting of a number of
communicating processes. The parallel program is executed on a multiprocessor
computer. The important performance criterion in this case is the completion of
the entire program. Typical examples of such applications include global weather
simulation, solving large systems of equations and image rendering in animated
films. The way the processes in such a program are scheduled to the processors
in a multiprocessor affects the completion time. Ideally we would like to find a
schedule that minimizes the completion time of the parallel program, but this
problem is unfortunately NP-hard so we need to resort to different heuristic
approaches. It is often difficult to know how close to the optimal case these
heuristic approaches actually are.
In this part of the course module we explain the supercomputing multiprocessor
scheduling problem and explain the difference between static scheduling, where a
process is always executed by the same processor, and dynamic scheduling, where
processes may migrate from one processor to another at run-time. We will also
discuss various heuristic approaches, and finally we will introduce some
theoretical performance bounds can make it possible to determine how close to
the optimal result a certain heuristic schedule is.
Part 2: Multiprocessor scheduling for real-time systems
In this case there is a set of independent tasks that are scheduled on a
multiprocessor. The important performance criterion here is the response time of
each task, and in most cases the most important issue is to guarantee that the
response time of a task will even during the worst-case conditions be within
certain specified limited, i.e. we want to guarantee the worst-case behavior. We
consider two kinds of multiprocessor systems: systems with static scheduling,
i.e. systems where a task is always executed by the same processor, and systems
with dynamic scheduling, i.e. systems where a task may be executed by different
processors at different points in time. We also consider two kinds of task sets:
periodic task sets where each task is repeated with a certain frequency (e.g.
sampling tasks), and sporadic task sets where each task is only executed once.
It turns out that it is NP-hard to find optimal schedules for most interesting
cases.
In this part of the course module we explain the real-time multiprocessor
scheduling problem and explain the difference between static and dynamic
scheduling and the difference between periodic and sporadic tasks. We will also
discuss various heuristic scheduling techniques and some theoretical bounds on
the worst-case performance of these techniques
Time & Location
Slides
Articles
Leistungserfassung
-
Der Kurs besteht aus drei Komponenten, und zwar:
- einer Blockvorlesung in der Woche (19.2 - 23.2)
- Literaturstudium zu ausgewählten Themen aus der Vorlesung (16h)
- einem Vortrag der Teilnehmer in einem zu den studierten Materialien (6h)
-
In den Leistungserfassungsprozess gehen neben dem Vortrag
die zugehörige Ausarbeitung ein.
-
Die Vorträge, deren Themen im Laufe der Vorlesung vergeben
werden, sollen im Laufe des SS2006
als Blockseminar (voraussichtlich Mitte Mai) stattfinden.
-
Für die Lehrveranstaltung gibt es insgesamt 3 benotete
Leistungspunkte.
-
Die Belegungsfrist endet am 26.4.2007
- Bitte sucht Euch ein/zwei Paper aus und meldet Euch bei Andreas
Rasche an. Der Termin für das Blockseminar wird noch bekannt
gegeben.
Vorträge
- Die Vortäge werden am Dienstag, den 12.6. um 13.00-15.00 Uhr
in der Kommunikationszone Haus C 1. Etage gehalten. Die Länge des
Vortrags sollte 45 min. nicht überschreiten.
Johannes Nicolai |
"Integrating list heuristics into genetic algorithms for multiprocessor scheduling"
"An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling" |
Steffen Ryll |
"Analyzing Fixed-Priority Global Multiprozessor Scheduling"
"Fixed-Priority Preemptive Multiprocessor Scheduling: To Partition or not to Partition" |