Schlagwort: Hardware

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.

Veröffentlicht am

Performance Verbesserungen mit SIMD (Single Instruction multiple data)

„Single Instruction Multiple Data“ (SIMD) bezieht sich auf eine Art von paralleler Datenverarbeitung, bei der eine CPU oder ein Prozessor mehrere gleiche Operationen auf mehreren Daten gleichzeitig ausführt. Diese Methode wird oft eingesetzt, wenn sehr große und ähnliche Datenmengen effizient verarbeitet werden müssen.

Um sich das genauer vorzustellen, können wir uns das Beispiel der Vektor-Addition ansehen. Normalerweise würden wir jedes Element der Vektoren einzeln durchlaufen und addieren, um den Ergebnisvektor zu erhalten.

Im Code Beispiel würde die Implementation so aussehen:

C
int main(){
  float a[4] = {1.0f, 2.0f, 3.0f, 4.0f};
  float b[4] = {5.0f, 6.0f, 7.0f, 8.0f};
  float c[4];

  for (int i = 0; i < 4; i++) {
    c[i] = a[i] + b[i];
  }

  return 0;
}

Deutlich zu erkennen ist, dass der Operator immer derselbe ist (single instruction). Die Daten ändern sich jedoch mit jedem Schleifendurchlauf (multiple data).

SIMD ermöglicht die Ausführung derselben Addition in nur einem Schritt anstelle von vier Schritten, indem die Arrays in SIMD-Register kopiert werden. Diese Register haben typischerweise Größen von 128, 256 oder 512 Bit. Im vorliegenden Beispiel wird ein 128-Bit-SIMD-Register verwendet, da genau 4 float-Werte darin Platz haben.

C
#include <xmmintrin.h>

int main() {
  float a[4] = {1.0f, 2.0f, 3.0f, 4.0f};
  float b[4] = {5.0f, 6.0f, 7.0f, 8.0f};
  float c[4];

  __m128 vecA = _mm_load_ps(a);
  __m128 vecB = _mm_load_ps(b);
  __m128 vecC = _mm_add_ps(vecA, vecB);
  _mm_store_ps(c, vecC);

  return 0;
}

Muss ich meinen Code extra anpassen, um von SIMD zu profitieren?

Ja und nein. Moderne Compiler sind in der Lage solche Konstrukte zu identifizieren und automatisch in SIMD-Code umzuwandeln (Automatic vectorization). Auch wenn dies in der Theorie möglich ist erkennen Compiler nicht jede Stelle, vor allem an komplizierten Code Stellen. Daher ist es ratsam diese Explizit mit den C Compiler Intrinsics zu schreiben.

Hardwareimplementierung

SIMD wird in modernen CPUs und Prozessoren durch spezielle Schaltkreise implementiert, die als SIMD-Units oder Vector Units bezeichnet werden. Diese Schaltkreise sind speziell für die parallele Verarbeitung von Daten ausgelegt und können eine hohe Anzahl von Daten gleichzeitig bearbeiten.

In CPUs von Intel und AMD wird SIMD durch die SSE (Streaming SIMD Extensions) und AVX (Advanced Vector Extensions) implementiert. Die SSE-Technologie unterstützt SIMD-Operationen auf 128-Bit-Datenblöcken, während AVX bis zu 256-Bit-Datenblöcke unterstützt. AVX-512 erweitert die Technologie auf 512-Bit-Datenblöcke.

Bei Arm Prozessoren werden die SIMD-Funktionalitäten durch den Neon Befehlssatz hinzugefügt. Diese haben eine Breite von 128 Bit.

Hinweise

Wichtig zu berücksichtigen ist, dass das Kopieren von Daten zwischen den normalen und den SIMD-Registern einen zusätzlichen Overhead verursacht, der die Laufzeit des Programms beeinträchtigen kann. Daher sollte das Kopieren nur so selten wie möglich erfolgen, um negative Auswirkungen auf die Gesamtlaufzeit zu vermeiden.

Zusätzlich beschränkt die Verwendung von C-Compiler-Intrinsics die Zielplattformen, da nicht alle Prozessoren über SIMD-Register verfügen. In solchen Fällen ist es möglicherweise notwendig, eine alternative Codeversion ohne SIMD zu implementieren, um auch die Prozessoren ohne diese Register zu unterstützen.