¿Es posible el práctico BigNum AVX/SSE?

biginteger simd

Question

Los registros SSE / AVX pueden verse como números enteros o de coma flotante BigNums. Es decir, uno podría descuidar que existen carriles en absoluto. ¿Existe una manera fácil de explotar este punto de vista y utilizar estos registros como BigNums, ya sea de forma individual o combinada? Pregunto porque, por lo poco que he visto de las bibliotecas BigNum, casi universalmente almacenan y hacen aritmética en matrices, no en registros SSE / AVX. ¿Portabilidad?

Ejemplo:

Supongamos que almacena el contenido de un registro SSE como clave en un std::set , podría comparar estos contenidos como un BigNum.

Answer 1

Creo que es posible implementar BigNum con SIMD de manera eficiente, pero no de la manera que sugiere.

En lugar de implementar un BigNum único utilizando un registro SIMD (o con una matriz de registros SIMD), debe procesar múltiples BigNums a la vez.

Consideremos la adición de 128 bits. Dejemos que los enteros de 128 bits se definan mediante un par de valores altos y bajos de 64 bits y supongamos que queremos agregar un entero de 128 bits (y_low, y_high) a un entero de 128 bits (x_low, x_high) . Con los registros escalares de 64 bits esto requiere solo dos instrucciones

add rax, rdi // x_low  += y_low;
adc rdx, rsi // x_high += y_high + (x_low < y_low);

Con SSE / AVX, el problema, como han explicado otros, es que no hay banderas de transporte SIMD. La bandera de acarreo debe calcularse y luego agregarse. Esto requiere una comparación sin signo de 64 bits. La única opción realista para esto con SSE es de la instrucción AMD XOP vpcomgtuq

vpaddq      xmm2, xmm0, xmm2 // x_low  += y_low;
vpcomgtuq   xmm0, xmm0, xmm2 // x_low  <  y_low
vpaddq      xmm1, xmm1, xmm3 // x_high += y_high
vpsubq      xmm0, xmm1, xmm0 // x_high += xmm0

Utiliza cuatro instrucciones para agregar dos pares de números de 128 bits. Con los registros escalares de 64 bits, esto también requiere cuatro instrucciones (dos add y dos adc ).

Con AVX2 podemos agregar cuatro pares de números de 128 bits a la vez. Pero no hay una instrucción sin signo de 64 bits de 256 bits de ancho de XOP. En cambio, podemos hacer lo siguiente para a<b :

__m256i sign64 = _mm256_set1_epi64x(0x8000000000000000L);
__m256i aflip = _mm256_xor_si256(a, sign64);
__m256i bflip = _mm256_xor_si256(b, sign64);
__m256i cmp = _mm256_cmpgt_epi64(aflip,bflip);

El registro sign64 puede calcular previamente, por lo que solo tres instrucciones son realmente necesarias. Por lo tanto, puede agregar cuatro pares de números de 128 bits con AVX2 con seis instrucciones

vpaddq
vpaddq
vpxor
vpxor
vpcmpgtq 
vpsubq

mientras que los registros escalares necesitan ocho instrucciones.

AVX512 tiene una sola instrucción para hacer vpcmpuq comparación sin signo de 64 bits. Por lo tanto, debería ser posible agregar ocho pares de números de 128 bits utilizando solo cuatro instrucciones

vpaddq
vpaddq
vpcmpuq
vpsubq

Con el registro escalar se requerirían 16 instrucciones para agregar ocho pares de números de 128 bits.

Aquí hay una tabla con un resumen del número de instrucciones SIMD (llamadas nSIMD) y el número de instrucciones escalares (llamadas nscalar) necesarias para agregar una cantidad de pares (llamados pares n) de números de 128 bits

              nSIMD      nscalar     npairs
SSE2 + XOP        4           4           2
AVX2              6           8           4
AVX2 + XOP2       4           8           4
AVX-512           4          16           8

Tenga en cuenta que XOP2 aún no existe y solo estoy especulando que puede existir en algún momento.

Tenga en cuenta también que para hacer esto de manera eficiente, las matrices BigNum deben almacenarse en una matriz de forma de estructura de matriz (AoSoA). Por ejemplo, usar l para significar los 64 bits más bajos y h para significar los 64 bits más altos que una matriz de enteros de 128 bits almacena como una matriz de estructuras como esta

lhlhlhlhlhlhlhlh

en su lugar debería almacenarse usando un AoSoA como este

SSE2:   llhhllhhllhhllhh
AVX2:   llllhhhhllllhhhh
AVX512: llllllllhhhhhhhh

Answer 2

Es posible, pero no práctico.

Como dije en la otra respuesta , no hay un indicador de acarreo en AVX / SSE, por lo que es imposible hacer sumas y restas de manera eficiente. Y para hacer multiplicaciones necesitarás muchos movimientos aleatorios para obtener el resultado de multiplicación de ampliación en la posición deseada.

Si se le permite trabajar con la nueva microarquitectura Haswell / Broadwell, la solución sería MULX en BMI2 y ADOX, ADCX en ADX . Puedes leer sobre ellos here .

Answer 3

Movido del comentario anterior

Es posible hacer esto, pero no se hace porque no es particularmente conveniente implementar bignums en registros vectoriales.

Para la simple tarea de agregar, es trivial usar la bandera de transporte del registro x86 EFLAGS / RFLAGS para propagar las cargas de la adición desde la "extremidad" más baja (para usar la terminología GMP ), y recorrer una cantidad arbitraria de extremidades colocadas en una matriz

Por el contrario, los carriles de los registros SSE / AVX no tienen indicadores de acarreo, lo que significa que el desbordamiento debe detectarse de una manera diferente que implique comparaciones para detectar envoltura, que es más computacionalmente intenso. Además, si se detecta un desbordamiento en una extremidad, tendría que propagarse mediante una mezcla fea "hacia arriba", y luego agregarse, y esta adición puede causar otro desbordamiento y arrastre, hasta N-1 veces para un N miembro bignum. Luego, una vez que una suma trae un bignum más allá de 128 bits / 256 bits (o más allá de 128 bits x # de registros), de todos modos tendría que moverlo a una matriz.

Por lo tanto, se necesitaría mucho código de casos especiales, y no sería más rápido (de hecho, mucho más lento), solo para agregarlo. ¿Imagina lo que se necesitaría para la multiplicación? o jadeo, división?