fma(a,b,c) es equivalente a a*b+c excepto que no redondea el resultado intermedio.¿Qué algoritmos se benefician más de fusionado multiplicar agregar?
¿Podría darme algunos ejemplos de algoritmos que no se benefician trivialmente al evitar este redondeo?
No es obvio, ya que el redondeo después de las multiplicaciones que evitamos tiende a ser menos problemático que el redondeo después de la suma, lo que no ocurre.
taw toque en un ejemplo importante; de manera más general, FMA permite a los escritores de bibliotecas implementar de manera eficiente muchas otras operaciones de coma flotante con redondeo correcto.
Por ejemplo, una plataforma que tiene un FMA puede usarlo para implementar una división y una raíz cuadrada correctamente redondeadas (PPC e Itanium adoptaron este enfoque), lo que permite que la FPU sea básicamente una máquina FMA de propósito único. Peter Tang y John Harrison (Intel) y Peter Markstein (HP) tienen algunos documentos que explican este uso si tiene curiosidad.
El ejemplo taw dio es más ampliamente útil que simplemente en el seguimiento de los límites de error. Le permite representar el producto de dos números de coma flotante como una suma de dos números de punto flotante sin ningún error de redondeo; esto es bastante útil para implementar funciones de biblioteca de coma flotante redondeadas correctamente. El libro de Jean-Michel Muller o los documentos en crlibm serían buenos lugares para comenzar a aprender más sobre estos usos.
FMA también es ampliamente útil en la reducción de argumentos en rutinas de estilo matemático-biblioteca para ciertos tipos de argumentos; cuando uno está haciendo una reducción de argumento, el objetivo del cálculo es a menudo un término del formulario (x - a*b), donde (a*b) es casi igual a x; en particular, el resultado es a menudo del orden del error de redondeo en el término (a*b), si esto se calcula sin una FMA. Creo que Muller también ha escrito algo sobre esto en su libro.
De la parte superior de mi cabeza - La multiplicación de matrices, la regla de Newton, la evaluación polinómica, métodos numéricos
El principal beneficio de FMA es que puede ser el doble de rápido. En lugar de tomar 1 ciclo para la multiplicación y luego 1 ciclo para el agregado, la FPU puede emitir ambas operaciones en el mismo ciclo. Obviamente, la mayoría de los algoritmos se beneficiarán de operaciones más rápidas.
Algunos ejemplos: Vector dot products. Transformadas de Fourier. Procesamiento de señales digitales. Polinomios. Todo tipo de cosas.
Es una cuestión de optimización y explotación de hardware más que cualquier otra cosa. Una suma de productos es un requisito muy común en los métodos numéricos, y de esta manera le permite dar una instrucción explícita al compilador sobre cómo hacer algo rápido y quizás con un poco más de precisión. A menos que me equivoque, el compilador puede reemplazar a = b * c + d con una instrucción FMA, pero también es libre de hacerlo. (a menos que el estándar requiera el redondeo, pero los compiladores del mundo real violan rutinariamente los estándares en pequeñas formas).
El compilador no puede reemplazar legalmente b * c + d con una FMA a menos que específicamente le informe al compilador que está bien (con -funciones matemáticas o algo similar), ya que perturba los resultados. –
@StephenLin: suponiendo que la evaluación de 'b',' c', y 'd' no mutee el estado ni tenga otros efectos secundarios, ¿cómo puede una optimización de hardware" perturbar los resultados "? – stakx
@stakx: muchas de las instrucciones compuestas en un conjunto de instrucciones de punto flotante están ahí porque el error de redondeo empantanaría el resultado. Ejemplo: si toma e^(cerca de cero) el resultado es cercano a uno, pero eso limita enormemente su precisión. Si tiene una instrucción que representa e^epsilon-1, entonces el hardware puede dar una precisión mucho mayor. Cualquier lenguaje de alto nivel dado se puede definir para ofrecer acceso a las instrucciones más precisas o para reescribir el árbol de expresiones en circunstancias reconocibles. El primero es más predecible. – Ian
Lo único que he encontrado hasta ahora son las "transformaciones sin errores". Para cualquier error de números de coma flotante de a+b, a-b y a*b, también son números de punto flotante (en el redondeo al modo más cercano, suponiendo que no hay desbordamiento/subdesbordamiento, etc.).
El error de suma (y obviamente substracción) es fácil de calcular; si es abs(a) >= abs(b), el error es exactamente b-((a+b)-a) (2 flops, o 4-5 si no sabemos cuál es más grande). El error de multiplicación es trivial para calcular con fma - es simplemente fma(a,b,-a*b). Sin fma son 16 fracasos de código bastante desagradable. Y la emulación totalmente genérica de fma redondeada correctamente es incluso más lenta que eso.
Extra 16 fracasos de seguimiento de errores por fracaso de cálculo real es una gran exageración, pero con solo 1-5 fracasos fáciles de usar es bastante razonable, y para muchos algoritmos basados en esa sobrecarga del 50% -200% de seguimiento de errores y la compensación da como resultado un error tan pequeño como si todos los cálculos se hicieran en el doble del número de bits que eran, evitando el mal acondicionamiento en muchos casos.
Curiosamente, fma no se usa nunca en estos algoritmos para calcular los resultados, sólo para encontrar errores, porque la búsqueda de errores de fma es un proceso lento como la búsqueda de errores de la multiplicación era sin fma.
Las palabras clave relevantes para la búsqueda serían "esquema de Horner compensado" y "producto de punto compensado", y el esquema de Horner se beneficiará mucho más.
Me pregunto cómo se compararía el costo de hardware de FMA en valores 'float 'con el costo de hardware de una operación que agregaba el producto de precisión completa de dos valores' float' a 'double'. Según entiendo, el hardware de costo de una multiplicación 'doble' es más de cuatro veces el de una multiplicación de 'flotante 'igualmente rápida que produce un resultado de precisión total, y para muchas operaciones como producto de punto es necesario mantener los valores intermedios con más precisión que los operandos o el resultado final. Usar un multiplicador y fma juntos podría funcionar, pero usar una operación f * f + d parecería el doble de rápido. – supercat
Ha sido bastante bien explicado en la Wikipedia entry for FMA que los algoritmos que tienen algo que ver con acumulación de productos beneficiarse al usar FMA:
A fast FMA can speed up and improve the accuracy of
many computations that involve the accumulation of products:
* Dot product
* Matrix multiplication
* Polynomial evaluation (e.g., with Horner's rule)
* Newton's method for evaluating functions.
pregunta es sobre impacto de redondeo, no se trata de esto. Su respuesta también es incorrecta ya que fma requiere 3 entradas de unidad de coma flotante en lugar de 2 entradas estándar, puerto adicional en el archivo de registro de coma flotante y sumadores de coma flotante más amplios. Esto no es gratuito, es una compensación de soporte de fma a costo de algunos otro hardware. – taw
taw: preguntaste qué algoritmos se benefician de FMA y algunos ejemplos donde el redondeo es un beneficio no trivial. Respondí la primera parte, que es que la mayoría de los algoritmos se beneficiarán. – Gabe