Me encontré con una pregunta de la clase de arquitectura de computadora. El profesor dice que para agregar dos números de 64 bits A y B usamos m-bit que llevan agregadores y multiplexores de rizado, como los siguientes:
y que para una m dada, digamos 8, obtenemos el mínimo retraso. ¿Por qué este diseño es más rápido?
Este es un carry adder select . El beneficio de la velocidad proviene de un multiplexor 2: 1 que selecciona M bits que es más rápido que un sumador de ondulación de M bits. (Cada bit del multiplexor solo depende de la suma del bit y del bit de selección (es decir, el arrastre), mientras que los bits más significativos de un ondulador de la sumadora de acarreo dependen del arrastre de los bits anteriores. El retraso del multiplexor sería el retardo de un multiplexor de un bit más el retardo de 1: M de abanico de salida para el acarreo desde el bloque anterior hasta los M bits.)
Los fragmentos más significativos de M bits se agregan en paralelo con los primeros M bits, por lo que su retraso es cero (las adiciones se completarán al mismo tiempo que se completa la primera adición de bit M ya que las entradas están disponibles en el Al mismo tiempo y los sumadores son los mismos).
Dado que la latencia de un simple sumador de selección de acarreo es la suma de las latencias del multiplexor y la latencia del sumador de acarreo de rizado M bit, hacer que M sea más grande puede reducir el número de multiplexores pero aumenta el retardo del sumador de arrastre de rizo. Para un sumador de 64 bits, esta latencia sería L rca + ((64 / M) -1) * L mux
Además, dado que el multiplexor agrega algo de retardo (y el retardo de salida del ventilador para el multiplexor no aumenta linealmente con M, por ejemplo, un multiplexor de 7 bits no sería 16.7% más lento que un multiplexor de 6 bits), los agregadores de acarreo de rizado para bits más significativos pueden ser capaces de usar más bits sin agregar retardo.
Ignorando las complejidades de las implementaciones reales, como el retardo del multiplexor dependiente del tamaño, si el sumador de un bit tiene N veces la latencia de un multiplexor, entonces un sumador selecto de acarreo de 64 bits de latencia mínima con todas las etapas tiene el mismo el tamaño equilibraría el retardo de acarreo de ondulación (L rca = N * M * L mux ) y los retrasos del multiplexor ((64 / M -1) * L mux ). Encontrar N * M * L mux = (64 / M -1) * L mux está resolviendo la ecuación cuadrática N * M 2 + M - 64 = 0. Si N = 2 (un sumador completo de un bit tiene el doble de latencia que un multiplexor), M = 5.41. En este caso, M = 5 y M = 6 dan una latencia total de un sumador de 64 bits de 22 retardos de multiplexor (13 etapas de 5 bits: 2 * 5 + 12; 11 etapas de 6 bits: 2 * 6 + 10) o 11 retrasos de sumador de un bit.
Bajo los mismos supuestos pero permitiendo sumadores de diferentes anchos, los anchos serían 5, 5, 5, 6, 6, 7, 7, 8, 8, 7. (La segunda etapa es el mismo ancho que la primera etapa , la tercera etapa podría ser de 5,5 bits, pero eso no es un número entero de bits.) Esto daría un retardo total de 19 multiplexores (10 etapas con un retardo de sumador de portadora de rizado inicial de 5 bits: 2 * 5 + 9) o 9.5 uno -bit retrasos del sumador.
Si la latencia de un sumador completo de un bit igualó la latencia del multiplexor (o, más correctamente, la latencia de un sumador de ondulación de transferencia de bit M igual a M por la latencia de un multiplexor de bit 2: 1 M, incluido el abanico de salida retraso), entonces la ecuación cuadrática a resolver sería M 2 + M - 64 = 0; M = 7.52, por lo que las etapas de 8 bits serían una latencia mínima (8 + 7 = 15 retardos de multiplexor). A medida que el número de bits en todo el sumador se acerca al infinito, la M ideal para un simple sumador de selección de acarreo se aproxima a la raíz cuadrada del número de bits (el término lineal se vuelve insignificante).
(El retardo del multiplexor también podría aprovecharse para permitir que los bits más significativos lleguen un poco más tarde. Los bits para la tercera etapa podrían llegar un retardo del multiplexor más tarde sin aumentar la latencia del sumador de 64 bits. Una técnica similar, canalización de ancho, divide el sumador en varias etapas de canalización pero con una latencia de ciclo único para operaciones dependientes si pueden comenzar con solo los bits menos significativos de los operandos. El Pentium 4 de Intel implementó una ALU de canalización de ancho (también llamada escalonada).
Tenga en cuenta que dichos sumadores de selección de acarreo no son los sumadores de latencia más bajos. Por ejemplo, el uso de un sumador carry-lookahead en lugar de un ondulador ondulador carry reducirá el retraso en la generación del bit de acarreo , proporcionando la señal de selección para los multiplexores anteriormente.
Lea otras preguntas en las etiquetas math computer-architecture computers delay adder