c++ - signos - suma y resta de numeros enteros ejercicios

¿Es la multiplicación de enteros realmente la misma velocidad que la adición en la CPU moderna? (8)

Escucho esta afirmación muy a menudo, que la multiplicación en el hardware moderno está tan optimizada que en realidad es la misma velocidad que la suma. ¿Es eso cierto?

Nunca puedo obtener ninguna confirmación autoritaria. Mi propia investigación solo añade preguntas. Las pruebas de velocidad suelen mostrar datos que me confunden. Aquí hay un ejemplo:

#include <stdio.h> #include <sys/time.h> unsigned int time1000() { timeval val; gettimeofday(&val, 0); val.tv_sec &= 0xffff; return val.tv_sec * 1000 + val.tv_usec / 1000; } int main() { unsigned int sum = 1, T = time1000(); for (int i = 1; i < 100000000; i++) { sum += i + (i+1); sum++; } printf("%u %u/n", time1000() - T, sum); sum = 1; T = time1000(); for (int i = 1; i < 100000000; i++) { sum += i * (i+1); sum++; } printf("%u %u/n", time1000() - T, sum); }

El código anterior puede mostrar que la multiplicación es más rápida:

clang++ benchmark.cpp -o benchmark ./benchmark 746 1974919423 708 3830355456

Pero con otro compilador, otros argumentos del compilador, un bucle interno escrito de manera diferente, los resultados pueden variar y ni siquiera puedo obtener una aproximación.

Dado que las otras respuestas se refieren a dispositivos reales del presente, que están obligados a cambiar y mejorar a medida que pase el tiempo, pensé que podríamos analizar la pregunta desde el punto de vista teórico.

Proposición: cuando se implementa en puertas lógicas, utilizando los algoritmos habituales, un circuito de multiplicación de enteros es O (log N) más lento que un circuito de adición, donde N es el número de bits en una palabra.

Prueba: El tiempo para que un circuito combinatorio se estabilice es proporcional a la profundidad de la secuencia más larga de puertas lógicas desde cualquier entrada a cualquier salida. Por lo tanto, debemos demostrar que un circuito de multiplicación de la escuela primaria es O (registro N) veces más profundo que un circuito de adición.

La adición se implementa normalmente como medio sumador seguido de sumadores completos N-1, con los bits de acarreo encadenados de un sumador a otro. Este circuito tiene claramente la profundidad O (N). (Este circuito se puede optimizar de muchas maneras, pero el peor desempeño siempre será O (N), a menos que se utilicen tablas de búsqueda absurdamente grandes).

Para multiplicar A por B, primero necesitamos multiplicar cada bit de A con cada bit de B. Cada multiplicador a nivel de bits es simplemente una puerta AND. Hay N ^ 2 multiplicaciones a nivel de bits para realizar, por lo tanto, N ^ 2 Y compuertas, pero todas pueden ejecutarse en paralelo, para una profundidad de circuito de 1. Esto resuelve la fase de multiplicación del algoritmo de la escuela primaria, dejando solo la fase de adición.

En la fase de adición, podemos combinar los productos parciales utilizando un circuito en forma de árbol binario invertido para hacer muchas de las adiciones en paralelo. El árbol tendrá (registro N) nodos profundos, y en cada nodo, estaremos sumando dos números con O (N) bits. Esto significa que cada nodo puede implementarse con un sumador de profundidad O (N), dando una profundidad total del circuito de O (N log N). QED.

En realidad, la respuesta centrada en la teoría que aceptaste es 100% errónea.

De hecho, la multiplicación de dos números de n bits se puede hacer en la profundidad del circuito O (log n) , al igual que la suma.

La adición en O (log n) se realiza dividiendo el número a la mitad y (recursivamente) agregando las dos partes en paralelo , donde la mitad superior se resuelve para el caso "0 carry" y "1 carry". Una vez que se agrega la mitad inferior, se examina el carry y su valor se utiliza para elegir entre el estuche de 0 carry y el de carry carry.

La multiplicación en profundidad O (log n) también se realiza a través de la paralelización , donde cada suma de 3 números se reduce a una suma de solo 2 números en paralelo, y las sumas se realizan de alguna manera como la anterior.
No lo explicaré aquí, pero puedes encontrar material de lectura sobre sumas y multiplicaciones rápidas al buscar las adiciones "carry-lookahead" y "carry-save" .

Por lo tanto, desde un punto de vista teórico, dado que los circuitos son obviamente paralelos (a diferencia del software), la única razón por la que la multiplicación sería asintóticamente más lenta es el factor constante en el frente, no la complejidad asintótica.

Esta es una respuesta aún más compleja que la simple multiplicación versus suma. En realidad, la respuesta probablemente NUNCA será sí. La multiplicación, electrónicamente, es un circuito mucho más complicado. La mayoría de las razones de por qué, es que la multiplicación es el acto de un paso de multiplicación seguido de un paso de suma, recuerda cómo era multiplicar números decimales antes de usar una calculadora.

La otra cosa a recordar es que la multiplicación será más larga o más corta dependiendo de la arquitectura del procesador en el que lo esté ejecutando. Esto puede o no puede ser simplemente específico de la empresa. Si bien es muy probable que un AMD sea diferente a un Intel, incluso un Intel i7 puede ser diferente de un Core 2 (dentro de la misma generación), y ciertamente diferente entre generaciones (especialmente cuanto más atrás esté).

En toda la TÉCNICA, si lo único que estaba haciendo (sin hacer un ciclo, contando, etc.) era multiplicar sería de 2 a (como he visto en arquitecturas de PPC) 35 veces más lento. Esto es más un ejercicio para entender su arquitectura y electrónica.

Además: se debe tener en cuenta que se PUEDE construir un procesador para el cual TODAS las operaciones, incluida la multiplicación, toman un solo reloj. Lo que tendría que hacer este procesador es deshacerse de toda la canalización y reducir la velocidad del reloj para que la latencia HW de cualquier circuito OP sea menor o igual a la latencia proporcionada por la temporización del reloj.

Para hacer esto, se eliminaría el aumento de rendimiento inherente que podemos obtener al agregar la canalización a un procesador. La canalización es la idea de tomar una tarea y dividirla en sub-tareas más pequeñas que se pueden realizar mucho más rápido. Al almacenar y enviar los resultados de cada subtarea entre subtareas, ahora podemos ejecutar una velocidad de reloj más rápida que solo necesita para permitir la latencia más larga de las subtareas, y no desde la tarea general en su conjunto.

Imagen del tiempo a través de una multiplicación:

| ------------------------------------------------- - | No Pipelined

En el diagrama anterior, el circuito sin tubería lleva 50 unidades de tiempo. En la versión canalizada, hemos dividido las 50 unidades en 5 pasos, cada una de las cuales lleva 10 unidades de tiempo, con un paso de almacenamiento intermedio. Es EXTREMADAMENTE importante tener en cuenta que en el ejemplo segmentado, cada uno de los pasos puede funcionar completamente por su cuenta y en paralelo. Para que se complete una operación, debe moverse a través de los 5 pasos en orden, pero otra operación de la misma operación con operandos puede estar en el paso 2 como uno en los pasos 1, 3, 4 y 5.

Habiendo dicho todo esto, este enfoque combinado nos permite llenar continuamente al operador en cada ciclo de reloj y obtener un resultado en cada ciclo de reloj SI podemos ordenar nuestras operaciones de tal manera que podamos realizar todas las operaciones antes de cambiar a otra operación, y todo lo que tomamos como un golpe de tiempo es la cantidad original de relojes necesarios para que la PRIMERA operación salga de la tubería.

La mística nos trae otro buen punto. También es importante mirar la arquitectura desde una perspectiva más sistémica. Es cierto que las arquitecturas más nuevas de Haswell se construyeron para mejorar el rendimiento de multiplicación de punto flotante dentro del procesador. Por esta razón, como nivel del sistema, se diseñó para permitir que se produjeran múltiples multiplicaciones en simultáneo contra un agregado que solo puede ocurrir una vez por reloj del sistema.

Todo esto se puede resumir de la siguiente manera:

Cada arquitectura es diferente de una perspectiva HW de nivel inferior así como de una perspectiva del sistema.
FUNCIONALMENTE, una multiplicación siempre llevará más tiempo que una suma, ya que combina una verdadera multiplicación junto con un verdadero paso de suma.
Comprenda la arquitectura en la que está intentando ejecutar su código y encuentre el equilibrio adecuado entre la legibilidad y obtener el mejor rendimiento de esa arquitectura.

Esto realmente depende de su máquina. Por supuesto, la multiplicación de enteros es bastante compleja en comparación con la suma, pero bastantes CPU de AMD pueden ejecutar una multiplicación en un solo ciclo . Eso es tan rápido como la suma.

Otras CPU tardan tres o cuatro ciclos para hacer una multiplicación, que es un poco más lenta que la suma. Pero no se acerca a la penalización de rendimiento que tuvo que sufrir hace diez años (en ese entonces, una multiplicación de 32 bits podía tomar ciclos de treinta y algo en algunas CPU).

Entonces, sí, la multiplicación está en la misma clase de velocidad en la actualidad, pero no, todavía no es exactamente tan rápida como la suma de todas las CPU.

Incluso si lo fuera, eso nos dice principalmente qué restricción impone el reloj a nuestro hardware. No podemos subir el reloj porque hay calor (?), Pero la cantidad de puertas de instrucciones ADD que una señal podría pasar durante un reloj puede ser muy grande, pero una sola instrucción ADD solo utilizará una de ellas. Por lo tanto, aunque en algún momento puede tomar muchos ciclos de reloj, no se utiliza todo el tiempo de propagación de las señales.

Si pudiéramos marcar más alto podríamos def. Hacer ADD más rápido, probablemente por varios órdenes de magnitud.

No, no lo es, y de hecho es notablemente más lento (lo que se tradujo en un 15% de éxito en el programa del mundo real en particular que estaba ejecutando).

Me di cuenta de esto cuando hice esta pregunta desde hace unos días here .

No, no son la misma velocidad. ¿Quién te dijo eso?

Las tablas de instrucciones de Agner Fog muestran que cuando se utilizan registros de enteros de 32 bits, los ADD / SUB de Haswell toman 0.25–1 ciclos (dependiendo de lo bien canalizadas que estén sus instrucciones) mientras que MUL toma 2-4 ciclos. El punto flotante es al revés: ADDSS / SUBSS toma 1–3 ciclos, mientras que MULSS toma 0.5–5 ciclos.

Una multiplicación requiere un paso final de una suma de, como mínimo, el mismo tamaño del número; por lo que tomará más tiempo que una adición. En decimal

123 112 ---- +246 ---- 123 | matrix generation 123 ---- ----- 13776 <---------------- Addition

Lo mismo se aplica en binario, con una reducción más elaborada de la matriz.

Dicho esto, razones por las que pueden tomar la misma cantidad de tiempo:

Para simplificar la arquitectura segmentada, todas las instrucciones regulares pueden diseñarse para tomar la misma cantidad de ciclos (las excepciones son, por ejemplo, los movimientos de memoria, que dependen del tiempo que demore hablar con la memoria externa).
Dado que el sumador para el paso final del multiplicador es igual que el sumador para una instrucción adicional ... ¿por qué no usar el mismo sumador omitiendo la generación y reducción de la matriz? Si usan el mismo sumador, obviamente tomarán la misma cantidad de tiempo.

Por supuesto, hay arquitecturas más complejas donde este no es el caso, y puede obtener valores completamente diferentes. También tienes arquitecturas que toman varias instrucciones en paralelo cuando no dependen unas de otras, y entonces estás un poco a merced de tu compilador ... y del sistema operativo.

La única forma de ejecutar esta prueba rigurosamente tendría que ejecutarse en ensamblaje y sin un sistema operativo; de lo contrario, hay demasiadas variables.