¿Por qué la adición es tan rápida como las operaciones de bits en procesadores modernos?

73

Sé que las operaciones a nivel de bits son tan rápidas en los procesadores modernos, porque pueden operar en 32 o 64 bits en paralelo, por lo que las operaciones a nivel de bits solo requieren un ciclo de reloj. Sin embargo, la adición es una operación compleja que consiste en al menos una y posiblemente hasta una docena de operaciones de bits, por lo que, naturalmente, pensé que sería de 3 a 4 veces más lenta. Me sorprendió ver, después de un punto de referencia simple, que la adición es exactamente tan rápida como cualquiera de las operaciones de bits (XOR, OR, AND, etc.). ¿Alguien puede arrojar luz sobre esto?

Anónimo
fuente
1
Sí, la multiplicación también fue bastante rápida en mis pruebas. Fue solo alrededor de 2 veces más lento que la suma, mientras que la división fue alrededor de 30 veces (!) Veces más lenta.
Anónimo
Descripción compacta de los sumadores de árbol de prefijos paralelos de última generación: una taxonomía de redes de prefijos paralelos de David Harris: pages.hmc.edu/harris/research/taxonomy.pdf
Franki
Más elaborado: Tesis doctoral del doctorado Jun Chen "Estructuras de prefijos paralelos para sumadores binarios y de módulo {2n − 1, 2n, 2n + 1}" digital.library.okstate.edu/etd/Chen_okstate_0664D_10070.pdf
Franki

Respuestas:

104

La adición es rápida porque los diseñadores de CPU han puesto los circuitos necesarios para hacerlo rápido. Se necesitan muchas más puertas que las operaciones bit a bit, pero es tan frecuente que los diseñadores de CPU han considerado que vale la pena. Ver https://en.wikipedia.org/wiki/Adder_(electronics) .

Ambos pueden hacerse lo suficientemente rápido como para ejecutarse dentro de un solo ciclo de CPU. No son igualmente rápidos (la adición requiere más compuertas y más latencia que una operación bit a bit), pero es lo suficientemente rápido como para que un procesador pueda hacerlo en un ciclo de reloj. Hay una sobrecarga de latencia por instrucción para la lógica de control y decodificación de instrucciones, y la latencia para eso es significativamente mayor que la latencia para hacer una operación bit a bit, por lo que la diferencia entre los dos se ve inundada por esa sobrecarga. La respuesta de AProgrammer y la respuesta de Paul92 explican bien esos efectos.

DW
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
38

Hay varios aspectos.

  • El costo relativo de una operación bit a bit y una adición. Un sumador ingenuo tendrá una profundidad de puerta que dependerá linealmente del ancho de la palabra. Hay enfoques alternativos, más costosos en términos de puertas, que reducen la profundidad (IIRC, la profundidad depende entonces logarítmicamente del ancho de la palabra). Otros han dado referencias para tales técnicas, solo señalaré que la diferencia también es menos importante de lo que puede parecer teniendo en cuenta el costo de la operación debido a la necesidad de una lógica de control que agregue retrasos.

  • Luego está el hecho de que los procesadores generalmente están sincronizados (estoy al tanto de algunas investigaciones o diseños no sincronizados para propósitos especiales, pero ni siquiera estoy seguro de que algunos estén disponibles comercialmente). Eso significa que cualquiera que sea la velocidad de una operación, tomará un múltiplo entero del ciclo del reloj.

  • Finalmente están las consideraciones micro-arquitectónicas: ¿estás seguro de que mides lo que quieres? Hoy en día, los procesadores tienden a ser canalizados, multiescalares, con ejecución fuera de orden y cualquier otra cosa. Eso significa que pueden ejecutar varias instrucciones al mismo tiempo, en varias etapas de finalización. Si quiere mostrar por mediciones que una operación lleva más tiempo que otra, debe tener en cuenta ese aspecto, ya que su objetivo es ocultar esa diferencia. Es muy posible que tenga el mismo rendimiento para operaciones de suma y bit a bit cuando usa datos independientes, pero una medida de la latencia o la introducción de dependencias entre las operaciones puede mostrar lo contrario. Y también debe asegurarse de que el cuello de botella de su medida esté en la ejecución, y no, por ejemplo, en los accesos a la memoria.

Un programador
fuente
66
+1. Sí, la mayoría de los procesadores tienen reloj, pero algunas CPU sin reloj están disponibles comercialmente.
David Cary
2
Otra posibilidad es que un procesador pueda almacenar un registro de 64 bits como una pieza de 16 bits y tres piezas de 17 bits, donde los bits adicionales de cada pieza que contienen un transporte diferido desde abajo. Una adición que es seguida por una operación bit a bit o una tienda puede requerir 1-2 ciclos adicionales para propagar el transporte, pero una adición que es seguida por otra adición no lo haría. Además, en el caso de "tienda", el tiempo de propagación adicional puede retrasar el rendimiento de la tienda, pero no habría necesidad de código para "esperar".
supercat
3
@supercat El Pentium 4 hizo algo como esto, con una ALU de doble velocidad (en relación con el resto del procesador) que tendría los 16 o 32 bits bajos listos para una operación posterior un medio ciclo antes de los bits de la mitad superior.
Jeffrey Bosboom
2
¿estás seguro de que mides lo que quieres? En este caso, la conclusión del OP de las mediciones es correcta para la gran mayoría de las CPU. La adición es tan común que las CPU superescalares tienen unidades adicionales en todos los puertos de ejecución, y los booleanos son tan baratos de implementar (en el recuento de transistores) que también están presentes en todos los puertos. Por lo tanto, agregar y booleanos casi siempre tienen el mismo rendimiento (por ejemplo, 4 por reloj en Intel Haswell).
Peter Cordes
2
Sin embargo, la suma de enteros SIMD suele tener un rendimiento menor que el booleano SIMD, a pesar de que generalmente tienen la misma latencia. Las CPU Intel de PentiumII a través de Broadwell solo pueden ejecutar adiciones vector-int (por ejemplo paddw) a 2 por reloj, pero booleanos (como pand) a 3 por reloj. (Skylake pone un sumador de vectores en los tres puertos de ejecución de vectores.)
Peter Cordes
24

Las CPU funcionan en ciclos. En cada ciclo, algo sucede. Por lo general, una instrucción tarda más ciclos en ejecutarse, pero se ejecutan varias instrucciones al mismo tiempo, en diferentes estados.

Por ejemplo, un procesador simple puede tener 3 pasos para cada instrucción: buscar, ejecutar y almacenar. En cualquier momento, se están procesando 3 instrucciones: una se está recuperando, una se está ejecutando y una almacena sus resultados. Esto se llama una tubería y tiene en este ejemplo 3 etapas. Los procesadores modernos tienen tuberías con más de 15 etapas. Sin embargo, además, así como la mayoría de las operaciones aritméticas, generalmente se ejecutan en una etapa (estoy hablando de la operación de sumar 2 números por la ALU, no de la instrucción en sí misma; dependiendo de la arquitectura del procesador, la instrucción puede requerir más ciclos para recuperar argumentos de la memoria, realizar condicionales, almacenar resultados en la memoria).

La duración de un ciclo está determinada por la ruta crítica más larga. Básicamente, es la mayor cantidad de tiempo necesaria para que se complete alguna etapa de la tubería. Si desea acelerar la CPU, debe optimizar la ruta crítica. Si no es posible reducir la ruta crítica per se, puede dividirse en 2 etapas de la tubería, y ahora puede registrar su CPU a casi el doble de frecuencia (suponiendo que no haya otra ruta crítica que le impida hacerlo) ) Pero esto viene con una sobrecarga: debe insertar un registro entre las etapas de la tubería. Lo que significa que realmente no obtienes una velocidad 2 veces mayor (el registro necesita tiempo para almacenar los datos) y has complicado todo el diseño.

Ya existen métodos bastante eficientes para realizar la suma (por ejemplo, llevar sumadores de búsqueda anticipada) y la suma no es una ruta crítica para la velocidad del procesador, por lo que no tiene sentido dividirla en múltiples ciclos.

Además, tenga en cuenta que si bien puede parecerle complicado, en hardware las cosas se pueden hacer en paralelo muy rápido.

Paul92
fuente
3
¡La gran sobrecarga de tuberías más largas es más ciclos para recuperarse de una predicción errónea de una rama! El gasto de transistores para almacenar datos entre las etapas es menor en estos días. Incluso una CPU simple canalizada debe buscar / decodificar antes de las instrucciones que realmente se están ejecutando. Si la CPU descubre que el front-end estaba trabajando en el código incorrecto porque una rama fue de una manera diferente a la prevista (o alguna otra especulación errónea), tiene que descartar ese trabajo y comenzar con la instrucción correcta. Las cosas solo empeoran con las CPU superescalares fuera de servicio que pueden tener muchos insns en vuelo.
Peter Cordes
12

Los procesadores están sincronizados, por lo que incluso si algunas instrucciones pueden hacerse claramente más rápido que otras, bien pueden tomar el mismo número de ciclos.

Probablemente encontrará que los circuitos necesarios para transportar datos entre registros y unidades de ejecución son significativamente más complicados que los sumadores.

Tenga en cuenta que la simple instrucción MOV (registro a registro) hace incluso menos cómputo que la lógica bit a bit, sin embargo, tanto MOV como ADD generalmente toman un ciclo. Si MOV se pudiera hacer el doble de rápido, las CPU se sincronizarían dos veces más rápido y los ADD serían dos ciclos.

James Hollis
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Gilles 'SO- deja de ser malvado'
1
Resumen de la discusión: algunas CPU fuera de servicio manejan MOV especialmente con cambio de nombre de registro, con latencia cero efectiva. Ver ¿Puede el MOV de x86 ser realmente "gratis"? ¿Por qué no puedo reproducir esto en absoluto? para los detalles completos de lo que realmente cuesta MOV.
Peter Cordes
12

La adición es lo suficientemente importante como para que no espere a que un bit de transporte se propague a través de un acumulador de 64 bits: el término para eso es un sumador de anticipación de transporte y que son básicamente parte de las CPU de 8 bits (y sus ALU) y hacia arriba. De hecho, los procesadores modernos tampoco necesitan mucho más tiempo de ejecución para una multiplicación completa: carry-lookahead es en realidad una herramienta realmente antigua (y relativamente asequible) en la caja de herramientas del diseñador de un procesador.

usuario72735
fuente
La multiplicación de enteros es definitivamente una latencia más alta y un rendimiento más bajo que ADD en x86. Pero es increíblemente rápido considerando cuántos sumadores se necesitan para construir un multiplicador rápido: por ejemplo, en Intel desde Nehalem y AMD desde Ryzen, la multiplicación de enteros escalares de 8/16/32/64 bits es latencia de 3 ciclos, con un rendimiento por 1c (una unidad de ejecución totalmente canalizada). Esto apesta en comparación con el rendimiento de ADD de 3 o 4 por reloj, pero es sorprendente en comparación con la latencia IMUL de 9 ciclos en Intel Pentium P5. Las cosas son similares para SIMD: multiplicar vector-int es una latencia más alta y un rendimiento más bajo que agregar, pero aún así es rápido.
Peter Cordes
Entonces, sí, multiplicar solía ser mucho más costoso en comparación con otras instrucciones de lo que es ahora. Evitarlo a un costo de más de 2 instrucciones generalmente no vale la pena, y a veces ni siquiera vale la pena un sustituto de 2 instrucciones (por ejemplo, con una leainstrucción shift + add ).
Peter Cordes
9

Creo que sería difícil encontrar un procesador que tuviera más ciclos que una operación bit a bit. En parte porque la mayoría de los procesadores deben realizar al menos una adición por ciclo de instrucción simplemente para incrementar el contador del programa. Las simples operaciones bit a bit no son tan útiles.

(Ciclo de instrucción, no ciclo de reloj; por ejemplo, el 6502 toma un mínimo de dos ciclos de reloj por instrucción debido a que no está conectado y no tiene un caché de instrucciones)

El concepto real que puede faltar es el de la ruta crítica : dentro de un chip, la operación más larga que se puede realizar dentro de un ciclo dicta, a nivel de hardware, qué tan rápido se puede sincronizar el chip.

La excepción a esto es la lógica asincrónica (raramente utilizada y apenas comercializada), que realmente se ejecuta a diferentes velocidades dependiendo del tiempo de propagación lógica, la temperatura del dispositivo, etc.

pjc50
fuente
No son operaciones bit a bit controlables por el usuario, pero algunas instrucciones en el 8086 (por ejemplo, borrar el indicador de interrupción ) tomaron menos ciclos que una suma entera. De manera más abstracta, un sistema RISC donde todas las instrucciones tienen una palabra de tamaño podría usar un contador binario simple para la PC, que sería un circuito mucho más rápido que un sumador de propósito general.
Marque
La adición en el contador del programa tiende a ser muy simple en comparación con una instrucción aritmética adicional, porque uno de los operandos es pequeño (ya sea un tamaño de instrucción o un desplazamiento de salto relativo que también tiene un tamaño limitado)
Ben Voigt
Se canalizó 6502: se leía el primer byte de la siguiente instrucción durante el último ciclo de la anterior. De lo contrario, fetch / decode / execute habría sido al menos tres ciclos.
gnasher729
8

En el nivel de la puerta, tiene razón en que se necesita más trabajo para hacer la suma y, por lo tanto, lleva más tiempo. Sin embargo, ese costo es lo suficientemente trivial que no importa.

Los procesadores modernos están sincronizados. No puede hacer instrucciones en nada excepto en múltiplos de esta frecuencia de reloj. Si las velocidades de reloj se elevaran, para maximizar la velocidad de las operaciones bit a bit, tendría que gastar al menos 2 ciclos en la suma. Pasaría gran parte de este tiempo esperando porque realmente no necesitaba el tiempo completo de 2 ciclos. Solo necesitabas 1.1 (o algún número como ese). Ahora su chip agrega más lento que todos los demás en el mercado.

Peor aún, el simple acto de agregar o realizar operaciones bit a bit es solo una pequeña parte de lo que sucede durante un ciclo. Debe poder obtener / decodificar instrucciones dentro de un ciclo. Debe poder realizar operaciones de caché dentro de un ciclo. Están sucediendo muchas otras cosas en la misma escala de tiempo que la simple adición o la operación bit a bit.

La solución, por supuesto, es desarrollar una tubería masivamente profunda, dividiendo estas tareas en pequeñas partes que se ajusten al pequeño tiempo de ciclo definido por una operación bit a bit. El Pentium 4 mostró los límites del pensamiento en estos términos de tubería profunda. Surgen todo tipo de problemas. En particular, la ramificación se vuelve notoriamente difícil porque tienes que vaciar la tubería una vez que tienes los datos para determinar qué rama tomar.

Cort Ammon
fuente
7

Los procesadores modernos están sincronizados: cada operación toma un número integral de ciclos de reloj. Los diseñadores del procesador determinan la duración de un ciclo de reloj. Hay dos consideraciones allí: una, la velocidad del hardware, por ejemplo, medida como el retraso de una sola compuerta NAND. Esto depende de la tecnología utilizada y de compensaciones como la velocidad frente al uso de energía. Es independiente del diseño del procesador. Dos, los diseñadores deciden que la duración de un ciclo de reloj es igual a n retrasos de una sola puerta NAND, donde n podría ser 10, o 30, o cualquier otro valor.

Esta opción n limita cuán complejas pueden ser las operaciones que se pueden procesar en un ciclo. Habrá operaciones que se pueden hacer en 16 pero no en 15 retrasos NAND. Por lo tanto, elegir n = 16 significa que tal operación se puede hacer en un ciclo, elegir n = 15 significa que no se puede hacer.

Los diseñadores elegirán n para que muchas operaciones importantes se puedan realizar en uno o dos o tres ciclos. n será elegido localmente óptimo: si reemplaza n con n-1, la mayoría de las operaciones serían un poco más rápidas, pero algunas (aquellas que realmente necesitan los retrasos completos de n NAND) serían más lentas. Si pocas operaciones se ralentizaran, de modo que la ejecución general del programa sea más rápida en promedio, entonces habría elegido n-1. También podrías haber elegido n + 1. Eso hace que la mayoría de las operaciones sean un poco más lentas, pero si tiene muchas operaciones que no se pueden realizar en n retrasos, pero se pueden realizar en n + 1, entonces el procesador en general sería más rápido.

Ahora su pregunta: Sumar y restar son operaciones tan comunes que desea poder ejecutarlas en un solo ciclo. Como resultado, no importa que AND, OR, etc. puedan ejecutarse más rápido: todavía necesitan ese ciclo. Por supuesto, la unidad "calculando" AND, OR, etc. tiene mucho tiempo para girar los pulgares, pero eso no se puede evitar.

Tenga en cuenta que no se trata solo de si una operación se puede realizar con n demoras NAND o no: una adición, por ejemplo, se puede hacer más rápido al ser un poco inteligente, aún más rápido al ser muy inteligente, aún un poco más rápido al invertir cantidades extraordinarias de hardware y, por fin, un procesador puede tener una combinación de circuitos muy rápidos, muy caros y un poco más lentos y más baratos, por lo que existe la posibilidad de hacer una operación lo suficientemente rápida gastando más dinero en ella.

Ahora puede hacer que la velocidad del reloj sea tan alta / el ciclo tan corto que solo las operaciones de bit simples se ejecutan en un ciclo y todo lo demás en dos o más. Eso probablemente ralentizaría el procesador. Para las operaciones que toman dos ciclos, generalmente hay gastos generales para mover una instrucción incompleta de un ciclo al siguiente, por lo que dos ciclos no significa que tenga el doble de tiempo para la ejecución. Entonces, para hacer la adición en dos ciclos, no podría duplicar la velocidad del reloj.

gnasher729
fuente
6

Permítanme corregir algunas cosas que no se mencionaron explícitamente en sus respuestas existentes:

Sé que las operaciones bit a bit son muy rápidas en los procesadores modernos, porque pueden operar en 32 o 64 bits en paralelo,

Esto es verdad. Etiquetar una CPU como bit "XX" generalmente (no siempre) significa que la mayoría de sus estructuras comunes (anchos de registro, RAM direccionable, etc.) tienen un tamaño de XX bits (a menudo "+/- 1" o algo así). Pero con respecto a su pregunta, puede asumir con seguridad que una CPU con 32 bits o 64 bits realizará cualquier operación básica de bits en 32 o 64 bits en tiempo constante.

entonces las operaciones bit a bit toman solo un ciclo de reloj.

Esta conclusión no es necesariamente el caso. Especialmente las CPU con conjuntos de instrucciones enriquecidos (google CISC vs. RISC) pueden tomar fácilmente más de un ciclo incluso para comandos simples. Con el entrelazado, incluso los comandos más simples pueden descomponerse en fetch-exec-store con 3 relojes (como ejemplo).

Sin embargo, la adición es una operación compleja

No, la suma de enteros es una operación simple; resta también. Es muy fácil implementar sumadores en hardware completo, y hacen sus cosas tan instantáneamente como las operaciones básicas de bits.

que consiste en al menos una y posiblemente hasta una docena de operaciones bit a bit, por lo que naturalmente pensé que sería 3-4 veces más lento.

Tomará 3-4 veces más transistores, pero en comparación con el panorama general que es descuidado.

Me sorprendió ver después de un simple punto de referencia que la adición es exactamente tan rápida como cualquiera de las operaciones bit a bit (XOR, OR, AND, etc.). ¿Alguien puede arrojar luz sobre esto?

Sí: la suma de enteros es una operación bit a bit (con algunos bits más que los otros, pero aún así). No hay necesidad de hacer nada por etapas, no hay necesidad de algoritmos complicados, relojes o cualquier otra cosa.

Si desea agregar más bits que la arquitectura de su CPU, incurrirá en una penalización por tener que hacerlo por etapas. Pero esto está en otro nivel de complejidad (nivel de lenguaje de programación, no nivel de ensamblaje / código de máquina). Este era un problema común en el pasado (o en la actualidad en pequeñas CPU integradas). Para PC, etc., sus 32 o 64 bits son suficientes para que los tipos de datos más comunes comiencen a convertirse en un punto discutible.

AnoE
fuente
Es interesante notar que reducir el costo de tiempo de la adición de O (N) a O (sqrt (N)) no aumenta significativamente el número requerido de transistores o la complejidad de enrutamiento (cada etapa solo necesita dejar que un cable se filtre desde abajo , y debe haber etapas de fusión adicionales sqrt (N). El costo de tiempo puede reducirse a O (lgN) a un costo de transistores O (lgN), pero en muchos casos puede ser útil procesar algo como un 64- adición de bits como, por ejemplo, ocho adiciones de 8 bits (utilizando el reenvío sqrtN) unidas con tres capas de lógica de fusión, en lugar de 64 adiciones de 1 bit con seis capas de fusión.
supercat
Sí, los sumadores son bastante simples. Lo que es realmente impresionante son las modernas CPU x86 con un multiplicador entero de 64 bits de latencia de 3 ciclos totalmente interconectado . (por ejemplo, imul rax, rcxtiene una latencia de 3c y un rendimiento por 1c en la familia Intel Sandybridge y AMD Ryzen). Incluso la multiplicación completa de 64 bits (que produce el resultado de 128 bits en rdx: rax) tiene la misma latencia y rendimiento, pero se implementa como 2 uops (que se ejecutan en paralelo en diferentes puertos). (Consulte agner.org/optimize para obtener tablas de instrucciones y una excelente guía de microarchivos).
Peter Cordes
[add-with-carry] está en otro nivel de complejidad (nivel de lenguaje de programación, no nivel de ensamblaje / código de máquina . Depende del lenguaje. El compilador de CA que apunta a una CPU de 16 bits tiene que emitir add / adc cuando compila adición de dos uint32_tvalores. Esto sigue siendo relevante hoy para int64_t en objetivos de 32 bits. AVR es un microcontrolador RISC de 8 bits, por lo que los enteros de 32 bits requieren 4 instrucciones: godbolt.org/g/wre0fM
Peter Cordes
Sí, @PeterCordes, eso es lo que quise decir, he aclarado un poco mi oración.
AnoE