El truco de la base 2^51 (2017)

• La suma de enteros grandes normalmente se procesa dividiéndolos en limbs de 64 bits, pero cuando se produce la propagación de acarreo, se vuelve difícil aprovechar bien la ejecución en paralelo de las CPU modernas
• adc en x86 depende del carry flag de la operación anterior y serializa la cadena de instrucciones, por lo que se convierte en un cuello de botella incluso en arquitecturas como Intel Haswell, que pueden ejecutar varios add en paralelo
• La representación en base 2^51 divide un valor de 256 bits en cinco posiciones de 2^51, en lugar de cuatro posiciones de 2^64, y usa los bits superiores sobrantes de cada limb como espacio de almacenamiento temporal para acarreos intermedios
• No es una forma de eliminar los acarreos; durante varias sumas, retrasa la propagación y luego la procesa de una sola vez en la etapa final de normalización
• En un benchmark simple sobre Haswell, incluso incluyendo el costo de conversión, a partir de tres sumas ya fue más rápida que el método en base 2^64, y la ventaja aumentó a medida que crecieron las iteraciones

---

Por qué el acarreo se vuelve un cuello de botella en la suma de enteros grandes

• La suma larga en papel avanza de derecha a izquierda, empezando por las unidades
  • Porque el resultado de cada posición depende del acarreo que llega desde la posición de la derecha
  • Si se suma desde la izquierda, un acarreo producido más tarde obligaría a corregir de nuevo los dígitos delanteros ya calculados
• La suma de enteros grandes tiene la misma restricción
  • Si los enteros de 256 bits x e y se dividen en cuatro limbs de 64 bits, se pueden sumar los limbs en la misma posición
  • Si ocurre un overflow en un limb inferior, ese 1 debe pasarse al limb superior
• adc de x86 es la instrucción que maneja esta propagación
  • Mira si hubo overflow en la operación anterior y suma 1 cuando hace falta
  • Una suma correcta de 256 bits continúa desde el limb menos significativo con la secuencia add, adc, adc, adc

La estructura que vuelve lento a adc en CPU modernas

• En general, adc tiene un costo de ejecución mayor que un add normal
  • adc usa una tercera entrada, llamada carry flag, por lo que es más complejo que add
  • Como se usa con menos frecuencia que add, los diseñadores de CPU tienen menos incentivos para invertir área del chip en optimizar el rendimiento de adc
• El problema más grande es la dependencia entre instrucciones
  • En Intel Haswell, un add individual tarda 1 ciclo en ejecutarse
  • En condiciones ideales, Haswell puede ejecutar hasta 4 add por ciclo
  • Haswell tiene 8 puertos de ejecución, y 4 de ellos pueden ejecutar add enteros
• Cuatro add independientes son fáciles de ejecutar en paralelo
  • En cambio, en una cadena de adc, cada instrucción depende de la salida del carry flag de la instrucción anterior
  • La CPU no puede paralelizar esas instrucciones y debe ejecutarlas en orden
• En SIMD la pérdida es aún mayor
  • vpaddq realiza cuatro sumas de 64 bits al mismo tiempo
  • Haswell puede ejecutar dos vpaddq por ciclo
  • Si se abandona ese paralelismo para manejar acarreos, se reduce la ventaja de rendimiento

Retrasar el acarreo visto con suma en papel

• Si se mantiene el valor posicional decimal, pero se amplía el conjunto de caracteres que puede entrar en cada posición, se puede retrasar el acarreo
  • En lugar de los dígitos normales 0-9, se usan también A-Z y *, para un total de 37 caracteres
  • Pero la base en sí no es base 37: sigue manteniendo valores posicionales decimales
• Aunque una posición supere 9, ya no hace falta acarrear de inmediato
  • 29 + 1 puede escribirse como 30, pero también como 2A, 1K o U
  • Si todos los dígitos de dos números están normalizados a 9 o menos, se puede postergar el acarreo durante la suma
• No se aplica siempre a todas las entradas
  • Si ya hay un valor grande en una posición, como 9 + W, hace falta acarrear
  • Entre números normalizados, se pueden sumar hasta cuatro números sin acarreo
• Al final, hay que normalizar de nuevo a la representación decimal común
  • Desde la derecha, se calcula cuántos grupos de 10 hay en cada posición
  • Esa cantidad se resta de la posición actual y se pasa a la siguiente
• La idea clave no es eliminar la propagación de acarreo, sino almacenarla durante los cálculos intermedios y propagarla una sola vez al final

Representación en base 2^51 en la computadora

• Si un valor de 256 bits se divide en cuatro limbs de 2^64, cada limb puede tomar valores de 0 a 2^64−1
  • Es una forma de ver cada limb como una posición en base 2^64
• Como no se puede ampliar el rango de enteros de 64 bits del hardware, se reduce el tamaño de la base
  • Un valor de 256 bits se divide en cinco posiciones de 2^51 en lugar de cuatro posiciones de 2^64
  • Cada limb se sigue almacenando como un entero de 64 bits, pero el valor real usa solo 51 o 52 bits
• Los bits superiores sobrantes se convierten en espacio de almacenamiento para acarreos intermedios
  • En cada limb entran 51 o 52 bits del número original
  • Los 12 o 13 bits restantes contienen los acarreos producidos durante el cálculo
• En la literatura criptográfica, esta técnica se llama radix 2^51 representation
• Si el número está normalizado, no hay que preocuparse por un overflow en los 13 bits superiores antes de sumar hasta 2^13 valores posibles de limb

Limb superior de 52 bits y normalización

• Al limb más significativo se le asignan 52 bits
  • Los demás limbs usan 51 bits
  • El acarreo del limb más significativo se ignora, de modo que los casos que superan 2^256−1 se tratan con wraparound
  • Esto es igual a la forma en que la suma de enteros unsigned de tamaño común en C hace wraparound ante overflow
• El código de suma en base 2^51 no usa una cadena de adc, sino que ejecuta cinco add independientes
  • En comparación con el método de cuatro limbs de 2^64, la cantidad de add aumenta de 4 a 5
  • A cambio, no hay dependencia del carry flag, por lo que es posible la ejecución en paralelo
• En la etapa de normalización se extraen los bits superiores de cada limb y se suman al siguiente limb superior
  • Con shr 51 se extrae la parte de acarreo
  • Con and 0x0007FFFFFFFFFFFF se deja solo la parte inferior de 51 bits
  • El limb más significativo se ajusta con and 0x000FFFFFFFFFFFFF
• La normalización es la etapa que realiza al final la propagación de acarreos que se había postergado
  • En las sumas intermedias no se crea dependencia del carry flag
  • Finalmente, cada limb se vuelve a ajustar dentro del rango permitido

Resultados de rendimiento y extensión a resta

• En un benchmark simple, la suma en base 2^51 mostró resultados más rápidos en una CPU Haswell
  • Incluyendo el costo de convertir hacia y desde la representación en base 2^51
  • Con solo tres sumas ya era más rápida que la suma en base 2^64
  • A medida que aumentaba el número de sumas, también crecía el ahorro
• La misma idea puede extenderse a la resta
  • En la resta, el acarreo se convierte en un carry negativo
• Para soportar resta, los limbs se tratan como enteros signed, no unsigned
  • Cada valor posicional puede ser positivo o negativo
  • Cada limb puede almacenar tanto carry positivo como carry negativo
• Este cambio tiene un costo
  • El bit superior de cada limb queda reservado como bit de signo
  • La cantidad de operaciones posibles entre normalizaciones se reduce de 2^13 a 2^12
• Aunque los datos se dividan en más registros y aumente la cantidad de operaciones, reducir la dependencia de acarreo puede mejorar el rendimiento total

[GN⁺]

Opiniones en Hacker News

• Me pregunto si no se podría dejar el limb más alto en 64 bits y los otros cuatro limbs en 48 bits cada uno.
  Antes de normalizar se podrían acumular más sumas, y si el conjunto de instrucciones tiene funciones útiles, al dividir y normalizar también se podría aprovechar la alineación de palabra; además, las características de overflow parecen iguales.

  • Si uno de los objetivos es hacer operaciones de 256 bits con 5 registros de 64 bits, entonces se están usando 256/5 = 51.2 bits por palabra, así que parece una distribución bastante ideal.
    Para una biblioteca genérica de enteros grandes quizá no sea óptimo, y antes, al no haber barrel shifters que hicieran shifts arbitrarios de bits de forma eficiente, probablemente convenía usar 56 bits de los 64 y dejar exactamente 1 byte para el carry.
    Como RISC-V no tiene flags, esta discusión es bastante relevante.
  • Si sumas los limbs más altos de dos números codificados, se produce overflow demasiado rápido.
    Por ejemplo, si ambos son 2^63, se desborda de inmediato; puede estar bien para aritmética con wraparound, pero no sirve para el caso general.
  • Si se hace eso, para guardar un valor de 256 bits se necesitan 6 palabras, no las 5 palabras del método original, y por lo tanto también más instrucciones de suma.

• Con AVX512, y en cierta medida también con AVX2, se puede implementar una suma de 256 bits de forma bastante eficiente, con la ventaja de guardar más números en registros.
  Es una combinación de _mm256_add_epi64, máscaras de comparación y máscaras de carry, y el throughput también parece mejor: https://godbolt.org/z/e7zETe8xY
  Pasarlo a suma de 512 bits también es sencillo, y ahí la mejora debería ser mayor.

  • En especial, en algunas arquitecturas de Intel, usar aunque sea un poco instrucciones AVX512 puede bajar la frecuencia de todo el procesador, así que el rendimiento puede terminar siendo irregular o incluso más lento.
    https://stackoverflow.com/questions/56852812/simd-instructio...

• En CPUs x86 suficientemente recientes, por ejemplo Intel Broadwell o AMD Ryzen, también se puede usar ADX, y hoy puede ser más rápido incluso en situaciones como Curve25519, donde la representación radix 2^51 tradicionalmente tenía ventaja.
  [1] https://en.wikipedia.org/wiki/Intel_ADX

• Como lecturas relacionadas, están los hilos anteriores sobre el radix 2^51 trick.
  The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - noviembre de 2022
  The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - mayo de 2020

• La idea central es que, aunque haya más operaciones, si en general son independientes se pueden ejecutar en paralelo y eso puede ser más rápido.
  A la inversa, aunque haya menos operaciones, si por dependencias de datos hay que ejecutarlas en serie, puede ser más lento; esta idea aplica mucho más allá de las operaciones con enteros largos.

  • Otro enfoque es usar los fragmentos de 64 bits normales, pero ejecutar en paralelo, de forma especulativa, cada suma con carry y sin carry, y luego elegir la correcta según el resultado del carry de la suma de menor orden.
    Se duplica la cantidad de sumas, pero el tiempo de propagación del carry se puede reducir de lineal a log(bits).
  • Lo que no me quedaba claro es que la técnica mostrada aquí parece centrarse en hacer que, al sumar N valores, el ripple carry ocurra una sola vez y no N-1 veces.
    La operación de carry es más compleja, pero las sumas reales se pueden paralelizar.
    Pero, para empezar, hay que dividir los números de entrada en grupos de 5 registros, así que me pregunto si, para obtener una ganancia global, esa división no tendría que ser también paralelizable.
  • Nvidia está explorando esa idea general, y parece estar obteniendo resultados bastante prometedores en algunos campos.
  • Esta regla se extiende incluso a supercomputadoras multinodo o a la nube.
    Si puedes usar 10,000 núcleos, el overhead es despreciable.

• Alguien que solo ha trabajado con x86_64 muestra muy bien que RISC-V no se equivocó al omitir el carry flag.

  • Se puede hacer de otra forma manteniendo limbs de 64 bits.
    La intuición clave es que, salvo que la suma en una determinada posición de limb sea todo unos, el carry que sale de esa posición no depende del carry que entra, sino solo de si la suma original en esa posición generó carry.
    Si la suma es todo unos, el carry que sale es igual al carry que entra.
    Si esto se expresa como una rama condicional que casi siempre se predice como not-taken, suponiendo que varias ramas condicionales puedan predecirse como not-taken en el mismo ciclo de reloj, cada bloque de instrucciones puede ejecutarse completamente en paralelo.
    Una vez cada 2^64 ejecuciones será muy lento.
    En una máquina 4-wide con números de 4 limbs no hay ventaja frente a adc, pero en una máquina 8-wide con números de 8 limbs la ganancia empieza a ser grande.
    Puede que no ayude mucho en x86_64 actual, pero en la serie Apple M, donde el M1 también es 8-wide, tiene potencial, aunque por el ISA de Arm el rodeo puede ser complicado.
    Cuando el Ascalon RISC-V 8-wide de Tenstorrent salga a fines de este año o a comienzos de 2026, junto con Ventana, Rivos, XiangShan y otros, se podrá comprobar en la práctica.
    Si hay un shift rápido de 1 lane, también funciona mejor en SIMD ancho, y en RISC-V a eso se le llama slideup.
  • Todavía hay muchos casos comunes en los que carry-save addition es peor que add-with-carry.
    Los dos algoritmos de suma multipalabra no se reemplazan entre sí y tienen usos distintos, así que un ISA decente incluye instrucciones ADC/SBB, y el costo adicional es mínimo.
    Tampoco hace falta necesariamente un registro de flags dedicado; algunos ISA guardan los flags de carry y borrow en registros de propósito general cuando se necesitan.
    La falta de carry en RISC-V no es su peor característica; peor es que no tenga flag de overflow entero.
    Detectar overflow entero es esencial en programas que afirman estar escritos de forma segura, y esquivarlo en software reduce el rendimiento alcanzable mucho más que esquivar la ausencia de carry.
  • Esta línea de diseño al final viene de que C omitió el carry flag, y en la práctica casi dejó de usarse para carry.
  • Si el carry flag de todos modos es lento, no fui el único que pensó: “¿entonces de qué se trataba la controversia de RISC-V GMP?”.

• Este radix trick también se aplica a estructuras de datos.
  Hay buenos ejemplos en el libro de Okasaki, 『Purely Functional Data Structures』.

• Ojalá hubiera visto este artículo hace unos meses.
  Intentando codificar y decodificar un búfer en una base arbitraria, llegué demasiado tarde a la conclusión de que el carry podía propagarse hasta el final del búfer y que eso volvía el algoritmo mucho más lento.
  La solución final también tenía algo parecido a este truco: dividir el búfer en chunks y dejar espacio libre para manejar el carry.
  No era exactamente lo mismo; dejaba algunos bits desperdiciados, usando un poquito más de almacenamiento o ancho de banda de red a cambio de reducir el cálculo.
  Me pregunto si acumulando los carries de esta forma y resolviéndolos en una etapa posterior se podría obtener lo mejor de ambos mundos, aunque quizá sea solo un deseo.

• Sé que las pautas de HN dicen que no se edite el título, pero no me gustan los títulos clickbait que inflan demasiado una afirmación pequeña.
  El título de este artículo debería haber sido algo como “El truco radix 2^51 para sumar enteros de 64 bits en paralelo en algunas arquitecturas x86 sin ralentizar el pipeline por dependencias de carry”.