Es la multiplicación de enteros realmente la misma velocidad que la adición en la CPU moderna

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

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

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

La otra cosa a recordar es que la multiplicación tomará más tiempo o más corto dependiendo de la arquitectura del procesador en el que lo esté ejecutando. Esto puede o no 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 se vaya).

En todo TECNICISMO, si los multiplicados fueran lo único que estabas haciendo (sin bucear, contar, etc...), multiplicado sería 2 a (como he visto en Arquitecturas PPC) 35 veces más lento. Esto es más un ejercicio en la comprensión de su arquitectura, y la electrónica.

Además: Cabe señalar que SE PODRÍA construir un procesador para el cual TODAS las operaciones, incluyendo una multiplicación, toman un solo reloj. Lo que este procesador tendría que hacer es, deshacerse de toda la canalización, y ralentizar el reloj para que la latencia HW de cualquier circuito OPs es menor o igual a la latencia PROPORCIONADA por la sincronización del reloj.

Para hacer esto obtendría deshazte de las ganancias de rendimiento inherentes que podemos obtener al agregar canalizaciones 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 reenviar los resultados de cada sub-tarea entre sub-tareas, ahora podemos ejecutar una velocidad de reloj más rápida que solo necesita permitir la latencia más larga de las sub-tareas, y no de la tarea general en su conjunto.

Imagen del tiempo a través de una multiplicar:

|--------------------------------------------------| No Canalizadas

|--Paso 1--|--Paso 2--|--Paso 3--|--Paso 4--|--Paso 5--| Canalizado

En el diagrama anterior, el circuito no canalizado toma 50 unidades de tiempo. En la versión canalizada, hemos dividido las 50 unidades en 5 pasos cada uno tomando 10 unidades de tiempo, con un paso de tienda en el medio. Es EXTREMADAMENTE importante tener en cuenta que en el ejemplo canalizado, cada uno de los pasos puede estar trabajando completamente en su propio y en paralelo. Para que una operación se complete, debe moverse a través de los 5 pasos en orden, pero otra de la misma operación con operandos puede estar en el paso 2 como uno está en el paso 1, 3, 4 y 5.

Con todo esto dicho, este enfoque canalizado nos permite llenar continuamente el operador cada ciclo de reloj, y obtener un resultado en cada ciclo de reloj SI somos capaces de ordenar nuestras operaciones de modo que podamos realizar todas una operación antes de cambiar a otra operación, y todo lo que tomar como un golpe de tiempo es la cantidad original de relojes necesarios para obtener la PRIMERA operación fuera de la tubería.

Místico trae otro buen punto. También es importante mirar la arquitectura desde una perspectiva más de sistemas. Es cierto que las nuevas arquitecturas de Haswell se construyeron para mejorar el rendimiento de multiplicación de Punto Flotante dentro del procesador. Por esta razón, como nivel de Sistema, se diseñó para permitir que ocurrieran múltiples multiplicaciones en simultaneidad versus una agregar que solo puede suceder una vez por reloj del sistema.

Todo esto se puede resumir de la siguiente manera:

1. Cada arquitectura es diferente desde una perspectiva de HW de nivel inferior, así como desde una perspectiva de sistema
2. FUNCIONALMENTE, una multiplicación siempre tomará más tiempo que una suma porque combina una multiplicación verdadera junto con un paso de suma verdadera.
3. Comprenda la arquitectura en la que está tratando de ejecutar su código y encuentre el equilibrio adecuado entre legibilidad y obtener realmente 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 AMD pueden ejecutar una multiplicación en un solo ciclo. Eso es tan rápido como la suma.

Otras CPU toman tres o cuatro ciclos para hacer una multiplicación, que es un poco más lenta que la suma. Pero no está cerca de la penalización de rendimiento que tuvo que sufrir hace diez años (en ese entonces una multiplicación de 32 bits podría tomar treinta y tantos ciclos en algunos CPU).

Así que, sí, la multiplicación está en la misma clase de velocidad hoy en día, pero no, todavía no es exactamente tan rápido como la suma en todas las CPU.

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 suma. 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, las razones por las que pueden tomar la misma cantidad de tiempo:

1. Para simplificar la arquitectura canalizada, todas las instrucciones regulares se pueden diseñar para tomar la misma cantidad de ciclos (las excepciones son movimientos de memoria, por ejemplo, que dependen de cuánto tiempo se tarda en hablar con la memoria externa).
2. Dado que el sumador para el paso final del multiplicador es igual que el sumador para una instrucción add... ¿por qué no usar el mismo sumador omitiendo la generación y reducción de la matriz? Si usan la misma víbora, entonces 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. Usted también tiene 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 manera de ejecutar esta prueba rigurosamente tendría que ejecutarse en ensamblado y sin un sistema operativo; de lo contrario, hay demasiadas variables.

Incluso si lo fuera, eso nos dice principalmente qué restricción pone el reloj en nuestro hardware. No podemos marcar más alto porque el calor(?), pero el número de puertas de instrucción ADD que una señal podría pasar durante un reloj podría ser muy muchos, pero una sola instrucción ADD solo utilizaría una de ellas. Así, mientras que en algún momento puede tomar igualmente muchos ciclos de reloj, no todo el tiempo de propagación de las señales se utiliza.

Si pudiéramos marcar más alto podríamos def. hacer AGREGAR 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 de rendimiento para el programa del mundo real en particular que estaba ejecutando).

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

Dado que las otras respuestas tratan de dispositivos reales, actuales which que están destinados a cambiar y mejorar a medida que pasa el tiempo thought pensé que podríamos mirar la pregunta desde el lado teórico.

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

Prueba: El tiempo para que un circuito combinatorio se estabilice es proporcional al profundidad de la secuencia más larga de puertas lógicas de cualquier entrada a cualquier salida. Así que debemos demostrar que un gradeschool multiplicar circuito es O (log N) veces más profundo que un circuito de suma.

La suma se implementa normalmente como una media sumadora seguida de N-1 sumadoras completas, con los bits de carga encadenados de una sumadora a la siguiente. Este circuito claramente tiene profundidad O (N). (Este circuito se puede optimizar de muchas maneras, pero el peor rendimiento de los casos siempre será O (N) a menos que las tablas de búsqueda absurdamente grandes sean utilizar.)

Para multiplicar A por B, primero necesitamos multiplicar cada bit de A con cada bit de B. Cada multiplicación bit a bit es simplemente an Y gate. Hay N^2 multiplicaciones bitwise para realizar, por lo tanto N^2 Y puertas but pero todos ellos pueden ejecutar en paralelo, para una profundidad de circuito de 1. Esto resuelve la fase de multiplicación del algoritmo gradeschool, dejando solo la fase de adición.

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