Beschleunigung x64 Assembler ADD Schleife

Question

Ich arbeite an Arithmetik für die Multiplikation sehr langer Ganzzahlen (einige 100.000 Dezimalziffern). Als Teil meiner Bibliothek füge ich zwei lange Zahlen hinzu.

Profiling zeigt, dass mein Code bis zu 25% seiner Zeit in den add() und sub() Routinen läuft, also ist es wichtig, dass sie so schnell wie möglich sind. Aber ich sehe noch nicht viel Potenzial. Vielleicht können Sie mir Hilfe, Rat, Einsicht oder Ideen geben. Ich werde sie testen und zu dir zurückkommen.

Bisher hat meine add-Routine einige Setup und verwendet dann eine 8-mal abgerollt Schleife:

mov rax, QWORD PTR [rdx+r11*8-64] 
mov r10, QWORD PTR [r8+r11*8-64] 
adc rax, r10 
mov QWORD PTR [rcx+r11*8-64], rax 

7 weitere Blöcke mit unterschiedlichen Offsets folgen und dann in einer Schleife es.

Ich habe versucht, die Werte aus dem Speicher früher zu laden, aber das hat nicht geholfen. Ich denke, das liegt an einem guten Prefetching. Ich benutze eine Intel i7-3770 Ivy Bridge 4-Core-CPU. Aber ich möchte Code schreiben, der auf jeder modernen CPU gut funktioniert.

Bearbeiten: Ich habe einige Timings: Es fügt 1k Wörter in etwa 2,25 Zyklen/Wort. Wenn ich den ADC entferne, so bleiben nur die MOVs übrig, es dauert immer noch etwa 1,95 Zyklen/Wort. Der größte Engpass scheint also der Speicherzugriff zu sein. Eine Bibliothek memcpy() arbeitet in etwa 0,65 Zyklen/Wort, hat aber nur einen Eingang, nicht zwei. Trotzdem ist es viel schneller wegen der Verwendung von SSE-Registern, denke ich.

Einige Fragen:

• Ist es sinnvoll Struktur zu verwenden, "Last, Last, einzugeben, zu speichern" oder wäre eine "Last, Add-to-memory" helfen? Bisher zeigten meine Tests keine Vorteile.
• Wie üblich, gibt es keine Hilfe von SSE (2,3,4) zu erwarten?
• Beeinträchtigt die Adressierung (skalierter Index plus Basis plus Offset) stark? Ich könnte stattdessen ADD r11, 8 verwenden.
• Was ist mit der Schleife abrollen? Ich habe gelesen, dass das Abrollern für die Sandy-Bridge-Architektur schlecht war (Agner Fog http://www.agner.org/optimize/). Soll es bevorzugt oder vermieden werden?
• (Bearbeiten) Kann ich SSE-Register verwenden, um Wörter in größeren Blöcken aus dem Speicher zu laden und zu speichern und effizient Wörter mit allgemeinen Registern und SSE-Registern auszutauschen?

Ich freue mich über Kommentare.

Answer 1

Versuchen Sie zuerst, Daten vorab zu lesen (Sie könnten versuchen, zuerst mehr Datenblöcke in x64-Register zu lesen, dann die Berechnungen durchführen), prüfen, ob die Daten korrekt im Speicher ausgerichtet sind entfernen SIB

Adressierung

Sie könnten auch versuchen, Ihren Code zu verkürzen:

mov rax, QWORD PTR [rdx+r11*8-64] 
adc rax, QWORD PTR [r8+r11*8-64] 
mov QWORD PTR [rcx+r11*8-64], rax 

Answer 2

die schwierigste Abhängigkeit ist die Ausbreitung der Verschleppung zwischen jedem Speicherblock; Ich würde versuchen, zuerst eine Methode zu schaffen, damit umzugehen.

Das folgende Fragment simuliert die Übertragsfortpflanzung, aber mit dem "Vorteil", das Übertragsflag nicht zu verwenden. Diese kann für drei oder vier separate Threads parallelisiert werden, von denen jeder eine Hälfte mit etwa 25000 Dezimalstellen (oder 10000 Bytes) erzeugt.Dann wird die Wahrscheinlichkeit, dass diese Übertragungen nur ein Byte, ein Wort, ein Dword usw. beeinflussen, asymptotisch Null erreichen.

long long carry=0; 
for (int i=0;i<N;i++) { 
    carry += (long long)*a++ + (long long)*b++; 
    *c++ = carry; carry>>=32; 
} 

Nach meiner Profilierung carryless zusätzlich xmm Verwendung würde ~ 550ms (1e9 Wörter), die simulierte Trag würde ~ 1020ms und 4-Wege-parallelisierte Version ~ 820ms dauern würde (ohne Assembler-Optimierung).

Architektonische Optimierungen könnten die Verwendung eines redundanten Zahlensystems beinhalten, wo der Übertrag nicht ständig verbreitet werden muss und wo die Bewertung des Übertrags fast ad infinitum verschoben werden könnte.

Answer 3

Ich bin mir ziemlich sicher memcpy ist schneller, da es keine Abhängigkeit von den Daten hat, die abgerufen werden, bevor es die nächste Operation ausführen kann.

Wenn Sie Ihren Code so anordnen, dass es so etwas wie dies funktioniert:

mov rax, QWORD PTR [rdx+r11*8-64] 
mov rbx, QWORD PTR [rdx+r11*8-56] 
mov r10, QWORD PTR [r8+r11*8-64] 
mov r12, QWORD PTR [r8+r11*8-56] 
adc rax, r10 
adc rbx, r12 
mov QWORD PTR [rcx+r11*8-64], rax 
mov QWORD PTR [rcx+r11*8-56], rbx 

Ich bin nicht 100% sicher, dass der Versatz von -56 die richtigen für Ihren Code, aber das Konzept ist " Recht".

Ich würde auch Cache-Treffer/Cache-Kollisionen betrachten. Z.B. Wenn Sie drei Datenblöcke haben [was Sie zu tun scheinen], stellen Sie sicher, dass sie NICHT auf den gleichen Offset im Cache ausgerichtet sind. Ein schlechtes Beispiel wäre, wenn Sie all Ihre Blöcke mit einem Vielfachen der Cachegröße von derselben Stelle im Cache aus zuweisen. Überzuordnen und sicherstellen, dass Ihre verschiedenen Datenblöcke um mindestens 512 Byte versetzt sind [also 4K-Übergröße zuweisen und auf 4K-Startadresse runden, dann 512 zum zweiten Puffer und 1024 zum dritten Puffer hinzufügen]

Wenn Ihre Daten groß genug sind (größer als L2-Cache), können Sie MOVNT zum Abrufen/Speichern Ihrer Daten verwenden. Das vermeidet das Einlesen in den Cache - das ist NUR von Vorteil, wenn Sie sehr große Datenmengen haben, bei denen der nächste Lesevorgang einfach etwas anderes verursacht, das Sie "nützlich" finden, um aus dem Cache rausgeschmissen zu werden zurück zu, bevor Sie es aus dem Cache sowieso weg - so den Wert im Cache speichern wird nicht wirklich helfen ...

Edit: Mit SSE oder ähnliches wird nicht helfen, wie hier behandelt: