358
6 Abbildung von Anwendungen
RMZL-Scheduling
Für bestimmte Task-Mengen kann G-RM Deadlines verpassen, obwohl ein Schedule existiert. Eine mögliche Verbesserung ist RMZL-Scheduling. Beim RMZLVerfahren nutzen wir (G-) RM-Scheduling, solange der Schlupf größer als Null ist.
Wir setzen aber die Priorität eines Jobs auf den höchsten Wert, wenn der Schlupf
für einen Job Null wird. RMZL-Scheduling ist RM-Scheduling überlegen, da wir die
Schedules nur dann ändern, wenn RM-Scheduling eine Deadline verpasst hätte [38].
Partitioniertes Scheduling für explizite Deadlines
Partitioniertes Scheduling für Tasks mit expliziten Deadlines kann ähnlich erfolgen
wie partitioniertes Scheduling für Tasks mit impliziten Deadlines, indem man das
Sortieren nach der Auslastung ersetzt durch ein Sortieren nach der Dichte. Allerdings wird dieses Verfahren nicht empfohlen, da die Dichte in manchen Fällen
unbeschränkt sein kann. Baruah et al. haben einen besseren Ansatz für partitioniertes
Scheduling publiziert [38].
6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen
Die Ergebnisse der vorherigen Abschnitte stellen Basiswissen dar, aber die Beschränkung auf unabhängige Tasks und identische Prozessoren verhindert in vielen
Fällen ihre Anwendung. Daher lassen wir jetzt diese Einschränkungen fallen. Zunächst geben wir die Beschränkung auf unabhängige Tasks auf. Wir konzentrieren
uns dabei auf einige einfache Algorithmen aus dem Bereich der Entwurfsautomatisierung für elektronische Schaltungen. Sehr populär sind beispielsweise die Algorithmen As-Soon-As-Possible (ASAP)-Scheduling, As-Late-As-Possible (ALAP)Scheduling, List-Scheduling (LS) und Force-Directed-Scheduling (FDS) im Bereich
der automatischen Synthese aus einer algorithmischen Beschreibung, der so genannten High-Level-Synthese (HLS) [113].
6.4.1 As-Soon-As-Possible-Scheduling
As-Soon-As-Possible-Scheduling (ASAP) versucht, unter Berücksichtigung der Reihenfolgebeschränkungen alle Tasks so früh wie möglich zu starten. In der HighLevel-Synthese werden üblicherweise nur ganzzahlige Startzeiten ≥0 betrachtet.
Verdrängungen sind nicht erlaubt. Die Zuordnung zu bestimmten Prozessoren erfolgt erst nach der Bestimmung der Startzeiten. Deshalb bietet ASAP-Scheduling
auch nur eine Abbildung auf Task-Startzeiten:
S : τ → N 0
(6.35)
6 Abbildung von Anwendungen
RMZL-Scheduling
Für bestimmte Task-Mengen kann G-RM Deadlines verpassen, obwohl ein Schedule existiert. Eine mögliche Verbesserung ist RMZL-Scheduling. Beim RMZLVerfahren nutzen wir (G-) RM-Scheduling, solange der Schlupf größer als Null ist.
Wir setzen aber die Priorität eines Jobs auf den höchsten Wert, wenn der Schlupf
für einen Job Null wird. RMZL-Scheduling ist RM-Scheduling überlegen, da wir die
Schedules nur dann ändern, wenn RM-Scheduling eine Deadline verpasst hätte [38].
Partitioniertes Scheduling für explizite Deadlines
Partitioniertes Scheduling für Tasks mit expliziten Deadlines kann ähnlich erfolgen
wie partitioniertes Scheduling für Tasks mit impliziten Deadlines, indem man das
Sortieren nach der Auslastung ersetzt durch ein Sortieren nach der Dichte. Allerdings wird dieses Verfahren nicht empfohlen, da die Dichte in manchen Fällen
unbeschränkt sein kann. Baruah et al. haben einen besseren Ansatz für partitioniertes
Scheduling publiziert [38].
6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen
Die Ergebnisse der vorherigen Abschnitte stellen Basiswissen dar, aber die Beschränkung auf unabhängige Tasks und identische Prozessoren verhindert in vielen
Fällen ihre Anwendung. Daher lassen wir jetzt diese Einschränkungen fallen. Zunächst geben wir die Beschränkung auf unabhängige Tasks auf. Wir konzentrieren
uns dabei auf einige einfache Algorithmen aus dem Bereich der Entwurfsautomatisierung für elektronische Schaltungen. Sehr populär sind beispielsweise die Algorithmen As-Soon-As-Possible (ASAP)-Scheduling, As-Late-As-Possible (ALAP)Scheduling, List-Scheduling (LS) und Force-Directed-Scheduling (FDS) im Bereich
der automatischen Synthese aus einer algorithmischen Beschreibung, der so genannten High-Level-Synthese (HLS) [113].
6.4.1 As-Soon-As-Possible-Scheduling
As-Soon-As-Possible-Scheduling (ASAP) versucht, unter Berücksichtigung der Reihenfolgebeschränkungen alle Tasks so früh wie möglich zu starten. In der HighLevel-Synthese werden üblicherweise nur ganzzahlige Startzeiten ≥0 betrachtet.
Verdrängungen sind nicht erlaubt. Die Zuordnung zu bestimmten Prozessoren erfolgt erst nach der Bestimmung der Startzeiten. Deshalb bietet ASAP-Scheduling
auch nur eine Abbildung auf Task-Startzeiten:
S : τ → N 0
(6.35)