Anteriormente vimos la teoría detrás de un sumador Carry Look-Ahead y cómo se construía uno de 4 bits de ancho. También analizamos por qué no era conveniente diseñar uno de mayor cantidad de bits (problemas de fan-in y fan-out). Sin embargo, es posible construir sumadores de más cantidad de bits a partir de varios módulos CLAA conectados entre sí. En este artículo se analizan diferentes alternativas.

¿Por qué se pone tanto énfasis en acelerar el cómputo de la suma en el diseño de un procesador? Porque es la operación básica que implementa todo microprocesador. En cada ciclo un procesador computa varias sumas por cada instrucción en el pipeline: al actualizar el PC (program counter); al calcular direcciones efectivas en accesos a memoria; cuando se modifica el PC en saltos absolutos y relativos; y para calcular operaciones aritméticas de suma precisamente (sumar valores en registros).

Un módulo CLAA (Carry Look-Ahead Adder) de 4 bits tiene 9 entradas y 7 salidas:

Las entradas son:

  • Dos operandos de 4 bits: xi-j e yi-j
  • Un carry de entrada: ci

A su vez, las salidas son:

  • La suma de 4 bits: si-j
  • Un carry de salida: cj
  • Los bits de generación y propagación de carry para el bloque/grupo: Gi-j y Pi-j respectivamente

Donde j = i + 3.

La implementación interna de este sumador es bastante compleja y se divide en 3 partes:

  • Cómputo de bits de generación y propagación a nivel bit y bloque: gi, pi, Gi,j y Pi,j
  • Cómputo de carrys internos: ci, pi (a partir de los gi y pi)
  • Cómputo de los bits de suma con full-adders (FA): si

El carry de salida (cj+1) se obtiene del último FA.

El diseño del circuito requiere que se implementen las siguientes ecuaciones para adelantar los carrys c1, c2 y c3:

Donde gi y pi son los valores de generación y propagación de carry respectivamente:

Y a nivel bloque (con j = i + 3):

Antes de comenzar el diseño del CLAA de 4 bits en Logisim es conveniente desarrollar el circuito que calcule los gi y pi para cada posición. La siguiente captura muestra el diseño de dicho circuito al que he llamado CLAA-1.circ:

El siguiente diagrama demuestra el diseño del circuito en Logisim empleando el circuito CLAA-1 junto con el full-adder desarrollado anteriormente (FA.circ):

Se observa que el cómputo del carry de entrada a cada full-adder atraviesa 3 niveles de compuerta (1 para calcular los bits gi y pi, y dos más para computar el carry a partir de c0).

El cálculo de c3 demuestra cómo, a medida que se avanzan posiciones, se va complicando el (layout) diseño en términos de fan-in y fan-out (compuertas cada vez más grandes y salidas conectadas a cada vez más cantidad de entradas).

A nivel MSI entonces, la idea es que en un chip es viable construir CLAA de pocos bits (típicamente 4). Por ende, para diseñar sumadores más grandes hay dos posibilidades: configurar varios CLAA en ripple o instanciar los Pi,j y Gi,j en varios niveles.

La primera solución implica lookahead interno a nivel CLAA, pero una vez más ripple de carry entre sumadores. Nuevamente aparece la idea de ripple del carry, no a nivel de FA pero sí a nivel de pequeños sumadores paralelos. Se observa en la siguiente figura el esquema de un sumador paralelo de 16 bits empleando 4 CLAA en configuración ripple (CLAA-ripple-16.circ):

Cada display de 7 segmentos visualiza 1 dígito en base hexadecimal. Respecto al tiempo de operación de este circuito, cada uno de los CLAA no puede computar el valor estable de su suma hasta tanto no disponga del carry de salida del bloque anterior. Notar que no se hace uso de las salidas de generación y propagación a nivel bloque de cada uno de los CLAA.

La solución alternativa plantea hacer uso de los Pi,j y Gi,j para computar cada carry de entrada a los CLAA por adelantado. Se requiere de lógica adicional para calcular los carrys en base a generación y propagación a nivel bloques, la cual será provista por un nuevo circuito denominado CLAG (Carry Look-Ahead Generator):

El generador de carrys toma 4 valores de G y P, junto con un carry de entrada, y retorna 3 carrys de salida, junto con los G y P para todo el grupo:

La lógica es exactamente igual a la interna del CLAA. Se trata de lookahead de carry basado en generación y propagación de posiciones anteriores, junto con el carry inicial. A pesar de contar con los operandos necesarios, no retorna un cuarto carry por cuestiones de layout, sino que retorna en su lugar los G y P para todo el siguiente nivel de abstracción:

La siguiente figura demuestra el diseño del CLAG en Logisim (CLAG.circ):

Haciendo uso del CLAG es posible entonces adelantar el cálculo de los carrys c4, c8 y c12 en lugar de usar ripple de carry, tal como lo hacía el sumador de 16 bits demostrado anteriormente:

Esta configuración se denomina de "dos niveles" pues está conformada por dos niveles de lookahead: el primero interno a cada CLAA y el segundo en nivel superior calculado por el generador (CLAG). Agregando más niveles de CLAG es posible crear sumadores más grandes, por ejemplo de 32 bit en tres niveles (donde un CLAG de tercer nivel adelantaría c16 en base al carry inicial c0 y G0,15, P0,15 entregados por el CLAG de segundo nivel).

A nivel VLSI este esquema tampoco resulta eficiente por cuestiones de layout, tal como se puede comprobar en el diagrama del circuito. Hay que favorecer estructuras regulares y comunicaciones cortas. Ninguna de las dos premisas se cumplen en los diagramas vistos para CLAA y CLAG.

Un esquema de lookahead de n bits que sí tiene los atributos necesarios para implementar a gran escala (estructuras regulares y comunicaciones cortas) emplea una profundidad logarítmica en n. Consta de dos partes, una para la generación de los G y P y otra para (a partir de estos) generar los distintos carrys de entrada a los full-adders.

Generados los gi y pi (módulo 1) con el circuito CLAA-1.circ (el mismo que se utilizó en la construcción del CLAA anteriormente), la primera parte de este esquema los agrupa en bloques adyacentes de manera logarítmica empleando un nuevo circuito CLAA-2.circ (módulo 2):

Este módulo toma dos valores de generación y propagación (correspondientes a bloques adyacentes) y obtiene G y P para ambos bloques:

La otra parte del circuito calcula los ci en base a generación y propagación con el siguiente módulo (3):

Este circuito (CLAA-3.circ) implementa la siguiente expresión:

El siguiente diagrama demuestra la implementación de lookahead logarítmica empleando estos tres módulos para 4 bits:

Se aprecia una estructura mucho más regular, con menor cantidad y longitud en las comunicaciones, en comparación a los diagramas de circuito de CLAA y CLAG vistos.

En la parte derecha del diagrama se produce la generación de los G y P en un árbol logarítmico. A la izquierda se computan los carrys de entrada en base a estos y se pasan como entrada a los FA. Este sumador está construido de sólo 4 bits a modo de ejemplo, sin embargo (y a diferencia de los CLAA y CLAG) puede ser expandido a cualquier cantidad de bits de longitud.

Referencias

Compartí este artículo