Automatische Vektorisierung - Automatic vectorization

Die automatische Vektorisierung bei der parallelen Berechnung ist ein Sonderfall der automatischen Parallelisierung , bei der ein Computerprogramm von einer skalaren Implementierung, die jeweils ein einzelnes Operandenpaar verarbeitet , in eine Vektorimplementierung umgewandelt wird , die eine Operation auf mehreren Paaren von . verarbeitet Operanden auf einmal. Moderne konventionelle Computer, einschließlich spezialisierter Supercomputer , verfügen beispielsweise typischerweise über Vektoroperationen , die gleichzeitig Operationen wie die folgenden vier Hinzufügungen ausführen (über SIMD- oder SPMD- Hardware):

{\begin{aligned}c_{1}&=a_{1}+b_{1}\\c_{2}&=a_{2}+b_{2}\\c_{3}&=a_ {3}+b_{3}\\c_{4}&=a_{4}+b_{4}\end{ausgerichtet}}

In den meisten Programmiersprachen schreibt man jedoch typischerweise Schleifen, die sequentiell viele Zahlen addieren. Hier ist ein Beispiel für eine solche Schleife, geschrieben in C :

for (i = 0; i < n; i++)
    c[i] = a[i] + b[i];

Ein vektorisierender Compiler wandelt solche Schleifen in Sequenzen von Vektoroperationen um. Diese Vektoroperationen ausführen Additions auf Blöcke von Elementen aus der Arrays a, bund c. Die automatische Vektorisierung ist ein wichtiges Forschungsthema in der Informatik.

Hintergrund

Frühe Computer hatten normalerweise eine Logikeinheit, die jeweils einen Befehl an einem Operandenpaar ausführte. Computersprachen und -programme wurden daher entworfen, um nacheinander ausgeführt zu werden. Moderne Computer können jedoch viele Dinge gleichzeitig tun. Daher führen viele optimierende Compiler eine automatische Vektorisierung durch, bei der Teile von sequentiellen Programmen in parallele Operationen umgewandelt werden.

Die Schleifenvektorisierung transformiert prozedurale Schleifen, indem sie jedem Operandenpaar eine Verarbeitungseinheit zuweist. Programme verbringen die meiste Zeit in solchen Schleifen. Daher kann die Vektorisierung sie erheblich beschleunigen, insbesondere bei großen Datensätzen. Loop Vektorisierung wird in implementiert Intel 's MMX , SSE und AVX , in Strom ISA ' s AltiVec und in ARM ‚s NEON , SVE und SVE2 Befehlssätze.

Viele Einschränkungen verhindern oder behindern die Vektorisierung. Manchmal kann die Vektorisierung die Ausführung verlangsamen, zum Beispiel aufgrund der Pipeline- Synchronisation oder des Datenbewegungs-Timings. Die Schleifenabhängigkeitsanalyse identifiziert Schleifen, die vektorisiert werden können, und stützt sich dabei auf die Datenabhängigkeit der Anweisungen in Schleifen.

Garantien

Die automatische Vektorisierung muss wie jede Schleifenoptimierung oder andere Optimierung zur Kompilierzeit das Programmverhalten genau beibehalten.

Datenabhängigkeiten

Alle Abhängigkeiten müssen während der Ausführung berücksichtigt werden, um falsche Ergebnisse zu vermeiden.

Im Allgemeinen können schleifeninvariante Abhängigkeiten und lexikalisch vorwärts gerichtete Abhängigkeiten leicht vektorisiert und lexikalisch rückwärts gerichtete Abhängigkeiten in lexikalisch vorwärts gerichtete Abhängigkeiten transformiert werden. Diese Transformationen müssen jedoch sicher durchgeführt werden, um sicherzustellen, dass die Abhängigkeit zwischen allen Aussagen originalgetreu bleibt.

Zyklische Abhängigkeiten müssen unabhängig von den vektorisierten Anweisungen verarbeitet werden.

Datengenauigkeit

Integer Präzision (Bitgröße) muss während der Vektorbefehlsausführung gehalten werden. Die richtige Vektoranweisung muss basierend auf der Größe und dem Verhalten der internen ganzen Zahlen ausgewählt werden. Außerdem muss bei gemischten Integer-Typen besonders darauf geachtet werden, dass sie korrekt hochgestuft/herabgestuft werden, ohne die Genauigkeit zu verlieren. Besondere Vorsicht ist bei der Vorzeichenerweiterung (da mehrere Ganzzahlen in das gleiche Register gepackt sind) und bei Schiebeoperationen oder Operationen mit Übertragsbits , die sonst berücksichtigt würden, geboten.

Die Gleitkomma- Präzision muss ebenfalls beibehalten werden, es sei denn, die IEEE-754- Konformität wird deaktiviert. In diesem Fall sind die Vorgänge schneller, die Ergebnisse können jedoch geringfügig abweichen. Große Variationen, selbst das Ignorieren von IEEE-754, deuten normalerweise auf einen Programmierfehler hin.

Theorie

Um ein Programm zu vektorisieren, muss der Optimierer des Compilers zunächst die Abhängigkeiten zwischen den Anweisungen verstehen und sie gegebenenfalls neu ausrichten. Sobald die Abhängigkeiten abgebildet sind, muss der Optimierer die Implementierungsbefehle richtig anordnen, indem er geeignete Kandidaten in Vektorbefehle ändert, die mit mehreren Datenelementen arbeiten.

Aufbau des Abhängigkeitsgraphen

Der erste Schritt besteht darin, den Abhängigkeitsgraph zu erstellen und zu identifizieren, welche Anweisungen von welchen anderen Anweisungen abhängen. Dies beinhaltet das Untersuchen jeder Anweisung und das Identifizieren jedes Datenelements, auf das die Anweisung zugreift, die Zuordnung von Array-Zugriffsmodifikatoren zu Funktionen und die Überprüfung der Abhängigkeit jedes Zugriffs von allen anderen in allen Anweisungen. Die Alias-Analyse kann verwendet werden, um zu bestätigen, dass die verschiedenen Variablen auf denselben Bereich im Speicher zugreifen (oder ihn überschneiden).

Der Abhängigkeitsgraph enthält alle lokalen Abhängigkeiten mit einem Abstand nicht größer als die Vektorgröße. Wenn das Vektorregister also 128 Bit und der Array-Typ 32 Bit hat, ist die Vektorgröße 128/32 = 4. Alle anderen nicht-zyklischen Abhängigkeiten sollten die Vektorisierung nicht ungültig machen, da es keinen gleichzeitigen Zugriff in der gibt gleiche Vektoranweisung.

Angenommen, die Vektorgröße entspricht 4 Ints:

for (i = 0; i < 128; i++) {
    a[i] = a[i-16]; // 16 > 4, safe to ignore
    a[i] = a[i-1]; // 1 < 4, stays on dependency graph
}

Clustering

Mithilfe des Graphen kann der Optimierer dann die stark verbundenen Komponenten (SCC) clustern und vektorisierbare Anweisungen vom Rest trennen.

Betrachten Sie beispielsweise ein Programmfragment, das drei Anweisungsgruppen innerhalb einer Schleife enthält: (SCC1+SCC2), SCC3 und SCC4, in dieser Reihenfolge, in der nur die zweite Gruppe (SCC3) vektorisiert werden kann. Das endgültige Programm enthält dann drei Schleifen, eine für jede Gruppe, wobei nur die mittlere vektorisiert ist. Der Optimierer kann die erste mit der letzten nicht verbinden, ohne die Ausführungsreihenfolge der Anweisung zu verletzen, was die notwendigen Garantien ungültig machen würde.

Idiome erkennen

Einige nicht offensichtliche Abhängigkeiten können basierend auf bestimmten Idiomen weiter optimiert werden.

Zum Beispiel können die folgenden Eigendatenabhängigkeiten vektorisiert werden, weil der Wert der rechten Werte ( RHS ) geholt und dann auf dem linken Wert gespeichert wird, sodass sich die Daten innerhalb der Zuweisung nicht ändern können.

a[i] = a[i] + a[i+1];

Die Selbstabhängigkeit von Skalaren kann durch Variablenelimination vektorisiert werden .

Rahmenbedingungen

Der allgemeine Rahmen für die Schleifenvektorisierung ist in vier Phasen unterteilt:

Vorwort : Wo die schleifenunabhängigen Variablen für die Verwendung in der Schleife vorbereitet sind. Dies beinhaltet normalerweise das Verschieben in Vektorregister mit spezifischen Mustern, die in Vektorbefehlen verwendet werden. Hier kann auch die Laufzeitabhängigkeitsprüfung eingefügt werden. Wenn die Prüfung entscheidet, dass eine Vektorisierung nicht möglich ist, verzweigen Sie zu Cleanup .
Schleife(n) : Alle vektorisierten (oder nicht) Schleifen, getrennt durch SCCs-Cluster in der Reihenfolge ihres Auftretens im Originalcode.
Nachspiel : Gib alle schleifenunabhängigen Variablen, Induktionen und Reduktionen zurück.
Bereinigung : Implementieren Sie einfache (nicht vektorisierte) Schleifen für Iterationen am Ende einer Schleife, die kein Vielfaches der Vektorgröße sind, oder wenn Laufzeitprüfungen die Vektorverarbeitung verbieten.

Laufzeit vs. Kompilierzeit

Einige Vektorisierungen können zur Kompilierzeit nicht vollständig überprüft werden. Bibliotheksfunktionen können beispielsweise die Optimierung zunichte machen, wenn die von ihnen verarbeiteten Daten vom Aufrufer bereitgestellt werden. Auch in diesen Fällen kann die Laufzeitoptimierung Schleifen im laufenden Betrieb vektorisieren.

Diese Laufzeitprüfung wird in der Vorstufe durchgeführt und leitet den Fluss nach Möglichkeit auf vektorisierte Anweisungen um, ansonsten kehrt sie zur Standardverarbeitung zurück, abhängig von den Variablen, die an die Register oder skalaren Variablen übergeben werden.

Der folgende Code kann zur Kompilierzeit leicht vektorisiert werden, da er nicht von externen Parametern abhängig ist. Auch die Sprache garantiert , dass weder die gleiche Region im Speicher als jede andere Variable besetzen, da sie lokale Variablen und leben nur in der Ausführung sind Stapel .

int a[128];
int b[128];
// initialize b

for (i = 0; i<128; i++)
    a[i] = b[i] + 5;

Andererseits enthält der folgende Code keine Informationen zu Speicherpositionen, da die Referenzen Zeiger sind und sich der Speicher, auf den sie zeigen, überlappen kann.

void compute(int *a, int *b)
{
    int i;
    for (i = 0; i < 128; i++, a++, b++)
        *a = *b + 5;
}

Eine schnelle Laufzeitprüfung der Adresse von a und b sowie des Schleifeniterationsraums (128) reicht aus, um festzustellen, ob sich die Arrays überlappen oder nicht, wodurch Abhängigkeiten aufgedeckt werden.

Es gibt einige Tools, um bestehende Anwendungen dynamisch zu analysieren, um das inhärente latente Potenzial für SIMD-Parallelismus zu bewerten, das durch weitere Compiler-Fortschritte und/oder durch manuelle Codeänderungen ausgenutzt werden kann.

Techniken

Ein Beispiel wäre ein Programm zum Multiplizieren von zwei Vektoren numerischer Daten. Ein skalarer Ansatz wäre etwa:

for (i = 0; i < 1024; i++)
    c[i] = a[i] * b[i];

Dies könnte vektorisiert werden, um etwa so auszusehen:

for (i = 0; i < 1024; i += 4)
    c[i:i+3] = a[i:i+3] * b[i:i+3];

Hier repräsentiert c[i:i+3] die vier Array-Elemente von c[i] bis c[i+3] und der Vektorprozessor kann vier Operationen für einen einzelnen Vektorbefehl ausführen. Da die vier Vektoroperationen ungefähr in der gleichen Zeit wie ein skalarer Befehl abgeschlossen sind, kann der Vektoransatz bis zu viermal schneller als der ursprüngliche Code ausgeführt werden.

Es gibt zwei unterschiedliche Compiler-Ansätze: Einer basiert auf der herkömmlichen Vektorisierungstechnik und der andere basiert auf dem Entrollen von Schleifen .

Automatische Vektorisierung auf Schleifenebene

Diese Technik, die für konventionelle Vektormaschinen verwendet wird, versucht, SIMD-Parallelität auf Schleifenebene zu finden und auszunutzen. Es besteht aus zwei Hauptschritten wie folgt.

Finden Sie eine innerste Schleife, die vektorisiert werden kann
Transformiere die Schleife und erzeuge Vektorcodes

Im ersten Schritt sucht der Compiler nach Hindernissen, die eine Vektorisierung verhindern können. Ein Haupthindernis für die Vektorisierung ist die wahre Datenabhängigkeit, die kürzer als die Vektorlänge ist. Andere Hindernisse sind Funktionsaufrufe und kurze Iterationszählungen.

Sobald festgestellt wurde, dass die Schleife vektorisierbar ist, wird die Schleife um die Vektorlänge gestreift und jeder Skalarbefehl innerhalb des Schleifenkörpers wird durch den entsprechenden Vektorbefehl ersetzt. Im Folgenden werden die Komponententransformationen für diesen Schritt anhand des obigen Beispiels gezeigt.

Nach dem Stripminen

for (i = 0; i < 1024; i += 4)
    for (j = 0; j < 4; j++)
        c[i+j] = a[i+j] * b[i+j];

After-Loop-Verteilung mit temporären Arrays

for (i = 0; i < 1024; i += 4)
{
    for (j = 0; j < 4; j++) tA[j] = A[i+j];
    for (j = 0; j < 4; j++) tB[j] = B[i+j];
    for (j = 0; j < 4; j++) tC[j] = tA[j] * tB[j];
    for (j = 0; j < 4; j++) C[i+j] = tC[j];
}

Nach dem Ersetzen durch Vektorcodes

for (i = 0; i < 1024; i += 4)
{
    vA = vec_ld(&A[i]);
    vB = vec_ld(&B[i]);
    vC = vec_mul(vA, vB);
    vec_st(vC, &C[i]);
}

Automatische Vektorisierung auf Blockebene

Diese relativ neue Technik zielt speziell auf moderne SIMD-Architekturen mit kurzen Vektorlängen ab. Obwohl Schleifen entrollt werden können, um das Ausmaß der SIMD-Parallelität in Basisblöcken zu erhöhen, nutzt diese Technik die SIMD-Parallelität innerhalb von Basisblöcken anstelle von Schleifen. Die zwei wichtigsten Schritte sind wie folgt.

Die innerste Schleife wird um einen Faktor der Vektorlänge abgerollt, um einen großen Schleifenkörper zu bilden.
Isomorphe Skalarbefehle (die dieselbe Operation ausführen) werden in einen Vektorbefehl gepackt, wenn dies nicht durch Abhängigkeiten verhindert wird.

Um schrittweise Transformationen für diesen Ansatz zu zeigen, wird das gleiche Beispiel erneut verwendet.

Nach dem Abrollen der Schleife (nach der Vektorlänge, in diesem Fall mit 4 angenommen)

for (i = 0; i < 1024; i += 4)
{
    sA0 = ld(&A[i+0]);
    sB0 = ld(&B[i+0]);
    sC0 = sA0 * sB0;
    st(sC0, &C[i+0]);
          ...
    sA3 = ld(&A[i+3]);
    sB3 = ld(&B[i+3]);
    sC3 = sA3 * sB3;
    st(sC3, &C[i+3]);
}

Nach dem Packen

for (i = 0; i < 1024; i += 4)
{
    (sA0, sA1, sA2, sA3) = ld(&A[i+0:i+3]);
    (sB0, sB1, sB2, sB3) = ld(&B[i+0:i+3]);
    (sC0, sC1, sC2, sC3) = (sA0, sA1, sA2, sA3) * (sB0, sB1, sB2, sB3);
    st((sC0, sC1, sC2, sC3), &C[i+0:i+3]);
}

Nach der Codegenerierung

for (i = 0; i < 1024; i += 4)
{
    vA = vec_ld(&A[i]);
    vB = vec_ld(&B[i]);
    vC = vec_mul(vA, vB);
    vec_st(vC, &C[i]);
}

Hier repräsentieren sA1, sB1, ... skalare Variablen und vA, vB und vC repräsentieren Vektorvariablen.

Die meisten automatisch vektorisierenden kommerziellen Compiler verwenden den herkömmlichen Ansatz auf Schleifenebene, mit Ausnahme des IBM XL-Compilers, der beide verwendet.

Bei Vorhandensein von Kontrollfluss

Das Vorhandensein von if-Anweisungen im Schleifenkörper erfordert die Ausführung von Anweisungen in allen Steuerpfaden, um die mehreren Werte einer Variablen zusammenzuführen. Ein allgemeiner Ansatz besteht darin, eine Sequenz von Codetransformationen durchzuführen: Prädikation → Vektorisierung (unter Verwendung einer der obigen Methoden) → Vektorprädikate entfernen → Skalarprädikate entfernen. Wenn der folgende Code als Beispiel verwendet wird, um diese Transformationen zu zeigen;

for (i = 0; i < 1024; i++)
    if (A[i] > 0)
        C[i] = B[i];
    else
        D[i] = D[i-1];

Nach der Vorhersage

for (i = 0; i < 1024; i++)
{
    P = A[i] > 0;
    NP = !P;
    C[i] = B[i];     (P)
    D[i] = D[i-1];   (NP)
}

wobei (P) ein Prädikat bezeichnet, das die Aussage schützt.

Nach der Vektorisierung

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = B[i:i+3];     (vP)
    (NP1, NP2, NP3, NP4) = vNP;
    D[i+3] = D[i+2];         (NP4)
    D[i+2] = D[i+1];         (NP3)
    D[i+1] = D[i];           (NP2)
    D[i]   = D[i-1];         (NP1)
}

Nach dem Entfernen von Vektorprädikaten

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);
    (NP1, NP2, NP3, NP4) = vNP;
    D[i+3] = D[i+2];         (NP4)
    D[i+2] = D[i+1];         (NP3)
    D[i+1] = D[i];           (NP2)
    D[i]   = D[i-1];         (NP1)
}

Nach dem Entfernen von Skalarprädikaten

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);
    (NP1, NP2, NP3, NP4) = vNP;
    if (NP4) D[i+3] = D[i+2];
    if (NP3) D[i+2] = D[i+1];
    if (NP2) D[i+1] = D[i];
    if (NP1) D[i]   = D[i-1];
}

Reduzierung des Vektorisierungsaufwands bei vorhandenem Kontrollfluss

Die Befehle in allen Steuerpfaden im Vektorcode ausführen zu müssen, war einer der Hauptfaktoren, die den Vektorcode in Bezug auf die skalare Basislinie verlangsamen. Je komplexer der Kontrollfluss wird und je mehr Befehle im Skalarcode umgangen werden, desto größer wird der Vektorisierungs-Overhead. Um diesen Vektorisierungs-Overhead zu reduzieren, können Vektorverzweigungen eingefügt werden, um Vektorbefehle zu umgehen, ähnlich wie skalare Verzweigungen skalare Befehle umgehen. Im Folgenden werden AltiVec-Prädikate verwendet, um zu zeigen, wie dies erreicht werden kann.

Skalare Basislinie (Originalcode)

for (i = 0; i < 1024; i++)
{
    if (A[i] > 0)
    {
        C[i] = B[i];
        if (B[i] < 0)
            D[i] = E[i];
    }
}

Nach Vektorisierung in Gegenwart von Kontrollfluss

for (i = 0; i < 1024; i += 4)
{
    vPA = A[i:i+3] > (0, 0, 0, 0);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);
    vT = B[i:i+3] < (0,0,0,0);
    vPB = vec_sel((0, 0, 0, 0), vT, vPA);
    D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);
}

Nach dem Einfügen von Vektorzweigen

for (i = 0; i < 1024; i += 4)
{
    if (vec_any_gt(A[i:i+3], (0, 0, 0, 0)))
    {
        vPA = A[i:i+3] > (0,0,0,0);
        C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);
        vT = B[i:i+3] < (0, 0, 0, 0);
        vPB = vec_sel((0, 0, 0, 0), vT, vPA);
        if (vec_any_ne(vPB, (0, 0, 0, 0)))
            D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);
    }
}

Im endgültigen Code mit Vektorverzweigungen sind zwei Dinge zu beachten; Zuerst wird die Prädikatsdefinitionsanweisung für vPA auch in den Körper des äußeren Vektorzweigs eingeschlossen, indem vec_any_gt verwendet wird. Zweitens hängt die Rentabilität des inneren Vektorzweigs für vPB von der bedingten Wahrscheinlichkeit ab, dass vPB falsche Werte in allen Feldern hat, wenn vPA falsche Werte in allen Feldern hat.

Betrachten Sie ein Beispiel, bei dem die äußere Verzweigung in der skalaren Basislinie immer genommen wird und die meisten Anweisungen im Schleifenkörper umgangen werden. Der obige Zwischenfall ohne Vektorverzweigungen führt alle Vektorbefehle aus. Der endgültige Code mit Vektorverzweigungen führt sowohl den Vergleich als auch die Verzweigung im Vektormodus aus, wodurch möglicherweise die Leistung über der skalaren Basislinie erhöht wird.

Manuelle Vektorisierung

In den meisten C- und C++- Compilern ist es auf Kosten des Programmieraufwands und der Wartbarkeit möglich, intrinsische Funktionen zur manuellen Vektorisierung zu verwenden .

Siehe auch

Verweise

Languages

In other projects