c++ - El código AVX de 256 bits tiene un rendimiento ligeramente peor que el código SSSE3 de 128 bits equivalente

performance avx2

Question

Estoy tratando de escribir código de Hamming-distancia muy eficiente. Inspirado por la muy inteligente implementation popcount SSE3 de Wojciech Muła, codifiqué una solución equivalente AVX2, esta vez utilizando registros de 256 bits. Esperaba al menos una mejora del 30% -40% basada en el doble paralelismo de las operaciones involucradas, sin embargo, para mi sorpresa, el código AVX2 es un poco más lento (alrededor del 2%)

¿Puede alguien explicarme las posibles razones por las que no estoy obteniendo el aumento de rendimiento esperado?

Desenrollado, SSE3 Hamming distancia de dos bloques de 64 bytes:

INT32 SSE_PopCount(const UINT32* __restrict pA, const UINT32* __restrict pB) {

   __m128i paccum  = _mm_setzero_si128();

   __m128i a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA));
   __m128i b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB));
   __m128i err     = _mm_xor_si128   (a, b);
   __m128i lo      = _mm_and_si128   (err, low_mask);
   __m128i hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
   __m128i popcnt1 = _mm_shuffle_epi8(lookup, lo);
   __m128i popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 4));
           b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 4));
           err     = _mm_xor_si128   (a, b);
           lo      = _mm_and_si128   (err, low_mask);
           hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
           popcnt1 = _mm_shuffle_epi8(lookup, lo);
           popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 8));
           b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 8));
           err     = _mm_xor_si128   (a, b);
           lo      = _mm_and_si128   (err, low_mask);
           hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
           popcnt1 = _mm_shuffle_epi8(lookup, lo);
           popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           a       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pA + 12));
           b       = _mm_loadu_si128 (reinterpret_cast<const __m128i*>(pB + 12));
           err     = _mm_xor_si128   (a, b);
           lo      = _mm_and_si128   (err, low_mask);
           hi      = _mm_srli_epi16  (err, 4);
           hi      = _mm_and_si128   (hi, low_mask);
           popcnt1 = _mm_shuffle_epi8(lookup, lo);
           popcnt2 = _mm_shuffle_epi8(lookup, hi);
           paccum  = _mm_add_epi8(paccum, popcnt1);
           paccum  = _mm_add_epi8(paccum, popcnt2);

           paccum  = _mm_sad_epu8(paccum, _mm_setzero_si128());
   UINT64  result =  paccum.m128i_u64[0] + paccum.m128i_u64[1];
   return (INT32)result;
}

Desenrollado, versión equivalente utilizando registros de 256 bits de AVX:

INT32 AVX_PopCount(const UINT32* __restrict pA, const UINT32* __restrict pB) {
   __m256i paccum =  _mm256_setzero_si256();

   __m256i a       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pA));
   __m256i b       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pB));
   __m256i err     = _mm256_xor_si256   (a, b);
   __m256i lo      = _mm256_and_si256   (err, low_mask256);
   __m256i hi      = _mm256_srli_epi16  (err, 4);
           hi      = _mm256_and_si256   (hi, low_mask256);
   __m256i popcnt1 = _mm256_shuffle_epi8(lookup256, lo);
   __m256i popcnt2 = _mm256_shuffle_epi8(lookup256, hi);
           paccum  = _mm256_add_epi8(paccum, popcnt1);
           paccum  = _mm256_add_epi8(paccum, popcnt2);

           a       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pA + 8));
           b       = _mm256_loadu_si256 (reinterpret_cast<const __m256i*>(pB + 8));
           err     = _mm256_xor_si256   (a, b);
           lo      = _mm256_and_si256   (err, low_mask256);
           hi      = _mm256_srli_epi16  (err, 4);
           hi      = _mm256_and_si256   (hi, low_mask256);
           popcnt1 = _mm256_shuffle_epi8(lookup256, lo);
           popcnt2 = _mm256_shuffle_epi8(lookup256, hi);
           paccum  = _mm256_add_epi8(paccum, popcnt1);
           paccum  = _mm256_add_epi8(paccum, popcnt2);

           paccum  = _mm256_sad_epu8(paccum, _mm256_setzero_si256());
           UINT64  result =  paccum.m256i_i64[0] + paccum.m256i_u64[1] + paccum.m256i_i64[2] + paccum.m256i_i64[3];
   return (INT32)result;
}

Ya verifiqué el código de ensamblaje de salida emitido por el compilador y se ve bien, con la traducción directa esperada de la instrucción intrínseca a la instrucción de máquina. Lo único que noté es que en la versión AVX2, la última línea donde se acumula el recuento de población de las 4 palabras cuádruples, genera un código más complejo que la versión SSE3 (donde solo se necesitan acumular 2 palabras cuádruples para obtener el conteo de la población), sin embargo, todavía esperaría un rendimiento más rápido.

Código AVX2 generado para la acumulación de cuatro palabras

vextractf128 xmm0, ymm2, 1
psrldq  xmm0, 8
movd    ecx, xmm2
movd    eax, xmm0
vextractf128 xmm0, ymm2, 1
psrldq  xmm2, 8
add eax, ecx
movd    ecx, xmm0
add eax, ecx
movd    ecx, xmm2
add eax, ecx

Código SSE3 generado para la acumulación de cuatro palabras

movd    ecx, xmm2
psrldq  xmm2, 8
movd    eax, xmm2
add eax, ecx

Mi programa de prueba está llamando 1 millón de veces a cada rutina, con diferentes valores de entrada, pero reutilizando dos búferes estáticos para mantener los datos de los parámetros pA y pB . En mi conocimiento limitado de la arquitectura de la CPU, esta localidad (reutilizando los mismos buffers de memoria una y otra vez) debería calentar los cachés de la CPU muy bien y no estar vinculada por un problema de ancho de banda de memoria, pero aparte de posiblemente el ancho de banda de la memoria, no puedo entender por qué no hay mejora de rendimiento

Rutina de prueba

int _tmain(int argc, _TCHAR* argv[]) {

   lookup = _mm_setr_epi8(
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4
    );
   low_mask = _mm_set1_epi8(0xf);

   lookup256 = _mm256_setr_epi8(
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4,
        /* 0 */ 0, /* 1 */ 1, /* 2 */ 1, /* 3 */ 2,
        /* 4 */ 1, /* 5 */ 2, /* 6 */ 2, /* 7 */ 3,
        /* 8 */ 1, /* 9 */ 2, /* a */ 2, /* b */ 3,
        /* c */ 2, /* d */ 3, /* e */ 3, /* f */ 4
    );

   low_mask256 = _mm256_set1_epi8(0xf);


   std::default_random_engine generator;
   generator.seed(37);
   std::uniform_int_distribution<UINT32> distribution(0, ULONG_MAX);
   auto dice = std::bind( distribution, generator);


   UINT32 a[16];
   UINT32 b[16];

   int count;
   count = 0;
   {
      cout << "AVX PopCount/r/n";
      boost::timer::auto_cpu_timer t;
      for( int i = 0; i < 1000000; i++ ) {
         for( int j = 0; j < 16; j++ ) {
            a[j] = dice();
            b[j] = dice();
         }
         count+= AVX_PopCount(a, b);
      }
   }

   cout << count << "/r/n";


   std::default_random_engine generator2;
   generator2.seed(37);
   std::uniform_int_distribution<UINT32> distribution2(0, ULONG_MAX);
   auto dice2 = std::bind( distribution2, generator2);


   count = 0;
   {
      cout << "SSE PopCount/r/n";
      boost::timer::auto_cpu_timer t;
      for( int i = 0; i < 1000000; i++ ) {
         for( int j = 0; j < 16; j++ ) {
            a[j] = dice2();
            b[j] = dice2();
         }
         count+= SSE_PopCount(a, b);
      }
   }
   cout << count << "/r/n";

   getch();
   return 0;
}

La máquina de prueba es un Intel Corei7 4790, y estoy usando Visual Studio 2012 Pro.

Answer 1

Además de los problemas menores en los comentarios (compilación de /arch:AVX ), su problema principal es la generación de matrices de entrada aleatoria en cada iteración. Este es su cuello de botella, por lo que su prueba no evalúa sus métodos de manera efectiva. Nota: no estoy usando boost, pero GetTickCount funciona para este propósito. Considere solo:

int count;
count = 0;
{
    cout << "AVX PopCount/r/n";
    unsigned int Tick = GetTickCount();
    for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 16; j++) {
            a[j] = dice();
            b[j] = dice();
        }
        count += AVX_PopCount(a, b);
    }
    Tick = GetTickCount() - Tick;
    cout << Tick << "/r/n";
}

produce salida:

AVX PopCount
2309
256002470

Por lo tanto, 2309 ms para completar ... ¿pero qué sucede si nos deshacemos de su rutina AVX por completo? Solo haz las matrices de entrada:

int count;
count = 0;
{
    cout << "Just making arrays.../r/n";
    unsigned int Tick = GetTickCount();
    for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 16; j++) {
            a[j] = dice();
            b[j] = dice();
        }           
    }
    Tick = GetTickCount() - Tick;
    cout << Tick << "/r/n";
}

produce salida:

Solo haciendo matrices ...
2246

Qué hay sobre eso. No es sorprendente, en realidad, ya que estás generando 32 números aleatorios, lo que puede ser bastante costoso, y luego realizar solo algunos enteros rápidos y aleatorios de números enteros.

Asi que...

Ahora agreguemos un factor de 100 iteraciones más y obtengamos el generador aleatorio fuera del circuito cerrado. La compilación aquí con las optimizaciones deshabilitadas ejecutará su código como se esperaba y no eliminará las iteraciones "inútiles". ¡Probablemente el código que nos importa aquí ya está optimizado (manualmente)!

    for (int j = 0; j < 16; j++) {
        a[j] = dice();
        b[j] = dice();
    }

    int count;
    count = 0;
    {
        cout << "AVX PopCount/r/n";
        unsigned int Tick = GetTickCount();
        for (int i = 0; i < 100000000; i++) {           
            count += AVX_PopCount(a, b);
        }
        Tick = GetTickCount() - Tick;
        cout << Tick << "/r/n";
    }

    cout << count << "/r/n";

    count = 0;
    {
        cout << "SSE PopCount/r/n";
        unsigned int Tick = GetTickCount();
        for (int i = 0; i < 100000000; i++) {
            count += SSE_PopCount(a, b);
        }
        Tick = GetTickCount() - Tick;
        cout << Tick << "/r/n";
    }
    cout << count << "/r/n";

produce salida:

AVX PopCount
3744
730196224
SSE PopCount
5616
730196224

Así que felicitaciones: puede darse una palmada en la espalda, su rutina AVX es aproximadamente un tercio más rápida que la rutina SSE (probada en Haswell i7 aquí). ¡La lección es asegurarse de que realmente esté perfilando lo que cree que está perfilando!

Answer 2

Debería considerar el uso de la instrucción _mm_popcnt_u64 habitual en lugar de piratearla en SSE o AVX. Probé a fondo todos los métodos para hacer popcount, incluyendo una versión SSE y AVX (lo que finalmente me llevó a mi pregunta más o menos famosa sobre popcount ). _mm_popcnt_u64 supera SSE y AVX considerablemente, especialmente cuando usas un compilador que evita el error de Intel Popcount descubierto en mi pregunta. Sin el error, mi Haswell puede cargar 26 GB / s, que casi alcanza el ancho de banda del bus.

La razón por la que _mm_popcnt_u64 es más rápida se debe simplemente al hecho de que contiene 64 bits a la vez (por lo que ya es 1/4 de la versión AVX) y requiere solo una instrucción de procesador barata. Solo cuesta unos pocos ciclos (latencia 3, rendimiento 1 para Intel). Incluso si cada instrucción AVX que utilizas requiriera solo un ciclo, obtendrías peores resultados debido a la gran cantidad de instrucciones necesarias para hacer popcount de 256 bits.

Intenta esto, debería ser más rápido:

int popcount256(const uint64_t* u){ 
    return _mm_popcnt_u64(u[0]);
         + _mm_popcnt_u64(u[1]);
         + _mm_popcnt_u64(u[2]);
         + _mm_popcnt_u64(u[3]);
}

Sé que esto no responde a su pregunta central por qué AVX es más lento, pero como su objetivo final es popcount rápido, la comparación AVX <-> SSE es irrelevante ya que ambos son inferiores al popcount integrado.