¿Hay una instrucción inversa a la instrucción movemask en Intel avx2?

Las instrucciones movemask toman un __m256i y devuelven un int32 donde cada bit (el primero 4, 8 o los 32 bits dependiendo del tipo de elemento vector de entrada) es el bit más significativo del elemento vector correspondiente.

Me gustaría hacer lo contrario: tomar un 32 (donde solo los 4, 8 o 32 bits menos significativos son significativos), y obtener un __m256i donde el bit más significativo de cada bloque de tamaño int8, int32 o int64 se establece en el original poco.

Básicamente, quiero pasar de una máscara de bits comprimida a otra que pueda usarse como máscara mediante otras instrucciones AVX2 (como maskstore, maskload, mask_gather).

No pude encontrar rápidamente una instrucción que lo haga, así que estoy preguntando aquí. Si no hay una instrucción con esa funcionalidad, ¿hay algún truco inteligente que se pueda pensar que logre esto en muy pocas instrucciones?

Mi método actual es usar una tabla de búsqueda de 256 elementos. Quiero usar esta operación dentro de un ciclo donde no ocurre mucho más, para acelerarlo. Tenga en cuenta que no me interesan demasiado las largas secuencias de instrucciones múltiples o los pequeños bucles que implementan esta operación.

No hay instrucciones únicas en AVX2 o anterior.

  • 4 bits -> 4 qwords en un registro YMM: esta respuesta: una LUT es buena, ALU también es buena
  • 8 bits -> 8 palabras en un registro YMM: esta respuesta: ALU es bueno
  • 16 bits -> 16 palabras : esta respuesta con vpbroadcastw / vpand / vpcmpeqw
  • 32 bits -> 32 bytes :
    ¿Cómo realizar el inverso de _mm256_movemask_epi8 (VPMOVMSKB)?
    También es la forma más rápida de descomprimir 32 bits en un vector SIMD de 32 bytes .

Si está cargando el bitmap desde la memoria, cargarlo directamente en registros de vectores para una estrategia de ALU debería funcionar bien.

Si tiene el bitmap como un resultado de cálculo, estará en un registro de enteros donde puede usarlo como un índice de LUT fácilmente, por lo que es una buena opción si está buscando elementos de 64 bits. De lo contrario, probablemente siga siendo ALU para elementos de 32 bits o más pequeños, en lugar de una LUT gigante o haciendo múltiples fragmentos.


Tendremos que esperar a los registros de máscara del AVX-512 antes de que sea posible una conversión económica de máscaras de bits enteros a máscaras de vectores. (Con kmovw k1, r/m16 , que los comstackdores generan implícitamente para int => __mmask16 ). Hay un AVX512 insento para establecer un vector a partir de una máscara ( VPMOVM2D zmm1, k1 , _mm512_movm_epi8/16/32/64 , con otras versiones para diferentes tamaños de elemento), pero generalmente no lo necesita ya que todo lo que solía usar vectores de máscara ahora usa registros de máscara. ¿Tal vez si quieres contar elementos que cumplen alguna condición de comparación? (donde usaría pcmpeqd / psubd para generar y acumular el vector de elementos 0 o -1). Pero el escalar popcnt en los resultados de la máscara sería una mejor apuesta.


Para elementos de 64 bits, la máscara solo tiene 4 bits, por lo que una tabla de búsqueda es razonable . Puede comprimir la LUT cargándola con VPMOVSXBQ ymm1, xmm2/m32 . ( _mm256_cvtepi8_epi64 ) . Esto le da un tamaño de LUT de (1 << 4) = 16 * 4 bytes = 64B = 1 línea de caché. Desafortunadamente, pmovsx es inconveniente de usar como una carga estrecha con intrínsecos .

Especialmente si ya tiene su bitmap en un registro entero (en lugar de memoria), un LUT vpmovsxbq debe ser excelente dentro de un bucle interno para elementos de 64 bits. O si el rendimiento de la instrucción o el rendimiento aleatorio es un cuello de botella, use una LUT sin comprimir. Esto puede permitirle (o al comstackdor) usar el vector de máscara como un operando de memoria para otra cosa, en lugar de necesitar una instrucción separada para cargarlo.


LUT para elementos de 32 bits: probablemente no sea óptimo, pero así es cómo podría hacerlo

Con elementos de 32 bits, una máscara de 8 bits te brinda 256 vectores posibles, cada uno de 8 elementos de largo. 256 * 8B = 2048 bytes, que es una huella de caché bastante grande incluso para la versión comprimida (carga con vpmovsxbd ymm, m64 ).

Para solucionar esto, puede dividir el LUT en fragmentos de 4 bits . Se necesitan aproximadamente 3 instrucciones enteras para dividir un entero de 8 bits en dos enteros de 4 bits ( mov/and/shr ). Luego, con un LUT sin comprimir de vectores 128b (para tamaño de elemento de 32 bits), vmovdqa la mitad baja y vinserti128 la mitad alta. Todavía podrías comprimir el LUT, pero no lo recomendaría porque necesitarás vmovd / vpinsrd / vpmovsxbd , que es 2 shuffles (por lo que probablemente tengas un cuello de botella en el rendimiento de uop).

O 2x vpmovsxbd xmm, [lut + rsi*4] + vinserti128 probablemente sea aún peor en Intel.


Alternativa ALU: buena para elementos de 16/32/64 bits

Cuando todo el bitmap se ajuste a cada elemento, difúndalo, Y con una máscara de selector, y VPCMPEQ contra la misma constante (que puede permanecer en un registro a través de múltiples usos de esto en un bucle).

 vpbroadcastd ymm0, dword [mask] vpand ymm0, ymm0, [vec of 1<<0, 1<<1, 1<<2, 1<<3, ...] vpcmpeqd ymm0, ymm0, [same constant] ; ymm0 = (mask & bit) == bit ; where bit = 1< 

(La máscara podría provenir de un registro entero con vmovd + vpbroadcastd, pero una carga de difusión

Para elementos de 8 bits, necesitará vpshufb del resultado vpbroadcastd para obtener el bit relevante en cada byte. Consulte Cómo realizar el inverso de _mm256_movemask_epi8 (VPMOVMSKB)? . Pero para elementos de 16 bits y más amplios, el número de elementos es <= el ancho del elemento, por lo que una carga de difusión lo hace de forma gratuita. (Las cargas de difusión de 16 bits cuestan un ALU aleatorio micro fusionado uop, a diferencia de las cargas de difusión de 32 y 64 bits que se manejan por completo en los puertos de carga).

vpbroadcastd/q ni siquiera cuesta ningún UUP de ALU, se hace bien en el puerto de carga. ( b y w son carga + mezcla). Incluso si sus máscaras están empaquetadas juntas (una por byte para elementos de 32 o 64 bits), aún podría ser más eficiente para vpbroadcastd lugar de vpbroadcastb . La comprobación de x & mask == mask no se preocupa por la basura en los bytes altos de cada elemento después de la transmisión. La única preocupación es dividir la línea de caché / página.


Variable shift (más barato en Skylake) si solo necesitas el bit de signo

Las mezclas variables y las cargas / tiendas enmascaradas solo se preocupan por el bit de signo de los elementos de máscara.

Esto es solo 1 uop (en Skylake) una vez que tienes la máscara de 8 bits transmitida a los elementos dword.

 vpbroadcastd ymm0, dword [mask] vpsllvd ymm0, ymm0, [vec of 24, 25, 26, 27, 28, 29, 30, 31] ; high bit of each element = corresponding bit of the mask ;vpsrad ymm0, ymm0, 31 ; broadcast the sign bit of each element to the whole element ;vpsllvd + vpsrad has no advantage over vpand / vpcmpeqb, so don't use this if you need all the bits set. 

vpbroadcastd es tan barato como una carga de memoria (sin ALU uop en absoluto en las CPU Intel y Ryzen). (Las transmisiones más vpbroadcastb y,mem , como vpbroadcastb y,mem toman una ALU shuffle uop en Intel, pero tal vez no en Ryzen).

El cambio de variable es ligeramente caro en Haswell / Broadwell (3 uops, puertos de ejecución limitados), ¡pero tan barato como turnos de conteo inmediato en Skylake! (1 uop en el puerto 0 o 1.) En Ryzen también son solo 2 uops (el mínimo para cualquier operación de 256b), pero tienen latencia 3c y una por 4c de rendimiento.

Consulte la wiki de la etiqueta x86 para obtener información sobre el rendimiento , especialmente las tablas ins de Agner Fog .

Para los elementos de 64 bits, tenga en cuenta que los desplazamientos aritméticos a la derecha solo están disponibles en tamaños de elementos de 16 y 32 bits. Utilice una estrategia diferente si desea que todo el conjunto de elementos sea todo-cero / todo-uno para elementos de 4 bits y> 64 bits.

Con intrínsecos:

 __m256i bitmap2vecmask(int m) { const __m256i vshift_count = _mm256_set_epi32(24, 25, 26, 27, 28, 29, 30, 31); __m256i bcast = _mm256_set1_epi32(m); __m256i shifted = _mm256_sllv_epi32(bcast, vshift_count); // high bit of each element = corresponding bit of the mask return shifted; // use _mm256_and and _mm256_cmpeq if you need all bits set. //return _mm256_srai_epi32(shifted, 31); // broadcast the sign bit to the whole element } 

Dentro de un bucle, una LUT puede valer la huella de caché, dependiendo de la combinación de instrucciones en el bucle. Especialmente para el tamaño de elemento de 64 bits donde no hay mucha huella de caché, pero posiblemente incluso para 32 bits.


Otra opción, en lugar del cambio de variable, es usar BMI2 para desempaquetar cada bit en un byte con ese elemento de máscara en el bit alto, luego vpmovsx :

 ; 8bit mask bitmap in eax, constant in rdi pdep rax, rax, rdi ; rdi = 0b1000000010000000... repeating vmovq xmm0, rax vpmovsxbd ymm0, xmm0 ; each element = 0xffffff80 or 0 ; optional ;vpsrad ymm0, ymm0, 8 ; arithmetic shift to get -1 or 0 

Si ya tiene máscaras en un registro de enteros (donde tendría que vmovq / vpbroadcastd separado de todos modos), entonces esta forma es probablemente mejor incluso en Skylake donde los cambios de conteo variable son baratos.

Si sus máscaras comienzan en la memoria, el otro método ALU ( vpbroadcastd directamente en un vector) es probablemente mejor, porque las cargas de difusión son muy baratas.

Tenga en cuenta que pdep es 6 uops dependientes en Ryzen (latencia 18c, rendimiento 18c), por lo que este método es horrible en Ryzen incluso si sus máscaras comienzan en regs enteros.

(Los lectores del futuro, pueden editar en una versión intrínseca de esto. Es más fácil escribir asm porque es mucho menos tipeo, y las mnemotécnicas de asm son más fáciles de leer (no estúpido _mm256_ todo el lugar)).