Instruction Scheduling: Befehlsreihenfolge gegen Pipeline-Stalls

Instruction Scheduling (Befehlsplanung) ist eine Optimierung der Codegenerierung: Der Compiler ordnet die Maschinenbefehle so um, dass die Pipeline-Stalls minimiert werden. Unabhängige Befehle werden zwischen abhängige geschoben, damit Latenzen (Speicherzugriffe, lange ALU-Operationen) überbrückt werden und die superskalare Ausführung mehrere Einheiten gleichzeitig beschäftigt.

Warum überhaupt umsortieren?

Moderne CPUs führen Befehle im Fließband aus (siehe Pipelining). Ein Load dauert je nach Cache ein paar Takte (siehe Cache-Speicher und TLB); wer das geladene Wort sofort benutzt, muss warten. Beispiel:

ldr r1, [r2]     ; Laden dauert einige Takte
add r3, r1, r4   ; wartet auf r1 → Stall

Findet sich dazwischen ein unabhängiger Befehl, wird er vorgezogen:

ldr r1, [r2]
sub r5, r6, r7   ; unabhängig, füllt die Wartezeit
add r3, r1, r4   ; Ergebnis von r1 ist jetzt da

Das Ergebnis der Berechnung bleibt identisch – die Reihenfolge der Effekte ist die gleiche; nur die zeitliche Anordnung der unabhängigen Arbeit ändert sich.

Regeln und Grenzen

  • Echte Abhängigkeiten (RAW) dürfen nie verletzt werden: Ein Befehl, der das Ergebnis eines anderen liest, muss danach stehen.
  • Anti- und Output-Abhängigkeiten (WAR/WAW auf denselben Registernamen) kann der Scheduler meist ignorieren oder umgehen – dank Register-Renaming in der Hardware sind sie für die Ausführung ohnehin kein Hindernis mehr.
  • Speicher-Aliasing: Ein Load darf nicht vor einem Store geschoben werden, der dieselbe Adresse treffen könnte – sonst liest er einen falschen Wert. Der Scheduler braucht Alias-Analyse oder konservative Annahmen.
  • Kontrollfluss: Befehle dürfen nicht über Sprünge hinweg verschoben werden (außer bei spekulativen Techniken), und die Sprungvorhersage bestimmt mit, wie teuer Fehlplanung ist.

Algorithmen und Spielarten

  • List Scheduling: der Standard-Algorithmus. Aus dem Abhängigkeitsgraphen (DAG der Befehle) wird eine Reihenfolge gebaut; als Priorität dienen Heuristiken wie Länge des kritischen Pfads oder Befehls-Latenz.
  • Software-Pipelining (auch Modulo Scheduling): Bei Schleifen werden Iterationen überlappt – der Prolog startet die erste Iteration, der Steady State arbeitet mehrere parallel, der Epilog räumt auf. Speziell bei VLIW-Prozessoren (z.B. Itanium) plant der Compiler statisch jede Takt-Slot-Belegung.
  • Superblock-/Trace-Scheduling: Mehrere Basic Blocks werden für längere Planungsfenster zusammengefasst.

In LLVM läuft das Scheduling in mehreren Passes (vor und nach der Registerallokation), in GCC analog als Scheduler-Passes der Codegenerierung. Die Registerallokation und das Scheduling hängen eng zusammen: Eine gute Verteilung der Register (siehe Registerallokation) erzeugt weniger künstliche Abhängigkeiten, ein gutes Scheduling verlangt dafür oft nach zusätzlichen Registern.

Abgrenzung

Instruction Scheduling ist statische Planung im Compiler – die Alternative ist die dynamische Planung in der Hardware (Out-of-Order-Ausführung, siehe Superskalar und Register-Renaming); bei CISC-Befehlssätzen zerlegt die Hardware die Instruktionen zusätzlich intern in Mikro-Operationen (siehe Mikrocode). Beide Seiten ergänzen sich: Der Compiler bereitet günstige Reihenfolgen vor, die CPU nutzt Rest-Parallelität zur Laufzeit. Es ist ein Teilschritt der Codegenerierung neben Instruktionsauswahl, Registerallokation und Peephole-Optimierung und verwandt mit der Code-Optimierung auf höherer Ebene (etwa Schleifen-Umformungen, die dem Scheduler gute Ausgangslagen schaffen).