En el pasado, la respuesta a esta pregunta era sólida, "no". Pero a partir de 2017, la situación está cambiando.
Pero antes de continuar, el tiempo para algunos antecedentes de la terminología:
- completa Palabra aritmética
- parcial Palabra aritmética
Full-Palabra Aritmética:
Este es la representación estándar donde se almacena el número en la base 2 o 2 usando una matriz de enteros de 32 bits o 64 bits. Muchas bibliotecas y aplicaciones bignum (incluido GMP) utilizan esta representación.
En representación de palabra completa, cada número entero tiene una representación única. Las 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 de propagación.
Es esta propagación de arrastre lo que hace que la aritmética de bignum sea casi imposible de vectorizar.
con palabras incompletas aritmética
Ésta es una versión de menor difusión, donde el número utiliza una base menos que el hardware de la palabra de tamaño. Por ejemplo, poniendo solo 60 bits en cada palabra de 64 bits. O utilizando la base 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 el "clavo" es la parte no utilizada de la palabra.
En el pasado, el uso de la aritmética de palabras parciales se limitaba principalmente a las aplicaciones que trabajan en bases no binarias. Pero hoy en día, se está volviendo más importante ya que permite retrasar la propagación de portes.
problemas con la aritmética completa-Word:
Vectorización-palabra completa aritmética ha sido históricamente una causa perdida:
- SSE/AVX2 no tiene soporte para equipaje de propagación.
- SSE/AVX2 no tiene adición/sub de 128 bits.
- SSE/AVX2 no tiene entero de 64 x 64 bits se multiplican. *
* AVX512-DQ añade una mitad inferior de 64x64 bits se multiplican. Pero todavía no hay instrucción de la mitad superior.
Además, x86/x64 tiene un montón de escalares especializados instrucciones de bignums:
- Add-con-Carry:
adc, adcx, adox.
- Multiplicación de doble palabra: operando solo
mul y mulx.
En vista de esto, tanto el bignum-add como el bignum-multiplican son difíciles de superar para el SIMD escalar en x64. Definitivamente no con SSE o AVX.
Con AVX2, SIMD es casi competitivo con escalar bignum-multiplican si reorganiza los datos para habilitar "vectorización vertical" de 4 diferente (e independientes) se multiplica de las mismas longitudes en cada uno de los 4 carriles de SIMD.
AVX512 inclinará las cosas más a favor de SIMD asumiendo nuevamente la vectorización vertical.
Pero en su mayor parte, la "vectorización horizontal" de bignums sigue siendo una causa perdida a menos que tenga muchos (del mismo tamaño) y pueda pagar el costo de transponerlos para hacerlos "verticales".
vectorización del Parcial-Word aritmética
Con la aritmética palabra parcial, el extra de bits "uñas" le permiten retrasar equipaje de propagación.
De modo que mientras usted no desborde la palabra, SIMD add/sub se puede hacer directamente. En muchas implementaciones, la representación de palabras parciales usa enteros con signo para permitir que las palabras se vuelvan negativas.
Debido a que (generalmente) no es necesario llevar a cabo el trabajo de desecho, las palabras parciales SIMD add/sub se pueden realizar de manera igualmente eficiente en bignums vectorizados vertical y horizontalmente.
El arrastre en bignums vectorizados horizontalmente sigue siendo económico, ya que simplemente desplaza los clavos en la siguiente línea.Por lo general, no es necesario llevar a cabo una tarea completa para despejar por completo las uñas y lograr 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 debe ocuparse de las uñas. Pero al igual que con add/sub, sin embargo, es posible hacerlo de manera eficiente en bignums horizontalmente vectorizados.
AVX512-IFMA (viene con procesadores Cannonlake) tendrá instrucciones que dan los 104 bits completos de una multiplicación de 52 x 52 bits (presumiblemente utilizando el hardware FPU). Esto funcionará muy bien con representaciones de palabras parciales que usan 52 bits por palabra.
grandes utilizando FFT multiplicación
Por muy grandes bignums, la multiplicación se hace más eficiente el uso de Fast-Fourier Transforms (FFTs).
Las FFT son completamente vectorizables ya que funcionan en double s independientes. Esto es posible porque, fundamentalmente, la representación que utilizan las FFT es una representación de palabra parcial.
En resumen, es posible la vectorización de la aritmética de bignum. Pero los sacrificios deben hacerse.
Si espera que SSE/AVX pueda acelerar algún código bignum existente sin cambios fundamentales en la representación y/o disposición de los datos, no es probable que suceda.
Pero, sin embargo, la aritmética de bignum se puede vectorizar.
Revelación:
Soy el autor de y-cruncher lo que hace un montón de grandes arihmetic número.
Esperamos con interés MULX, ADCX, ADOX en Haswell/Broadwell ... –
Gran respuesta. Creo que soy otro de los muchos que lo han intentado y han fallado. –
Pero no entiendo el punto sobre "No hay número entero de 128 bits add/sub". ¿Por qué es esto un problema? Los registros de propósito general/escalares tampoco tienen hardware para esto. La forma de hacerlo es dos tiendas hi y baja en registros SIMD separados. –