Ruta crítica del sumador Carry-Skip

Question

¿Puede alguien explicar por qué el sumador Carry-Skip tiene la misma ruta crítica que el sumador Carry-Ripple normal? Mi libro de texto dice que el camino crítico se produce cuando el acarreo se genera en el LSB y luego se propaga a través del resto del sumador. Tal y como yo lo veo, el camino crítico se produce cuando cada etapa tiene que generar o matar el acarreo, por lo que cada etapa siguiente tiene que esperar al rizado 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 lo mismo que el sumador Carry-Lookahead, pero no calcula la señal de generación de grupo.

Answer 1

El peor escenario para un sumador de acarreo ondulado (RCA) es cuando el LSB genera un acarreo, y el acarreo ondula a través de todo el sumador desde el bit 0 hasta el bit ( N - 1). Un ejemplo de patrón sería 00000001 + 11111111. En la terminología del sumador, los bits 7-1 son "Propagadores", y el bit 0 es un "Generador". El camino crítico es desde el acarreo del LSB hasta el acarreo del MSB, y cada sumador está en el camino crítico.

La idea de un sumador Carry-Skip (CSA) es reducir la longitud de esta ruta crítica dando a la ruta de acarreo un atajo si todos los bits de un bloque propagan un acarreo. Una señal de propagación en 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 caso sigue siendo el mismo escenario, pero lo que ocurre es un poco diferente.

Digamos que seguimos teniendo el mismo problema de 0000......001 + 0111.....111. El primer bloque calculará un carry en el primer bit, y propagará el carry a través de los bits 1, 2 y 3. En este punto, la señal de carry-out del primer bloque es válida. Las señales de selección de propagación ya son válidas, ya que tiene 2-3 retardos de puerta y la señal de carry tiene 4 retardos de puerta. El multiplexor de acarreo para los bits 8-11 obtiene la señal de acarreo del acarreo del bit 3, ya que los bits 4-7 propagarían un acarreo. Obsérvese que esto requiere 1 retardo de puerta, mientras que un RCA normal requeriría 4 retardo de puerta. Cada bloque añadirá 1 retardo de puerta a la señal de acarreo.

Si el MSB matara la propagación del acarreo, entonces eso causaría que el último bloque CSA ondulara la entrada, lo que llevaría otros 4 retrasos de compuerta. Esta configuración de una generación LSB y una eliminación MSB es el nuevo peor caso. El origen de la ruta crítica es el mismo entre el RCA y el CSA, pero la ruta crítica es diferente.

Si un bloque arbitrario genera un carry por sí mismo, el carry siempre se propagará al siguiente bloque. Sin embargo, si el segundo bloque genera un acarreo por sí mismo, o mata el acarreo, entonces 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 utiliza el término "camino crítico", generalmente implica que se está considerando un conjunto de entradas que causarán el peor retraso. Los escenarios que usted proporciona dan casos "feos" que pueden tener un gran retraso, pero no es el más grande retraso.

Answer 2

Permítanme responder de esta manera.

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

Si hay algún bit que genere o borre el carry, no necesitará el carry de la 1ª etapa. En este caso, no necesitaría esperar el resultado del carry de la etapa anterior. Por lo tanto, el peor caso ocurre cuando debe esperar el carry de la 1ª etapa.

Y permítanme decirlo de otra manera. El peor caso de retardo = tiempo de preparación + todo el tiempo de transporte en la primera etapa + 2* tiempo de paso + (4-1)*tiempo de transporte para cada bit

El acarreo de la entrada en se propaga desde el primer bit hasta el último en la primera etapa. Al mismo tiempo, la segunda etapa está esperando el carry de la 1ª etapa o empieza a generar o borrar su propio carry. Y el peor caso sería la espera. Por lo tanto, el peor caso es que la segunda etapa decida propagar el acarreo de la 1ª etapa.

Espero que esto responda a sus dudas.

Answer 3

En un sumador de acarreo típico 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 equivalentes; todas tendrán el mismo retardo hasta Cout. Si se encadenan varias etapas del sumador, el tiempo total de propagación del acarreo será el tiempo desde X[0] e Y[0] de la primera etapa hasta su Cout, más los tiempos desde Cin de las etapas posteriores hasta su Cout. Si se encadenan, por ejemplo, ocho secciones idénticas de 4 bits, el tiempo de X[0] o Y[0] a Cout sólo importará 1/7 del tiempo de Cin a Cout.

Esencialmente, lo que ocurre es que si todas las entradas llegan simultáneamente, un sumador de acarreo ondulado tendría tres caminos críticos 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 demás entradas lo hayan hecho, entonces con cualquier sumador combinatorio sería el camino crítico (nada más podría ser camino crítico, ya que todo estaría esperando a la entrada de acarreo). Un sumador carry-skip busca minimizar el tiempo entre el momento en que se estabiliza la entrada carry y el momento en que se estabiliza su salida, asumiendo que todas las demás entradas han sido estables durante un tiempo pero si todas las entradas se vuelven estables simultáneamente, los caminos críticos desde X[0] e Y[0] hasta la salida de acarreo seguirán siendo los mismos.

Por cierto, un sumador basado en sumadores de salto de arrastre en cascada puede proporcionar un tiempo de propagación O(sqrt(N)) con circuitos O(N) haciendo que las etapas de orden superior sean más largas que las de orden inferior. Si una etapa de carry-skip de N bits tiene un tiempo de propagación de 2N+2 retardos de puerta desde sus entradas X e Y, y 2 retardos desde su entrada de carry, y una etapa de ripple-carry de N bits tiene un tiempo de 2N retardos desde cualquier entrada, entonces si uno construye un sumador de 32 bits a partir de una etapa de ripple carry de 4 bits, y etapas de carry-skip de 4, 5, 6, 7 y 8 bits, el carry de la primera etapa estabilizará 8 retardos después de X e Y. La segunda etapa se estabilizará 10 retardos después de X e Y, o 2 ciclos después de su entrada de acarreo, lo que ocurra último (ambos ocurrirán juntos). La tercera etapa se 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 suma, pero es un buen compromiso entre velocidad y circuito. Es posible reducir el tiempo de propagación a O(lgN), pero hacerlo requiere O(NlgN circuitos).