364
6 Abbildung von Anwendungen
Wir nehmen an, dass unser Task-Graph G = (τ, E) einen gemeinsamen Ausgangsknoten τ exit besitzt. Wir fügen einen solchen Knoten künstlich hinzu, wenn
es ihn zunächst nicht geben sollte. Die Fertigstellungszeit dieses Knotens entspricht
dem Makespan MS max . Wir können diese Zeit als unsere zu minimierende Kostenfunktion verwenden. Daher können wir das Zielkriterium wie folgt ausdrücken:
Min( f τ e x i t )
(6.36)
Nun sehen wir uns die Randbedingungen an. Erstens müssen wir verlangen, dass
jede Task auf einem Prozessor ausgeführt wird:
∀τ i ∈ τ :
k ∈ {1..m}
x i,k = 1
(6.37)
Zweitens sind die verschiedenen Zeiten über die folgenden Gleichungen miteinander
verbunden:
∀τ i ∈ τ : f i = s i + C i
(6.38)
Drittens können die folgenden Gleichungen benutzt werden, um die Reihenfolgebedingungen einzuhalten:
∀(τ i , τ j ) ∈ E : s j − f i ≥ 0
(6.39)
Viertens müssen wir bei einem Einzelprozessor den Code in einer Reihenfolge
ausführen, der durch die Variable b i, j bestimmt wird:
∀(τ i , τ j ) : f i ≤ s j falls b i, j = 1
(6.40)
Fünftens müssen wir berücksichtigen, dass ein Prozessor zu einer bestimmten Zeit
nur eine Task ausführen kann. Dies kann auf die folgende Weise ausgedrückt werden:
∀(τ i , τ j ) : b i, j + b j,i = 1 falls ∃ π k : x i,k = x j,k = 1
(6.41)
Die Gleichungen (6.40) und (6.41) können auf die lineare Form gebracht werden,
die für ein ILP-Modell erforderlich ist [112].
Das entstehende ILP-Modell kann einem ILP-Lösungsverfahren übergeben werden. ILP-Modelle, wie das vorgestellte, haben den Vorteil einer präzisen Modellierung des Entwurfsproblems und der Zielfunktion. Sie erlauben globale Optimierungen mittels mathematischer Methoden und gehen damit über die imperative
Programmierung hinaus.
Das ILP-Problem ist NP-hart. Daher können die Laufzeiten von ILP-Lösungsverfahren groß werden. Allerdings hat es in den letzten Jahren große Fortschritte
beim der Konzeption von ILP-Lösungsverfahren gegeben. Daher können moderat
große Probleme in akzeptabler Zeit gelöst werden. Aufgrund ihrer Komplexität
können sie aber nicht für wirklich große Probleme benutzt werden, weil für diese die
6 Abbildung von Anwendungen
Wir nehmen an, dass unser Task-Graph G = (τ, E) einen gemeinsamen Ausgangsknoten τ exit besitzt. Wir fügen einen solchen Knoten künstlich hinzu, wenn
es ihn zunächst nicht geben sollte. Die Fertigstellungszeit dieses Knotens entspricht
dem Makespan MS max . Wir können diese Zeit als unsere zu minimierende Kostenfunktion verwenden. Daher können wir das Zielkriterium wie folgt ausdrücken:
Min( f τ e x i t )
(6.36)
Nun sehen wir uns die Randbedingungen an. Erstens müssen wir verlangen, dass
jede Task auf einem Prozessor ausgeführt wird:
∀τ i ∈ τ :
k ∈ {1..m}
x i,k = 1
(6.37)
Zweitens sind die verschiedenen Zeiten über die folgenden Gleichungen miteinander
verbunden:
∀τ i ∈ τ : f i = s i + C i
(6.38)
Drittens können die folgenden Gleichungen benutzt werden, um die Reihenfolgebedingungen einzuhalten:
∀(τ i , τ j ) ∈ E : s j − f i ≥ 0
(6.39)
Viertens müssen wir bei einem Einzelprozessor den Code in einer Reihenfolge
ausführen, der durch die Variable b i, j bestimmt wird:
∀(τ i , τ j ) : f i ≤ s j falls b i, j = 1
(6.40)
Fünftens müssen wir berücksichtigen, dass ein Prozessor zu einer bestimmten Zeit
nur eine Task ausführen kann. Dies kann auf die folgende Weise ausgedrückt werden:
∀(τ i , τ j ) : b i, j + b j,i = 1 falls ∃ π k : x i,k = x j,k = 1
(6.41)
Die Gleichungen (6.40) und (6.41) können auf die lineare Form gebracht werden,
die für ein ILP-Modell erforderlich ist [112].
Das entstehende ILP-Modell kann einem ILP-Lösungsverfahren übergeben werden. ILP-Modelle, wie das vorgestellte, haben den Vorteil einer präzisen Modellierung des Entwurfsproblems und der Zielfunktion. Sie erlauben globale Optimierungen mittels mathematischer Methoden und gehen damit über die imperative
Programmierung hinaus.
Das ILP-Problem ist NP-hart. Daher können die Laufzeiten von ILP-Lösungsverfahren groß werden. Allerdings hat es in den letzten Jahren große Fortschritte
beim der Konzeption von ILP-Lösungsverfahren gegeben. Daher können moderat
große Probleme in akzeptabler Zeit gelöst werden. Aufgrund ihrer Komplexität
können sie aber nicht für wirklich große Probleme benutzt werden, weil für diese die