SIMD-Code für Potenzierung

Question

Ich bin mit SIMD schnell Potenzierung Ergebnis zu berechnen. Ich vergleiche das Timing mit Nicht-SIMD-Code. Die Potenzierung ist quadratisch und mehrfach Algorithmus implementiert werden.

Ordinary (Nicht-SIMD) Version des Codes:

b = 1;  
for (i=WPE-1; i>=0; --i){  
    ew = e[i];  
    for(j=0; j<BPW; ++j){  
        b = (b * b) % p;  
        if (ew & 0x80000000U)  b = (b * a) % p;  
        ew <<= 1;  
    }  
}  

SIMD-Version:

   B.data[0] = B.data[1] = B.data[2] = B.data[3] = 1U;  
   P.data[0] = P.data[1] = P.data[2] = P.data[3] = p;  
   for (i=WPE-1; i>=0; --i) {  
      EW.data[0] = e1[i]; EW.data[1] = e2[i]; EW.data[2] = e3[i]; EW.data[3] = e4[i];  
      for (j=0; j<BPW;++j){  
         B.v *= B.v; B.v -= (B.v / P.v) * P.v;  
         EWV.v = _mm_srli_epi32(EW.v,31);  
         M.data[0] = (EWV.data[0]) ? a1 : 1U;  
         M.data[1] = (EWV.data[1]) ? a2 : 1U; 
         M.data[2] = (EWV.data[2]) ? a3 : 1U; 
         M.data[3] = (EWV.data[3]) ? a4 : 1U;  
         B.v *= M.v; B.v -= (B.v / P.v) * P.v;  
         EW.v = _mm_slli_epi32(EW.v,1);  
      }  
   } 

Die Frage ist, ob es richtig ist, die Berechnung, SIMD-Version wird mehr Zeit als Nicht-SIMD-Version nehmen.

Bitte helfen Sie mir die Gründe debuggen. Irgendwelche Vorschläge auf SIMD-Codierung ist auch willkommen.

Danke & Grüße, Anup.

Answer 1

Alle Funktionen in der for-Schleifen sollten SIMD-Funktionen, nicht nur zwei. Zeit nehmen, die Argumente für Ihre zwei Funktionen eingestellt ist weniger optimal dann Ihre ursprüngliche Beispiel (die höchstwahrscheinlich durch den Compiler optimiert)

Answer 2

Ein SIMD-Schleife für 32-Bit-int Daten sieht in der Regel so etwas wie diese:

for (i = 0; i < N; i += 4)
{
    // load input vector(s) with data at array index i..i+3
    __m128 va = _mm_load_si128(&A[i]);
    __m128 vb = _mm_load_si128(&B[i]);

    // process vectors using SIMD instructions (i.e. no scalar code)
    __m128 vc = _mm_add_epi32(va, vb);

    // store result vector(s) at array index i..i+3
    _mm_store_si128(&C[i], vc);
}

Wenn Sie feststellen, dass Sie benötigen innerhalb der Schleife zwischen skalaren Code und SIMD-Code zu bewegen, dann werden Sie wahrscheinlich nichts von SIMD-Optimierung gewinnen.

Ein großer Teil der Fertigkeit in SIMD-Programmierung kommt aus Wegen zu finden, Ihre Algorithmus Arbeit mit der begrenzten Anzahl der unterstützten Befehle und Datentypen zu machen, dass eine gegebene SIMD-Architektur zur Verfügung stellt. Sie werden oft a priori Wissen Ihres Datensatzes zu nutzen, müssen die bestmögliche Leistung zu erzielen, zum Beispiel wenn Sie sicher wissen, dass Ihr 32-Bit-Integer-Werte tatsächlich einen Bereich haben, dass passt in 16 Bits dann, dass die Multiplikation Teil Ihres Algorithmus viel einfacher zu implementieren wäre.