Sumador con acarreo anticipado: más rápido que el acarreo en cascada

Resumen: El acarreo anticipado reescribe la recurrencia serial mediante señales de generate/propagate. Las versiones jerárquicas y de prefijo paralelo reducen la profundidad a costa de más celdas y cableado.

Un sumador de acarreo en cascada de 4 bits es sencillo: encadena cuatro sumadores completos y lleva cada $C_{out}$ al siguiente $C_{in}$. Su dependencia de acarreo en el peor caso crece con la anchura de palabra. Que ese camino cumpla la temporización depende de la tecnología, el reloj objetivo, el diseño de las celdas y la ruta de datos circundante; la anchura por sí sola no hace que un diseño sea «inaceptable».

Los sumadores con acarreo anticipado (CLA) atacan la dependencia serial derivando expresiones de acarreo a partir de señales intermedias disponibles directamente desde los operandos.

Qué hace lento al acarreo en cascada

Recuerda las ecuaciones del sumador completo:

$S_i = A_i \oplus B_i \oplus C_i$ $C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

La suma $S_i$ depende de $C_i$. El acarreo $C_{i+1}$ también depende de $C_i$. Por tanto, la cadena de dependencias es $C_0 \to C_1 \to C_2 \to \dots \to C_n$. Si una etapa de acarreo tarda $t_c$, el tiempo total de suma en el peor caso es aproximadamente:

$T_{ripple} \approx n \cdot t_c + t_{sum}$

La dependencia de primer orden es lineal respecto a la anchura de palabra. Los nanosegundos absolutos requieren una implementación especificada, así que los recuentos de retardos de puertas solo sirven aquí para comparar topologías. Este es el tipo de límite de retardo de propagación que motiva redes de acarreo más rápidas.

Generación y propagación

Mira de nuevo la ecuación del acarreo:

$C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

El primer término, $A_i B_i$, es verdadero exactamente cuando ambos bits de los operandos son 1; en ese caso, la etapa $i$ produce incondicionalmente un acarreo de salida, independientemente de lo que llegue a $C_i$. Define:

$G_i = A_i \cdot B_i$

Esta es la señal de generación: la etapa $i$ genera un acarreo por sí misma.

El segundo término, $(A_i \oplus B_i) C_i$, indica que, si exactamente uno de los bits de los operandos es 1, lo que llegue a $C_i$ se propaga directamente. Define:

$P_i = A_i \oplus B_i$

Esta es la señal de propagación: la etapa $i$ pasa cualquier acarreo entrante a su salida.

La ecuación del acarreo se reduce a:

$C_{i+1} = G_i + P_i \cdot C_i$

Estas son la puerta AND y la puerta OR que ya conoces, realizando exactamente el trabajo que describen sus tablas de verdad, pero ahora combinadas en una recurrencia que puedes aplanar.

Aplanar la recurrencia del acarreo

Sustituye la recurrencia en sí misma. Partiendo de un $C_0$ conocido:

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 C_1 = G_1 + P_1(G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 C_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

El patrón es claro. Cada acarreo $C_{i+1}$ es una suma de productos de las señales de generación y propagación de las etapas 0 a $i$. Lógicamente, cada expresión depende solo de $G$, $P$ y $C_0$, no de que se haya completado una transición física en el sumador completo anterior. Físicamente, los términos de producto anchos y su cableado aún requieren puertas, buffers y enrutamiento finitos.

Ejemplo resuelto de 4 bits

Suma $A=1011_2$ (11) y $B=0110_2$ (6), con $C_0=0$. Escribe primero los bits menos significativos:

Las ecuaciones del acarreo dan $C_1=0$, $C_2=1$, $C_3=1$ y $C_4=1$. Leer $C_4S_3S_2S_1S_0$ produce $10001_2=17$, como se esperaba. La aritmética coincide con la del acarreo en cascada; solo cambia la topología de la red de acarreo.

Generación y propagación de grupo

Para un grupo de bits de $i$ a $j$, define una propagación y una generación de grupo:

$P_{j:i}=P_jP_{j-1}\cdots P_i$

$G_{j:i}=G_j+P_jG_{j-1}+\cdots+P_jP_{j-1}\cdots P_{i+1}G_i$

Entonces, el acarreo que sale del grupo es:

$C_{j+1}=G_{j:i}+P_{j:i}C_i$

Dos grupos adyacentes pueden combinarse con la misma operación:

Esta asociatividad es la clave de los sumadores jerárquicos y de prefijo paralelo: se combinan pares, después pares de pares, formando un árbol en lugar de una cadena serial.

Arquitectura CLA de 4 bits

En el nivel booleano, un CLA plano de 4 bits tiene tres funciones:

1. Capa de generación/propagación. $n$ puertas AND producen $G_i = A_i B_i$ en un retardo; $n$ puertas XOR producen $P_i = A_i \oplus B_i$ en un retardo. Funcionan en paralelo.
2. Red de acarreo. La lógica AND-OR calcula $C_1$ a $C_4$ a partir de las fórmulas expandidas. Con puertas hipotéticas de fan-in ilimitado parece haber dos niveles lógicos; una biblioteca real descompone los términos anchos, así que la profundidad y la carga aumentan con la anchura.
3. Capa de suma. $n$ puertas XOR producen $S_i = P_i \oplus C_i$ en un retardo. (Observa que $S_i = A_i \oplus B_i \oplus C_i = P_i \oplus C_i$ una vez calculado $P_i$.)

Para cuatro bits, esto puede acortar el camino de acarreo respecto a una cadena de celdas de sumador completo. Extender indefinidamente las ecuaciones planas no es práctico, por eso los CLA más grandes introducen grupos.

Diagrama de bloques de un CLA de 4 bits

A0,B0 ─┬── XOR ── P0 ──┐                           ┌── XOR ── S0
       └── AND ── G0 ──┤                           │
                       │   ┌─── carry network ───┐ │
A1,B1 ─┬── XOR ── P1 ──┤   │                     │ ├── XOR ── S1
       └── AND ── G1 ──┤   │   computes          │ │
                       ├──>│   C1, C2, C3, C4    │─┤
A2,B2 ─┬── XOR ── P2 ──┤   │   desde las         │ ├── XOR ── S2
       └── AND ── G2 ──┤   │                     │ │
                       │   │   carry expressions  │ │
                       │   └─────────────────────┘ │
A3,B3 ─┬── XOR ── P3 ──┤                           ├── XOR ── S3
       └── AND ── G3 ──┘                           │
                                                   └────────── C4
C0 ──────────────────────>┘

Fan-in, cableado y coste oculto

Para $C_4$, la expresión plana más larga contiene un término de producto de cinco entradas cuando se incluye $C_0$. Para $C_{16}$, el término correspondiente tendría 17 entradas. Las bibliotecas de celdas estándar solo ofrecen un fan-in limitado, y los cables largos junto con las cargas grandes añaden retardo. Por eso un CLA plano literal deja de escalar bien aunque su expresión booleana parezca poco profunda.

La solución habitual es la jerarquía. Agrupa los bits —a menudo en bloques de cuatro—, calcula $G$ y $P$ del grupo y combina después esos grupos en otro nivel. Un diseño de 16 bits puede usar cuatro grupos de 4 bits más una segunda etapa de anticipación. Los sumadores de prefijo paralelo aplican la operación asociativa de grupos en todo un árbol.

El compromiso no queda reflejado en una única tabla universal de recuento de puertas:

El retardo, el área y la energía reales deben medirse después de la asignación y la implementación física. Una topología que gana en niveles de puertas abstractos puede perder cuando se incluyen la congestión, los buffers y la carga.

Más allá del CLA: sumadores de prefijo paralelo

La idea del acarreo anticipado se generaliza. La recurrencia $C_{i+1} = G_i + P_i C_i$ es asociativa bajo un operador personalizado: puedes emparejar posiciones adyacentes y después pares de pares en un árbol. Esta es la familia de prefijo paralelo:

• Kogge–Stone: poca profundidad de prefijo y fan-out lógico acotado, pero cableado denso y muchos nodos de prefijo.
• Brent–Kung: menos nodos de prefijo y menos cableado, con mayor profundidad.
• Han-Carlson, Ladner-Fischer y Sklansky: distintos compromisos entre fan-out, complejidad de cableado y profundidad.

Los sumadores de producción también pueden mezclar estructuras de prefijo, usar dispersión o colocar lógica de selección de acarreo alrededor de grupos concretos. La elección se hace frente a un presupuesto específico de temporización, área, potencia y enrutamiento; la frecuencia de reloj de un procesador por sí sola no revela la topología de su sumador.

Implementación de un CLA en DigiSim

Puedes construir un CLA de 4 bits a partir de primitivas: cuatro puertas AND para generación, cuatro puertas XOR para propagación, las ecuaciones de acarreo anteriores y cuatro puertas XOR finales para la suma. Los componentes de nivel superior sumador y sumador de 8 bits son comodidades de comportamiento; no deduzcas su arquitectura interna salvo que la documentación del componente la especifique.

Para comparar la topología, encadena cuatro sumadores completos como acarreo en cascada y construye un CLA de 4 bits separado. Primero verifica la equivalencia funcional para todas las combinaciones de operandos. Después, si el simulador modela el retardo por puerta, compara el último tiempo de estabilización tras un cambio de entrada. Si sus puertas son ideales, cuenta en su lugar los niveles lógicos dependientes; una forma de onda ideal no puede predecir la temporización del silicio.

Errores habituales

• Olvidar que $P_i$ usa XOR, no OR. Cualquiera de las dos definiciones —$P_i = A_i + B_i$ o $P_i = A_i \oplus B_i$— produce un acarreo correcto, porque el caso $A_i = B_i = 1$ ya está cubierto por $G_i$. Se prefiere XOR porque el mismo cable alimenta la etapa de suma: $S_i = P_i \oplus C_i$. Con un $P_i$ definido mediante OR, esa reutilización deja de funcionar y necesitas una XOR separada para la suma.
• Subestimar el escalado del fan-in. Una expansión plana de 16 bits contiene un término de 17 literales cuando se incluye $C_0$. Los diseños anchos prácticos descomponen o agrupan la lógica.
• Suponer que CLA siempre es más rápido. Para anchuras pequeñas, una implementación en cascada puede ganar en área y cumplir holgadamente la temporización. No existe una anchura de cruce independiente de la arquitectura.
• Confundir los caminos críticos de suma y acarreo. La profundidad de la red de acarreo domina el retardo total, pero la XOR final de suma añade un retardo de puerta más. Especificar el retardo como «profundidad de la red de acarreo» es un error habitual.

Qué sigue

Continúa con Cómo funciona una ALU: unidad aritmético-lógica a partir de puertas, y después con Multiplicador Booth explicado para conocer otra optimización aritmética.

Para comparar de forma práctica las dos arquitecturas de sumador, abre la plantilla de sumador completo con acarreo, encadena cuatro instancias como sumador de acarreo en cascada y observa la propagación bit a bit en el analizador lógico. Después construye el CLA equivalente de 4 bits a partir de las ecuaciones de esta publicación y mide ambos circuitos: esa diferencia es precisamente la razón de existir de las ALU de alta velocidad.