Vektorisierungskonzept

Das Vektorisierungskonzept ermöglicht logische und mathematische Operation (Addieren, Subtrahieren, Dividieren, Multiplizieren) statt nur skalar auf eine Variable auf mehrere Variablen (typischerweise Felder) gleichzeitig durchzuführen. Ein anschauliches Beispiel, das auch die Nomenklaturherkunft des Wortes „Vektorisierung“ erklärt, ist die Operation des Vektorprodukts. Bei diesem Algorithmus werden alle Elemente eines Vektors multipliziert, um dann anschließend summiert zu werden. In diesem Artikel wurden Vergleiche auf Basis der Sandybridge-Architektur durchgeführt. Aber auch die X86-basierende, stromsparende Intel Atom-Architektur profitiert von SIMD. Im Atom-Prozessor ist SIMD bis hin zu SSE3-Version implementiert.

Das Vektorisierungskonzept ermöglicht logische und mathematische Operation (Addieren, Subtrahieren, Dividieren, Multiplizieren) statt nur skalar auf eine Variable auf mehrere Variablen (typischerweise Felder) gleichzeitig durchzuführen. Ein anschauliches Beispiel , das auch die Nomenklaturherkunft des Wortes „Vektorisierung“ erklärt, ist die Operation des Vektorprodukts. 

Bei diesem Algorithmus werden alle Elemente eines Vektors multipliziert um dann anschließend summiert zu werden. Bild 1 zeigt die vektorisierte Multiplikation mehrerer Elemente. SIMD-Instruktionen offerieren hier ihr Leistungspotenzial.

Evolution des Vektorisierungskonzept (MMX, SSE, AVX)

Die erste SIMD-Implementierung Mitte der 90er Jahre wurde beim Pentium MMX-Prozessor eingeführt. Intel spendierte damals 8 neue Register (MM0 bis MM7) für den Rechnerkern. MMX war auf 64 Bit breite Register und auf Integerdatentypen begrenzt und wurde zunächst hauptsächlich bei der Games- und Multimediaprogrammierung eingesetzt.

Mit dem Aufkommen der verschiedenen SSE-Versionen (SSE = SIMD Streaming Extension) SSE, SSE2, SSE3, SSE4.1 und SSE4.2  wurden die 8 Register umbenannt (XMM0 bis XMM7) und auf 128 Bit erweitert. Dies ermöglichte unter anderem vier 4 Bytes große Integerdatentypen gleichzeitig (quasi vektoriell) zu addieren anstatt nacheinander die einzelnen 4 Operationen auszuführen.  Auch die Datentypvielfalt wurde nach und nach erhöht. So wurden neben den verschiedenen Integerdatentypen auch diverse Floatingdatentypen zugelassen (Bild 2). Für die 64-Bit-Prozessoren kamen noch einmal 8 zusätzliche Register (XMM8-XMM15) hinzu.

Mit Einführung der neuesten Intel Core-Architektur der 2-ten Generation (intern auch als SandyBridge-Architektur bezeichnet) gab es mit AVX ( Advanced Vector Extension) sogar 256 Bit breite Register, die in YMM0–YMM15 umbenannt sind. AVX erlaubt sogar 3 bis 4 Operandenbefehle, die ebenfalls zu Leistungssteigerungen von datenintensiven Algorithmen beitragen. Es sei hier angemerkt, dass auch die Betriebssysteme bei neuen SIMD-Instruktionen nachführt werden müssen. Zum Beispiel benötigt man bei AVX das Service Pack 1 von Windows 7.

Einführung in die Nutzung der SIMD-Instruktionen

Zu Beginn der Einführung von MMX hatte der Entwickler selbst für die effizente Nutzung der Vektorisierung und der Performance-Optimierung zu sorgen. Er musste die neuen Befehlsinstruktionen händisch per Assemblerbefehl programmieren. Inzwischen nimmt einem der Intel Compiler die Arbeit weitgehend ab, indem er automatisch SSE- bzw. AVX-Instruktionen auf effizienteste Weise nutzt. Bei dieser automatischen Verfahrensweise nimmt der Programmierer über so genannte Compilerschalter (auch Switches genannt) Einfluss auf den Compiler und dessen Optimierungsanstrengungen. Diese Vorgehensweise wird Autovektorisierung genannt. Es stellt sich zunächst die Frage, wo die der Vektorisierungsbeschleunigung, der Speed-Up, herkommt. Das soll an einem kleinen Programmfragment klargemacht werden, wobei die Variablen a, b und c dabei Integer-basierende Arrays sind :

for(i=0;i<=MAX;i++)

c[i]=a[i]+b[i];

Ohne Autovektorisierung, gesteuert durch die Compiler-Switches /Od, /O1 oder /Qvec- (hier beispielhaft die Switch-Nomenklatur gezeigt für Windows), ergäbe sich ein Resultat gemäß Bild 3. 75 Prozent der Vektorisierungseinheit blieben ungenutzt.

Applikationen können mit den Optimierungseinstellungen (Switch: /O2 (Standdardeinstellung) oder besser /O3) vektorisiert werden. Damit würden dann auch die unbenutzten SIMD-Register (Bild 3) verwendet.

Der Compiler hält dabei nicht nur Ausschau nach Möglichkeiten SIMD-Instruktionen in den Code einzubauen, sondern auch ein Loop-Unrolling-Verfahren durchzuführen, was die Leistung nochmal steigert, da die Anzahl der Schleifendurchläufe und damit das notwendige Branching reduziert werden.

Die gezielte Optimierung auf eine bestimmte SIMD-Version sind mit definierten Switches möglich. 

Vektorisierungs-Reports und -Pragmas der Intel-Compiler

In einigen Fällen ist es aber wichtig den Compiler bei der Autovektorisierung durch Schlüsselworte und Direktiven (Pragmas) zu unterstützen, um damit noch optimalere Resultate zu erzielen. 

Dabei kommen Log-Reports der Intel-Compiler zum Tragen, die zwei relevante Vektorisierungsinformationen mit dem Switch „/Qvec-report“ anzeigen:

1. Zunächst gibt der Log-Report an, ob der Code überhaupt vektorisiert wurde.

2. Es ist ohne weiteres möglich, dass der Compiler eine Vektorisierung aus guten Gründen verweigert. In diesem Fall gibt der Log-Report Auskunft über diese Gründe mit einem Hinweis zur entsprechenden Quellcodezeile. Außerdem gibt er nicht nur Tipps wie die Probleme zu beheben sind, sondern auch wie der Programmierer mögliche Pragmadirektiven einsetzen kann. Der Entwickler, der ja mit seinem Programm vertraut ist, kann unter anderem dem Compiler über die Pragmaanweisungen mitteilen, dass potenzielle Datenabhängigkeiten, die vom Compiler moniert worden sind, nicht relevant sind und damit ignoriert werden dürfen.

Guided Auto-Parallelization

Guided Auto-Parallelization (GAP) ist ein Merkmal des Intel- Compilers und wird mit dem Switch „/Qguide“ aufgerufen. Dadurch werden weitere Programmdiagnosen angestoßen und Vektorisierungsvorschläge erstellt. Unter anderem werden Quellcodeänderungen, Pragmaempfehlungen oder bestimmte Compileroptionen per GAP-Funktion vorgeschlagen.

Empfehlungen für das erfolgreiche Vektorisieren

Beginnen wir mit einigen allgemeinen Tipps, die zu schnellerem, vektorisierten Code führen.

1. Schleifen sollten jeweils nur eine einzige Einsprung- und eine Austrittsstelle besitzen (z.B. sind „for – loops“ gut geeignet).
Man sollte auch komplexe Exitkonditionen vermeiden. Die Loops sollten während ihrer Ausführung einen festgelegten Schleifenzähler haben. Nur die innerste Schleife eines „nested loops“ sollte vektorisiert werden.

2. Verzweigungen wie Switch-, Goto- und Return-Anweisungen sind zu vermeiden. „if“-Statements sind in Schleifen nur erlaubt, wenn sie als maskierte Assignments durch die Autovektorisierung implementiert werden können, was aber meistens der Fall ist. Die SIMD-Kalkulation wird dann für alle Array-Elemente durchgeführt. Aber nur die Elemente, die durch die Maske als wahr evaluiert wurden, werden gespeichert.

Auch Funktionsaufrufe (beispielsweise „printf“) von Bibliotheken in Schleifen sind nicht erlaubt, und bedeuten, dass nicht vektorisiert wird. Ausnahmen sind mathematische „intrinsic“-Funktionen und „inline“-Funktionen. Eine Liste von erlaubten mathematischen Funktionen ist bereits vektorisiert wie etwa sin(), log(), fmax(), ….

3. Vermeiden von Datenabhängigkeiten zwischen Schleifeniterationen bzw. von „read-after-write“-Abhängigkeiten.

4. Man sollte Felder (Arrays) verwenden. Dabei können Alias-Pointers in diesem Zusammenhang dagegen zu Datenabhängigkeiten führen. Für die Arrayindizierung sollte man die Schleifenindizees verwenden (also keine eigenen neuen Index-Variablen definieren).

5. Die inneren Schleifenindizees sollten in Einerschritten inkrementiert/dekrementiert werden.

6. Minimierung der indirekten Adressierung.

7. Datenausrichtung auf 16 Byte-Grenzen (für SSE-Instruktionen) bzw. auf 32 Byte-Grenzen (für AVX-Instruktionen). Datenstrukturen, die man generiert, sollten ebenfalls ein Alignment besitzen .

8. Nutzung von effizientem Speicherzugriff.

a. Daten sollten während ihrer Berechnung möglichst nah am CPU-Kern im Cache sein (Datenlokalität).

b. Es lohnt sich eine Struktur von Arrays (SOA) statt eines Arrays mit komplexer Struktur (ASO) zu wählen. Ein Beispiel wäre, dass man für die Behandlung dreidimensionaler Koordinaten statt eines zweidimensionalen Arrays mit drei Komponenten (x, y und z) jeweils drei eindimensionale Felder mit den x-, y- und z-Elementen speichert. Bei der AOS-Struktur in diesem Beispiel, wird die SIMD-Einheit in jedem Schleifendurchlauf maximal zu 75% genutzt, da eine vierte Komponente fehlt. Teilweise wird die SIMD-Einheit sogar nur zu 25% genutzt. Im Gegensatz dazu werden beim SOA-Konzept die eindimensionalen X-, Y- und Z-Vektoren optimal ausgewertet. Alle vier SIMD-Register werden dann parallel eingesetzt und damit eine 100-prozentige Ausnutzung gewährleistet.

c. Zuletzt sei hier auch noch erwähnt, dass man bei Nutzung von mehrdimensionalen Arrays auf die reihenorientierte Abspeicherung der Elemente achten muss. Das bedeutet, dass man bei „nested“-Schleifen den innersten Schleifenindex mit dem letzten Arrayindex benutzt.

SIMD-Leistungsvergleiche

Zunächst werden wir verschiedene kleinere Algorithmen im direkten Vergleich von SSE zu AVX behandeln. Wie erwartet (Tabelle 1) erzielt die AVX-Vektorisierung aufgrund seiner doppelten AVX-Registerbreite ein Ergebnis, das bei der Addition und Multiplikation nahe bei dem Speed-Up-Faktor von 2 liegt. Die Determinantenberechnung, basierend auf der Laplaceformel, rechnet acht mal (4×4) Determinanten nacheinander aus. Generell kann man sagen, dass einfach strukturierte, datenintensive Algorithmen gegenüber speicherintensiven Algorithmen im Vorteil sind.

Das zweite Beispiel rendert die Pixel in fortlaufenden Frames innerhalb einer Videosequenz. Bei Videos und Spielen zeigt sich das Potenzial von SIMD. SIMD gewährleistet hohe Bildraten (Frames per seconds = FPS). Das Programm verarbeitet parallel mit Hilfe von AVX „8 float“-Matrix-Datentypelemente, um eine gitternetzbasierende Simulation von seperaten Leinendecken-Objekten zu bewerkstelligen (Bild 4). Bei dieser Implementierung einer Bildberechnung kommt u.a. das oben beschriebene schnellere SOA-Konzept zum Einsatz. Die Ergebnisse in Tabelle 2 zeigen, dass man per Vektorisierung erhebliche Speedup-Gewinne verzeichnet. SSE ergibt mit seinen gleichzeitigen 4 float-Operationen fast den maximal zu erreichenden Speedup-Faktor von 4 gegenüber dem nicht vektorisierten Programm. AVX bringt dann zusätzlich noch einmal fast 40% Leistungszuwachs. Das die Ideal-Speedupfaktoren nicht ganz erreicht werden, ist der Tatsache geschuldet, dass nicht alle Leinendeckenobjekte klein genug sind, um in den L1-Cache zu passen und deshalb zwischendurch aus dem Speicher nachgeladen werden müssen.

Edmund Preiss

: Edmund Preiss ist Manager für das Business Development der Intel Softwareentwicklungswerkzeuge in EMEA.

(sb)

Sie möchten gerne weiterlesen?

Unternehmen

Intel GmbH

Dornacher Straße 1
85622 Feldkirchen
Germany