🔢 mathematics

Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic

Este artículo propone y evalúa nuevos algoritmos de multiplicación-acumulación fusionada sin saltos para aritmética de precisión múltiple de doble palabra, triple palabra y cuádruple palabra, demostrando que logran mejoras de rendimiento adicionales sobre los métodos existentes al eliminar las bifurcaciones condicionales.

Autores originales: Tomonori Kouya

Publicado 2026-07-14

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Tomonori Kouya

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando construir una calculadora súper precisa utilizando solo piezas de Lego estándar. Estas piezas de Lego son los números de punto flotante normales de tu computadora. Normalmente, cuando apilas estas piezas para hacer un "doble-palabra" (dos piezas), "triple-palabra" (tres piezas) o "cuádruple-palabra" (cuatro piezas), tienes que estar constantemente comprobando el tamaño de las piezas mientras construyes. Si una pieza es demasiado grande o demasiado pequeña, tienes que detenerte, hacer una pausa y reorganizar la pila. En el mundo de los chips de computadora, estas "pausas" se llaman ramas (branches).

Cuando intentas construir un millón de estas pilas a la vez (como en una tarjeta gráfica moderna o un procesador potente), estas pausas se convierten en una pesadilla. Es como un embotellamiento donde cada coche tiene que detenerse y consultar una señal diferente antes de avanzar. Algunos coches van a la izquierda, otros a la derecha, y toda la fila se detiene por completo. Esto se llama "divergencia de carriles" (lane divergence), y destruye el rendimiento.

El Gran Descubrimiento: La Autopista "Sin Paradas"
El artículo de Tomonori Kouya introduce una nueva forma de construir estas pilas que nunca se detiene a consultar las señales. Es un algoritmo "libre de ramas" (branch-free). En lugar de preguntar "¿Es esta pieza lo suficientemente grande?" y esperar una respuesta, el nuevo método utiliza una ruta inteligente y pre-planificada que funciona perfectamente sin importar cómo sean las piezas.

El artículo demuestra, utilizando un robot matemático superinteligente (un resolvedor SMT llamado FPANVerifier), que esta nueva ruta es segura y precisa para todos los formatos de computación estándar. El hallazgo principal es que, al eliminar estas pausas de "detenerse y comprobar", la computadora puede calcular mucho más rápido.

El Truco de Magia: Fusionar el Movimiento
El artículo se centra en un movimiento específico llamado Multiplicación-Suma Fusionada (FMA). Imagina que tienes que multiplicar dos números y luego sumar un tercero. Normalmente, haces esto en dos pasos:

Multiplicar (y quizás hacer una pausa para corregir el resultado).
Sumar (y quizás hacer otra pausa también).

El autor propone una versión "Fusionada" que hace ambos en un solo movimiento fluido, como un ninja que lanza un cuchillo y lo atrapa en el mismo aliento.

Para Doble-Palabra (2 piezas): El método antiguo tomaba 29 pasos. El nuevo método toma solo 17.
Para Triple-Palabra (3 piezas): El método antiguo tomaba 96 pasos. El nuevo método toma 66.
Para Cuádruple-Palabra (4 piezas): El método antiguo tomaba 209 pasos. El nuevo método toma 146.

El artículo también analiza un método de "atajo" propuesto por otros investigadores (el método de 6 pasos). Crucialmente, este atajo NO es generalmente válido. Es una herramienta de alta velocidad que solo funciona si los números ya están perfectamente dispuestos de una manera específica (específicamente, si el número sumado es al menos dos veces más grande que el producto). Si intentas usar este atajo en problemas matemáticos generales como la división o la raíz cuadrada, donde no puedes garantizar que esos números se alineen, la precisión se degrada gravemente. El nuevo método del autor, sin embargo, funciona para cualquier número sin necesidad de arreglos especiales, lo que lo convierte en un verdadero reemplazo directo para la matemática de alta precisión general.

¿Qué tan seguros estamos?
Los autores están increíblemente confiados, pero respaldan esto con evidencia sólida, no solo con suposiciones.

Verificado por Máquina: No se limitaron a escribir código y esperar; utilizaron un programa de computadora para demostrar matemáticamente que el error en su nuevo método es minúsculo (específicamente, acotado por fórmulas como $34u^2$ , $184u^3$ y $812u^4$ , donde $u$ es el error de redondeo minúsculo de un solo número).
Probado en Todas Partes: Ejecutaron sus nuevos algoritmos en dos supercomputadoras muy diferentes: un chip basado en Arm (GB10) y un chip basado en Intel (H100).
Los Resultados:
- En el chip Arm, el nuevo método fue de 1.5 a 2.1 veces más rápido para cálculos de división y raíz cuadrada.
- En el chip Intel, fue de 1.2 a 1.6 veces más rápido para división y raíz cuadrada.
- Para tareas matemáticas grandes como la multiplicación de matrices (GEMM), la aceleración fue aún más dramática en el chip Arm, alcanzando hasta 2.0 veces más rápido para triple-palabra.

La Alternativa "Exacta"
El artículo también menciona una versión "Perfecta" de este truco llamada FMA Exacto. Esta versión es aún más precisa, pero conlleva un precio elevado: es de 6 a 11 veces más lenta que el método propuesto. Los autores sugieren usar esta versión "Perfecta" solo cuando necesites absolutamente, al 100%, la mayor precisión posible y no te importe la velocidad. Para casi todo lo demás, el método "libre de ramas" es el ganador.

¿Qué pasa con el método "antiguo"?
El artículo también corrige un error de una versión anterior de esta investigación. Previamente, los autores compararon su nuevo método con un método antiguo "totalmente destilado" que era increíblemente lento e ineficiente. Se dieron cuenta de que esa no era una pelea justa. Cuando compararon su nuevo método contra el método "libre de ramas" estándar (que ya es bastante rápido), el nuevo método seguía ganando, pero la aceleración era más modesta (alrededor de 1.3 a 1.7 veces más rápido). Esto sigue siendo una gran victoria, pero es una victoria realista.

La Conclusión
Este artículo demuestra que, al eliminar las pausas de "detenerse y comprobar" en la matemática de alta precisión, podemos hacer que las computadoras sean significativamente más rápidas sin perder exactitud. Es como actualizar de un coche que tiene que detenerse en cada intersección a un coche que puede volar sobre ellas. Los autores han demostrado que esto funciona, lo han probado en hardware real y han demostrado que está listo para ser utilizado en la próxima generación de calculadoras súper rápidas.

Resumen Técnico: Evaluación del Rendimiento de Algoritmos de Multiplicación-Acumulación Fusionada Libres de Ramificaciones para Aritmética de Precisión Múltiple de Múltiples Componentes

1. Planteamiento del Problema

La aritmética de precisión múltiple de múltiples componentes (por ejemplo, Double-Word/DW, Triple-Word/TW, Quadruple-Word/QW) logra un alto rendimiento agrupando componentes estándar de binary64 (o binary32) y gestionando los acarreos de forma exacta mediante Transformaciones Libres de Error (EFTs). Sin embargo, las etapas de renormalización en estos algoritmos dependen típicamente de ramificaciones if basadas en las magnitudes de los valores intermedios. Estas ramificaciones causan penalizaciones significativas de rendimiento en implementaciones SIMD y GPU debido a la divergencia de carriles (lanes) o de warps.

Aunque Zhang y Aiken propusieron previamente algoritmos libres de ramificaciones para la adición y multiplicación de DW/TW/QW, la composición de estas operaciones separadas libres de ramificaciones sigue siendo subóptima. Específicamente, realizar una operación de multiplicación-acumulación fusionada (FMA) $z \leftarrow x \cdot y + c$ mediante la composición secuencial de una multiplicación libre de ramificaciones y una adición libre de ramificaciones incurre en un alto recuento de operaciones (por ejemplo, 29 flops para DW, 96 para TW y 209 para QW) y pasos de renormalización redundantes.

2. Metodología

El artículo propone nuevos algoritmos de multiplicación-acumulación fusionada (FMA) libres de ramificaciones para la aritmética DW, TW y QW (y sus variantes de base de precisión simple DS, TS, QS). La metodología central consiste en:

Estructura Algorítmica: El FMA propuesto calcula $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ en una única etapa fusionada en lugar de componer operaciones de multiplicación y adición por separado. El proceso implica:
1. Expansión del Producto: Descomposición de los productos de los componentes utilizando TwoProd.
2. Acumulación por Pesos: Recopilación de términos que llegan a la misma posición de potencia de dos mediante cadenas de TwoSum.
3. Renormalización: Remodelación del resultado en $K$ componentes no superpuestos.
Selección de Puertas y Verificación: Un principio de diseño crítico es la selección de las puertas de renormalización basadas en precondiciones verificables por máquina. El algoritmo utiliza FastTwoSum (3 flops) solo donde la precondición $\text{exp}(a) \ge \text{exp}(b)$ puede ser probada por máquina para todas las precisiones $p$ utilizando el resolvedor SMT z3 a través de la herramienta FPANVerifier. Donde la precondición no puede probarse, se utiliza TwoSum (6 flops) para garantizar la corrección.
Conmutatividad: Para asegurar el acuerdo bit a bit bajo el intercambio de operandos ( $x \leftrightarrow y$ ), el algoritmo reasocia las sumas diagonales de modo que los pares transpuestos (por ejemplo, $P_{ij}$ y $P_{ji}$ ) se procesen primero. Esto se logra sin aumentar el recuento de operaciones.
Variante Exacta: También se implementa una variante de "destilación" (Exact FMA) como referencia. Esta realiza una expansión completa libre de error seguida de múltiples barridos de TwoSum para lograr límites de error relativos al resultado, aunque con un costo computacional significativamente mayor.

3. Contribuciones Clave

3.1 Construcciones de FMA Mínimas y Libres de Ramificaciones

El artículo presenta algoritmos FMA mínimos, libres de ramificaciones y verificados por máquina con los siguientes recuentos de operaciones (la instrucción FMA fusionada cuenta como 1):

DW (K=2): 17 flops (frente a 29 para la composición de mul+add libre de ramificaciones).
TW (K=3): 66 flops (frente a 96).
QW (K=4): 146 flops (frente a 209).

Estos recuentos representan las construcciones mínimas donde cada precondición de FastTwoSum es verificada por máquina.

3.2 Límites de Error Verificados por Máquina

Utilizando FPANVerifier, los autores certifican los límites de error relativos a $(|xy| + |c|)$ para todas las precisiones:

DW: $34 u^2 (|xy| + |c|)$
TW: $184 u^3 (|xy| + |c|)$
QW: $812 u^4 (|xy| + |c|)$
Se confirma la validez de cada precondición de FastTwoSum y el acuerdo bit a bit entre la variante probada y una variante ingenua (donde FastTwoSum se coloca en la cola independientemente de la prueba).

3.3 Conmutatividad

Los algoritmos propuestos son bitwise commutativos en $x$ e $y$ para los seis tipos (DD/TD/QD/DS/TS/QS). Esto se logra simetrizando el orden de asociación de las sumas simples, asegurando $fma(x, y, c) \equiv fma(y, x, c)$ sin añadir operaciones.

3.4 Variantes Especializadas para División y Raíz Cuadrada

El artículo identifica que los residuos intermedios en los algoritmos de división y raíz cuadrada pueden no satisfacer las suposiciones de no superposición requeridas para las pruebas de FMA estándar. En consecuencia, se propone una variante "segura" para estos contextos (DW 20 / TW 69 / QW 149 flops), que degrada las puertas FastTwoSum no probadas a TwoSum para garantizar la exactitud sin necesidad de volver a verificar toda la estructura para cada contexto de uso.

4. Resultados Experimentales

Los algoritmos fueron evaluados en dos plataformas:

Arm: NVIDIA GB10 (Grace-Blackwell, CPU Cortex-X925, GPU Blackwell).
x86: Nodo H100 (CPU Intel Xeon Gold 6526Y, GPU H100).
Implementaciones: Escalar, AVX2, AVX-512, NEON, SVE2 y CUDA.

4.1 Kernels de Álgebra Lineal (AXPY, GEMV, GEMM)

Aceleración (Speedup): El FMA propuesto supera consistentemente a la línea base libre de ramificaciones (BF) en escenarios limitados por cómputo.
- AVX2 (x86): Aceleraciones de $\times 1.49$ (DD), $\times 1.32$ (TD) y $\times 1.47$ (QD) en GEMM.
- NEON (Arm): Aceleraciones de $\times 1.40$ (DD), $\times 1.42$ (TD) y $\times 1.47$ (QD) en GEMM.
- SVE2: Rendimiento similar a NEON a igual ancho de carril, con QD GEMM alcanzando una aceleración de $\times 1.62$ sobre BF.
- GPU (GB10): En cargas de trabajo limitadas por cómputo de precisión doble, las aceleraciones coinciden con las proporciones teóricas de FLOPs ( $\times 1.71$ para DD, $\times 1.46$ para TD, $\times 1.40$ para QD). En cargas de trabajo limitadas por ancho de banda (precisión simple o H100), las aceleraciones son cercanas a $\times 1.00$ .
Exactitud: El FMA propuesto mantiene una exactitud de trabajo comparable con los métodos libres de ramificaciones existentes (Q/BF). En escenarios de cancelación, el comportamiento del error es numéricamente idéntico al de la línea base. El Exact FMA ofrece una exactitud relativa al resultado superior, pero incurre en una ralentización de 2.5–5.0 $\times$ .

4.2 División y Raíz Cuadrada

División: El FMA propuesto acelera significativamente la división larga, particularmente para precisiones más altas.
- NEON/SVE2: Aceleraciones de $\times 1.54$ a $\times 2.11$ (la división QD alcanza $\times 2.11$ , superando la relación de recuento de operaciones de 1.51 debido al plegado de dos cadenas de normalización seriales en una sola).
- GB10 (Solo cómputo): Aceleraciones de $\times 1.25$ a $\times 1.61$ .
Raíz Cuadrada: El FMA propuesto logra aceleraciones de $\times 1.51$ a $\times 1.61$ con cero pérdida de exactitud en comparación con la línea base. Esto se debe a que la iteración de Newton converge muy por debajo de la unidad de redondeo, haciendo que el error final esté dominado por la última multiplicación común a todos los métodos.

4.3 Base de Precisión Simple (DS/TS/QS)

Los algoritmos se extendieron con éxito a componentes de precisión simple, manteniendo la exactitud de trabajo y logrando aceleraciones de $\times 1.37$ a $\times 1.83$ sobre la línea base BF.

5. Significado y Reivindicaciones

El artículo afirma que el FMA fusionado libre de ramificaciones propuesto representa una construcción mínima y verificada por máquina que logra plegar las dos etapas de la multiplicación y adición libres de ramificaciones existentes en una sola operación.

Rendimiento: Proporciona aceleraciones en el mundo real (hasta $\times 2.11$ en división en CPUs y $\times 1.71$ en GEMM en GPUs) al reducir los recuentos de operaciones y acortar las cadenas de dependencia, lo cual es particularmente beneficioso para precisiones más altas (TW/QW).
Corrección: Los algoritmos están rigurosamente verificados. Los límites de error y las precondiciones de FastTwoSum están probados por máquina para todas las precisiones, y el acuerdo bit a bit entre la variante probada y una variante ingenua se confirmó mediante pruebas extensas (más de 200,000 ensayos).
Generalidad: El enfoque no se limita al álgebra lineal; acelera eficazmente los algoritmos de división y raíz cuadrada, que dependen fuertemente de las operaciones MAC.
Conmutatividad: A diferencia de algunos enfoques previos libres de ramificaciones, el FMA propuesto preserva la conmutatividad bitwise, una propiedad crucial para la reproducibilidad en reducciones paralelas.

Los autores posicionan este trabajo como un reemplazo práctico para la composición de operaciones separadas libres de ramificaciones, ofreciendo una aceleración de "caída directa" (drop-in) para las librerías de aritmética de múltiples componentes sin sacrificar la exactitud ni la capacidad de prueba. Se sugiere como trabajo futuro explorar estructuras de renormalización alternativas (por ejemplo, estilo Priest) para reducir potencialmente los recuentos de operaciones manteniendo la verificabilidad por máquina.