6.5 Abhängige Jobs auf heterogenen Multiprozessoren
371
Insgesamt werden Implementierungen durch ein Tripel beschrieben:
• Eine Allokation A: A ist eine Teilmenge des Architekturgraphen, die für einen
bestimmten Entwurf reservierte (ausgewählte) Hardwarekomponenten darstellt.
• Eine Bindung b: eine ausgewählte Teilmenge der Kanten zwischen Spezifikation und Architektur kennzeichnet eine Relation zwischen diesen beiden. Die
ausgewählten Kannten werden als Bindung bezeichnet.
• Einen Zeitplan (Schedule) S: S weist jedem Knoten τ i im Problemgraphen seine
Startzeit zu.
Bus1
S
0
1
21
29
1
21
30
A
b
4
6
2
7
3
5
1
RISC
HWM1
HWM1
HWM2
RISC
Abb. 6.35 DOL Implementierung
Beispiel 6.19: Abb. 6.35 zeigt, wie
die Spezifikation aus Abb. 6.34 in
eine Implementierung umgesetzt werden kann. HWM2 und der Bus2 werden nicht benutzt und sind nicht in
der Menge A enthalten. Eine Teilmenge b der Kanten wurde für die
Abbildung ausgewählt. Die Knoten
1, 2, 3, 5 wurden alle auf den RISCProzessor abgebildet, wodurch die
Kommunikation 5 eine rein lokale
Kommunikation wird. Knoten 4 ist
auf HWM1 abgebildet und er kommuniziert über den Bus Bus1. Der Ablaufplan S besagt, dass Berechnung 1 zur Zeit
0 startet, Kommunikation 5 und Berechnung 2 beginnen zur Zeit 1, Berechnung 3
und Kommunikation 6 fangen zur Zeit 21 an, Kommunikation 7 beginnt zur Zeit 29
und Berechnung 4 startet zum Zeitpunkt 30.
∇
DOL erzeugt Implementierungen mit Hilfe evolutionärer Algorithmen [31, 30,
107]. In solchen Algorithmen werden Lösungen durch Folgen von Werten in den
Chromosomen von „Individuen” dargestellt. Mit evolutionären Algorithmen lassen
sich neue Lösungsmengen aus existierenden Mengen von Lösungen ableiten. Die
Ableitung basiert dabei auf evolutionären Operatoren wie Mutation, Selektion und
Rekombination. Die Auswahl neuer Lösungsmengen erfolgt auf der Grundlage von
Eignungswerten (engl. fitness values). Evolutionäre Algorithmen können komplexe
Optimierungsprobleme lösen, bei denen andere Arten von Algorithmen versagen.
Es ist nicht leicht, geeignete Kodierungen von Lösungen in Chromosomen zu finden.
Einerseits sollte die Dekodierung nicht zu viel Rechenzeit benötigen, andererseits
müssen wir die Situation nach den evolutionären Transformationen berücksichtigen.
Diese Transformationen könnten nicht realisierbare Lösungen erzeugen, wenn die
Kodierungen nicht sorgfältig gewählt werden.
In DOL kodieren die Chromosomen die Auswahl (Allokation) von Hardware und
die Bindungen. Zur Berechnung der Fitness einer Lösung müssen Allokationen und
Bindungen aus den Individuen dekodiert werden (siehe Abb. 6.36).
371
Insgesamt werden Implementierungen durch ein Tripel beschrieben:
• Eine Allokation A: A ist eine Teilmenge des Architekturgraphen, die für einen
bestimmten Entwurf reservierte (ausgewählte) Hardwarekomponenten darstellt.
• Eine Bindung b: eine ausgewählte Teilmenge der Kanten zwischen Spezifikation und Architektur kennzeichnet eine Relation zwischen diesen beiden. Die
ausgewählten Kannten werden als Bindung bezeichnet.
• Einen Zeitplan (Schedule) S: S weist jedem Knoten τ i im Problemgraphen seine
Startzeit zu.
Bus1
S
0
1
21
29
1
21
30
A
b
4
6
2
7
3
5
1
RISC
HWM1
HWM1
HWM2
RISC
Abb. 6.35 DOL Implementierung
Beispiel 6.19: Abb. 6.35 zeigt, wie
die Spezifikation aus Abb. 6.34 in
eine Implementierung umgesetzt werden kann. HWM2 und der Bus2 werden nicht benutzt und sind nicht in
der Menge A enthalten. Eine Teilmenge b der Kanten wurde für die
Abbildung ausgewählt. Die Knoten
1, 2, 3, 5 wurden alle auf den RISCProzessor abgebildet, wodurch die
Kommunikation 5 eine rein lokale
Kommunikation wird. Knoten 4 ist
auf HWM1 abgebildet und er kommuniziert über den Bus Bus1. Der Ablaufplan S besagt, dass Berechnung 1 zur Zeit
0 startet, Kommunikation 5 und Berechnung 2 beginnen zur Zeit 1, Berechnung 3
und Kommunikation 6 fangen zur Zeit 21 an, Kommunikation 7 beginnt zur Zeit 29
und Berechnung 4 startet zum Zeitpunkt 30.
∇
DOL erzeugt Implementierungen mit Hilfe evolutionärer Algorithmen [31, 30,
107]. In solchen Algorithmen werden Lösungen durch Folgen von Werten in den
Chromosomen von „Individuen” dargestellt. Mit evolutionären Algorithmen lassen
sich neue Lösungsmengen aus existierenden Mengen von Lösungen ableiten. Die
Ableitung basiert dabei auf evolutionären Operatoren wie Mutation, Selektion und
Rekombination. Die Auswahl neuer Lösungsmengen erfolgt auf der Grundlage von
Eignungswerten (engl. fitness values). Evolutionäre Algorithmen können komplexe
Optimierungsprobleme lösen, bei denen andere Arten von Algorithmen versagen.
Es ist nicht leicht, geeignete Kodierungen von Lösungen in Chromosomen zu finden.
Einerseits sollte die Dekodierung nicht zu viel Rechenzeit benötigen, andererseits
müssen wir die Situation nach den evolutionären Transformationen berücksichtigen.
Diese Transformationen könnten nicht realisierbare Lösungen erzeugen, wenn die
Kodierungen nicht sorgfältig gewählt werden.
In DOL kodieren die Chromosomen die Auswahl (Allokation) von Hardware und
die Bindungen. Zur Berechnung der Fitness einer Lösung müssen Allokationen und
Bindungen aus den Individuen dekodiert werden (siehe Abb. 6.36).