¿Cómo realizar el inverso de _mm256_movemask_epi8 (VPMOVMSKB)?

Lo intrínseco

int mask = _mm256_movemask_epi8(__m256i s1) 

crea una máscara, con sus 32 bits correspondientes al bit más significativo de cada byte de s1 . Después de manipular la máscara usando operaciones de bits ( BMI2 por ejemplo) me gustaría realizar el inverso de _mm256_movemask_epi8 , es decir, crear un vector __m256i con el bit más significativo de cada byte que contiene el bit correspondiente de la uint32_t mask .

¿Cuál es la mejor manera de hacer esto?

Editar: Necesito realizar el inverso porque el _mm256_blendv_epi8 intrínseco _mm256_blendv_epi8 acepta la máscara de tipo __m256i lugar de uint32_t . Como tal, en la máscara __m256i resultante, puedo ignorar los bits distintos del MSB de cada byte.

Aquí hay una alternativa a las instrucciones LUT o pdep que pueden ser más eficientes:

  1. Copie su máscara de 32 bits a ambos bytes bajos de algunos registros ymm y los bytes 16..19 del mismo registro. Puede usar una matriz temporal y _mm256_load_si256 . O puede mover una sola copia de la máscara de 32 bits a bytes bajos de algún registro ymm , luego transmitirla con VPBROADCASTD (_mm_broadcastd_epi32) u otras instrucciones de transmisión / reproducción aleatoria.
  2. Reorganice los bytes del registro de modo que 8 bytes bajos (cada uno) contengan 8 bits bajos de su máscara, 8 bytes siguientes, 8 bits siguientes, etc. Esto podría hacerse con VPSHUFB (_mm256_shuffle_epi8) con registro de control que contiene ‘0’ en 8 bajo bytes, ‘1’ en los próximos 8 bytes, etc.
  3. Seleccione el bit apropiado para cada byte con VPOR (_mm256_or_si256) o VPAND (_mm256_and_si256) .
  4. Establezca MSB de bytes apropiados con VPCMPEQB (_mm256_cmpeq_epi8) . Compara cada byte con 0xFF . Si quiere que cada bit de la máscara se VPAND , use VPAND en el paso anterior y compare con cero.

La flexibilidad adicional de este enfoque es que puede elegir diferentes registros de control para el paso # 2 y diferentes máscaras para el paso # 3 para mezclar bits de su máscara de bits (por ejemplo, puede copiar esta máscara en el registro ymm en orden inverso).

Implementé los tres enfoques anteriores en una máquina Haswell. El enfoque de Evgeny Kluev es el más rápido (1.07 s), seguido de Jason R (1.97 s) y Paul R (2.44 s). El siguiente código se compiló con -march = core-avx2 -O3 indicadores de optimización.

 #include  #include  //t_icc = 1.07 s //t_g++ = 1.09 s __m256i get_mask3(const uint32_t mask) { __m256i vmask(_mm256_set1_epi32(mask)); const __m256i shuffle(_mm256_setr_epi64x(0x0000000000000000, 0x0101010101010101, 0x0202020202020202, 0x0303030303030303)); vmask = _mm256_shuffle_epi8(vmask, shuffle); const __m256i bit_mask(_mm256_set1_epi64x(0x7fbfdfeff7fbfdfe)); vmask = _mm256_or_si256(vmask, bit_mask); return _mm256_cmpeq_epi8(vmask, _mm256_set1_epi64x(-1)); } //t_icc = 1.97 s //t_g++ = 1.97 s __m256i get_mask2(const uint32_t mask) { __m256i vmask(_mm256_set1_epi32(mask)); const __m256i shift(_mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0)); vmask = _mm256_sllv_epi32(vmask, shift); const __m256i shuffle(_mm256_setr_epi64x(0x0105090d0004080c, 0x03070b0f02060a0e, 0x0105090d0004080c, 0x03070b0f02060a0e)); vmask = _mm256_shuffle_epi8(vmask, shuffle); const __m256i perm(_mm256_setr_epi64x(0x0000000000000004, 0x0000000100000005, 0x0000000200000006, 0x0000000300000007)); return _mm256_permutevar8x32_epi32(vmask, perm); } //t_icc = 2.44 s //t_g++ = 2.45 s __m256i get_mask1(uint32_t mask) { const uint64_t pmask = 0x8080808080808080ULL; // bit unpacking mask for PDEP uint64_t amask0, amask1, amask2, amask3; amask0 = _pdep_u64(mask, pmask); mask >>= 8; amask1 = _pdep_u64(mask, pmask); mask >>= 8; amask2 = _pdep_u64(mask, pmask); mask >>= 8; amask3 = _pdep_u64(mask, pmask); return _mm256_set_epi64x(amask3, amask2, amask1, amask0); } int main() { __m256i mask; boost::posix_time::ptime start( boost::posix_time::microsec_clock::universal_time()); for(unsigned i(0); i != 1000000000; ++i) { mask = _mm256_xor_si256(mask, get_mask3(i)); } boost::posix_time::ptime end( boost::posix_time::microsec_clock::universal_time()); std::cout << "duration:" << (end-start) << " mask:" << _mm256_movemask_epi8(mask) << std::endl; return 0; } 

Aquí hay otra implementación que podría funcionar en AVX2 ya que tenía esa etiqueta en su pregunta (no se ha probado ya que no tengo una máquina Haswell). Es similar a la respuesta de Evgeny Kluev, pero podría necesitar menos instrucciones. Sin embargo, requiere dos máscaras __m256i constantes. Si está haciendo esto muchas veces en un bucle, entonces la sobrecarga de configurar esas constantes con anticipación puede ser insignificante.

  • Tome su máscara de 32 bits y ymm a las 8 ranuras de un registro _mm_broadcastd_epi32() usando _mm_broadcastd_epi32() .

  • Cree un __m256i que __m256i 8 enteros de 32 bits con los valores [0, 1, 2, 3, 4, 5, 6, 7] (del elemento menos significativo al más significativo).

  • Use esa máscara constante para rotar cada uno de los enteros de 32 bits en su registro ymm dejado por una cantidad diferente, usando _mm256_sllv_epi32() .

  • Ahora, si vemos el registro ymm como que contiene enteros de 8 bits y miramos sus MSB, entonces el registro ahora contiene los MSB para los índices de bytes [7, 15, 23, 31, 6, 14, 22, 30, 5, 13, 21, 29, 4, 12, 20, 28, 3, 11, 19, 27, 2, 10, 18, 26, 1, 9, 17, 25, 0, 8, 16, 24] (del menor significativo para el elemento más significativo).

  • Use un AND bit a bit contra una máscara constante de [0x80, 0x80, 0x80, ...] para aislar los MSB de cada byte.

  • Use una secuencia de mezclas y / o permuta para volver a los elementos en el orden que desee. Desafortunadamente, no existe ningún permute cualquiera para enteros de 8 bits como los que existen para valores de coma flotante en AVX2.

Mi aproximación inicial a esto fue similar a la de @Jason R porque así es como funcionan las operaciones “normales”, pero la mayoría de estas operaciones solo se preocupan por el bit alto, ignorando todos los demás bits. Una vez que me di cuenta de esto, la serie de funciones _mm*_maskz_broadcast*_epi*(mask,__m128i) tuvo más sentido. Deberá habilitar -mavx512vl y -mavx512bw (gcc)

Para obtener un vector con el bit más alto de cada conjunto de bytes según una máscara:

 /* convert 16 bit mask to __m128i control byte mask */ _mm_maskz_broadcastb_epi8((__mmask16)mask,_mm_set1_epi32(~0)) /* convert 32 bit mask to __m256i control byte mask */ _mm256_maskz_broadcastb_epi8((__mmask32)mask,_mm_set1_epi32(~0)) /* convert 64 bit mask to __m512i control byte mask */ _mm512_maskz_broadcastb_epi8((__mmask64)mask,_mm_set1_epi32(~0)) 

Para obtener un vector con el bit más alto de cada conjunto de palabras según una máscara:

 /* convert 8 bit mask to __m128i control word mask */ _mm_maskz_broadcastw_epi16((__mmask8)mask,_mm_set1_epi32(~0)) /* convert 16 bit mask to __m256i control word mask */ _mm256_maskz_broadcastw_epi16((__mmask16)mask,_mm_set1_epi32(~0)) /* convert 32 bit mask to __m512i control word mask */ _mm512_maskz_broadcastw_epi16((__mmask32)mask,_mm_set1_epi32(~0)) 

Para obtener un vector con el bit más alto de cada palabra doble establecida de acuerdo con una máscara:

 /* convert 8 bit mask to __m256i control mask */ _mm256_maskz_broadcastd_epi32((__mmask8)mask,_mm_set1_epi32(~0)) /* convert 16 bit mask to __m512i control mask */ _mm512_maskz_broadcastd_epi32((__mmask16)mask,_mm_set1_epi32(~0)) 

Para obtener un vector con el bit más alto de cada palabra cuádruple configurada según una máscara:

 /* convert 8 bit mask to __m512i control mask */ _mm512_maskz_broadcastq_epi64((__mmask8)mask,_mm_set1_epi32(~0)) 

El específico para esta pregunta es: _mm256_maskz_broadcastb_epi8((__mmask32)mask,_mm_set1_epi32(~0)) pero _mm256_maskz_broadcastb_epi8((__mmask32)mask,_mm_set1_epi32(~0)) los otros para referencia / comparación.

Tenga en cuenta que cada byte / palabra / … será uno o más ceros según la máscara (no solo el bit más alto). Esto también puede ser útil para realizar operaciones de bits vectorizadas (y con otro vector, por ejemplo, para poner a cero bytes / palabras no deseados).

Otra nota: cada _mm_set1_epi32(~0) podría / debería convertirse en una constante (ya sea manualmente o por el comstackdor), por lo que debería comstackrse para una sola operación bastante rápida, aunque puede ser un poco más rápida en las pruebas que en la vida real ya que la constante probablemente permanecerá en un registro. Luego, estos se convierten en instrucciones VPMOVM2 {b, w, d, q}

Editar: en caso de que su comstackdor no sea compatible con AVX512, la versión del ensamblado en línea debería verse así:

 inline __m256i dmask2epi8(__mmask32 mask){ __m256i ret; __asm("vpmovm2b %1, %0":"=x"(ret):"k"(mask):); return ret; } 

Las otras instrucciones son similares.

La única forma razonablemente eficiente en que puedo pensar es con un LUT de 8 bits: realice búsquedas de 4 x 8 bits y luego cargue los resultados en un vector, por ejemplo

 static const uint64_t LUT[256] = { 0x0000000000000000ULL, ... 0xffffffffffffffffULL }; uint64_t amask[4] __attribute__ ((aligned(32))); uint32_t mask; __m256i vmask; amask[0] = LUT[mask & 0xff]; amask[1] = LUT[(mask >> 8) & 0xff]; amask[2] = LUT[(mask >> 16) & 0xff]; amask[3] = LUT[mask >> 24]; vmask = _mm256_load_si256((__m256i *)amask); 

Alternativamente, podría usar registros en lugar de la matriz temporal y ver si su comstackdor puede hacer algo más eficiente que no implique pasar por la memoria:

 static const uint64_t LUT[256] = { 0x0000000000000000ULL, ... 0xffffffffffffffffULL }; uint64_t amask0, amask1, amask2, amask3; uint32_t mask; __m256i vmask; amask0 = LUT[mask & 0xff]; amask1 = LUT[(mask >> 8) & 0xff]; amask2 = LUT[(mask >> 16) & 0xff]; amask3 = LUT[mask >> 24]; vmask = _mm256_set_epi64x(amask3, amask2, amask1, amask0); 

Pensamiento de último momento: un desafío interesante podría ser usar, por ejemplo, instrucciones de Haswell BMI para realizar el equivalente de la operación de LUT de 8 -> 64 bits y así deshacerse de la LUT. Parece que podría usar PDEP para esto, por ejemplo

 const uint64_t pmask = 0x8080808080808080ULL; // bit unpacking mask for PDEP uint64_t amask0, amask1, amask2, amask3; uint32_t mask; __m256i vmask; amask0 = _pdep_u64(mask, pmask); mask >>= 8; amask1 = _pdep_u64(mask, pmask); mask >>= 8; amask2 = _pdep_u64(mask, pmask); mask >>= 8; amask3 = _pdep_u64(mask, pmask); vmask = _mm256_set_epi64x(amask3, amask2, amask1, amask0);