performance - ¿Pueden las rutinas enteras largas beneficiarse del SSE?

integer bignum

Question

Todavía estoy trabajando en rutinas para enteros largos arbitrarios en C ++. Hasta ahora, he implementado sumas / restas y multiplicaciones para CPU Intel de 64 bits.

Todo funciona bien, pero me pregunté si podría acelerarlo un poco usando SSE. Hojeé los documentos de SSE y las listas de instrucciones del procesador, pero no pude encontrar nada que creo que pueda usar y aquí es por qué:

• SSE tiene algunas instrucciones de enteros, pero la mayoría de las instrucciones manejan el punto flotante. No parece que haya sido diseñado para usarse con enteros (por ejemplo, ¿existe una comparación de enteros por menos?)

• La idea de SSE es SIMD (la misma instrucción, datos múltiples), por lo que proporciona instrucciones para 2 o 4 operaciones independientes. Por otro lado, me gustaría tener algo así como un agregado de entero de 128 bits (entrada y salida de 128 bits). Esto no parece existir. (¿Aún? ¿En AVX2 tal vez?)

• Las adiciones y sustracciones de enteros no manejan entradas ni salidas. Así que es muy engorroso (y por lo tanto, lento) hacerlo a mano.

Mi pregunta es: ¿es correcta mi evaluación o hay algo que he pasado por alto? ¿Pueden las rutinas enteras largas beneficiarse del SSE? En particular, ¿pueden ayudarme a escribir una rutina de adición, sub o mul más rápida?

Answer 1

En el pasado, la respuesta a esta pregunta era un sólido "no". Pero a partir de 2017, la situación está cambiando.

Pero antes de continuar, es hora de una terminología de fondo:

1. Aritmética completa de la palabra
2. Aritmética parcial de palabras

Aritmética de palabra completa:

Esta es la representación estándar donde el número se almacena en la base 2 ³² o 2 ⁶⁴ usando una matriz de enteros de 32 bits o de 64 bits. Muchas bibliotecas y aplicaciones bignum (incluyendo GMP) utilizan esta representación.

En la representación de palabra completa, cada entero tiene una representación única. Operaciones como las comparaciones son fáciles. Pero cosas como la adición son más difíciles debido a la necesidad de propagación por acarreo.

Es esta propagación portadora lo que hace que la aritmética bignum sea casi imposible de vectorizar.

Aritmética de palabra parcial

Esta es una representación menos utilizada donde el número usa una base menor que el tamaño de palabra del hardware. Por ejemplo, poner solo 60 bits en cada palabra de 64 bits. O usar una base de 1,000,000,000 con un tamaño de palabra de 32 bits para la aritmética decimal.

Los autores de GMP llaman a esto, "clavos", donde "clavo" es la parte no utilizada de la palabra.

En el pasado, el uso de aritmética de palabras parciales se limitaba principalmente a aplicaciones que trabajaban en bases no binarias. Pero hoy en día, es cada vez más importante ya que permite retrasar la propagación del transporte.

Problemas con la aritmética de palabra completa:

Vectorizar aritmética de palabra completa ha sido históricamente una causa perdida:

1. SSE / AVX2 no tiene soporte para la propagación de acarreo.
2. SSE / AVX2 no tiene ninguna adición / sub de 128 bits.
3. SSE / AVX2 no tiene multiplicidad de enteros de 64 x 64 bits. *

* AVX512-DQ agrega una mitad inferior de 64 x 64 bits de multiplicación. Pero todavía no hay instrucción en la mitad superior.

Además, x86 / x64 tiene muchas instrucciones escalares especializadas para bignums:

• Add-with-Carry: adc , adcx , adox .
• Multiplicación de palabras dobles: un solo operando mul y mulx .

En vista de esto, tanto bignum-add como bignum-multiply son difíciles para SIMD para vencer al escalar en x64. Definitivamente no con SSE o AVX.

Con AVX2, SIMD es casi competitivo con el aumento múltiple multiplicador escalar si reorganiza los datos para permitir la "vectorización vertical" de 4 multiplicaciones diferentes (e independientes) de las mismas longitudes en cada una de las 4 vías SIMD.

AVX512 inclinará las cosas más a favor de que SIMD asuma nuevamente la vectorización vertical.

Pero en su mayor parte, la "vectorización horizontal" de los bignums sigue siendo en gran medida una causa perdida a menos que tenga muchos de ellos (del mismo tamaño) y pueda pagar el costo de transponerlos para hacerlos "verticales".

Vectorización de aritmética de palabra parcial

Con aritmética de palabras parciales, los bits adicionales "clave" le permiten retrasar la propagación de acarreo.

Por lo tanto, mientras usted no rebosa la palabra, SIMD add / sub se puede hacer directamente. En muchas implementaciones, la representación de palabras parciales utiliza números enteros con signo para permitir que las palabras se vuelvan negativas.

Debido a que (por lo general) no hay necesidad de llevar a cabo, la adición / subimisión de SIMD en palabras parciales se puede hacer con la misma eficiencia en los bignums vectorizados vertical y horizontalmente.

La realización de bignums vectorizados horizontalmente aún es barata, ya que simplemente se desplazan las uñas hacia el próximo carril. Por lo general, no es necesario realizar un traspaso completo para limpiar completamente las brocas y llegar a una representación única, a menos que necesite hacer una comparación de dos números que sean casi iguales.

La multiplicación es más complicada con la aritmética de palabras parciales, ya que necesitas lidiar con los bits de clavos. Pero al igual que con add / sub, sin embargo, es posible hacerlo de manera eficiente en bignums vectorizados horizontalmente.

AVX512-IFMA (que vendrá con los procesadores Cannonlake) tendrá instrucciones que proporcionen los 104 bits completos de una multiplicación de 52 x 52 bits (probablemente utilizando el hardware FPU). Esto funcionará muy bien con representaciones de palabras parciales que usan 52 bits por palabra.

Multiplicación grande utilizando FFTs

Para bignos realmente grandes, la multiplicación se realiza de manera más eficiente utilizando transformadas rápidas de Fourier (FFT) .

Las FFT son completamente vectorizables ya que trabajan en double s independientes. Esto es posible porque, fundamentalmente, la representación que utilizan las FFT es una representación parcial de la palabra.

En resumen, es posible la vectorización de la aritmética bignum. Pero hay que hacer sacrificios.

Si espera que SSE / AVX pueda acelerar algunos códigos bignum existentes sin cambios fundamentales en la representación y / o el diseño de los datos, es probable que eso no suceda.

Pero sin embargo, la aritmética bignum es posible vectorizar.

Revelación:

Soy el autor de y-cruncher que hace un montón de gran número de medicamentos.