Ruta crítica para el sumador Carry-Skip

7

¿Alguien puede explicar por qué el sumador de Carry-Skip tiene la misma ruta crítica que el sumador de Carry-Ripple normal? Mi libro de texto dice que la ruta crítica se produce cuando el acarreo se genera en LSB y luego se propaga a través del resto del sumador. De la manera que lo veo, la ruta crítica ocurre cuando cada etapa tiene que generar o eliminar el acarreo, por lo tanto, cada etapa siguiente tiene que esperar la onda de la etapa anterior para obtener las sumas. Todos los sitios dicen que mi libro de texto es correcto, pero ninguno de ellos explica por qué. Agradecería cualquier ayuda.

Por cierto, el sumador Carry-Skip es el mismo que el sumador Carry-Lookahead, pero no calcula la señal de generación de grupo.

    
pregunta Alex

3 respuestas

9

El caso más desfavorable para un sumador de acarreo de ondulación (RCA) es cuando el LSB genera un arrastre y el arrastre ondula a través de todo el sumador desde el bit 0 al bit ( N - 1) . Un patrón de ejemplo sería 00000001 + 11111111. En la terminología del sumador, los bits 7-1 son "Propagadores" y el bit 0 es un "Generador". La ruta crítica es desde la entrega de la LSB hasta la entrega de la MSB, y cada sumador está en la ruta crítica.

La idea detrás de un sumador Carry-Skip (CSA) es reducir la longitud de esta ruta crítica al darle a la ruta de acceso un atajo si todos los bits de un bloque propagarían un acarreo. Una señal de propagación de todo el bloque es bastante fácil de calcular, y cada bloque puede calcular su propia señal de propagación simultáneamente. Así que el peor de los casos sigue siendo el mismo escenario, pero lo que sucede se ve un poco diferente.

Digamos que todavía tenemos el mismo problema de 0000 ...... 001 + 0111 ..... 111. El primer bloque calculará un acarreo en el primer bit y propagará los bits de arrastre 1, 2 y 3. En este punto, la primera señal de traspaso de bloque es válida. Las señales de selección de propagación ya son válidas, ya que son retrasos de 2-3 puertas y la señal de acarreo son retardos de 4 puertas. El multiplexor de acarreo para los bits 8-11 obtiene la señal de acarreo del bit 3, ya que los bits 4 a 7 propagan un acarreo. Tenga en cuenta que esto toma 1 retraso de puerta, mientras que un RCA normal tomaría 4 retrasos de puerta. Cada bloque agregará 1 retardo de puerta a la señal de acarreo.

Si el MSB mató a la propagación de acarreo, entonces eso causaría que el último bloque CSA se ondulara al acarrear la entrada, lo que tomaría otros 4 retrasos de puerta. Esta configuración de un generador de LSB y una eliminación de MSB es el nuevo peor caso. La fuente de la ruta crítica es la misma entre RCA y CSA, pero la ruta crítica es diferente.

Si un bloque arbitrario genera un acarreo por sí mismo, el acarreo siempre se propagará al siguiente bloque. Sin embargo, si el segundo bloque genera un acarreo en sí mismo, o mata el acarreo, ese es el final de la ruta crítica. Si el segundo bloque propaga el acarreo, entonces vemos la ventaja de la arquitectura CSA.

Además, cuando se usa el término "ruta crítica", generalmente implica que está considerando un conjunto de entradas que causarán el retraso del peor de los casos. Los escenarios que está proporcionando proporcionan casos "feos" que pueden tener un gran retraso, pero no es el mayor retraso .

    
respondido por el W5VO
1

Déjame responderla de esta manera.

Digamos que tiene 3 etapas en este sumador de by-pass. Y cada etapa tiene 4 bits.

Si hay algún bit que genere o elimine el acarreo, no necesitará el acarreo desde la primera etapa. En este caso, no tendría que esperar el resultado del acarreo de la etapa anterior. Por lo tanto, el caso más desfavorable ocurre cuando debe esperar la primera etapa de transporte.

Y déjame ponerlo de otra manera. La peor demora de caso = tiempo de configuración + todo el tiempo de transporte en la 1ª etapa + 2 * tiempo de bypass + (4-1) * tiempo de transporte para cada bit

El acarreo desde la entrada se propaga desde el primer bit hasta el último bit en la primera etapa. Al mismo tiempo, la segunda etapa es si esperar el acarreo desde la primera etapa o comenzar a generar o eliminar su propio acarreo. Y el peor caso estaría esperando. Entonces, el peor caso es que la segunda etapa decide propagar el acarreo de la primera etapa.

Espero que esto responda a tus dudas.

    
respondido por el zhiyangyang
1

En un sumador típico de ondulación que combina, por ejemplo, X [3..0] + Y [3..0] + Cin para obtener Z [3..0] y Cout, las señales X [0], Y [0] y Cin son todas equivalentes; Todos tendrán el mismo retraso que Cout. Si se encadenan múltiples etapas de sumador, el tiempo total de propagación de acarreo será el tiempo desde la X [0] e Y [0] de la primera etapa hasta su Cout, más los tiempos desde el Cin hasta el Cout de las etapas subsiguientes. Si uno encadena por ej. Ocho secciones idénticas de 4 bits, el tiempo de X [0] o Y [0] a Cout importará solo 1/7 tanto como el tiempo de Cin a Cout.

Esencialmente, lo que sucede es que si todas las entradas llegan simultáneamente, un sumador de acarreo de ondulación tendría tres rutas críticas equivalentes desde X [0], Y [0] y Cin hasta la salida de acarreo. Si la entrada de acarreo no se estabiliza hasta mucho después de que todas las otras entradas lo hayan hecho, entonces con cualquier sumador combinatorio sería la ruta crítica (nada más podría ser la ruta crítica, ya que todo estaría esperando en la entrada de acarreo). Un sumador de carry-skip busca minimizar el tiempo entre la estabilización de la entrada de acarreo y la estabilización de su salida, asumiendo que todas las demás entradas han sido estables por un tiempo , pero si todas las entradas se estabilizan simultáneamente, la crítica las rutas de X [0] e Y [0] a la salida de acarreo seguirán siendo las mismas.

Por cierto, un sumador basado en agregadores de arrastre y salto en cascada puede proporcionar el tiempo de propagación O (sqrt (N)) con circuitos O (N) al tener las etapas de orden superior más largas que las de orden más corto. Si una etapa de arrastre y omisión de N bits tiene un tiempo de propagación de 2 N + 2 retardos de compuerta de sus entradas X e Y, y 2 demoras de su entrada de acarreo, y una etapa de arrastre de onda de N bits tiene un tiempo de demora de 2 N desde cualquier entrada, entonces si se construye un sumador de 32 bits desde una etapa de acarreo de rizado de 4 bits, y etapas de arrastre y omisión de 4, 5, 6, 7 y 8 bits, el acarreo de la primera etapa estabilizará 8 retrasos después de X e Y. La segunda etapa estabilizará 10 retrasos después de X e Y, o 2 ciclos después de su entrada de acarreo, lo que ocurra último (ambos sucederán juntos). La tercera etapa estabilizará 12 ciclos después de X e Y, o 2 ciclos después de su entrada de acarreo, etc. Esta no es la forma más rápida de hacer una adición, pero es un buen compromiso entre la velocidad y los circuitos. Es posible reducir el tiempo de propagación a O (lgN), pero hacerlo requiere O (circuitos NlgN).

    
respondido por el supercat

Lea otras preguntas en las etiquetas