6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen
361
16
27
3
14
20
12
22
29
22
27
29
34
34
9
8
7
10
9
41
6
5
2
1
4
0
9
22
22
34
34
t
6
2
7
9
10
1
40
30
20
10
0
3
5
Abb. 6.28 Links: Mit ALAP-Scheduling eingeplanter Task-Graph; rechts: Zeitachse
∇
Auch ALAP-Scheduling kann im täglichen Leben eingesetzt werden. Es entspricht
einer Situation, in der alle Aufgaben so lange wie möglich aufgeschoben werden.
Beim ALAP-Schedule werden viele Prozessoren benötigt, wenn der Task-Graph
an seinem unteren Ende breit ist. Dementsprechend fällt bei diesem Vorgehen im
täglichen Leben zum Schluss viel Arbeit an.
6.4.3 List-Scheduling
Beim List-Scheduling (LS) versuchen wir, die geringe Komplexität von ASAP- und
ASAP-Scheduling beizubehalten, aber auf die Anzahl verfügbarer Prozessoren Rücksicht zu nehmen. Die Prozessoren können verschiedenen Typs sein, aber wir nehmen
immer noch an, dass es eine Eins-zu-eins-Beziehung zwischen Tasks und Prozessortypen gibt. Somit können die Prozessoren heterogen sein, aber die kritische
Abbildung von Tasks auf Prozessortypen wird nicht durch LS erzeugt.
Wir nehmen an, dass wir eine Menge L von Prozessortypen haben. LS respektiert
obere Schranken B l für die Anzahl von Prozessoren für jeden Typ l ∈ L.
LS setzt voraus, dass eine Prioritätsfunktion definiert ist, welche die Dringlichkeit
angibt, mit der eine bestimmte Task τ i eingeplant werden muss. Die folgenden
Dringlichkeitsmetriken finden dabei Anwendung [528]:
• Die Beweglichkeit (engl. mobility) ist die Differenz zwischen den Startzeiten für
die ASAP- und ALAP-Schedules. Abb. 6.29 (links) zeigt die Mobilität für unser
Beispiel in rot. Offenbar ist das Scheduling dringend für alle Tasks auf dem
kritischen Pfad, denn deren Mobilität ist 0.
• Die Anzahl an Nachfolgern ist die Anzahl von Knoten im Baum unterhalb des
aktuellen Knotens τ (siehe Abb. 6.29 (rechts)).
• Die Pfadlänge für einen Knoten τ i ist definiert als die Länge des Pfades vom
Startknoten τ i bis zum Endknoten des Graphen G. Die Pfadlänge ist typischer-
361
16
27
3
14
20
12
22
29
22
27
29
34
34
9
8
7
10
9
41
6
5
2
1
4
0
9
22
22
34
34
t
6
2
7
9
10
1
40
30
20
10
0
3
5
Abb. 6.28 Links: Mit ALAP-Scheduling eingeplanter Task-Graph; rechts: Zeitachse
∇
Auch ALAP-Scheduling kann im täglichen Leben eingesetzt werden. Es entspricht
einer Situation, in der alle Aufgaben so lange wie möglich aufgeschoben werden.
Beim ALAP-Schedule werden viele Prozessoren benötigt, wenn der Task-Graph
an seinem unteren Ende breit ist. Dementsprechend fällt bei diesem Vorgehen im
täglichen Leben zum Schluss viel Arbeit an.
6.4.3 List-Scheduling
Beim List-Scheduling (LS) versuchen wir, die geringe Komplexität von ASAP- und
ASAP-Scheduling beizubehalten, aber auf die Anzahl verfügbarer Prozessoren Rücksicht zu nehmen. Die Prozessoren können verschiedenen Typs sein, aber wir nehmen
immer noch an, dass es eine Eins-zu-eins-Beziehung zwischen Tasks und Prozessortypen gibt. Somit können die Prozessoren heterogen sein, aber die kritische
Abbildung von Tasks auf Prozessortypen wird nicht durch LS erzeugt.
Wir nehmen an, dass wir eine Menge L von Prozessortypen haben. LS respektiert
obere Schranken B l für die Anzahl von Prozessoren für jeden Typ l ∈ L.
LS setzt voraus, dass eine Prioritätsfunktion definiert ist, welche die Dringlichkeit
angibt, mit der eine bestimmte Task τ i eingeplant werden muss. Die folgenden
Dringlichkeitsmetriken finden dabei Anwendung [528]:
• Die Beweglichkeit (engl. mobility) ist die Differenz zwischen den Startzeiten für
die ASAP- und ALAP-Schedules. Abb. 6.29 (links) zeigt die Mobilität für unser
Beispiel in rot. Offenbar ist das Scheduling dringend für alle Tasks auf dem
kritischen Pfad, denn deren Mobilität ist 0.
• Die Anzahl an Nachfolgern ist die Anzahl von Knoten im Baum unterhalb des
aktuellen Knotens τ (siehe Abb. 6.29 (rechts)).
• Die Pfadlänge für einen Knoten τ i ist definiert als die Länge des Pfades vom
Startknoten τ i bis zum Endknoten des Graphen G. Die Pfadlänge ist typischer-