next up previous contents
Next: Schnittstellen Up: Implementierung in Hardware Previous: Der Mikrocontroller   Inhalt


Einordnung in die Pipeline

Der Prioritäten-Manager soll die Entscheidung treffen, welcher Thread als nächstes ausgeführt werden soll. Diese Information muß in jedem Takt zur Verfügung stehen, bevor ein Befehl dekodiert werden kann.

Es gibt mehrere Möglichkeiten, den Prioritäten-Manager in die Pipeline einzufügen:

Die Idee, den Scheduler als eigene Pipeline-Stufe zu betreiben, wird hier nicht weiter verfolgt, da in diesem Fall die Latenzen der einzelnen Bytecode-Befehle erst einen Takt zu spät an den Eingängen des Schedulers anliegen würden. Dadurch könnten Latenzen von einem Takt Länge nur selten und durch Zufall genutzt werden, bei Scheduling-Verfahren, die von sich aus selten den Kontext wechseln wie etwa EDF, könnten diese Latenzen praktisch nie genutzt werden.

Abbildung 4.1: Einbau in eine schnelle Pipeline

Abbildung 4.1 zeigt den Fall, in dem das Scheduling parallel zum Dekodieren ausgeführt wird. Diese Variante wird hier auch nicht weiter betrachtet, da die Ausführungseinheit die längste Pipeline-Stufe ist und somit genug Zeit in der Decode-Stufe zur Verfügung steht, um das Scheduling noch vor dem eigentlichen Dekodieren der Bytecode-Befehle in Opcodes durchzuführen. Dies vereinfacht zudem den Aufbau des Prioritäten-Managers.

Die Scheduling-Entscheidung parallel zum Dekodieren zu treffen, bringt noch weitere Probleme mit sich. So muß der Scheduler wissen, ob der parallel dekodierte Befehl zu einer Latenz führt, da er den betroffenen Thread dann nicht sofort wieder für den nächsten Takt auswählen darf. Das kann dadurch ausgeglichen werden, daß er zwei Threads auswählt und zu Beginn des nächsten Taktes den zweiten an die Dekodiereinheit weitergibt, wenn der erste in eine Latenz fallen würde.

Zudem kann es sein, daß die Decode-Stufe den im vorherigen Takt ausgewählten Thread nicht ausführen kann, weil das Befehlsfenster nicht den vollständigen Befehl enthält. Das muß insbesondere Guaranteed Percentage frühzeitig wissen, da die Scheduling-Entscheidung davon abhängt, ob ein Thread bereits genug Takte bekommen hat, oder nicht.

Um zu verhindern, daß die Decode-Stufe einen vom Scheduler ausgewählten Befehl nicht bearbeiten kann, wird die Untergrenze des Füllstandes für den Scheduler auf drei festgesetzt. Der Scheduler wählt einen Thread also nur dann aus, wenn sich mindestens drei Bytes in dem dazugehörigen Befehlsfenster befinden. Damit hat die Decode-Stufe immer genug Bytes in dem Befehlsfenster, das ausgewählt wurde.

Um immer die aktuellen Füllstände berechnen zu können, braucht der Scheduler einige Informationen aus der Execute-Stufe (Blockierung des Befehlsholens bei Speicherzugriffen, Leeren nach genommenen Sprüngen), die schon schwierig rechtzeitig zu bekommen sind (etwa indem man die Speicherzugriffe und Sprünge schon beim Dekodieren erkennt und pessimistisch davon ausgeht, daß alle Sprünge genommen werden). Zudem wird aber auch noch die Länge des gerade parallel dekodierten Befehls benötigt, um die Füllstände der Fenster berechnen zu können. Dies entspricht dem senkrechten Pfeil zwischen Decode und Scheduler in Abbildung 4.1. Dies ist in einem synchron getakteten System nicht zu erreichen.

Da der Scheduler mit der zusätzlichen Berechnung der Füllstände und der Auswahl eines zweiten Thread als ,,Reserve`` außerdem sehr komplex wird, weil sie einige zusätzliche Addierer und zusätzliche Vergleiche benötigt, wird diese Variante hier auch nicht weiter verfolgt.

Abbildung 4.2: Einbau in eine langsamere Pipeline

Abbildung 4.2 zeigt den für diese Arbeit gewählten Aufbau, bei dem der Prioritätenmanager in die Decode-Stufe eingesetzt wird.

Da für jeden Thread-Kontext ein eigenes Befehlsfenster vorhanden ist, kann aus einem Fenster ein Befehl dekodiert werden, unabhängig davon, für welches Fenster gerade Befehle aus dem Speicher nachgeladen werden. Daher kann das Holen der Befehle unabhängig vom Scheduling betrachtet werden.

Die Berechnung der Befehlshole-Reihenfolge wird nach den Untersuchungen aus Abschnitt 3.3 nur noch vom Füllstand der Befehlsfenster abhängen. Daher wird dieser Teil in die Fetch-Stufe verlegt, so daß auch hier alle Informationen rechtzeitig zur Verfügung stehen und nicht erst einen Takt später. Wenn im Folgenden von Fetch-Logik die Rede ist, handelt es sich um diese Kontrolleinheit, die vorgibt, für welchen Thread im nächsten Takt Befehle nachgeladen werden sollen. Diese Einheit sollte nicht mit der Fetch-Stufe der Pipeline verwechselt werden.


next up previous contents
Next: Schnittstellen Up: Implementierung in Hardware Previous: Der Mikrocontroller   Inhalt
Alexander Schulz
2000-06-18