El truco de la base 2^51 (2017)

• El problema del carry (acarreo) que aparece en las operaciones con enteros grandes es una de las principales razones por las que resulta difícil paralelizar los cálculos
• En la arquitectura x86, la instrucción adc para manejar carry es más lenta que la instrucción normal add, y el procesamiento continuo de carry limita la ejecución en paralelo
• Si se usa la representación en radix 2^51, se puede retrasar la propagación del carry y realizar más sumas rápidamente
• A cada limb (valor parcial) se le asignan solo 51 o 52 bits, y el espacio restante de bits superiores se usa como almacenamiento temporal para carry
• Esta técnica, a pesar del uso adicional de registros y del costo de conversión, en la práctica ofrece mejor rendimiento que la base 2^64

---

Suma y resta rápidas: el problema del carry

• En la suma de enteros grandes, igual que una persona maneja el carry dígito por dígito al hacer cuentas a mano, la computadora también tiene dificultades para paralelizar el algoritmo de suma debido al carry
• Básicamente, sumamos desde la derecha (dígitos menos significativos) uno por uno, y el carry generado en cada posición se transfiere a la izquierda (dígitos más significativos)
• Si la suma empezara desde la izquierda, el carry previo afectaría la operación de la siguiente posición, por lo que no se podría paralelizar el orden de cálculo

Cómo se maneja el carry en la computadora

• La computadora procesa sumas en unidades de enteros de 64 bits
• Puede parecer que un entero de 256 bits puede dividirse en 4 limbs de 64 bits y sumarse en paralelo, pero en la práctica hay que manejar el overflow (carry) para obtener el resultado correcto
• En x86 existe la instrucción adc (add with carry), que maneja automáticamente el carry

Causa de la pérdida de rendimiento

• La instrucción adc requiere un valor de entrada adicional llamado carry flag, por lo que rinde peor que una add simple
• En la arquitectura Haswell, add puede ejecutarse en paralelo en varios puertos, mientras que adc inevitablemente requiere ejecución serial (secuencial)
• En particular, al usar instrucciones SIMD (vpaddq, etc.), la suma paralela sin carry es mucho más rápida

La idea de retrasar el carry (ejemplo en papel)

• Para reducir el carry, se puede ampliar el rango de dígitos (por ejemplo, de 0-9 a 0-9, A-Z y *) y así sumar temporalmente varios números sin carry
• De esta forma, se pueden hacer varias sumas sin propagar carry y al final ordenar el carry de una sola vez (normalization)
• Este concepto separa la acumulación y la propagación del carry para que solo se procese al final
• En la operación real, si aparece un valor por encima del valor base del dígito, el carry se acumula y refleja en orden de derecha a izquierda

Aplicación en computadora del carry diferido (truco radix 2^51)

• Para reducir la propagación del carry en la computadora, se usa la representación radix 2^51
• En lugar de dividir 256 bits en 4 limbs de 64 bits, se divide en 5 limbs de 51~52 bits cada uno
  • Los 12~13 bits superiores de cada limb funcionan como almacenamiento temporal para carry
• Con este método, cada limb mantiene el rango de valores de 2^64 y, como durante la operación real el carry no aparece fácilmente, se pueden ejecutar varias operaciones en paralelo sin carry
• Se necesita una normalization (normalización) una vez cada aproximadamente 2^13 operaciones consecutivas
• En CPUs Haswell, después de aplicar radix 2^51, al ejecutar repetidamente solo sumas simples sin carry, el rendimiento mejora notablemente frente al radix 2^64 normal
• La carry propagation para normalization se realiza solo una vez al final

Ejemplo de código

• Al repartir el valor en 5 registros, es posible hacer sumas sin carry
• La normalization repite el proceso de extraer los bits superiores de cada limb, sumarlos al limb vecino y dejar en 0 su propio valor de carry

Extensión a la resta

• La resta también puede aplicarse de manera similar
• En este caso, el carry también puede ser negativo, por lo que el limb se trata como signed integer
• El bit más alto del limb se asigna como bit de signo, así que la cantidad de operaciones que pueden procesarse de una vez se reduce ligeramente en comparación con la suma

Conclusión

• La técnica de resistencia al carry (o carry diferido), a pesar de aumentar la cantidad de limbs y agregar trabajo de conversión, realmente mejora mucho el rendimiento total de las operaciones
• El truco radix 2^51 se usa ampliamente en campos que requieren alto rendimiento, como operaciones con enteros grandes y criptografía
• Esta técnica es una idea importante para optimizar el rendimiento real del hardware y de los algoritmos

[GN⁺]

Opiniones en Hacker News

• Al ver el número 2^51, al principio pensé que sería sobre almacenar enteros en tipo double, pero luego recordé que el valor máximo que puede representarse exactamente como entero en double es 2^53-1

• AVX512 (y en cierta medida también AVX2) ofrece un entorno donde es posible implementar sumas de 256 bits de forma bastante eficiente, con la ventaja adicional de poder meter más números en registros
  Un ejemplo directo funciona como en el siguiente código

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

Incluso muestra mejoras en throughput, así que el ejemplo de código real puede verse en godbolt.org
Extender esta lógica hasta sumas de 512 bits también es muy simple

• En particular, se señala que en ciertas arquitecturas de CPU Intel, con solo usar instrucciones AVX512 ya puede bajar el reloj total del procesador, lo que lleva a un rendimiento general inconsistente o incluso peor
  La referencia relacionada puede verse en este enlace de Stack Overflow

• Ante la duda de “¿por qué no usar 12 bits en lugar de 13?”, aquí se ignora el manejo del carry del bit más alto (limb), para que en caso de overflow funcione con wraparound
  Como resultado, al limb más alto se le asignan 52 bits, así que aunque tiene la desventaja de quedarse sin espacio antes que los otros limbs, funciona de forma parecida a una suma de enteros sin signo en C
  Entonces se propone: ¿qué tal asignar 64 bits al limb más alto y 48 bits a los otros cuatro limbs?
  Eso permitiría acumular más operaciones antes de normalizar, y además tendría ventajas como la alineación por palabra
  La característica del manejo de overflow sería la misma

  • Si solo al limb más alto se le asignan 64 bits, al sumar los limbs de dos números el overflow ocurre demasiado pronto
    Por ejemplo, si ambos valen 2^63, se produce overflow de inmediato
    En aritmética con wraparound eso no importa, pero en el caso general no es viable

  • Con esa estructura se necesitarían 6 palabras en lugar de 5, como en el OP
    También harían falta más instrucciones

  • El objetivo es resolver aritmética de 256 bits con 5 registros de 64 bits
    Es decir, lo ideal sería repartir 256/5 = 51.2 bits por palabra
    Si esto se limita a 256 bits, está bien, pero no es lo óptimo para una biblioteca big-int de propósito general
    Antes existía el antecedente de querer usar exactamente 1 byte por carry, y en la época sin barrel shifter se prefería usar solo 56 de 64 bits para facilitar la alineación
    En RISC-V esta discusión es aún más importante porque no hay flags en hardware

• En CPUs x86 modernas (por ejemplo, Intel Broadwell y AMD Ryzen), usando instrucciones Intel ADX, la representación radix 2^51 puede incluso ser más rápida en situaciones donde tradicionalmente dominaba (por ejemplo, Curve25519)

• Como material de discusión relacionado

  • The radix 2^51 trick (noviembre de 2022)
  • The radix 2^51 trick (2017)

• La lección clave es que, si las operaciones son independientes entre sí, ejecutar más operaciones en paralelo puede terminar siendo más rápido
  Por el contrario, si por dependencias hay que ejecutarlas secuencialmente, entonces incluso con menos operaciones puede ser más lento
  Esta idea puede aplicarse no solo a enteros largos, sino también a muchas otras áreas

  • Se propone dividir en chunks de 64 bits y ejecutar por adelantado, en paralelo, los dos casos según haya carry o no, para luego elegir la operación correcta según el resultado real del carry
    Este método duplica la cantidad de sumas, pero acelera la propagación a un nivel de log(bits) en vez de lineal

  • La parte que no había entendido bien de esta técnica es que, en esencia, hace que el ripple carry, que al sumar N valores se ejecutaría N-1 veces, se ejecute una sola vez
    El manejo de carry se vuelve más complejo, pero la suma sí puede paralelizarse
    Eso sí, para que la eficiencia total valga la pena, la propia división de los números de entrada en unidades de 5 registros también tendría que paralelizarse

  • Esta regla puede extenderse incluso al nivel de supercomputadoras o la nube con decenas de miles de nodos
    Si se pueden usar muchos núcleos, el overhead pasa a ser despreciable

  • A NVidia también le interesa esta idea y está dando buenos resultados en varias áreas

• Aunque las guías de HN dicen que no se debe agregar opinión en el título, no me gustan los títulos exagerados tipo clickbait
  Creo que algo como “el truco de radix 2^51 para suma paralela de enteros de 64 bits sin dependencia de carry en algunas arquitecturas x86” sería más preciso

• Da pena pensar que me habría servido leer este artículo unos meses antes
  Tuve la experiencia de que, al codificar y decodificar un buffer en una base arbitraria, el carry se propagaba por todo el buffer y volvía el algoritmo mucho más lento
  Al final dejé 'espacio libre' y lo dividí en chunks para manejar el carry, y parece tener similitudes con este truco
  En la práctica elegí desperdiciar algunos bits a cambio de ahorrar cómputo o ancho de banda de red
  Me pregunto si este tipo de manejo de carry también podría agruparse como postprocesamiento
  Ojalá haya una estructura con la que se puedan obtener prácticamente todas las ventajas

• Mi experiencia usando solo entornos x86_64 deja claro que, en RISC-V, no tener carry flag tampoco implica necesariamente un mal enfoque

  • Además de este método, se explica otra forma de mantener limbs de 64 bits y hacer sumas seguras respecto al carry usando únicamente variables uint64_t
    El flujo sería algo así

  s0 += a0;
  s1 += a1;
  s2 += a2;
  s3 += a3;
  c0 = s0 < a0; // RISC-V sltu
  c1 = s1 < a1;
  c2 = s2 < a2;
  if (s1 == -1) goto propagate0;
  check_s2:
  if (s2 == -1) goto propagate1;
  add_carries:
  s1 += c0;
  s2 += c1;
  s3 += c2;
  goto done;
  propagate0: c1 = c0; goto check_s2;
  propagate1: c2 = c1; goto add_carries;
  done:
  

  La clave es que, cuando el resultado de la suma (limb) no es todo 1s, el carry out de ese limb no depende del carry in, sino solo del resultado de sumar los valores originales
  En cambio, si el valor es todo 1s, entonces carry out = carry in
  Si la estructura de ramas casi no necesita predicción, puede ejecutarse completamente en paralelo
  Probabilísticamente solo se vuelve más lenta en 1 de cada 2^64 casos, aunque en una máquina de 4 vías no hay gran ganancia
  En una máquina de 8 vías o con una estructura de 8 limbs sí puede haber una mejora de rendimiento significativa
  No encaja en x86_64, pero en máquinas de 8 vías como la serie Apple M* podría ser aprovechable
  Hay expectativas de futuro en el procesador RISC-V Ascalon de 8 vías de Tenstorrent, así como en Ventana, Rivos, XiangShan y otros
  En arquitecturas SIMD o con instrucciones rápidas de shift (slideup) de 1 lane, el efecto se maximiza

  • La suma carry-save no siempre supera a add-with-carry
    Los dos tipos de algoritmos de suma multi-word no son intercambiables y cada uno tiene ventajas y desventajas
    Por eso las instrucciones ADC/SBB deberían venir incluidas de base en la ISA, y también es posible guardar flags en registros
    Una desventaja más seria en RISC-V es que no tiene integer overflow flag
    Cuando se necesita un workaround por software para detectar overflow, la caída de rendimiento es mucho peor que la de emular el bit de carry

  • La ausencia de carry flag en RISC-V se deriva de que el lenguaje C ignoró el carry flag binario
    En la práctica, la frecuencia de uso del carry flag es bastante baja

  • No fui el único en pensar “si el carry flag de todos modos es lento, entonces ¿por qué existió la polémica sobre risc5 gmp?”

• El 'radix trick' también puede aplicarse a estructuras de datos
  Hay un ejemplo interesante en el libro 'Purely Functional Data Structures' de Okasaki