Tomasulo-Algorithmus

Der Tomasulo-Algorithmus ist ein Algorithmus zur Implementierung von dynamischem Scheduling in Prozessoren. Er wurde von Robert Tomasulo bei IBM entwickelt – ursprünglich für die Gleitkommaeinheit des 360/91.

Einordnung

Um die Geschwindigkeit zu erhöhen, mit der ein Prozessor auszuführende Instruktionen bei konstanter Taktfrequenz durchläuft, wird die Ausführung von Instruktionen in mehrere Schritte unterteilt. Sobald eine Instruktion eine Stufe durchlaufen hat, kann die nächste Instruktion bereits diese Stufe betreten, so dass der Prozessor stets an mehreren Instruktionen gleichzeitig arbeitet. Dieses Verfahren bezeichnet man als Pipelining, die Stationen, die die Befehle durchlaufen, als Stages.

Wenn nun Teile der Pipeline oder die gesamte Pipeline mehrfach vorkommen, spricht man von Superskalarität. Da sich mehrere Befehle gleichzeitig in der Pipeline befinden, kann es durch Abhängigkeiten zwischen den auszuführenden Befehlen zu Problemen kommen. Eine naive Lösung ist es, mit der Abarbeitung der nächsten Befehle zu warten. Ein intelligenteres Verfahren, das dies umgeht, ist das dynamische Scheduling. Der Tomasulo-Algorithmus stellt eine konkrete Implementierung dieses Verfahrens dar. Ein weiteres Verfahren ist z. B. das Scoreboarding.

Strategie

Der Tomasulo-Algorithmus verfolgt das Ziel, die Ausführung von Befehlen fortzusetzen, selbst wenn Datenabhängigkeiten vorliegen. Zum einen handhabt er Read-after-write-Hazards (RAW), indem der Prozessor verfolgt, wann ein Operand zur Verfügung steht. Zum anderen verhindert er Write-after-write- (WAW) und Write-after-read-Hazards (WAR), indem relevante Registerinhalte beim Decodieren eines Befehls in sogenannten Reservation Stations zwischengespeichert und so vor vorzeitigem Überschreiben geschützt werden.

Prozessoraufbau

Tomasulos Gleitkommaeinheit

Ein Prozessor, der den Tomasulo-Algorithmus implementiert, enthält unter anderem folgende Komponenten:

• Functional Units (FU): Die Functional Units sind Prozessorbausteine, die logisch/arithmetische Berechnungen ausführen. Es gibt hiervon meist mehrere; sie unterscheiden sich in der Art der Operationen, welche sie ausführen können (floating point, integer, load/store etc.). Bei modernen Prozessoren ist fünf eine typische Zahl für die Anzahl an FUs.

• Reservation Stations (RS): Jeder FU sind zwei bis acht Reservation Stations zugeordnet. Diese implementieren Registerumbenennung und werden wie temporäre Register behandelt. Eine Reservation Station enthält den Opcode der auszuführenden Operation, zwei Felder für die Werte der Operanden und zwei Felder für die Adressen der RSs, die die Operanden berechnen, falls sie zum aktuellen Zeitpunkt noch nicht zur Verfügung stehen bzw. noch nicht gültig sind.

• Registersatz: Der Registersatz enthält für jedes Register neben einem Feld für den gespeicherten Wert auch ein Feld für die Adresse einer RS. Hier wird eine RS eingetragen, falls diese den Wert des Registers noch berechnet.

• Common Data Bus: Alle FUs und RSs sind durch einen gemeinsamen Ergebnisbus miteinander verbunden. Eine FU legt nach Fertigstellung einer Berechnung die Adresse der bearbeiteten RS und das Ergebnis auf den Bus. Die RSs beobachten den Bus um den Wert noch benötigter Operanden direkt zu übernehmen.

Funktionsweise

Jeder auszuführende Befehl durchläuft drei Stationen.

1. Issue: Der Befehl an der aktuellen Position in der Operation Queue wird dekodiert und entsprechend seiner auszuführenden Operation in eine passende Reservation Station eingetragen. Operanden werden direkt aus der Registerdatei übernommen, wenn sie gültig sind. Dieser Vorgang wird als Registerumbenennung bezeichnet. Steht ein Operand noch nicht zur Verfügung, wird stattdessen die Adresse der RS eingetragen, die den Wert gerade berechnet. Ist keine passende RS frei, verbleibt der Befehl in der Operation Queue und die Zuweisung wird im nächsten Takt erneut versucht.
2. Execute: Sobald alle Operanden in der Reservation Station zur Verfügung stehen, wird die Operation an die FU weiter gegeben und ausgeführt. Andernfalls wird der Common Data Bus auf eingehende Werte beobachtet und fehlende Operanden übernommen, wenn die Adresse der Quell-RS mit der benötigten Adresse übereinstimmt.
3. Write result: Sobald das Ergebnis der Operation berechnet wurde, wird es mitsamt der Adresse der ausgeführten RS auf den Common Data Bus gelegt und somit für die RS sichtbar, welche auf das Ergebnis warten.

Weitere Merkmale

Über die obige Logik hinaus erkennt der Tomasulo-Algorithmus sich überlappende Write-Befehle auf ein und dasselbe Register und führt nur den letzten zum Aktualisieren des Registers aus.

Weblinks

• Ursprünglicher Aufsatz (engl.): An Efficient Algorithm for Exploiting Multiple Arithmetic Units
• Einführung Rechnerarchitektur von Holger Kreißl : Superskalarität
• WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm, Institute for Computing Systems Architecture, Edinburgh University.
• Dynamic Scheduling – Tomasulo (engl.)