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^[1].

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

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): Diese implementieren Registerumbenennung und werden wie temporäre Register behandelt. Für jede FU gibt es zwei bis acht Reservation Stations. Eine Reservation Station enthält die auszuführende Operation, zwei Felder für die Werte der Operanden und zwei Felder für die Herkunft der Operanden, falls sie zum aktuellen Zeitpunkt noch nicht zur Verfügung stehen bzw. noch nicht gültig sind.

Funktionsweise

Jeder auszuführende Befehl durchläuft drei Stationen.

1. Issue: Die Operation des Befehls an der aktuellen Position in der Operation Queue wird inspiziert. Handelt es sich um eine arithmetische Operation, wird nur fortgefahren, wenn eine Reservation Station der entsprechenden Art frei ist. Der Befehl wird dekodiert und samt seiner Operanden in der freien Reservation Station zwischengespeichert. Dieser Vorgang wird als Registerumbenennung bezeichnet.
2. Execute: Sobald beide Operanden als tatsächliche Register oder als Speicheradressen zur Verfügung stehen, wird die Operation ausgeführt. Andernfalls wird der Common Data Bus auf weitere eingehende Werte beobachtet; trifft ein Wert ein, wird er übernommen, sofern die Adresse der Quelleinheit mit der benötigten Adresse übereinstimmt.
3. Write result: Sobald das Ergebnis der Operation berechnet wurde, wird es inklusive der Adresse der sendenden Einheit auf den Common Data Bus gelegt, und somit für die Einheiten aus Stufe 2 sichtbar welche auf ein ausstehendes 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.

Einzelnachweise

1. ↑ John Hennessy, David Patterson: Computer Architecture. A Quantitative Approach., 4th Edition, Morgan Kaufmann Publishers, ISBN 978-0-12-370490-0 (engl.), S. 92

Weblinks

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