Ich habe den folgenden C-Code. Der erste Teil liest einfach eine Matrix komplexer Zahlen aus dem Standard in die Matrix M ein. Der interessante Teil ist der zweite Teil.
Ich kompiliere mit gcc -fopt-info-vec-all -O3 -ffast-math -march=bdver2 permanent-in-c.c -lm . Dies erklärt mir, warum fast keine der Schleifen vektorisiert wird.
Der wichtigste Teil für die Leistung sind die Zeilen 47 - 50, die sind:
%Vor%gcc sagt mir:
%Vor%Wie kann ich die Probleme beheben, die diesen Teil stoppen? vektorisiert?
Seltsamerweise ist dieser Teil vektorisiert, aber ich bin mir nicht sicher warum:
%Vor%Die vollständige Ausgabe von gcc -fopt-info-vec-all -O3 -ffast-math -march = bdver2 permanent-in-cc -lm ist bei Ссылка .
Ich denke, ich hätte es herausgefunden. Nach vielen Versuchen / Irrtümern wurde klar, dass die in gcc eingebauten Vektorisierungsoptimierungen eine Art von hartem Code sind und komplexe Zahlen nicht richtig "verstehen". Ich habe einige Änderungen im Code vorgenommen und die innere Performance-sensitive Schleife vektorisiert, bestätigt durch die gcc-Ausgabe (obwohl ich nicht sicher bin, ob das gewünschte Ergebnis rechnerisch dem entspricht, was Sie wollen). Während mein Verständnis auf das beschränkt ist, was der Code tun soll, ist das Ergebnis, dass es gut funktioniert, wenn Sie real und imag getrennt berechnen. Schau es dir an:
%Vor%Sehen wir uns zuerst den Code genauer an. Wir haben
%Vor% Während delta[] von complex float in OPs Code eingibt, enthält es immer nur -1.0f oder +1.0f . (Außerdem könnten die Berechnungen vereinfacht werden, wenn es stattdessen -2.0f oder +2.0f wäre.) Aus diesem Grund habe ich definiert, dass es so real und nicht komplex ist.
Ähnlich definiert OP s als int , verwendet es aber effektiv nur als -1.0f und +1.0f (in den Berechnungen). Deshalb habe ich es explizit als float definiert.
Ich lasse das f -Array weg, weil es eine triviale Möglichkeit gibt, es vollständig zu vermeiden.
Die erste Schleife des interessanten Teils des Codes,
%Vor% führt mehrere Dinge aus. Es initialisiert alle Elemente im Array delta[] auf 1; es könnte (und sollte wahrscheinlich) in eine separate Schleife aufgeteilt werden.
Da die äußere Schleife in i zunimmt, ist p das Produkt der Elemente in v ; es könnte auch in eine separate Schleife aufgeteilt werden.
Da die innere Schleife alle Elemente in der Spalte i bis v[i] summiert, addiert die äußere und die innere Schleife einfach jede Zeile als Vektor zum Vektor v .
Wir können also das obige im Pseudocode als neu schreiben
%Vor%
Als nächstes schauen wir uns die zweite verschachtelte Schleife an:
Es ist schwer zu sehen, es sei denn, Sie untersuchen die Werte von j , während die Schleife fortschreitet, aber die letzten 4 Zeilen im Körper der äußeren Schleife implementieren die OEIS A007814 Integerfolge in j (0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4, ... ). Die Anzahl der Iterationen in dieser Schleife beträgt 2 Zeilen -1. Dieser Teil der Sequenz ist symmetrisch und implementiert einen binären Baum der Höhe rows-1:
Es stellt sich heraus, dass, wenn wir eine Schleife über i = 1 .. 2 rows-1 machen, r die Anzahl von null niedrigen Bits in i ist. GCC bietet eine integrierte __builtin_ctz() Funktion, die genau das berechnet. (Beachten Sie, dass __builtin_ctz(0) einen undefinierten Wert ergibt; also tun Sie das nicht, auch wenn es einen bestimmten Wert auf Ihrem Computer erzeugt.)
Die innere Schleife subtrahiert die komplexen Werte in der Zeile j der Matrix, skaliert mit 2*delta[j] , aus dem Vektor v[] . Sie berechnet auch das Produkt der komplexen Einträge in Vektor v[] (nach der Subtraktion) in die Variable prod .
Nach der inneren Schleife wird delta[j] ebenso wie der Skalierungsfaktor s negiert. Der Wert der Variablen prod , skaliert von s , wird zu p hinzugefügt.
Nach der Schleife ist das endgültige (komplexe) Ergebnis p dividiert durch 2 rows-1 . Dies ist besser mit der ldexp() C99-Funktion (separat auf der realen und komplexen Teile).
Wir können daher die zweite verschachtelte Schleife im Pseudocode als neu schreiben
%Vor%Nach meiner Erfahrung ist es am besten, die Real- und Imaginärteile in separate Vektoren und Matrizen aufzuteilen. Betrachten Sie die folgenden Definitionen:
%Vor% Alle oben genannten werden leicht vektorisiert, solange float_malloc() ausreichend ausgerichtete Zeiger liefert (und dem Compiler wird mitgeteilt, dass zB über das GCC Funktionsattribut __attribute__ ((__assume_aligned__ (BYTES_IN_VECTOR))); ) und das floats_per_row Mitglied in der Matrix a ist Vielfaches der Anzahl der Floats in einem Vektor.
(Ich weiß nicht, ob GCC die obigen Funktionen automatisch vektorisieren kann, aber ich weiß, dass sie mithilfe der GCC-Vektorerweiterungen "von Hand" vektorisiert werden können.)
Mit dem obigen wird der gesamte interessante Teil des Codes in Pseudo-C
%Vor%An dieser Stelle würde ich das Obige ohne Vektorisierung persönlich implementieren, dann ausgiebig testen, bis ich sicher war, dass es richtig funktioniert.
Dann würde ich die GCC-Assembly-Ausgabe ( -S ) untersuchen, um zu sehen, ob sie die einzelnen Operationen (die Funktionen, die ich zuvor aufgelistet habe) ausreichend vektorisieren kann.
Hand-Vektorisierung der Funktionen mit GCC-Vektor-Erweiterungen ist ziemlich einfach. Einen Float-Vektor zu deklarieren ist trivial:
%Vor% Die einzelnen Komponenten in jedem Vektor können mit der Array-Notation ( v[0] und v[1] für vec2f v; ) adressiert werden. GCC kann grundlegende Operationen an ganzen Vektoren elementweise durchführen; Wir brauchen hier nur Addition und Multiplikation. Horizontale Operationen (Operationen, die zwischen Elementen in demselben Vektor angewendet werden) sollten vermieden werden und stattdessen Elemente neu geordnet werden.
GCC wird Arbeitscode für die obigen Vektorgrößen selbst auf Architekturen ohne solche Vektorisierung erzeugen, aber der resultierende Code kann langsam sein. (GCC-Versionen bis mindestens 5.4 generieren viele unnötige Bewegungen, typischerweise zum Stapeln und Zurückspielen.)
Der für einen Vektor zugewiesene Speicher muss ausreichend ausgerichtet sein. malloc() bietet nicht in allen Fällen ausreichend ausgerichteten Speicher; Sie sollten stattdessen posix_memalign() verwenden.Das Attribut aligned kann verwendet werden, um die Ausrichtung zu erhöhen, die GCC für den Vektortyp verwendet, wenn einer lokal oder statisch zugewiesen wird. In einer Matrix müssen Sie sicherstellen, dass die Zeilen an einer ausreichend ausgerichteten Grenze beginnen. das ist der Grund, warum ich die Variable floats_per_row in der Struktur habe.
In Fällen, in denen die Anzahl der Elemente in einem Vektor (oder in einer Zeile) groß ist, aber nicht ein Vielfaches der Anzahl der Floats in einem Vektor, sollten Sie den Vektor mit "inerten" Werten auffüllen - Werte, die keinen Einfluss haben das Ergebnis, wie 0.0f für Addition und Subtraktion und 1.0f für Multiplikation.
Mindestens auf x86 und x86-64 erzeugt GCC besseren Code für Schleifen, die nur Zeiger verwenden. Zum Beispiel, dies
%Vor%ergibt besseren Code als
%Vor%oder
%Vor%(die dazu neigen, einen ähnlichen Code zu erzeugen). Persönlich würde ich es als implementieren
%Vor% und float_copy() als
oder etwas in der Nähe.
Am schwierigsten zu Vektorisieren ist complex_float_product() . Wenn Sie die nicht verwendeten Elemente im endgültigen Vektor mit 1.0f für den realen Teil und 0.0f für den imaginären Teil ausfüllen, können Sie das komplexe Produkt für jeden Vektor einfach berechnen. Denk daran,
( a + b ) ( c d ) c - b d d d d i> b c ) i
Der schwierige Teil ist hier, das komplexe Produkt für die Elemente im Vektor effizient zu berechnen. Glücklicherweise ist dieser Teil überhaupt nicht kritisch für die Gesamtleistung (außer für sehr kurze Vektoren oder Matrizen mit sehr wenigen Spalten), daher sollte in der Praxis nicht viel ausmachen.
(Kurz gesagt, der "harte" Teil besteht darin, die Elemente neu zu ordnen, um die gepackte Vektormultiplikation maximal zu verwenden, und nicht so viele Shuffle / Moves, um sie zu verlangsamen.)
Für die Funktion float_add_scaled() sollten Sie einen Vektor erstellen, der mit dem Skalierungsfaktor gefüllt ist. etwas wie das Folgende,
wenn wir die Alignment- und Size-Checks und die Fallback-Implementierung ignorieren.
Optimizer Protokolle zeigen deutlich
Unbekannte Ausrichtung für den Zugriff: ...
beim Versuch, zu vektorisieren
%Vor% Es scheint wirklich verknüpft zu sein, dass Sie die Ausrichtung Ihrer Arrays M , delta und v im Speicher erzwingen müssen.
Auto-Vektorisierung in GCC
Behandlung von ausgerichteten Speicherzugriffen (versuchen Sie nicht, Loops mit nicht ausgerichteten Zugriffen zu vektorisieren)
Wie in früheren Kommentaren erwähnt, würde ich vorschlagen, dass Sie posix_memalign für diesen Zweck verwenden.
Was ist Ihre Zielumgebung? (OS, CPU)
Sehen Sie sich bitte Daten-Alignment-to-Assist-Vectorization
Tags und Links c gcc auto-vectorization