368
6 Abbildung von Anwendungen
Beispiel 6.17: Wir nehmen an, dass die Ausführungszeiten durch die Tabelle in Abb.
6.31 (links) gegeben sind. Für jede Task wurden die Ausführungszeiten in Abb. 6.26
(rechts) als Minimum über die drei Prozessoren gewählt.
Task π 1 π 2 π 3
1
14 16 9
2
13 19 18
3
11 13 19
4
13 8 17
5
12 13 10
6
13 16 9
7
7 15 11
8
5 11 14
9
18 12 20
10 21 7 16
π
π
π 1
2
3
9
8
2
4
6
7
5
3
1
0
10
90
80
70
60
50
40
30
20
10
1
2
3
π
π
π
10
1
3
5
7
6
4
2
8
9
10
20
30
40
50
60
70
80
90
0
Abb. 6.31 Links: Ausführungszeiten; Mitte: Ergebnisse für HEFT; rechts: Ergebnisse für CPOP
Abb. 6.31 (Mitte) zeigt das Schedule, welches HEFT für den DAG in Abb. 6.26
(links) erzeugt. Es ist kein kurzes Schedule wie beim ASAP/ALAP-Scheduling, da
wir jetzt Reihenfolge- und Ressourcenbeschränkungen beachten.
∇
Der CPOP-Algorithmus konzentriert sich auf den kritischen Pfad im DAG und er
benutzt verschiedene Task-Prioritäten und verschiedene Strategien für die Zuordnung
von Prozessoren. Der CPOP-Algorithmus arbeitet wie folgt:
Setze die Berechnungs- und die Kommunikationskosten auf ihre Mitteewerte;;
Berechne ∀i : r ank u (τ i ) und r ank d (τ i );
Berechne ∀i : priority(τ i ) = r ank d (τ i ) + r ank u (τ i );
|C P | = priority(τ e nt r y ); /* Länge des kritischen Pfades */
SET C P = {τ e nt r y }, mit SET C P : Menge der Tasks auf dem kritischen Pfad;
τ i = τ e nt r y ;
whiie τ i ist nicht der exit-Task {
Wähhe τ j ∈ succ(τ i ), mit priority(τ j ) == |C P |.
SET C P = SET C P ∪ {τ j };
τ i = τ j
};
Wähhe Prozessor π C P , der Ausführungszeit auf kritischem Pfad minimiert;
Initiaaisiere eine Warteschhange mit der entry-Task;
whiie es gibt eine ungeppante Task in der Warteschhange {
Wähhe die Task der höchsten Priorität τ i aus der Warteschhange;
if τ i ∈ SET C P {weise τ i Prozessor π C P zu}
eese {weise Task τ i dem Prozessor zu, der f e (τ i , π k ) minimiert};
Aktuaaisiere Warteschhange mit Nachfoogern von τ i wenn sie bereit werden;
}
Beispiel 6.18: Abb. 6.31 (rechts) zeigt das mit CPOP erzeugte Schedule .
∇