Code SIMD pour exponentiation

Question

J'utilise SIMD pour calculer résultat exponentiation rapide. Je compare le calendrier avec le code non SIMD. L'exponentiation est mis en oeuvre en utilisant square and multiply algorithme.

version du Code ordinaire (non SIMD):

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;  
    }  
}  

Version SIMD:

   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);  
      }  
   } 

La question est si elle est correctement calculait, version SIMD prend plus de temps que la version non-SIMD.

S'il vous plaît aidez-moi déboguer les raisons. Toutes les suggestions sur le codage SIMD est également la bienvenue.

Merci et salutations, Anup.

Answer 1

Toutes les fonctions les boucles for doivent être des fonctions SIMD, non seulement deux. Le temps de prendre pour régler les arguments pour vos 2 fonctions est moins optimale, votre exemple original (ce qui est très probablement optimisé par le compilateur)

Answer 2

Une boucle SIMD pour les données int 32 bits ressemble généralement quelque chose comme ceci:

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);
}

Si vous trouvez que vous devez déplacer entre le code scalaire et le code SIMD dans la boucle, alors vous ne serez probablement pas gagner quoi que ce soit de l'optimisation SIMD.

Une grande partie de la compétence en matière de programmation SIMD vient de trouver des moyens de faire votre travail de l'algorithme avec le nombre limité d'instructions et types de données qu'une architecture SIMD donnée fournit. Vous aurez souvent besoin d'exploiter a priori connaissance de votre ensemble de données pour obtenir les meilleures performances possibles, par exemple si vous savez que vos 32 valeurs entières de bits ont effectivement une gamme qui s'insère dans 16 bits alors que ferait la partie de multiplication de votre algorithme beaucoup plus facile à mettre en œuvre.