BRANCH PREDICTION

Branch Prediction

 

[dt. »Verzweigungsvorhersage«, »Sprungvorhersage«] die, eine von Intel erstmals im Pentium-Prozessor eingesetzte Technik zur Erhöhung der Arbeitsgeschwindigkeit. Branch Prediction setzt auf der Prefetch-Technik (Prefetch) auf, bei welcher der nächste Befehl während der Erledigung des aktuellen schon geladen wird. Dies wird erweitert für den Fall, dass der nächste Befehl eine Verzweigung ist. Bei einem solchen bedingten Sprung ist das Sprungziel noch nicht bekannt, weil es anhand der Bedingung erst bestimmt werden muss.

 

Die Branch Prediction Unit (BPU) nun macht eine Vorhersage für das wahrscheinlichste Sprungziel anhand statistischer Regeln. Dazu speichert sie die Adressen und Sprungziele von bereits abgearbeiteten Verzweigungsbefehlen in einem Pufferspeicher (Prefetch Buffer) und wertet die Häufigkeit jeder Verzweigung aus. Durchläuft ein Programm eine Schleife, so hält die BPU nach dem ersten Durchlauf bereits die Adressen der möglichen Sprungziele bereit und bietet die wahrscheinlichste Zieladresse an. Ist diese Adresse richtig, so beginnt die Befehlsverarbeitung unmittelbar. Ansonsten wird das Sprungziel »normal« bestimmt; Verzögerungen durch das Verwerfen des vorgewählten Sprungziels treten nicht auf.Die Geschwindigkeitserhöhung durch Branch Prediction kann bis zu 25 % betragen; der genaue Wert hängt von der Qualität der Regeln ab, anhand derer die »wahrscheinlichen« Sprungziele bestimmt werden.

 

Es gibt zwei Arten von Buffern bei der Branch Prediction: im Branch Target Buffer (Abk. BTB, »Verzweigungszielpuffer«) werden direkte Sprungziele gespeichert, in der Branch History Table (Abk. BHT, »Tabelle der früher aufgetretenen Verzweigungen«) werden die zuletzt getroffenen Entscheidungen abgelegt. In diesem Fall muss der Prozessor aus den dokumentierten Entscheidungen das Sprungziel ableiten. Die AMD-Prozessoren K5 und K6 verwendeten eine BHT, während Intel und Cyrix auf den BTB setzten. Der AMD Athlon verfolgt beide Konzepte. Die Treffgenauigkeit der Branch Prediction liegt nach Herstellerangaben bei allen modernen Prozessoren z. T. deutlich über 90 %.

 

 

Anwender bemängeln, dass viele Windows-Anwendungen auf dem Pentium 4 langsamer ablaufen als auf dem älteren Pentium III. Einer der Gründe ist, dass die Regeln der Branch Prediction für diesen Prozessor für den Bereich Multimedia optimiert wurden; die Trefferquote für Windows-Code (und damit die mögliche Geschwindigkeitssteigerung durch Branch Prediction) ist jedoch nur gering.