Vectorizing Modular Arithmetic

10

Ich versuche, einen einigermaßen schnellen komponentenweisen Vektoradditionscode zu schreiben. Ich arbeite mit 64-Bit-Ganzzahlen (signiert, glaube ich).

Die Funktion ist

%Vor%

Ich kompiliere mit icc -std=gnu99 -O3 (icc, damit ich später SVML verwenden kann) auf einer IvyBridge (SSE4.2 und AVX, aber nicht AVX2).

Meine Baseline entfernt %q von LINE1. 100 (iterierte) Funktionsaufrufe mit dim=11221184 benötigen 1,6 Sekunden. ICC auto-vektorisiert den Code für SSE; großartig.

Ich möchte jedoch wirklich modulare Erweiterungen machen. Mit %q wird der Code von ICC nicht automatisch vektorisiert und in 11,8 Sekunden (!) Ausgeführt. Selbst wenn man die automatische Vektorisierung für den vorherigen Versuch ignoriert, scheint dies immer noch übertrieben.

Da ich AVX2 nicht habe, benötigt die Vektorisierung mit SSE SVML, weshalb ICC sich nicht automatisch vektorisiert hat. Auf jeden Fall, hier ist mein Versuch, die innere Schleife zu vektorisieren:

%Vor%

Die Baugruppe für die Hauptschleife ist:

%Vor%

Der Code wird also wie erwartet vektorisiert. Ich weiß, dass ich aufgrund von SVML vielleicht keine 2-fache Beschleunigung bekomme, aber der Code läuft in 12,5 Sekunden langsamer als überhaupt ohne Vektorisierung! Ist das wirklich das Beste, was man hier machen kann?

    
crockeea 16.12.2013, 06:35
quelle

1 Antwort

12

Weder SSE2 noch AVX2 haben Integer-Instruktionen. Intel ist unaufrichtig, die SVML-Funktionen intrinsics zu nennen, da viele von ihnen komplizierte Funktionen sind, die auf mehrere Anweisungen und nicht nur auf einige Befehle abbilden.

Es gibt eine Möglichkeit, schneller mit SSE2 oder AVX2 zu arbeiten (und modulo). Siehe dieses Papier Verbesserte Division durch invariante Ganzzahlen . Im Grunde vorberechnen Sie einen Divisor und dann Multiplikation. Vorberechnen des Divisors braucht Zeit, aber für einen Wert von dim in Ihrem Code sollte es sich durchsetzen. Ich habe diese Methode hier genauer beschrieben SSE-Integer-Division? Ich habe diese Methode auch erfolgreich in einem Primzahlenfinder Finding lists of implementiert Primzahlen mit SIMD - SSE / AVX

Agner Fog implementiert 32-Bit-Division (aber nicht 64-Bit) in seiner Vektorklasse mit dieser Methode in diesem Papier beschrieben. Das wäre ein guter Startpunkt, wenn Sie etwas Code möchten, aber Sie müssen es auf 64-Bit erweitern.

Bearbeiten: Basierend auf Mysticials Kommentaren und der Annahme, dass die Eingaben bereits reduziert sind, habe ich eine Version für SSE erstellt. Wenn dies in MSVC kompiliert wird, muss es im 64-Bit-Modus als 32-Bit-Modus sein unterstützt _mm_set1_epi64x nicht. Dies kann für den 32-Bit-Modus behoben werden, aber ich möchte es nicht tun.

%Vor%     
Z boson 16.12.2013, 08:06
quelle

Tags und Links