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

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

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

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

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