Sumador de acarreo y salto

Circuito lógico aritmético

Un sumador de acarreo-salto ^{[nb 1]} (también conocido como sumador de acarreo-derivación ) es una implementación de sumador que mejora el retardo de un sumador de acarreo-desplazamiento con poco esfuerzo en comparación con otros sumadores. La mejora del retardo en el peor de los casos se logra utilizando varios sumadores de acarreo-salto para formar un sumador de acarreo-salto en bloque.

A diferencia de otros sumadores rápidos, el rendimiento del sumador de acarreo-salto aumenta solo con algunas de las combinaciones de bits de entrada. Esto significa que la mejora de la velocidad es solo probabilística .

Sumador de acarreo y salto simple

El peor caso para un sumador de acarreo de ondulación de un nivel simple ocurre cuando la condición de propagación ^[1] es verdadera para cada par de dígitos . Entonces, el acarreo de entrada se propaga a través del sumador de bits y aparece como acarreo de salida después de . ${\displaystyle (a_{i},b_{i})}$ ${\displaystyle n}$ ${\displaystyle \tau _{CRA}(n)\approx n\cdot \tau _{VA}}$

Sumador completo con señales de generación y propagación adicionales.

Para cada par de bits de entrada de operando, las condiciones de propagación se determinan mediante una compuerta XOR. Cuando todas las condiciones de propagación son verdaderas , el bit de entrada determina el bit de salida. ${\displaystyle (a_{i},b_{i})}$ ${\displaystyle p_{i}=a_{i}\oplus b_{i}}$ ${\displaystyle c_{0}}$

El sumador de salto de acarreo de n bits consta de una cadena de ondulación de acarreo de n bits, una compuerta AND de n entradas y un multiplexor. Cada bit de propagación , que es proporcionado por la cadena de ondulación de acarreo, está conectado a la compuerta AND de n entradas. El bit resultante se utiliza como bit de selección de un multiplexor que conmuta el último bit de acarreo o la señal de acarreo de entrada a la señal de acarreo de salida . ${\displaystyle p_{i}}$ ${\displaystyle c_{n}}$ ${\displaystyle c_{0}}$ ${\displaystyle c_{out}}$

• ${\displaystyle s=p_{n-1}\wedge p_{n-2}\wedge \dots \wedge p_{1}\wedge p_{0}=p_{[0:n-1]}}$

Esto reduce en gran medida la latencia del sumador a través de su ruta crítica, ya que el bit de acarreo para cada bloque ahora puede "saltear" bloques con una señal de propagación de grupo establecida en lógica 1 (a diferencia de una cadena de acarreo de ondulación larga, que requeriría que el acarreo se ondule a través de cada bit en el sumador). El número de entradas de la compuerta AND es igual al ancho del sumador. Para un ancho grande, esto se vuelve poco práctico y conduce a demoras adicionales, porque la compuerta AND tiene que construirse como un árbol. Se logra un buen ancho cuando la lógica de suma tiene la misma profundidad que la compuerta AND de n entradas y el multiplexor.

Sumador de acarreo-salto de 4 bits.

Actuación

La ruta crítica de un sumador de acarreo-salto comienza en el primer sumador completo, pasa por todos los sumadores y termina en el bit de suma . Los sumadores de acarreo-salto se encadenan (consulte los sumadores de acarreo-salto en bloque) para reducir la ruta crítica general, ya que un sumador de acarreo-salto de un solo bit no tiene un beneficio real de velocidad en comparación con un sumador de acarreo-desplazamiento de bits. ${\displaystyle s_{n-1}}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle \tau _{CSA}(n)=\tau _{CRA}(n)}$

La lógica de salto consta de una puerta AND de entrada y un multiplexor. ${\displaystyle m}$

${\displaystyle T_{SK}=T_{AND}(m)+T_{MUX}}$

Como las señales de propagación se calculan en paralelo y están disponibles anticipadamente, la ruta crítica para la lógica de salto en un sumador de acarreo-salto consiste únicamente en el retraso impuesto por el multiplexor (salto condicional).

${\displaystyle T_{CSK}=T_{MUX}=2D}$.

Sumadores de bloques carry-skip

Sumador de acarreo y salto de bloque fijo de 16 bits con un tamaño de bloque de 4 bits.

Los sumadores de bloques de acarreo y salto se componen de varios sumadores de acarreo y salto. Hay dos tipos de sumadores de bloques de acarreo y salto. Los dos operandos y se dividen en bloques de bits. ${\displaystyle A=(a_{n-1},a_{n-2},\dots ,a_{1},a_{0})}$ ${\displaystyle B=(b_{n-1},b_{n-2},\dots ,b_{1},b_{0})}$ ${\displaystyle k}$ ${\displaystyle (m_{k},m_{k-1},\dots ,m_{2},m_{1})}$

• ¿Por qué se utilizan sumadores block-carry-skip?
• ¿El tamaño del bloque debe ser constante o variable?
• Ancho de bloque fijo vs. ancho de bloque variable

Sumadores de bloques de tamaño fijo con acarreo y salto

Los sumadores de salto de acarreo de bloques de tamaño fijo dividen los bits de entrada en bloques de bits cada uno, lo que da como resultado bloques. La ruta crítica consta de la ruta de ondulación y el elemento de salto del primer bloque, las rutas de salto que se encuentran entre el primer y el último bloque y, por último, la ruta de ondulación del último bloque. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle k={\frac {n}{m}}}$

${\displaystyle T_{FCSA}(n)=T_{CRA_{[0:c_{out}]}}(m)+T_{CSK}+(k-2)\cdot T_{CSK}+T_{CRA}(m)=3D+m\cdot 2D+(k-1)\cdot 2D+(m+2)2D=(2m+k)\cdot 2D+5D}$

El tamaño de bloque óptimo para un ancho de sumador dado n se deriva igualando a 0

${\displaystyle {\frac {dT_{FCSA}(n)}{dm}}=0}$

${\displaystyle 2D\cdot \left(2-n\cdot {\frac {1}{m^{2}}}\right)=0}$

${\displaystyle \Rightarrow m_{1,2}=\pm {\sqrt {\frac {n}{2}}}}$

Sólo se pueden realizar tamaños de bloque positivos

${\displaystyle \Rightarrow m={\sqrt {\frac {n}{2}}}}$

Sumadores de bloques de tamaño variable (VBA, Oklobdzija-Barnes)

El rendimiento se puede mejorar, es decir, todos los acarreos se propagan más rápidamente al variar los tamaños de los bloques. En consecuencia, los bloques iniciales del sumador se hacen más pequeños para detectar rápidamente los acarreos generados que deben propagarse a los siguientes, los bloques intermedios se hacen más grandes porque no son el caso problemático y luego los bloques más significativos se vuelven a hacer más pequeños para que las entradas de acarreo que llegan tarde se puedan procesar rápidamente. ^[2]

Sumadores de acarreo y salto de varios niveles

Al utilizar bloques de salto adicionales en una capa adicional, las señales de propagación de bloques se resumen aún más y se utilizan para realizar saltos más grandes: ${\displaystyle p_{[i:i+3]}}$

${\displaystyle p_{[i:i+15]}=p_{[i:i+3]}\wedge p_{[i+4:i+7]}\wedge p_{[i+8:i+11]}\wedge p_{[i+12:i+15]}}$

Haciendo así que el sumador sea aún más rápido.

Optimización de carry-skip

El problema de determinar los tamaños de bloque y la cantidad de niveles necesarios para crear el sumador de acarreo-salto más rápido físicamente se conoce como "problema de optimización del sumador de acarreo-salto". Este problema se vuelve complejo por el hecho de que los sumadores de acarreo-salto se implementan con dispositivos físicos cuyo tamaño y otros parámetros también afectan el tiempo de adición.

El problema de optimización de acarreo-salto para tamaños de bloques variables y niveles múltiples para un nodo de proceso de dispositivo arbitrario fue resuelto por Oklobdzija y Barnes en IBM y publicado en 1985.

Descripción general de la implementación

Si lo desglosamos en términos más específicos, para construir un sumador de acarreo-derivación de 4 bits, se necesitarían 6 sumadores completos . Los buses de entrada serían un A de 4 bits y un B de 4 bits , con una señal de acarreo de entrada ( CIN ). La salida sería un bus X de 4 bits y una señal de acarreo de salida ( COUT ).

Los dos primeros sumadores completos sumarían los dos primeros bits. La señal de salida del segundo sumador completo ( ) activaría la señal de selección para tres multiplexores 2 a 1. El segundo conjunto de 2 sumadores completos sumaría los dos últimos bits suponiendo que es un 0 lógico. Y el conjunto final de sumadores completos asumiría que es un 1 lógico. ${\displaystyle C_{1}}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{1}}$

Los multiplexores luego controlan qué señal de salida se utiliza para COUT y . ${\displaystyle X_{2}}$ ${\displaystyle X_{3}}$

Notas

1. El sumador de acarreo-salto a menudo se abrevia como CSA, sin embargo, esto puede confundirse con el sumador de acarreo-guardado .

Referencias

1. Parhami, Behrooz (2000). Aritmética informática: algoritmos y diseños de hardware . Oxford University Press . pág. 108. ISBN. 0-19-512583-5.
2. VG Oklobdzija y ER Barnes, "Algunos esquemas óptimos para la implementación de ALU en tecnología VLSI", Actas del 7.º Simposio sobre aritmética informática ARITH-7, págs. 2-8. Reimpreso en Computer Arithmetic, EE Swartzlander (editor), vol. II, págs. 137-142, 1985.

Enlaces externos

• Explicación de la ruta crítica del sumador de salto de variable