Sumador de acarreo y salto

Circuito lógico aritmético

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

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

Sumador de salto de acarreo único

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

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

Para cada par de bits de entrada de operando, las condiciones de propagación se determinan utilizando una puerta XOR. Cuando todas las condiciones de propagación son verdaderas , el bit de acarreo determina el bit de acarreo. ${\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 puerta AND de n entradas y un multiplexor. Cada bit de propagación , proporcionado por la cadena de ondulación de transporte, está conectado a la puerta 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 el acarreo a la señal de acarreo . ${\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 "saltar" bloques con una señal de propagación de grupo configurada en 1 lógico (a diferencia de una larga cadena de acarreo ondulado, que requeriría el acarreo se propagará a través de cada bit en el sumador). El número de entradas de la puerta AND es igual al ancho del sumador. En el caso de una anchura grande, esto resulta poco práctico y provoca retrasos adicionales, ya que la puerta AND debe construirse en forma de árbol. Se logra un buen ancho cuando la lógica de suma tiene la misma profundidad que la puerta AND de n entradas y el multiplexor.

Sumador de acarreo y salto de 4 bits.

Actuación

La ruta crítica de un sumador con salto de acarreo comienza en el primer sumador completo, pasa por todos los sumadores y termina en el bit de suma . Los sumadores de acarreo y salto están encadenados (ver sumadores de acarreo y salto en bloque) para reducir la ruta crítica general, ya que un sumador de acarreo y salto de un solo bit no tiene un beneficio de velocidad real en comparación con un sumador de acarreo de ondulación de un bit. ${\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 tempranamente, la ruta crítica para la lógica de salto en un sumador de salto de acarreo consiste únicamente en el retraso impuesto por el multiplexor (salto condicional).

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

Bloquear sumadores de acarreo y salto

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

Los sumadores de bloqueo de acarreo y salto se componen de varios sumadores de acarreo y salto. Hay dos tipos de sumadores de bloqueo, 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 los sumadores de bloqueo, acarreo y salto?
• ¿El tamaño del bloque debe ser constante o variable?
• Ancho de bloque fijo versus ancho de bloque variable

Sumadores de bloqueo, acarreo y omisión de tamaño fijo

Los sumadores de salto de bloque de tamaño fijo dividen los bits de 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 están encerradas entre el primer y el último bloque y, finalmente, 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 obtiene 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 bloqueo, acarreo y omisión de tamaño variable

El rendimiento se puede mejorar, es decir, todos los acarreos se propagan más rápidamente variando los tamaños de bloque. En consecuencia, los bloques iniciales del sumador se hacen más pequeños para detectar rápidamente las generaciones de acarreo que deben propagarse a medida que avanzan, 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 pueden procesar rápidamente.

Sumadores de acarreo y salto multinivel

Al utilizar bloques de salto adicionales en una capa adicional, las señales de propagación de bloques se resumen 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 salto de transporte

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

Thomas W. Lynch resolvió el problema de optimización de salto de acarreo para tamaños de bloques variables y niveles múltiples para un nodo de proceso de dispositivo arbitrario. ^[2] Esta referencia también muestra que la suma con salto de acarreo es lo mismo que la suma de prefijos paralelos y, por lo tanto, está relacionada con el Han-Carlson, y para algunas configuraciones es idéntica a él, ^{[3] [4]} el Brent-Kung , ^[5] el sumador Kogge-Stone ^[6] y varios otros tipos de sumadores.

Descripción general de la implementación

Desglosando esto en términos más específicos, para construir un sumador de derivación de acarreo 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 entrada ( CIN ). La salida sería un bus X de 4 bits y una señal de acarreo ( COUT ).

Los dos primeros sumadores completos sumarían los dos primeros bits. La señal de transferencia del segundo sumador completo ( ) impulsarí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 supondría que es un 1 lógico. ${\displaystyle C_{1}}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{1}}$

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

Notas

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

Referencias

1. Parhami, Behrooz (2000). Aritmética informática: algoritmos y diseños de hardware . Prensa de la Universidad de Oxford . pag. 108.ISBN​ 0-19-512583-5.
2. Lynch, Thomas Walker (mayo de 1996). "Sumadores binarios" (Tesis). Universidad de Texas . Archivado (PDF) desde el original el 14 de abril de 2018 . Consultado el 14 de abril de 2018 .
3. Han, Tackdon; Carlson, David A.; Levitan, Steven P. (octubre de 1982). "Diseño VLSI de circuitos de adición de área baja y alta velocidad". Actas de la Conferencia internacional IEEE de 1981 sobre diseño de computadoras: VLSI en computadoras y procesadores . IEEE : 418–422. ISBN 0-81860802-1.
4. Han, Tackdon; Carlson, David A. (octubre de 1987). "Sumadores VLSI rápidos y eficientes en área". Actas del 8º Simposio sobre aritmética informática . IEEE : 49–56.
5. Brent, Richard Peirce ; Kung, Hsiang Te (marzo de 1982). "Un diseño normal para sumadores paralelos" (PDF) . Transacciones IEEE en computadoras . C-31 (3): 260–264. doi :10.1109/TC.1982.1675982. S2CID  17348212. Archivado desde el original el 24 de septiembre de 2017.
6. Kogge, Peter Michael ; Stone, Harold S. (agosto de 1973). "Un algoritmo paralelo para la solución eficiente de una clase general de ecuaciones de recurrencia". Transacciones IEEE en computadoras . C-22 (8): 786–793. doi :10.1109/TC.1973.5009159. S2CID  206619926.

enlaces externos

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