Was ist "Vektorisierung"?

188

Mehrmals bin ich auf diesen Begriff in matlab, fortran ... einem anderen ... gestoßen, aber ich habe nie eine Erklärung gefunden, was er bedeutet und was er tut. Ich frage hier also, was ist Vektorisierung und was bedeutet es zum Beispiel, dass "eine Schleife vektorisiert ist"?

Thomas Geritzma
quelle
1
@geoffspear Der Link scheint auf en.wikipedia.org/wiki/Array_programming
Ich mag es, den

Antworten:

221

Viele CPUs verfügen über "Vektor" - oder "SIMD" -Befehlssätze, die dieselbe Operation gleichzeitig auf zwei, vier oder mehr Daten anwenden. Moderne x86-Chips haben die SSE-Anweisungen, viele PPC-Chips haben die "Altivec" -Anweisungen und sogar einige ARM-Chips haben einen Vektorbefehlssatz namens NEON.

"Vektorisierung" (vereinfacht) ist der Prozess des Umschreibens einer Schleife, so dass anstelle eines einzelnen Elements eines Arrays N-mal 4 Elemente des Arrays gleichzeitig N / 4-mal verarbeitet werden.

(Ich habe 4 gewählt, weil es das ist, was moderne Hardware am wahrscheinlichsten direkt unterstützt. Der Begriff "Vektorisierung" wird auch verwendet, um eine übergeordnete Softwaretransformation zu beschreiben, bei der Sie die Schleife möglicherweise vollständig abstrahieren und nur den Betrieb von Arrays anstelle der Elemente beschreiben das umfasst sie)


Der Unterschied zwischen Vektorisierung und Abrollen von Schleifen: Betrachten Sie die folgende sehr einfache Schleife, die die Elemente von zwei Arrays hinzufügt und die Ergebnisse in einem dritten Array speichert.

for (int i=0; i<16; ++i)
    C[i] = A[i] + B[i];

Das Abrollen dieser Schleife würde sie in etwa Folgendes verwandeln:

for (int i=0; i<16; i+=4) {
    C[i]   = A[i]   + B[i];
    C[i+1] = A[i+1] + B[i+1];
    C[i+2] = A[i+2] + B[i+2];
    C[i+3] = A[i+3] + B[i+3];
}

Wenn man es dagegen vektorisiert, entsteht so etwas:

for (int i=0; i<16; i+=4)
    addFourThingsAtOnceAndStoreResult(&C[i], &A[i], &B[i]);

Wobei "addFourThingsAtOnceAndStoreResult" ein Platzhalter für alle Eigenheiten ist, die Ihr Compiler zum Angeben von Vektoranweisungen verwendet. Beachten Sie, dass einige Compiler sehr einfache Schleifen wie diese automatisch vektorisieren können, die häufig über eine Kompilierungsoption aktiviert werden können. Komplexere Algorithmen erfordern immer noch die Hilfe des Programmierers, um einen guten Vektorcode zu generieren.

Stephen Canon
quelle
11
Was ist der Unterschied zwischen diesem und dem Abwickeln / Abrollen der Schleife?
Jeremy Powell
1
Stimmt es nicht, dass ein Compiler es leichter haben würde, die entrollte Schleife automatisch zu vektorisieren?
Nikos Athanasiou
@NikosAthanasiou: Es ist plausibel, aber im Allgemeinen sollte ein Compiler in der Lage sein, jede Schleife automatisch zu automatisieren, da beide recht einfach sind.
Stephen Canon
1
@StephenCanon Wie kann man überprüfen, ob einige Linien vektorisiert wurden oder nicht? Wenn man objdump verwenden würde, wonach würde man in der Ausgabe von objdump suchen?
user1823664
3
@Shuklaswag: Vektorisierung ist etwas, das Compiler für Sie tun können, aber es ist auch etwas, das Programmierer explizit selbst tun. Das Betriebssystem ist nicht beteiligt.
Stephen Canon
32

Vektorisierung ist der Begriff für die Konvertierung eines Skalarprogramms in ein Vektorprogramm. Vektorisierte Programme können mehrere Operationen mit einem einzigen Befehl ausführen, während Skalar nur mit Operandenpaaren gleichzeitig arbeiten kann.

Aus Wikipedia :

Skalaransatz:

for (i = 0; i < 1024; i++)
{
   C[i] = A[i]*B[i];
}

Vektorisierter Ansatz:

for (i = 0; i < 1024; i+=4)
{
   C[i:i+3] = A[i:i+3]*B[i:i+3];
}
Anders
quelle
Ist das nicht im Wesentlichen dasselbe wie der skalare Ansatz? Ihre Syntax und Ihr Loop-Fortschritt sind unterschiedlich, aber darunter multiplizieren Sie sie immer noch viermal. Aber irgendwie wird es schneller sein, wahrscheinlich hat die CPU Anweisungen, die einen Trick namens Vectorization ausführen.
mskw
Sieht so aus, als würde ich hier meine eigene Frage beantworten. Die Syntax im Vektorisierungsansatz übersetzt sie, wenn der Complier dies sieht, in optimierte CPU-Anweisungen, die Vektoren multiplizieren. Wie SIMD.
mskw
10

Es bezieht sich auf die Fähigkeit, eine einzelne mathematische Operation an einer Liste - oder einem "Vektor" - von Zahlen in einem einzigen Schritt durchzuführen. Sie sehen es oft bei Fortran, weil dies mit wissenschaftlichem Rechnen verbunden ist, das mit Supercomputing verbunden ist, bei dem die vektorisierte Arithmetik zum ersten Mal auftrat. Heutzutage bieten fast alle Desktop-CPUs eine Form der vektorisierten Arithmetik durch Technologien wie Intels SSE. GPUs bieten auch eine Form der vektorisierten Arithmetik.

Warren Young
quelle
7

Die Vektorisierung wird häufig im wissenschaftlichen Rechnen eingesetzt, wo große Datenmengen effizient verarbeitet werden müssen.

In einer echten Programmieranwendung weiß ich, dass es in NUMPY verwendet wird (ich bin mir anderer nicht sicher).

Numpy (Paket für wissenschaftliches Rechnen in Python) verwendet die Vektorisierung zur schnellen Manipulation von n-dimensionalen Arrays, die im Allgemeinen langsamer ist, wenn integrierte Python-Optionen für die Handhabung von Arrays verwendet werden.

Obwohl es jede Menge Erklärungen gibt, ist hier, was Vektorisierung wie auf der NUMPY DOCUMENTATION-Seite definiert ist

Die Vektorisierung beschreibt das Fehlen expliziter Schleifen, Indizierungen usw. im Code - diese Dinge finden natürlich nur „hinter den Kulissen“ in optimiertem, vorkompiliertem C-Code statt. Vektorisierter Code hat viele Vorteile, darunter:

  1. vektorisierter Code ist prägnanter und leichter zu lesen

  2. Weniger Codezeilen bedeuten im Allgemeinen weniger Fehler

  3. Der Code ähnelt eher der mathematischen Standardnotation (was es normalerweise einfacher macht, mathematische Konstrukte korrekt zu codieren).

  4. Die Vektorisierung führt zu mehr "Pythonic" -Code. Ohne Vektorisierung wäre unser Code mit ineffizienten und schwer lesbaren For-Schleifen übersät.

schlechter Programmierer
quelle
4

Vektorisierung bedeutet in einfachen Worten, den Algorithmus so zu optimieren, dass er SIMD-Anweisungen in den Prozessoren verwenden kann.

AVX, AVX2 und AVX512 sind die Befehlssätze (Intel), die dieselbe Operation für mehrere Daten in einem Befehl ausführen. für zB. AVX512 bedeutet, dass Sie jeweils 16 Ganzzahlwerte (4 Byte) bearbeiten können. Dies bedeutet, dass Sie, wenn Sie einen Vektor mit 16 Ganzzahlen haben und diesen Wert in jeder Ganzzahl verdoppeln und dann 10 hinzufügen möchten. Sie können entweder 16-mal Werte in das allgemeine Register [a, b, c] laden und dieselbe Operation ausführen, oder Sie können dieselbe Operation ausführen, indem Sie alle 16 Werte in SIMD-Register [xmm, ymm] laden und die Operation einmal ausführen. Dies beschleunigt die Berechnung von Vektordaten.

Bei der Vektorisierung nutzen wir dies zu unserem Vorteil, indem wir unsere Daten so umgestalten, dass wir SIMD-Operationen daran ausführen und das Programm beschleunigen können.

Das einzige Problem bei der Vektorisierung sind die Handhabungsbedingungen. Weil Bedingungen den Ausführungsfluss verzweigen. Dies kann durch Maskieren erfolgen. Durch Modellieren der Bedingung in eine arithmetische Operation. z.B. Wenn wir 10 zum Wert hinzufügen möchten, wenn er größer als 100 ist, können wir dies auch.

if(x[i] > 100) x[i] += 10; // this will branch execution flow.

oder wir können die Bedingung in eine arithmetische Operation modellieren, wobei ein Bedingungsvektor c erzeugt wird.

c[i] = x[i] > 100; // storing the condition on masking vector
x[i] = x[i] + (c[i] & 10) // using mask

Dies ist jedoch ein sehr triviales Beispiel. Daher ist c unser Maskierungsvektor, mit dem wir eine binäre Operation basierend auf ihrem Wert ausführen. Dies vermeidet eine Verzweigung des Ausführungsflusses und ermöglicht eine Vektorisierung.

Vektorisierung ist genauso wichtig wie Parallelisierung. Daher sollten wir es so weit wie möglich nutzen. Alle modernen Prozessoren verfügen über SIMD-Anweisungen für hohe Rechenauslastungen. Wir können unseren Code für die Verwendung dieser SIMD-Anweisungen mithilfe der Vektorisierung optimieren. Dies ähnelt der Parallelisierung unseres Codes für die Ausführung auf mehreren Kernen, die auf modernen Prozessoren verfügbar sind.

Ich möchte mit der Erwähnung von OpenMP gehen, mit dem Sie den Code mit Pragmas vektorisieren können. Ich halte es für einen guten Ausgangspunkt. Gleiches gilt für OpenACC.

Marktwarteschlange
quelle
0

Von Intel-Leuten denke ich, ist leicht zu verstehen.

Bei der Vektorisierung wird ein Algorithmus von der gleichzeitigen Bearbeitung eines einzelnen Werts in die gleichzeitige Bearbeitung einer Reihe von Werten konvertiert . Moderne CPUs bieten direkte Unterstützung für Vektoroperationen, bei denen ein einzelner Befehl auf mehrere Daten (SIMD) angewendet wird.

Beispielsweise könnte eine CPU mit einem 512-Bit-Register 16 32-Bit-Doppel mit einfacher Genauigkeit enthalten und eine einzelne Berechnung durchführen.

16-mal schneller als die Ausführung einer einzelnen Anweisung gleichzeitig. Die Kombination mit Threading- und Multi-Core-CPUs führt zu Leistungssteigerungen um Größenordnungen.

Link https://software.intel.com/en-us/articles/vectorization-a-key-tool-to-improve-performance-on-modern-cpus

In Java besteht die Möglichkeit, dass dies in JDK 15 von 2020 oder spät in JDK 16 von 2021 aufgenommen wird.

https://bugs.openjdk.java.net/browse/JDK-8201271

chiperortiz
quelle
-4

Siehe die beiden obigen Antworten. Ich wollte nur hinzufügen, dass der Grund für die Vektorisierung darin besteht, dass diese Operationen von Supercomputern und Multiprozessoren problemlos in Paraell ausgeführt werden können, was einen großen Leistungsgewinn ergibt. Auf Einzelprozessor-Computern gibt es keinen Leistungsgewinn.

Larry Watanabe
quelle
12
"Auf Einzelprozessor-Computern gibt es keinen Leistungsgewinn": nicht wahr. Die meisten modernen Prozessoren bieten (eingeschränkte) Hardware-Unterstützung für die Vektorisierung (SSE, Altivec usw., wie von Stephentyron benannt), was bei Verwendung zu einer erheblichen Beschleunigung führen kann.
Sleske
danke, ich habe vergessen, dass Parallelisierung auch auf dieser Ebene möglich ist.
Larry Watanabe