código SIMD para exponenciación

Question

Estoy usando SIMD para calcular resultado exponenciación rápida. Comparo la sincronización con código no SIMD. La exponenciación se implementa utilizando algoritmo de cuadrado y se multiplican.

ordinario (no SIMD) versión de código:

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

versión 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 cuestión es si está calculando correctamente, la versión SIMD está tomando más tiempo que la versión no SIMD.

Por favor me ayude a depurar las razones. ¿Alguna sugerencia sobre SIMD de codificación es también agradable.

Gracias y Saludos, Anup.

Answer 1

Todas las funciones en el de bucles debe ser funciones SIMD, no sólo dos. Tiempo de tomar para establecer los argumentos para sus 2 funciones es menos óptimo, entonces su ejemplo original (que es más probable optimizado por el compilador)

Answer 2

A SIMD bucle para datos int de 32 bits normalmente se ve algo como esto:

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 usted encuentra que tiene que mover entre el código y el código SIMD escalar dentro del bucle, entonces probablemente no va a ganar nada de SIMD optimización.

Una gran parte de la habilidad en la programación SIMD proviene de encontrar maneras de hacer su trabajo algoritmo con el número limitado de instrucciones soportadas y tipos de datos que una arquitectura SIMD dada proporciona. A menudo se necesitan para explotar a priori conocimiento de su conjunto de datos para obtener el mejor rendimiento posible, por ejemplo, si se sabe con certeza que sus valores enteros de 32 bits en realidad tienen un rango que se ajusta dentro de 16 bits entonces que harían que la parte multiplicación de su algoritmo mucho más fácil de implementar.