6.5 Abhängige Jobs auf heterogenen Multiprozessoren
365
Laufzeiten evtl. unannehmbar groß werden. Für mittelgroße Probleme ist dennoch
eine exakte Optimierung möglich und bei größeren Problemen können diese Modelle
als Ausgangsbasis für Heuristiken eingesetzt werden.
6.5 Abhängige Jobs auf heterogenen Multiprozessoren
6.5.1 Problem-Beschreibung
Nach dem Streichen der Beschränkung auf unabhängige Tasks wollen wir nunmehr
auch die Beschränkung auf homogene Prozessoren aufheben. Wir nehmen an, dass
die Ausführungszeiten auf den verschiedenen Prozessoren unserer Ausführungsplattform π = {π 1 , ..., π m } nicht miteinander in einer Beziehung stehen. Gemäß
der Klassifikation von Pinedo betrachten wir damit den Fall (R m |r i , prec, ...|...).
Dies erlaubt es uns, Plattformen mit einer Mischung von Ausführungseinheiten zu
modellieren, einschließlich FPGAs und GPUs.
Die Theorie der resultierenden Scheduling-Probleme ist nicht umfangreich untersucht worden. Folglich schreiben Baruah et al. im Kapitel 22 ihres Buchs [38]:
„although unrelated multiprocessors are becoming increasingly more important in
real-time systems implementation, the resulting scheduling theoretic study of such
systems is, relatively speaking, still in its infancy.” Einige erste Ergebnisse wurden
im Buch von Baruah et al. vorgestellt, aber wir ziehen es hier vor, Methoden aus der
Entwurfsautomatisierung von Schaltkreisen vorzustellen. Diese Methoden sind in
der Lage, realistische Entwurfsaufgaben zu lösen, unter Verzicht auf eine Garantie
der Optimalität.
6.5.2 Statisches Scheduling mit lokalen Heuristiken
Nachfolgend werden wir den Heterogeneous-Earliest-Finish-Time (HEFT)- und den
Critical-Path-On-a-Processor (CPOP)-Algorithmus beschreiben. Diese beiden Algorithmen bilden Tasks eines Task-Graphen auf ein heterogenes MultiprozessorSystem π = {π 1 , ..., π m } ab [545]. Diese beiden Algorithmen sind Standard-Beispiele
für schnelle Algorithmen. In gewisser Weise erweitern sie ASAP- und ALAPScheduling auf heterogene Prozessoren. Wir benutzen die nachfolgend beschriebene
Notation:
• Wir nehmen an, dass der Task-Graph einen gemeinsamen Eingangsknoten τ entr y
besitzt. Sollte ein solcher Knoten anfänglich nicht vorhanden sein, so fügen wir
einen Knoten mit einer Ausführungszeit von 0 und ohne Kommunikationsanforderungen künstlich hinzu.
• Wir nehmen an, dass der Task-Graph einen gemeinsamen Ausgangsknoten τ exit
besitzt. Sollte ein solcher Knoten anfänglich nicht vorhanden sein, so fügen wir
365
Laufzeiten evtl. unannehmbar groß werden. Für mittelgroße Probleme ist dennoch
eine exakte Optimierung möglich und bei größeren Problemen können diese Modelle
als Ausgangsbasis für Heuristiken eingesetzt werden.
6.5 Abhängige Jobs auf heterogenen Multiprozessoren
6.5.1 Problem-Beschreibung
Nach dem Streichen der Beschränkung auf unabhängige Tasks wollen wir nunmehr
auch die Beschränkung auf homogene Prozessoren aufheben. Wir nehmen an, dass
die Ausführungszeiten auf den verschiedenen Prozessoren unserer Ausführungsplattform π = {π 1 , ..., π m } nicht miteinander in einer Beziehung stehen. Gemäß
der Klassifikation von Pinedo betrachten wir damit den Fall (R m |r i , prec, ...|...).
Dies erlaubt es uns, Plattformen mit einer Mischung von Ausführungseinheiten zu
modellieren, einschließlich FPGAs und GPUs.
Die Theorie der resultierenden Scheduling-Probleme ist nicht umfangreich untersucht worden. Folglich schreiben Baruah et al. im Kapitel 22 ihres Buchs [38]:
„although unrelated multiprocessors are becoming increasingly more important in
real-time systems implementation, the resulting scheduling theoretic study of such
systems is, relatively speaking, still in its infancy.” Einige erste Ergebnisse wurden
im Buch von Baruah et al. vorgestellt, aber wir ziehen es hier vor, Methoden aus der
Entwurfsautomatisierung von Schaltkreisen vorzustellen. Diese Methoden sind in
der Lage, realistische Entwurfsaufgaben zu lösen, unter Verzicht auf eine Garantie
der Optimalität.
6.5.2 Statisches Scheduling mit lokalen Heuristiken
Nachfolgend werden wir den Heterogeneous-Earliest-Finish-Time (HEFT)- und den
Critical-Path-On-a-Processor (CPOP)-Algorithmus beschreiben. Diese beiden Algorithmen bilden Tasks eines Task-Graphen auf ein heterogenes MultiprozessorSystem π = {π 1 , ..., π m } ab [545]. Diese beiden Algorithmen sind Standard-Beispiele
für schnelle Algorithmen. In gewisser Weise erweitern sie ASAP- und ALAPScheduling auf heterogene Prozessoren. Wir benutzen die nachfolgend beschriebene
Notation:
• Wir nehmen an, dass der Task-Graph einen gemeinsamen Eingangsknoten τ entr y
besitzt. Sollte ein solcher Knoten anfänglich nicht vorhanden sein, so fügen wir
einen Knoten mit einer Ausführungszeit von 0 und ohne Kommunikationsanforderungen künstlich hinzu.
• Wir nehmen an, dass der Task-Graph einen gemeinsamen Ausgangsknoten τ exit
besitzt. Sollte ein solcher Knoten anfänglich nicht vorhanden sein, so fügen wir