c++ - programacion - División de punto flotante vs multiplicación de coma flotante

punto flotante plc (7)

La división es intrínsecamente una operación mucho más lenta que la multiplicación.

Y esto, de hecho, puede ser algo que el compilador no puede (y puede que no desee) optimizar en muchos casos debido a inexactitudes en coma flotante. Estas dos declaraciones:

double d1 = 7 / 10.; double d2 = 7 * 0.1;

no son semánticamente idénticos: 0.1 no se puede representar exactamente como un double , por lo que un valor ligeramente diferente terminará usándose; sustituir la multiplicación por la división en este caso arrojaría un resultado diferente.

¿Hay alguna ganancia de rendimiento (no microoptimización) por codificación?

float f1 = 200f / 2

en comparación con

float f2 = 200f * 0.5

Un profesor mío me dijo hace unos años que las divisiones de punto flotante eran más lentas que las multiplicaciones de punto flotante sin explicar el por qué.

¿Tiene esta afirmación para la arquitectura de PC moderna?

Actualización1

Con respecto a un comentario, considere también este caso:

float f1; float f2 = 2 float f3 = 3; for( i =0 ; i < 1e8; i++) { f1 = (i * f2 + i / f3) * 0.5; //or divide by 2.0f, respectively }

Actualización 2 Citando de los comentarios:

[Quiero] saber cuáles son los requisitos algorítmicos / arquitectónicos que hacen que la división sea mucho más complicada en hardware que la multiplicación

La respuesta depende de la plataforma para la que está programando.

Por ejemplo, hacer muchas multiplicaciones en una matriz en x86 debería ser mucho más rápido que hacer una división, porque el compilador debería crear el código ensamblador que usa instrucciones SIMD. Ya que no hay división en las instrucciones SIMD, entonces verás grandes mejoras usando la multiplicación y luego la división.

Newton rhapson resuelve la división de enteros en O (M (n)) complejidad a través de la aproximación de álgebra lineal. Más rápido que La complejidad O (n * n).

En código El método contiene 10mults 9adds 2bitwiseshifts.

Esto explica por qué una división es aproximadamente 12 veces más ticks de CPU que una multiplicación.

Piensa en lo que se requiere para la multiplicación de dos números de n bits. Con el método más simple, toma un número x y lo desplaza repetidamente y lo agrega condicionalmente a un acumulador (basado en un bit en el otro número y). Después de n adiciones ya terminaste. Su resultado se ajusta en 2n bits.

Para la división, comienzas con x de 2n bits ey de n bits, quieres calcular x / y. El método más simple es la división larga, pero en binario. En cada etapa haces una comparación y una resta para obtener un poco más del cociente. Esto te lleva a n pasos.

Algunas diferencias: cada paso de la multiplicación solo necesita mirar 1 bit; cada etapa de la división necesita observar n bits durante la comparación. Cada etapa de la multiplicación es independiente de todas las demás etapas (no importa el orden en que se agreguen los productos parciales); para la división, cada paso depende del paso anterior. Esto es un gran problema en hardware. Si las cosas se pueden hacer de manera independiente, pueden suceder al mismo tiempo dentro de un ciclo de reloj.

Sí, muchas CPU pueden realizar multiplicaciones en 1 o 2 ciclos de reloj, pero la división siempre lleva más tiempo (aunque la división FP a veces es más rápida que la división entera).

Si miras esta respuesta , verás que la división puede exceder los 24 ciclos.

¿Por qué la división toma mucho más tiempo que la multiplicación? Si recuerda de nuevo a la escuela primaria, puede recordar que la multiplicación se puede realizar esencialmente con muchas adiciones simultáneas. La división requiere una resta iterativa que no se puede realizar simultáneamente, por lo que lleva más tiempo. De hecho, algunas unidades de FP aceleran la división realizando una aproximación recíproca y multiplicando por eso. No es tan preciso, pero es algo más rápido.

Sí. Cada FPU que conozco realiza multiplicaciones mucho más rápido que las divisiones.

Sin embargo, las PC modernas son muy rápidas. También contienen estructuras de tuberías que pueden hacer la diferencia insignificante bajo muchas circunstancias. Para colmo, cualquier compilador decente realizará la operación de división que mostró en el momento de la compilación con las optimizaciones activadas. Para su ejemplo actualizado, cualquier compilador decente realizaría esa transformación en sí mismo.

Por lo tanto, en general debe preocuparse por hacer que su código sea legible y dejar que el compilador se preocupe por hacerlo rápido. Solo si tienes un problema de velocidad medido con esa línea deberías preocuparte por pervertir tu código por el bien de la velocidad. Los compiladores son muy conscientes de lo que es más rápido que lo que tienen en sus CPU, y en general son optimizadores mucho mejores de lo que usted puede esperar.

Tenga mucho cuidado con la división y evítela cuando sea posible. Por ejemplo, float inverse = 1.0 / divisor; elevación float inverse = 1.0 / divisor; fuera de un bucle y multiplicar por inverse dentro del bucle. (Si el error de redondeo en inverse es aceptable)

Por lo general, 1.0/x no será exactamente representable como float o double . Será exacto cuando x sea una potencia de 2. Esto permite a los compiladores optimizar x / 2.0 a x * 0.5 sin ningún cambio en el resultado.

Para que el compilador realice esta optimización incluso cuando el resultado no sea exacto (o con un divisor de variable de tiempo de ejecución), necesita opciones como gcc -O3 -ffast-math . Específicamente, -freciprocal-math (habilitado por -funsafe-math-optimizations habilitado por -ffast-math ) le permite al compilador reemplazar x / y con x * (1/y) cuando sea útil. Otros compiladores tienen opciones similares, e ICC puede habilitar una optimización "insegura" por defecto (creo que sí, pero lo olvido).

-ffast-math es a menudo importante para permitir la auto-vectorización de los bucles FP, especialmente las reducciones (por ejemplo, sumando una matriz en un total escalar), porque la matemática FP no es asociativa. ¿Por qué GCC no optimiza a * a * a * a * a * a a (a * a * a) * (a * a * a)?

También tenga en cuenta que los compiladores C ++ pueden doblar + y * en una FMA en algunos casos (cuando se compila para un destino que lo admite, como -march=haswell ), pero no pueden hacer eso con / .

La división tiene una latencia peor que la multiplicación o adición (o FMA ) por un factor de 2 a 4 en las CPU x86 modernas, y peor rendimiento por un factor de 6 a 40 ¹ (para un circuito cerrado haciendo solo división en lugar de solo multiplicación).

La unidad de división / sqrt no está completamente canalizada, por razones explicadas en la respuesta de @ NathanWhitehead . Las peores proporciones son para vectores 256b, porque (a diferencia de otras unidades de ejecución) la unidad de división no suele ser de ancho completo, por lo que los vectores amplios tienen que hacerse en dos mitades. Una unidad de ejecución no totalmente arith.divider_active es tan inusual que las CPU Intel tienen un arith.divider_active rendimiento de hardware arith.divider_active que lo ayuda a encontrar código que obstaculiza el rendimiento del divisor en lugar de los cuellos de botella habituales en el front-end o en el puerto de ejecución. (O más a menudo, cuellos de botella de memoria o cadenas de latencia largas que limitan el paralelismo de nivel de instrucción que hace que el rendimiento de la instrucción sea inferior a ~ 4 por reloj).

Sin embargo, la división FP y sqrt en las CPU Intel y AMD (distintas de KNL) se implementan como un solo uop, por lo que no necesariamente tienen un gran impacto en el rendimiento del código circundante . El mejor caso para la división es cuando la ejecución fuera de orden puede ocultar la latencia, y cuando hay muchas multiplicaciones y agrega (u otro trabajo) que pueden suceder en paralelo con la división.

(La división entera se microcodifica como múltiples uops en Intel, por lo que siempre tiene más impacto en el código circundante que la multiplicación de enteros. Hay menos demanda de división de enteros de alto rendimiento, por lo que el soporte de hardware no es tan elegante. Relacionado: instrucciones microcodificadas como idiv puede causar cuellos de botella de front-end sensibles a la alineación .)

Entonces, por ejemplo, esto será realmente malo:

for () a[i] = b[i] / scale; // division throughput bottleneck // Instead, use this: float inv = 1.0 / scale; for () a[i] = b[i] * inv; // multiply (or store) throughput bottleneck

Todo lo que estás haciendo en el ciclo es cargar / dividir / almacenar, y son independientes, por lo que importa el rendimiento, no la latencia.

Una reducción como accumulator /= b[i] sería un cuello de botella en dividir o multiplicar la latencia, en lugar de rendimiento. Pero con múltiples acumuladores que divide o multiplica al final, puede ocultar la latencia y aún así saturar el rendimiento. Tenga en cuenta que sum += a[i] / b[i] cuellos de botella en latencia agregada o rendimiento div , pero no latencia div porque la división no está en la ruta crítica (la cadena de dependencia transportada por bucle).

Pero en algo como esto ( aproximándose a una función como log(x) con una relación de dos polinomios ), la división puede ser bastante barata :

for () { // (not shown: extracting the exponent / mantissa) float p = polynomial(b[i], 1.23, -4.56, ...); // FMA chain for a polynomial float q = polynomial(b[i], 3.21, -6.54, ...); a[i] = p/q; }

Para log() sobre el rango de la mantisa, una relación de dos polinomios de orden N tiene mucho menos error que un solo polinomio con coeficientes 2N, y la evaluación de 2 en paralelo le da cierto paralelismo de nivel de instrucción dentro de un solo cuerpo de bucle en lugar de una cadena de depósito masivamente larga, facilitando mucho las cosas para la ejecución fuera de servicio.

En este caso, no bloqueamos la latencia de división porque la ejecución fuera de orden puede mantener múltiples iteraciones del ciclo sobre las matrices en vuelo.

No obstaculizamos el rendimiento dividido siempre que nuestros polinomios sean lo suficientemente grandes como para que solo tengamos una división por cada 10 instrucciones de FMA, más o menos. (Y en un caso real de uso de log() , hay mucho trabajo extrayendo exponente / mantisa y combinando cosas nuevamente juntas, por lo que aún hay más trabajo por hacer entre divisiones).

Cuando necesitas dividir, generalmente lo mejor es dividir en lugar de `rcpps`

x86 tiene una instrucción recíproca aproximada ( rcpps ), que solo le proporciona 12 bits de precisión. (AVX512F tiene 14 bits, y AVX512ER tiene 28 bits).

Puede usar esto para hacer x / y = x * approx_recip(y) sin usar una instrucción de división real. ( rcpps itsef es bastante rápido, generalmente un poco más lento que la multiplicación. Utiliza una búsqueda de tabla desde una tabla interna a la CPU. El hardware del divisor puede usar la misma tabla para un punto de partida).

Para la mayoría de los propósitos, x * rcpps(y) es demasiado inexacto, y se requiere una iteración de Newton-Raphson para duplicar la precisión. Pero eso le cuesta 2 multiplicaciones y 2 FMA , y tiene una latencia tan alta como una instrucción de división real. Si todo lo que estás haciendo es división, entonces puede ser una ganancia de rendimiento. (Pero deberías evitar ese tipo de bucle en primer lugar si puedes, tal vez haciendo la división como parte de otro bucle que hace otro trabajo).

Pero si usa la división como parte de una función más compleja, el rcpps mismo + el mul + FMA extra por lo general hace que sea más rápido dividirse con una instrucción de divps , excepto en CPU con muy bajo rendimiento de divps .

(Por ejemplo, Knight''s Landing, ver a continuación. KNL admite AVX512ER , por lo que para los vectores float el resultado VRCP28PS ya es lo suficientemente preciso como para multiplicarse sin una iteración Newton-Raphson. El tamaño de la mantisa float es de solo 24 bits).

Números específicos de las tablas de Agner Fog:

A diferencia de cualquier otra operación de ALU, la latencia / rendimiento de división depende de los datos en algunas CPU. De nuevo, esto se debe a que es muy lento y no está totalmente canalizado. La programación fuera de orden es más fácil con latencias fijas, ya que evita conflictos de escritura regresiva (cuando el mismo puerto de ejecución intenta producir 2 resultados en el mismo ciclo, por ejemplo, ejecutando una instrucción de 3 ciclos y luego dos operaciones de 1 ciclo) .

En general, los casos más rápidos son cuando el divisor es un número "redondo" como 2.0 o 0.5 (es decir, la representación de float base2 tiene muchos ceros finales en la mantisa).

latencia de float (ciclos) / rendimiento (ciclos por instrucción, ejecutando solo eso a la inversa con entradas independientes):

double latencia (ciclos) / rendimiento (ciclos por instrucción):

Ivybridge y Broadwell también son diferentes, pero yo quería mantener la mesa pequeña. (Core2 (antes de Nehalem) tiene un mejor rendimiento del divisor, pero sus velocidades máximas de reloj eran más bajas).

Atom, Silvermont e incluso Knight''s Landing (Xeon Phi basado en Silvermont) tienen un rendimiento de división excepcionalmente bajo , e incluso un vector 128b es más lento que escalar. La CPU Jaguar de baja potencia de AMD (utilizada en algunas consolas) es similar. Un divisor de alto rendimiento ocupa una gran cantidad de área del dado. Xeon Phi tiene una baja potencia por núcleo , y el empaquetado de muchos núcleos en un dado le da restricciones más estrechas en el área de matriz que Skylake-AVX512. Parece que AVX512ER rcp28ps / pd es lo que se supone que debes usar en KNL.

(Vea este resultado de InstLatx64 para Skylake-AVX512 aka Skylake-X. Números para vdivps zmm : 18c / 10c, entonces la mitad del rendimiento de ymm ).

Las cadenas de latencia largas se convierten en un problema cuando se transportan por bucle, o cuando son tan largas que impiden que la ejecución fuera de orden encuentre paralelismo con otro trabajo independiente.

Nota al pie 1: cómo hice esas relaciones de rendimiento div vs. mul:

La división FP frente a las relaciones de rendimiento múltiples son incluso peores que en CPU de bajo consumo como Silvermont y Jaguar, e incluso en Xeon Phi (KNL, donde debe usar AVX512ER).

Proporciones reales de división / multiplicación de rendimiento para el double escalar (no vectorizado) : 8 en Ryzen y Skylake con sus divisores reforzados, pero 16-28 en Haswell (depende de los datos, y más probablemente hacia el final del ciclo 28 a menos que sus divisores estén números redondos). Estas CPUs modernas tienen divisores muy potentes, pero su rendimiento multiplicado de 2 por reloj lo destruye. (Aún más cuando su código puede auto-vectorizarse con 256b vectores AVX). También tenga en cuenta que con las opciones correctas del compilador, esos rendimientos de multiplicación también se aplican a FMA.

Números de agner.org/optimize tablas de instrucciones para Intel Haswell / Skylake y AMD Ryzen, para SSE escalar (sin incluir x87 fmul / fdiv ) y para 256b AVX SIMD vectores de float o double . Ver también la wiki de la etiqueta x86 .

c++ - programacion - División de punto flotante vs multiplicación de coma flotante

punto flotante plc (7)

Cuando necesitas dividir, generalmente lo mejor es dividir en lugar de rcpps

Números específicos de las tablas de Agner Fog:

Cuando necesitas dividir, generalmente lo mejor es dividir en lugar de `rcpps`