Tomasulo-Algorithmus - LinkFang.de





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): 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 Befeht 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.

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


Kategorien: Algorithmus | Rechnerarchitektur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Tomasulo-Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.