6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen
363
8
8
4
4
25
32
14
7
12
19
27
29
21
41
2
5
3
0
10
20
30
40
1
10
9
7
2
6
t
1
5
6
9
10
7
3
Abb. 6.30 Links: Task-Graph mit Pfadlängen; rechts: Zeitachse
∇
LS wählt ebenso wie ASAP- und ALAP-Scheduling für die Tasks keine Prozessoren aus, aber aufgrund des eingeschränkten Ressourcenmodells muss das auch
nicht sein. Eine Erweiterung von LS auf reelle Zahlen als Ausführungszeiten ist
möglich. Üblicherweise erzeugt der Algorithmus gute Ergebnisse und er kann an
verschiedene Szenarien leicht angepasst werden. Deshalb ist LS ein beliebter Scheduling-Algorithmus für Tasks mit Reihenfolgebeschränkungen.
Force-directed scheduling (FDS) ist eine weitere beliebte Heuristik für abhängige
Tasks. FDS zielt auf eine möglichst effiziente Nutzung der Prozessoren, indem es
versucht, die Nutzung der Prozessoren über der Zeit möglichst gut auszubalancieren.
Details finden sich bei Paulin et al. [449].
6.4.4 Optimales Scheduling mit Ganzzahliger Programmierung
Als nächstes beschreiben wir einen Ansatz, um Tasks auf verschiedenen Prozessoren
zu verteilen, wobei die Entscheidungen auf einer mehr globalen Basis getroffen
werden. Der Ansatz basiert auf der Ganzzahligen Linearen Programmierung (engl.
Integer Linear Programming (ILP)) (siehe Anhang A). Auf diese Weise werden
Randbedingungen und Zielkriterien explizit dargestellt. Wir benutzen dabei Material
aus einer Publikation von Coscun et al. [112].
ILP-Modelle bestehen aus einer linearen Kostenfunktion und einer Menge an
linearen Randbedingungen. Im Modell werden wir die folgenden Variablen benutzen:
x i,k : = 1 wenn Task τ i auf Prozessor π k ausgeführt wird und =0 sonst
s i : Startzeit von Task τ i
f i : Fertigstellungszeit von Task τ i
C i : Ausführungsdauer von Task τ i
b i, j : = 1 wenn Task τ i vor τ j auf demselben Prozessor ausgeführt wird, sonst =0
363
8
8
4
4
25
32
14
7
12
19
27
29
21
41
2
5
3
0
10
20
30
40
1
10
9
7
2
6
t
1
5
6
9
10
7
3
Abb. 6.30 Links: Task-Graph mit Pfadlängen; rechts: Zeitachse
∇
LS wählt ebenso wie ASAP- und ALAP-Scheduling für die Tasks keine Prozessoren aus, aber aufgrund des eingeschränkten Ressourcenmodells muss das auch
nicht sein. Eine Erweiterung von LS auf reelle Zahlen als Ausführungszeiten ist
möglich. Üblicherweise erzeugt der Algorithmus gute Ergebnisse und er kann an
verschiedene Szenarien leicht angepasst werden. Deshalb ist LS ein beliebter Scheduling-Algorithmus für Tasks mit Reihenfolgebeschränkungen.
Force-directed scheduling (FDS) ist eine weitere beliebte Heuristik für abhängige
Tasks. FDS zielt auf eine möglichst effiziente Nutzung der Prozessoren, indem es
versucht, die Nutzung der Prozessoren über der Zeit möglichst gut auszubalancieren.
Details finden sich bei Paulin et al. [449].
6.4.4 Optimales Scheduling mit Ganzzahliger Programmierung
Als nächstes beschreiben wir einen Ansatz, um Tasks auf verschiedenen Prozessoren
zu verteilen, wobei die Entscheidungen auf einer mehr globalen Basis getroffen
werden. Der Ansatz basiert auf der Ganzzahligen Linearen Programmierung (engl.
Integer Linear Programming (ILP)) (siehe Anhang A). Auf diese Weise werden
Randbedingungen und Zielkriterien explizit dargestellt. Wir benutzen dabei Material
aus einer Publikation von Coscun et al. [112].
ILP-Modelle bestehen aus einer linearen Kostenfunktion und einer Menge an
linearen Randbedingungen. Im Modell werden wir die folgenden Variablen benutzen:
x i,k : = 1 wenn Task τ i auf Prozessor π k ausgeführt wird und =0 sonst
s i : Startzeit von Task τ i
f i : Fertigstellungszeit von Task τ i
C i : Ausführungsdauer von Task τ i
b i, j : = 1 wenn Task τ i vor τ j auf demselben Prozessor ausgeführt wird, sonst =0