División en coma flotante vs multiplicación en coma flotante

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

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

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

Son no semánticamente idénticas - 0.1 no se puede representar exactamente como double, por lo que un valor ligeramente diferente va a terminar siendo utilizado para la sustitución de la multiplicación de la división en este caso sería obtener un resultado diferente!

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

Sin embargo, los PC modernos son muy rápidos. También contienen arqutecturas de canalización que pueden hacer que la diferencia sea negligente en muchas circunstancias. Para colmo, cualquier compilador decente realizará la operación de división que mostró en tiempo de compilación con las optimizaciones activadas. Para su ejemplo actualizado, cualquier compilador decente realizaría esa transformación por sí mismo.

So generalmente debería preocuparse por hacer que su código sea legible, y dejar que el compilador se preocupe por hacerlo rápido. Solo si usted tiene un problema de velocidad medida con esa línea debe preocuparse por pervertir su código por el bien de la velocidad. Los compiladores son muy conscientes de lo que es más rápido que lo que en su CPU, y son generalmente mucho mejores optimizadores de lo que nunca se puede esperar ser.

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

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

Algunas diferencias: cada paso de la multiplicación solo necesita mirar 1 bit; cada etapa de la división necesita mirar 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 agregue 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 forma independiente, entonces pueden suceder en el mismo tiempo dentro de un ciclo de reloj.

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

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

Para permitir que el compilador haga esta optimización por usted incluso cuando el resultado no sea exacto (o con un divisor 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) permite al compilador reemplazar x / y con x * (1/y) cuando sea útil. Otros compiladores tienen opciones similares, y ICC puede habilitar alguna optimización "insegura" por defecto (creo que lo hace, pero lo olvido).

-ffast-math a menudo es importante permitir la auto-vectorización de bucles FP, especialmente las reducciones (por ejemplo, la suma de una matriz en un total escalar), porque FP math no es asociativo. ¿por Qué no GCC optimizar a*a*a*a*a*a (a*a*a)*(a*a*a)?

También tenga en cuenta que los compiladores de C++ pueden plegar + y * en un FMA en algunos casos (al compilar para un destino que lo soporte, como -march=haswell), pero no pueden hacer eso con /.

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

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

Sin embargo, la división FP y sqrt en CPU Intel y AMD (que no sean KNL) se implementan como una única uop, por lo que no necesariamente tiene un gran impacto en el rendimiento 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 muchos multiplicaciones y adiciones (u otro trabajo) que pueden ocurrir 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 el número entero se multiplica. Hay menos demanda de división de enteros de alto rendimiento, por lo que el soporte de hardware no es tan sofisticado. Relacionado: instrucciones microcodificadas como idiv puede causar cuellos de botella front-end sensibles a la alineación.)

Así que, 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á haciendo en el bucle es cargar/dividir/almacenar, y son independientes, por lo que es el rendimiento lo que importa, 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 saturar el rendimiento. Tenga en cuenta que sum += a[i] / b[i] cuellos de botella en la latencia add o en el rendimiento div, pero no en la latencia div porque la división no está en la ruta crítica (la cadena de dependencias en bucle).

Pero en algo como esto (aproximando 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 a polinomio único con coeficientes 2N, y la evaluación de 2 en paralelo le da cierto paralelismo a nivel de instrucción dentro de un cuerpo de bucle único en lugar de una cadena dep masivamente larga, lo que facilita mucho la ejecución fuera de orden.

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

No tenemos cuellos de botella en dividir rendimiento mientras nuestros polinomios sean lo suficientemente grande como para que solo tengamos una división por cada 10 instrucciones FMA más o menos. (Y en un caso de uso real log(), hay un montón de trabajo extrayendo exponente / mantissa y combinando cosas de nuevo, así que hay aún más trabajo que hacer entre divisiones.)

Cuando necesitas dividir, por lo general es mejor dividir en lugar de {[34]]}

X86 tiene una instrucción recíproca aproximada(rcpps), lo que solo te da 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 de la CPU. El hardware divisor puede utilizar 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 te cuesta 2 multiplica y 2 FMAs , y tiene una latencia tan alta como una instrucción de división real. Si todo que estás haciendo es división, entonces puede ser una ganancia de rendimiento. (Pero debes 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 está utilizando la división como parte de una función más compleja, el rcpps en sí + el mul extra + FMA generalmente hace que sea más rápido simplemente dividir con una instrucción divps, excepto en CPU con un rendimiento divps muy bajo.

(Por ejemplo, Desembarco de Caballeros, ver más abajo. KNL soporta AVX512ER, por lo que para los vectores float el resultado VRCP28PS ya es lo suficientemente preciso como para multiplicarse sin una iteración de Newton-Raphson. float el tamaño de la mantissa es de solo 24 bits.)

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

A diferencia de cualquier otra operación ALU, la latencia/rendimiento de división depende de los datos de algunas CPU. Una vez más, esto es porque es tan lento y no totalmente canalizado. La programación fuera de orden es más fácil con latencias fijas, porque evita conflictos de escritura (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).

Generalmente, 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 base2 float tiene muchos ceros finales en la mantisa).

float latencia (ciclos) / rendimiento (ciclos por instrucción, corriendo solo eso de espaldas con entradas independientes):

                   scalar & 128b vector        256b AVX vector
                   divss      |  mulss
                   divps xmm  |  mulps           vdivps ymm | vmulps ymm

Nehalem          7-14 /  7-14 | 5 / 1           (No AVX)
Sandybridge     10-14 / 10-14 | 5 / 1        21-29 / 20-28 (3 uops) | 5 / 1
Haswell         10-13 / 7     | 5 / 0.5       18-21 /   14 (3 uops) | 5 / 0.5
Skylake            11 / 3     | 4 / 0.5          11 /    5 (1 uop)  | 4 / 0.5

Piledriver       9-24 / 5-10  | 5-6 / 0.5      9-24 / 9-20 (2 uops) | 5-6 / 1 (2 uops)
Ryzen              10 / 3     | 3 / 0.5         10  /    6 (2 uops) | 3 / 1 (2 uops)

 Low-power CPUs:
Jaguar(scalar)     14 / 14    | 2 / 1
Jaguar             19 / 19    | 2 / 1            38 /   38 (2 uops) | 2 / 2 (2 uops)

Silvermont(scalar)    19 / 17    | 4 / 1
Silvermont      39 / 39 (6 uops) | 5 / 2            (No AVX)

KNL(scalar)     27 / 17 (3 uops) | 6 / 0.5
KNL             32 / 20 (18uops) | 6 / 0.5        32 / 32 (18 uops) | 6 / 0.5  (AVX and AVX512)

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

                   scalar & 128b vector        256b AVX vector
                   divsd      |  mulsd
                   divpd xmm  |  mulpd           vdivpd ymm | vmulpd ymm

Nehalem         7-22 /  7-22 | 5 / 1        (No AVX)
Sandybridge    10-22 / 10-22 | 5 / 1        21-45 / 20-44 (3 uops) | 5 / 1
Haswell        10-20 /  8-14 | 5 / 0.5      19-35 / 16-28 (3 uops) | 5 / 0.5
Skylake        13-14 /     4 | 4 / 0.5      13-14 /     8 (1 uop)  | 4 / 0.5

Piledriver      9-27 /  5-10 | 5-6 / 1       9-27 / 9-18 (2 uops)  | 5-6 / 1 (2 uops)
Ryzen           8-13 /  4-5  | 4 / 0.5       8-13 /  8-9 (2 uops)  | 4 / 1 (2 uops)

  Low power CPUs:
Jaguar            19 /   19  | 4 / 2            38 /  38 (2 uops)  | 4 / 2 (2 uops)

Silvermont(scalar) 34 / 32    | 5 / 2
Silvermont         69 / 69 (6 uops) | 5 / 2           (No AVX)

KNL(scalar)      42 / 42 (3 uops) | 6 / 0.5   (Yes, Agner really lists scalar as slower than packed, but fewer uops)
KNL              32 / 20 (18uops) | 6 / 0.5        32 / 32 (18 uops) | 6 / 0.5  (AVX and AVX512)

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

Atom, Silvermont, and even Knight's Landing (Xeon Phi basado en Silvermont) tiene un rendimiento de división excepcionalmente bajo, e incluso un vector 128b es más lento que el 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 de la matriz. Xeon Phi tiene baja potencia por núcleo, y empaquetar muchos núcleos en un troquel le da restricciones de área de troquel más estrictas que Skylake-AVX512. Parece que AVX512ER rcp28ps / pd es lo que "se supone" que debes usar en KNL.

(Véase este resultado de InstLatx64 para Skylake-AVX512 también conocido como Skylake-X. Números para vdivps zmm: 18c / 10c, por lo que la mitad del rendimiento de ymm.)

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

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

La división FP vs. las relaciones de rendimiento múltiples son pares peor que eso en CPU de baja potencia como Silvermont y Jaguar, e incluso en Xeon Phi (KNL, donde debe usar AVX512ER).

Relaciones de rendimiento real de dividir/multiplicar para escalar (no vectorizado) double: 8 en Ryzen y Skylake con sus divisores reforzados, pero 16-28 en Haswell (dependiente de datos, y más probable hacia el final del ciclo 28 a menos que sus divisores sean números redondos). Estas CPU modernas tienen divisores muy potentes, pero su rendimiento multiplicado de 2 por reloj lo sopla lejos. (Aún más cuando su código puede auto-vectorizarse con vectores AVX de 256b). También tenga en cuenta que con las opciones de compilador correctas, esos rendimientos multiplicados también se aplican a FMA.

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

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

En code 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.

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 división, porque el compilador debería crear el código ensamblador que usa instrucciones SIMD. Dado que no hay división en las instrucciones del SIMD, entonces verá grandes mejoras usando multiplicación y división.