next up previous contents
Next: Testumgebung Up: Simulationsaufbau Previous: Auswahl   Inhalt

Aufwand

Da der Scheduler später in Hardware implementiert werden muß, ist es wichtig, daß der Aufwand nicht zu groß wird. Dazu müssen insbesondere Divisionen vermieden werden, soweit nicht durch Potenzen von zwei geteilt wird, so daß man Schieberegister benutzen kann. Ansonsten gliedert sich der Aufwand in drei Teile. Ein Teil bleibt immer fest, ein Teil ändert sich je nach verwendetem Scheduling-Verfahren. Der dritte Teil ändert sich mit der Anzahl der Threads.

Der Aufbau des Schedulers ist in Abschnitt 3.2.4 beschrieben. Er muß sich merken, welchen Thread er zuletzt zur Ausführung an die Decode-Stufe übergeben hat. Er führt eine Liste der ausführbaren Threads, die nach absteigender Priorität geordnet wird. Dazu gehört noch ein Speicherplatz für die Anzahl der momentan ausführbaren Threads.

Als Ausgaben des Schedulers an die anderen Stufen werden für die Decode- und die Fetch-Stufe je ein Bus benötigt, der die Nummer des nächsten zu bearbeitenden Thread angibt. Eine Leitung signalisiert, daß es gerade nichts zu tun gibt.

Von der Fetch-Stufe bekommt der Scheduler den Füllstand der Befehlsfenster, von der Decode-Stufe die Latenzzeit, die Anzahl der Mikrobefehle und die Information, ob der zuletzt ausgeführte Befehl ein Sprung war.

Tabelle 3.1 faßt die Parameter zusammen, die für die verschiedenen Verfahren gebraucht werden. Der Anteil bezeichnet hier den Prozentsatz der Rechenleistung, den der Thread bei Guaranteed Percentage Scheduling erhält. Diese Parameter werden für jeden Threadkontext einmal benötigt. Bei Guaranteed Percentage kann man die Bits für den Anteil und den für die Klasse in einem Register zusammenfassen, so daß man nur bei Least Laxity First tatsächlich zwei Register und zwei Befehle braucht.


Tabelle: Parameter für verschiedene Scheduler
  GP EDF LLF FPP Größe (Bit)
Deadline   x x   32
Laufzeit     x   32
Priorität       x ld(n)
Anteil x       8
Klasse x       3

Der Aufwand für zusätzliche Threads ist im wesentlichen höchstens linear. Eine Ausnahme bildet hier die Sortierung der Folge der Prozesse nach ihrer Priorität, die in der Softwaresimulation quadratisch in der Anzahl der Threads ist. In Hardware wird das dadurch aufgelöst, daß man den größten Wert unter den Prioritäten mit einem Vergleicherbaum sucht, diesen ausmaskiert und den größten der verbliebenen Werte sucht.


next up previous contents
Next: Testumgebung Up: Simulationsaufbau Previous: Auswahl   Inhalt
Alexander Schulz
2000-06-18