SSE Integer Division?

Question

Es gibt _mm_div_ps für Gleitkommawerte, es gibt _mm_mullo_epi16 für Integer Multiplikation. Aber gibt es etwas für Integer Division (16 Bit Wert)? Wie kann ich eine solche Teilung durchführen?

Answer 1

Bitte sehen Agner Fog vectorclass er einen schnellen Algorithmus zu tun Integer-Division mit SSE/AVX für 8-Bit implementiert hat, 16-Bit und 32-Bit-Worte (aber nicht 64-bit) http://www.agner.org/optimize/#vectorclass

Blick in der Datei vectori128.h für den Code und eine Beschreibung des algoirthm als sein gut geschriebenes Handbuch VectorClass.pdf

Hier ist ein Fragment, das den Algorithmus von seinem Handbuch beschreibt.

„Integer Division Es gibt keine Anweisungen in dem x86-Befehlssatz und seine Erweiterungen, die nützlich für Integer-Vektor-Abteilung sind, und solche Anweisungen würden sehr langsam sein, wenn sie existierten. Daher ist die Vektor-Klassenbibliothek ein mit Algorithmus für schnelle Ganzzahl Division.Das Grundprinzip dieses Algorithmus kann in dieser Formel ausgedrückt werden: a/b ≈ a * (2n/b) >> n Diese Berechnung durchläuft die folgenden Schritte: 1. finden Sie eine geeignete Wert für n 2. Berechne 2n/b 3. berechne notwendige Korrekturen für Rundungsfehler 4. mache die Multiplikation an und shift-right und Korrekturen für Rundung anwenden Fehler

Diese Formel ist vorteilhaft, wenn mehrere Zahlen durch denselben Divisor b geteilt werden. Die Schritte 1, 2 und 3 müssen nur einmal ausgeführt werden, während Schritt 4 für jeden Wert des Dividenden a wiederholt wird. Die mathematischen Details sind in der Datei vectori128.h beschrieben. (Siehe auch T. Granlund und PL Montgomery. Die Division durch unveränderlich Integers Mit Multiplikation, Proceedings of the SIGPLAN "...

Edit: in der Nähe des Ende der Datei vectori128.h zeigt, wie kurze Teilung zu tun mit eine Skalarvariable "Es dauert mehr Zeit, um die für die schnelle Division verwendeten Parameter zu berechnen als . Daher ist es vorteilhaft, das gleiche Divisor-Objekt mehrfach zu verwenden. Zum Beispiel, um 80 vorzeichenlose kurze ganze Zahlen zu teilen 10:

short x = 10; 
uint16_t dividends[80], quotients[80];   // numbers to work with 
Divisor_us div10(x);       // make divisor object for dividing by 10 
Vec8us temp;         // temporary vector 
for (int i = 0; i < 80; i += 8) {    // loop for 4 elements per iteration 
    temp.load(dividends+i);     // load 4 elements 
    temp /= div10;        // divide each element by 10 
    temp.store(quotients+i);     // store 4 elements 
} 

"

Edit: Integer-Division durch einen Vektor von Shorts

#include <stdio.h> 
#include "vectorclass.h" 

int main() {  
    short numa[] = {10, 20, 30, 40, 50, 60, 70, 80}; 
    short dena[] = {10, 20, 30, 40, 50, 60, 70, 80}; 

    Vec8s num = Vec8s().load(numa); 
    Vec8s den = Vec8s().load(dena); 

    Vec4f num_low = to_float(extend_low(num)); 
    Vec4f num_high = to_float(extend_high(num)); 
    Vec4f den_low = to_float(extend_low(den)); 
    Vec4f den_high = to_float(extend_high(den)); 

    Vec4f qf_low = num_low/den_low; 
    Vec4f qf_high = num_high/den_high; 
    Vec4i q_low = truncate_to_int(qf_low); 
    Vec4i q_high = truncate_to_int(qf_high); 

    Vec8s q = compress(q_low, q_high); 
    for(int i=0; i<8; i++) { 
     printf("%d ", q[i]); 
    } printf("\n"); 
}