Schlagwort: Branch Prediction

Veröffentlicht am

Der Motor der Leistung: Branch Prediction in modernen CPU Architekturen

Die Leistungsfähigkeit eines Prozessors wird von vielen Faktoren beeinflusst. Eine entscheidende Rolle spielt dabei die Branch Prediction. Diese Technik wird von modernen CPUs genutzt, um die Ausführung von Programmcode zu beschleunigen, indem sie voraussagt, welchen Weg ein Programmzweig nehmen wird.

Was ist Branch Prediction?

Programmcode besteht aus einer Reihe von Anweisungen, die in einer bestimmten Reihenfolge ausgeführt werden. Manchmal gibt es jedoch Verzweigungen, bei denen die Ausführung abhängig von bestimmten Bedingungen unterschiedliche Pfade nehmen kann. Ein Beispiel für eine Verzweigung ist eine bedingte Anweisung wie „if-else“, bei der abhängig von der Erfüllung einer Bedingung entweder der Code im „if“-Zweig oder der Code im „else“-Zweig ausgeführt wird. Die Branch Prediction versucht nun, im Voraus zu erraten, welcher Zweig genommen wird, bevor dies tatsächlich feststeht.

C
if(foo > 42) {
  // Execute if block
  foo = 0;
}
else {
  // Execute else block
  foo = 1;
}

Warum ist Branch Prediction wichtig?

Die Ausführung von Programmen erfordert Zeit und Ressourcen, und Verzweigungen können zu Verzögerungen führen. Wenn der Prozessor auf die Auflösung einer Verzweigung warten muss, kann dies zu sogenannten Pipeline-Stalls führen, bei denen der Prozessor nicht effizient genutzt. Damit die Pipeline immer maximal ausgelastet ist und somit am effizientesten arbeitet, sind Stalls dringlichst zu vermeiden. An dieser Stelle versucht Branch Prediction, die Stalls zu minimieren, indem versucht wird vorherzusagen, welcher Pfad genommen wird und entsprechend frühzeitig die Pipeline mit dem nächsten Befehl aufgefüllt wird. Ohne Branch Prediction würde in dem Beispiel die Pipeline bis zu der if Abfrage nicht mit neuen Instruktionen aufgefüllt, da der Wert von foo nicht klar ist. Je nach länge der Pipeline würden diese Taktzyklen dann ungenutzt bleiben.

Wie funktioniert Branch Prediction?

Moderne CPUs setzen verschiedene Techniken ein, um Branch Prediction durchzuführen. Eine gängige dynamische Methode besteht darin, sogenannte Branch History Tables (BHT) oder Branch Target Buffers (BTB) zu verwenden. Diese speziellen Hardwarestrukturen speichern Informationen über vorherige Verzweigungen und deren Ausführungspfade. Anhand dieser Informationen wird eine Vorhersage für zukünftige Verzweigungen getroffen. Der „Two-bit-Counter“ oder der „Gshare-Algorithmus“ analysieren die Vergangenheit der Verzweigungen und passen ihre Vorhersagen entsprechend an. Der Prozessor nutzt dann diese Vorhersagen, um den nächsten Befehl vorzubereiten und die Pipeline effizient zu befüllen.

Vor- und Nachteile der Branch Prediction

Die Branch Prediction ist eine äußerst effektive Technik, um die CPU-Leistung zu steigern. Sie hilft dabei, Pipeline-Stalls zu reduzieren und die Anzahl der Taktzyklen, die für die Auflösung von Verzweigungen benötigt werden, zu minimieren. Stimmt die Vorhersage allerdings nicht, kann dies zu einer „Branch Misprediction“ führen, bei der die Pipeline zurückgesetzt werden muss. Dies kann insbesondere bei komplexen Verzweigungsstrukturen oder wenn sich das Verhalten des Programms während der Laufzeit ändert passieren. Durch Predication kann der CPU geholfen werden die Branch Prediction effektiver zu nutzen.

Veröffentlicht am

Predication

In diesem Artikel wird untersucht, warum gewöhnliche if-Anweisungen die Ausführungsdauer erheblich verlangsamen können und wie man dem entgegenwirken kann. Um die Ursprünge dieses Phänomens besser zu verstehen, ist ein grundlegendes Verständnis von Branch Prediction erforderlich.

Um die Ausführungsgeschwindigkeit von Code zu verbessern, verwendet die CPU das sogenannte Pipelining, um die Pipeline maximal auszulasten. Dieser Effekt kann jedoch durch sogenannte Pipeline-Flushes beeinträchtigt werden. Um dieses Thema genauer zu verstehen, hier ein kurzes Beispiel: Das folgende Programm zählt die Anzahl der Zahlen, die größer als 50 sind. Da die Zahlen mithilfe einer Zufallsfunktion und Modulo 101 generiert werden, liegen sie immer im Bereich von 0 und 100. Aus diesem Grund sollte der Counter in der if-Bedingung in etwa der Hälfte der Schleifendurchläufe erhöht werden.

C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  int counter = 0;
  for (int i = 0; i < 100000; i++)
  {
    if (rand() % 101 > 50)
    {
      counter++;
    }
  }
  printf("%d", counter);
  return 0;
}

Warum genau ist diese Implementierung langsam? Die CPU versucht mithilfe der sogenannten Branch Prediction, zukünftige Programmzeilen vorherzusagen und vorzeitig auszuführen. Da die nächste Zufallszahl noch nicht bekannt ist, muss die CPU raten, ob der Counter erhöht wird oder nicht. Anhand dieser Entscheidung werden der Pipeline neue Instruktionen zugeführt. Wenn die Vorhersage jedoch falsch ist, wird ein Pipeline-Flush ausgelöst, der dazu führt, dass die Pipeline einige Takte benötigt, um alle vorherigen Anweisungen zu löschen. Erst dann kann die korrekte Instruktion ausgeführt werden. Da dies jedoch nur in 50% der Fälle zutrifft, kann praktisch kein Laufzeitgewinn durch die Branch Prediction erzielt werden. Im Gegenteil, durch die Flushes wird sogar die Ausführungsdauer verlangsamt. Bei den 50% spricht man auch von der Selektivität.

Wie kann dieses Verhalten verhindert werden?

Das beste Mittel, um falsche Branch Predictions zu vermeiden, besteht darin, erst gar keine Branches zu verwenden. Dazu kann die boolsche If-Bedingung in einen Integer gecastet werden. Dieser hat entweder den Wert 0 oder 1, der direkt auf die Variable counter addiert werden kann.

C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  int counter = 0;
  for (int i = 0; i < 100000; i++)
  {
    counter += (int)(rand() % 101 > 50);
  }
  printf("%d", counter);
  return 0;
}

Auf diese Weise ist die Ausführungsgeschwindigkeit unabhängig von der Selektivität.

Vergleich der Laufzeiten von Branched zu Predicated

Deutlich wird bei einem Vergleich der Laufzeiten ersichtlich, wie sich die Selektivität auf die Performance auswirkt. Bei einer Selektivität von 50% zeigt sich deutlich, dass die Branch Prediction am ineffektivsten ist. Eine Implementierung mit Predication bleibt hingegen gänzlich unberührt von der Selektivität.