6.5 Abhängige Jobs auf heterogenen Multiprozessoren
369
HEFT und CPOP sind relativ schnelle und einfache Algorithmen. Diese Algorithmen nutzen verschiedene Näherungen (wie z.B. durchschnittliche Kommunikationskosten) und Heuristiken. HEFT und CPOP wurden für dieses Buch ausgewählt,
um Schwierigkeiten mit Scheduling-Algorithmen für heterogene Prozessoren zu demonstrieren. Allerdings ist es möglich, im Vergleich zu diesen beiden Algorithmen
bessere Ergebnisse zu erzielen. Beispielsweise haben Kim et al. [295] komplexere
Algorithmen beschrieben, die bessere Ergebisse liefern. Castrillon et al. [86] haben
ein Scheduling für KPNs entwickelt, welches ebenfalls den Makespan minimieren
soll.
6.5.3 Statisches Scheduling mit Ganzzahliger Programmierung
Die Ganzzahlige Lineare Programmierung kann auch auf heterogene Prozessoren
angewandt werden. Ein Ansatz hierzu wurde von Maculan et al. [362] publiziert.
Sehr wichtig ist, dass dabei prozessorabhängige Ausführungszeiten betrachtet werden. Allerdings bedürfen die gezeigten Gleichungen noch einiger Überarbeitungen,
bevor sie vollständig die Form eines Ganzzahligen Optimierungsproblems haben.
Weiterhin ist es auch möglich, Techniken der High-Level-Synthese [43, 315] zu
adaptieren.
In vielen der Publikationen werden Optimierungen für eine einzelne Metrik (ein
Zielkriterium) betrachtet. Im allgemeinen sollten mehrere Zielkriterien betrachtet
werden. Beispielsweise beschreiben Fard et al. [162] einen Algorithmus, der mehrere
Zielkriterien betrachtet.
6.5.4 Statisches Scheduling mit Evolutionären Algorithmen
Verfahren auf der Basis der Ganzzahligen Programmierung leiden unter potentiell
großen Rechenzeiten. In vielen Fällen erlauben evolutionäre Algorithmen bei akzeptablen Rechenzeiten eine bessere Optimierung. Wir werden dies am Beispiel der
Distributed Operation Layer (DOL)-Werkzeuge von der ETH Zürich zeigen [537].
Diese Werkzeuge beinhalten folgende Funktionen:
• Automatische Selektion von Prozessorarchitekturen: die Prozessortypen können vollständig heterogen sein. Mögliche Optionen sind Standard-Prozessoren,
Mikrocontroller, DSP-Prozessoren, FPGAs usw.
• Automatische Selektion von Kommunikationstechniken: verschiedene Verbindungsschemata wie zentrale Busse, hierarchische Busse, Ringe usw. sind realisierbar.
• Automatische Selektion von Scheduling und Arbitrierung: die in DOL verfügbaren Werkzeuge zur Erkundung des Entwurfsraumes wählen automatisch zwischen Rate Monotonic Scheduling, EDF, TDMA- und prioritätsbasierten Schemata.
369
HEFT und CPOP sind relativ schnelle und einfache Algorithmen. Diese Algorithmen nutzen verschiedene Näherungen (wie z.B. durchschnittliche Kommunikationskosten) und Heuristiken. HEFT und CPOP wurden für dieses Buch ausgewählt,
um Schwierigkeiten mit Scheduling-Algorithmen für heterogene Prozessoren zu demonstrieren. Allerdings ist es möglich, im Vergleich zu diesen beiden Algorithmen
bessere Ergebnisse zu erzielen. Beispielsweise haben Kim et al. [295] komplexere
Algorithmen beschrieben, die bessere Ergebisse liefern. Castrillon et al. [86] haben
ein Scheduling für KPNs entwickelt, welches ebenfalls den Makespan minimieren
soll.
6.5.3 Statisches Scheduling mit Ganzzahliger Programmierung
Die Ganzzahlige Lineare Programmierung kann auch auf heterogene Prozessoren
angewandt werden. Ein Ansatz hierzu wurde von Maculan et al. [362] publiziert.
Sehr wichtig ist, dass dabei prozessorabhängige Ausführungszeiten betrachtet werden. Allerdings bedürfen die gezeigten Gleichungen noch einiger Überarbeitungen,
bevor sie vollständig die Form eines Ganzzahligen Optimierungsproblems haben.
Weiterhin ist es auch möglich, Techniken der High-Level-Synthese [43, 315] zu
adaptieren.
In vielen der Publikationen werden Optimierungen für eine einzelne Metrik (ein
Zielkriterium) betrachtet. Im allgemeinen sollten mehrere Zielkriterien betrachtet
werden. Beispielsweise beschreiben Fard et al. [162] einen Algorithmus, der mehrere
Zielkriterien betrachtet.
6.5.4 Statisches Scheduling mit Evolutionären Algorithmen
Verfahren auf der Basis der Ganzzahligen Programmierung leiden unter potentiell
großen Rechenzeiten. In vielen Fällen erlauben evolutionäre Algorithmen bei akzeptablen Rechenzeiten eine bessere Optimierung. Wir werden dies am Beispiel der
Distributed Operation Layer (DOL)-Werkzeuge von der ETH Zürich zeigen [537].
Diese Werkzeuge beinhalten folgende Funktionen:
• Automatische Selektion von Prozessorarchitekturen: die Prozessortypen können vollständig heterogen sein. Mögliche Optionen sind Standard-Prozessoren,
Mikrocontroller, DSP-Prozessoren, FPGAs usw.
• Automatische Selektion von Kommunikationstechniken: verschiedene Verbindungsschemata wie zentrale Busse, hierarchische Busse, Ringe usw. sind realisierbar.
• Automatische Selektion von Scheduling und Arbitrierung: die in DOL verfügbaren Werkzeuge zur Erkundung des Entwurfsraumes wählen automatisch zwischen Rate Monotonic Scheduling, EDF, TDMA- und prioritätsbasierten Schemata.