366
6 Abbildung von Anwendungen
einen Knoten mit einer Ausführungszeit von 0 und ohne Kommunikationsanforderungen künstlich hinzu.
• Die Matrix C = (c i,k ) bezeichnet die Ausführungszeit von Task τ i auf Prozessor
π k .
• Die Matrix B = (b k,l ) bezeichnet die Kommunikationsbandbreite für die Kommunikation vom Prozessor π k zum Prozessor π l .
• Die Matrix data = (data i, j ) kennzeichnet das Datenvolumen, das von Task τ i
nach Task τ j übertragen werden muss.
• Der Vektor κ = (κ k ) enthält die Initialisierungskosten für Kommunikation auf
dem Prozessor π k .
• Die Matrix H = (h i, j,k,l ) repräsentiert die Kommunikationskosten für die Kommunikation von der Task τ i zur Task τ j unter der Annahme, dass die Task τ i
auf den Prozessor π k abgebildet wird und dass die Task τ j auf den Prozessor π l
abgebildet wird8.
In unserer Notation werden wir generell den Index i für den Ausgangsknoten bei
Präzedenzrelationen bzw. Datenabhängigkeiten verwenden und den Index k für
den Prozessor, auf den dieser abgebildet wird.
In ähnlicher Weise steht j für das Ziel bei Präzedenzrelationen und l für den
dazugehörigen Prozessor.
• Für eine Abbildung auf Prozessoren π k und π l stellt h i, j,k,l die Kommunikationskosten von Task τ i zu Task τ j dar:
h i, j,k,l = κ k +
data i, j
b k,l
falls k l
(6.42)
= 0 falls k = l
(6.43)
• Die durchschnittlichen Kommunikationskosten sind definiert als
h i, j = κ +
data i, j
B
(6.44)
Dabei ist κ die durchschnittliche Zeit für das Starten der Kommunikation und B
ist die durchschnittliche Kommunikationsbandbreite.
• Die früheste Startzeit für Task τ i auf Prozessor π k für ein partielles Schedule ist
s e (τ i , π k ) mit ∀k : s e (τ entr y , π k ) = 0
(6.45)
• Die früheste Fertigstellungszeit für Task τ i auf Prozessor π k für ein gegebenes
partielles Schedule heißt
f e (τ i , π k ) mit f e (τ entr y , π k ) = c entr y,k
(6.46)
• Auf der Basis der Entscheidung, Task τ i auf Prozessor π k abzubilden, können die
tatsächliche Startzeit s(τ i , π k ) und die tatsächliche Fertigstellungszeit f (τ i , π k )
berechnet werden.
8 Die Indices k und l sind in der ursprünglichen Veröffentlichung nicht explizit vorhanden.
6 Abbildung von Anwendungen
einen Knoten mit einer Ausführungszeit von 0 und ohne Kommunikationsanforderungen künstlich hinzu.
• Die Matrix C = (c i,k ) bezeichnet die Ausführungszeit von Task τ i auf Prozessor
π k .
• Die Matrix B = (b k,l ) bezeichnet die Kommunikationsbandbreite für die Kommunikation vom Prozessor π k zum Prozessor π l .
• Die Matrix data = (data i, j ) kennzeichnet das Datenvolumen, das von Task τ i
nach Task τ j übertragen werden muss.
• Der Vektor κ = (κ k ) enthält die Initialisierungskosten für Kommunikation auf
dem Prozessor π k .
• Die Matrix H = (h i, j,k,l ) repräsentiert die Kommunikationskosten für die Kommunikation von der Task τ i zur Task τ j unter der Annahme, dass die Task τ i
auf den Prozessor π k abgebildet wird und dass die Task τ j auf den Prozessor π l
abgebildet wird8.
In unserer Notation werden wir generell den Index i für den Ausgangsknoten bei
Präzedenzrelationen bzw. Datenabhängigkeiten verwenden und den Index k für
den Prozessor, auf den dieser abgebildet wird.
In ähnlicher Weise steht j für das Ziel bei Präzedenzrelationen und l für den
dazugehörigen Prozessor.
• Für eine Abbildung auf Prozessoren π k und π l stellt h i, j,k,l die Kommunikationskosten von Task τ i zu Task τ j dar:
h i, j,k,l = κ k +
data i, j
b k,l
falls k l
(6.42)
= 0 falls k = l
(6.43)
• Die durchschnittlichen Kommunikationskosten sind definiert als
h i, j = κ +
data i, j
B
(6.44)
Dabei ist κ die durchschnittliche Zeit für das Starten der Kommunikation und B
ist die durchschnittliche Kommunikationsbandbreite.
• Die früheste Startzeit für Task τ i auf Prozessor π k für ein partielles Schedule ist
s e (τ i , π k ) mit ∀k : s e (τ entr y , π k ) = 0
(6.45)
• Die früheste Fertigstellungszeit für Task τ i auf Prozessor π k für ein gegebenes
partielles Schedule heißt
f e (τ i , π k ) mit f e (τ entr y , π k ) = c entr y,k
(6.46)
• Auf der Basis der Entscheidung, Task τ i auf Prozessor π k abzubilden, können die
tatsächliche Startzeit s(τ i , π k ) und die tatsächliche Fertigstellungszeit f (τ i , π k )
berechnet werden.
8 Die Indices k und l sind in der ursprünglichen Veröffentlichung nicht explizit vorhanden.