Optimiere für schnelle Multiplikation, aber langsame Addition: FMA und doubleouble

9

Als ich einen Haswell-Prozessor bekam, habe ich versucht, FMA zu implementieren, um das Mandelbrot-Set zu bestimmen. Der Hauptalgorithmus ist dies:

%Vor%

Dies bestimmt, ob n Pixel im Mandelbrot-Set sind. Also für Doppel-Gleitpunkt läuft es über 4 Pixel ( floatn = __m256d , intn = __m256i ). Dies erfordert 4 SIMD-Gleitkomma-Multiplikation und vier SIMD-Gleitkomma-Additionen.

Dann habe ich das geändert, um mit FMA so zu arbeiten

%Vor%

wobei mul_add die Aufrufe von _mm256_fmad_pd und mul_sub _mm256_fmsub_pd aufruft. Dieses Verfahren verwendet 4 FMA-SIMD-Operationen und zwei SIMD-Multiplikationen, was zwei weniger arithmetische Operationen als ohne FMA ist. Außerdem können FMA und Multiplikation zwei Ports und nur eine Addition verwenden.

Um meine Tests weniger voreingenommen zu machen, habe ich in einen Bereich gezoomt, der sich vollständig im Mandelbrot-Set befindet, also sind alle Werte maxiter . In diesem Fall ist die Methode mit FMA um 27% schneller. Das ist sicherlich eine Verbesserung, aber der Übergang von SSE zu AVX verdoppelte meine Leistung und ich hoffte auf einen weiteren Faktor zwei mit FMA.

Aber dann habe ich diese Antwort in Bezug auf FMA, wo es heißt

  

Der wichtige Aspekt der fusionierten Multiply-Add-Anweisung ist die (nahezu) unendliche Genauigkeit des Zwischenergebnisses. Dies hilft mit der Leistung, aber nicht so sehr, weil zwei Operationen in einer einzigen Anweisung codiert sind - Es hilft mit der Leistung, weil die virtuell unendliche Genauigkeit des Zwischenergebnisses manchmal wichtig ist, und sehr teuer, mit gewöhnlicher Multiplikation und Addition wiederherzustellen, wenn dieses Niveau von Präzision ist das, wonach der Programmierer sucht.

und gibt später ein Beispiel double * Doppel double-double Multiplikation

%Vor%

Daraus zog ich den Schluss, dass ich FMA nicht optimal implementierte und entschied mich für SIMD double-double. Ich implementierte Double-Double basierend auf dem Papier Gleitkommazahlen mit erweiterter Genauigkeit für die GPU-Berechnung . Das Papier ist für Double-Float, also habe ich es für Double-Double modifiziert. Anstatt einen Doppel-Doppel-Wert in ein SIMD-Register zu packen, packe ich zusätzlich 4 Doppel-Doppelwerte in ein AVX-Hoch-Register und ein AVX-Tief-Register.

Für das Mandelbrot-Set, was ich wirklich brauche, ist doppelte Multiplikation und Addition. In diesem Papier sind dies die Funktionen df64_add und df64_mult . Das Bild unten zeigt die Assembly für meine Funktion df64_mult für Software FMA ( links) und Hardware FMA (rechts). Dies zeigt deutlich, dass Hardware-FMA eine große Verbesserung für Doppel-Doppel-Multiplikation ist.

Wie funktioniert die Hardware-FMA in der Doppel-Mandelbrot-Mengenberechnung? Die Antwort ist, das ist nur etwa 15% schneller als mit Software-FMA. Das ist viel weniger, als ich mir erhofft hatte. Die doppel-doppelte Mandelbrot-Berechnung benötigt 4 Doppel-Doppel-Additionen und vier Doppel-Doppel-Multiplikationen ( x*x , y*y , x*y und 2*(x*y) ). Doch das 2*(x*y) Multiplikation trivial für double-double so kann diese Multiplikation in den Kosten ignoriert werden. Daher ist der Grund, warum ich denke, dass die Verbesserung unter Verwendung von Hardware-FMA so klein ist, dass die Berechnung durch die langsame Doppel-Doppel-Addition dominiert wird (siehe die folgende Zusammenstellung).

Früher war die Multiplikation langsamer als die Addition (und die Programmierer verwendeten mehrere Tricks, um die Multiplikation zu vermeiden), aber bei Haswell scheint es andersherum zu sein. Nicht nur wegen der FMA, sondern auch weil die Multiplikation zwei Ports verwenden kann, aber nur eine Addition.

Also meine Fragen (endlich) sind:

  1. Wie optimiert man, wenn die Addition im Vergleich zur Multiplikation langsam ist?
  2. Gibt es eine algebraische Möglichkeit, meinen Algorithmus zu ändern, um mehr Multiplikationen zu verwenden? und weniger Zusätze? Ich weiß, dass es eine Methode gibt, das Gegenteil zu tun, z. (x+y)*(x+y) - (x*x+y*y) = 2*x*y , die zwei weitere Zusätze für eine Multiplikation weniger verwenden.
  3. Gibt es eine Möglichkeit, die Funktion df64_add einfach zu verwenden (z. B. mit FMA)?

Falls jemand sich fragt, ob die Double-Double-Methode etwa zehnmal langsamer ist als Double. Das ist nicht so schlimm, ich denke, als ob es einen Hardware-Quad-Precision-Typ gäbe, wäre es wahrscheinlich doppelt so langsam wie Double, also ist meine Software-Methode etwa fünfmal langsamer als das, was ich für Hardware erwarten würde, wenn sie existierte.

df64_add assembly

%Vor%     
Z boson 01.06.2015, 12:25
quelle

1 Antwort

4

Um meine dritte Frage zu beantworten, fand ich eine schnellere Lösung für Doppel-Doppel-Zugabe. Ich fand eine alternative Definition in der Arbeit Implementierung von Float-Float-Operatoren für Grafiken Hardware .

%Vor%

So habe ich das (Pseudocode) implementiert:

%Vor%

Diese Definition von Add22 verwendet 11 Additionen statt 20, aber es erfordert zusätzlichen Code, um zu bestimmen, ob |ah| >= |bh| . Hier finden Sie eine Diskussion darüber, wie SIMD minmag und maxmag Funktionen implementiert werden können . Glücklicherweise verwendet der größte Teil des zusätzlichen Codes nicht Port 1. Jetzt gehen nur 12 Anweisungen an Port 1 statt an 20.

Hier ist eine Durchsatzanalyseform IACA für das neue Add22

%Vor%

und hier ist die Durchsatzanalyse von den alten

%Vor%

Eine bessere Lösung wäre, wenn neben der FMA drei Anweisungen für den Operand-Single-Rundungsmodus vorhanden wären. Es scheint mir, dass es Anweisungen für den einfachen Rundungsmodus für

geben sollte %Vor%     
Z boson 04.06.2015 12:20
quelle