Tomasulo-Algorithmus: So sortieren Prozessoren Befehle um
Ohne Out-of-Order-Execution wären Prozessoren deutlich langsamer. Der grundlegende Algorithmus dazu ist über 50 Jahre alt – wir erklären, wie er funktioniert.
Dieser Algorithmus des Monats hat nichts mit Mathematik zu tun: Er steckte ursprünglich in Mainframes und steckt heute – in erweiterter Form – in jedem größeren Prozessor, vom Raspberry Pi bis zur Server-CPU.
Mit dem nach ihm benannten Algorithmus entwickelte Robert Tomasulo 1967 bei IBM für das System/360 Model 91(öffnet im neuen Fenster) die erste vollständige Out-of-Order-Pipeline. Damit kann der Prozessor die eingehenden Befehle umsortieren und in anderer Reihenfolge ausführen. Wir erklären, warum das sinnvoll ist, welche Probleme es verursacht, wie der Tomasulo-Algorithmus sie löst – und warum er noch nicht perfekt war.