decodificador con direccionamiento por suma

En el diseño de CPU , el uso de un decodificador de suma de direcciones (SAD) o de memoria de suma de direcciones (SAM) es un método para reducir la latencia del acceso a la caché de la CPU y el cálculo de direcciones (base + desplazamiento). Esto se logra fusionando la operación de suma de generación de direcciones con la operación de decodificación en la SRAM de caché .

La caché de datos L1 debería ubicarse en el recurso de CPU más crítico, ya que pocas cosas mejoran el número de instrucciones por ciclo (IPC) tan directamente como una caché de datos más grande. Además, el acceso a una caché de datos más grande requiere más tiempo, y la segmentación de la caché de datos empeora el IPC. Una forma de reducir la latencia de acceso a la caché de datos L1 es fusionar la operación de suma de generación de direcciones con la operación de decodificación en la SRAM de caché.

Aún debe realizarse la operación de suma para la generación de direcciones, ya que otras unidades en la tubería de memoria utilizarán la dirección virtual resultante. Dicha suma se realizará en paralelo con la operación de suma/decodificación combinada descrita aquí.

La recurrencia más rentable para acelerar es una carga, seguida del uso de esa carga en una cadena de operaciones con enteros que conducen a otra carga. Suponiendo que los resultados de la carga se omiten con la misma prioridad que los resultados de los enteros, entonces es posible resumir esta recurrencia como una carga seguida de otra carga, como si el programa estuviera siguiendo una lista enlazada .

El resto de esta página asume una arquitectura de conjunto de instrucciones (ISA) con un único modo de direccionamiento (registro + desplazamiento), una caché de datos indexada virtualmente y cargas de extensión de signo que pueden ser de ancho variable. La mayoría de las ISA RISC se ajustan a esta descripción. En ISA como la Intel x86 , se suman tres o cuatro entradas para generar la dirección virtual. Las sumas de múltiples entradas se pueden reducir a una suma de dos entradas con sumadores de acarreo guardado, y el problema restante es el que se describe a continuación. La recurrencia crítica, entonces, es un sumador , un decodificador , la línea de palabra SRAM, la(s) línea(s) de bit SRAM, el(los) amplificador(es) de sentido, los multiplexores de dirección de bytes y los multiplexores de derivación.

Para este ejemplo, se asume una caché de datos de 16 KB con mapeo directo que devuelve valores alineados de doble palabra (8 bytes). Cada línea de la SRAM tiene 8 bytes y hay 2048 líneas, direccionadas por Addr[13:3]. La idea de la SRAM con direccionamiento por suma se aplica igualmente bien a las cachés asociativas por conjuntos. 

El decodificador SRAM de este ejemplo tiene una entrada de 11 bits, Addr[13:3], y 2048 salidas, las líneas de palabra decodificadas. Una línea de palabra se activa en respuesta a cada valor único de Addr[13:3].

En la forma más simple de decodificador, cada una de las 2048 líneas es lógicamente una puerta AND . Los 11 bits (llamémoslos A[13:3] y sus inversos (llamémoslos B[13:3]) se envían al decodificador. Para cada línea, 11 bits o sus inversos se introducen en una puerta AND de 11 entradas. Por ejemplo, 1026 en decimal es igual a 10000000010 en binario. La función para la línea 1026 sería:

wordline[1026] = A[13] & B[12] & B[11] & B[10] & B[9] & B[8] & B[7] & B[6] & B[5] & A[4] & B[3]

Tanto la cadena de acarreo del sumador como la del decodificador combinan información de todo el ancho de la porción del índice de la dirección. Combinar la información de todo el ancho dos veces es redundante. Una SRAM con direccionamiento por suma combina la información solo una vez al implementar el sumador y el decodificador juntos en una sola estructura.

Recordemos que la SRAM se indexa con el resultado de una suma. Denominemos a los sumandos R (de registro) y O (de desplazamiento a ese registro). El decodificador direccionado por suma decodificará R+O. Para cada línea del decodificador, denominemos a la línea L.

Supongamos que nuestro decodificador impulsa tanto R como O a través de cada línea del decodificador, y que cada línea del decodificador implementa:

línea de palabras[L] = (R+O)==L

(R+O)==L <=> R+OL==0 <=> R+O+~L+1==0 <=> R+O+~L==-1==11..1.

Se puede usar un conjunto de sumadores completos para reducir R+O+~L a S+C (esta es una suma sin acarreo). S+C==11..1 <=> S==~C. No habrá acarreos en la suma final. Nótese que, dado que C es una fila de acarreos, se desplaza un bit hacia arriba, de modo que R[13:3]+O[13:3]+~L[13:3] == {0,S[13:3]} + {C[14:4],0}

Con esta formulación, cada fila del decodificador consta de un conjunto de sumadores completos que reducen el registro base, el desplazamiento y el número de fila a un formato con acarreo guardado, además de un comparador . Más adelante se demostrará que la mayor parte de este hardware es redundante, pero por ahora es más sencillo considerar que todo se encuentra en cada fila.

La formulación anterior verifica el resultado completo de una suma. Sin embargo, en un decodificador de caché de CPU, el resultado completo de la suma es una dirección de byte, y la caché generalmente se indexa con una dirección mayor; en nuestro ejemplo, la de un bloque de 8 bytes. Es preferible ignorar algunos de los bits menos significativos (LSB) de la dirección. Sin embargo, los LSB de los dos sumandos no se pueden ignorar, ya que podrían producir un acarreo que modificaría la dirección de la palabra doble.

Si se suman R[13:3] y O[13:3] para obtener un índice I[13:3], entonces la dirección real Addr[13:3] es igual a I[13:3] o a I[13:3] + 1, dependiendo de si R[2:0]+O[2:0] genera un acarreo. Tanto I como I+1 pueden obtenerse si hay dos bancos de SRAM, uno con direcciones pares y otro con direcciones impares. El banco par contiene las direcciones 000xxx, 010xxx, 100xxx, 110xxx, etc., y el banco impar contiene las direcciones 001xxx, 011xxx, 101xxx, 111xxx, etc. El acarreo de R[2:0]+O[2:0] puede usarse para seleccionar la palabra doble par o impar que se obtendrá posteriormente.

Tenga en cuenta que la lectura de dos bancos de SRAM de tamaño reducido disipará más energía que la lectura de un banco de tamaño completo, ya que provoca una mayor conmutación en los amplificadores de detección y en la lógica de direccionamiento de datos.

En referencia al diagrama adjunto, el banco par obtendrá la línea 110 cuando I[13:3]==101 o I[13:3]==110. El banco impar obtendrá la línea 101 cuando I[13:3]==100 o I[13:3]==101.

En general, el banco SRAM impar debería obtener la línea Lo==2N+1 cuando I[13:3]==2N o I[13:3]==2N+1. Las dos condiciones se pueden escribir como:

I[13:3] = Lo-1 => R[13:3] + O[13:3] + ~Lo+1 = 11..11 => R[13:3] + O[13:3] + ~Lo = 11..10 I[13:3] = Lo => R[13:3] + O[13:3] + ~Lo = 11..11

Ignora el último dígito de la comparación: (S+C)[13:4]==11..1

De manera similar, el banco SRAM par obtiene la línea Le==2N cuando I[13:3]==2N o I[13:3]==2N-1. Las condiciones se escriben como sigue, y una vez más se ignora el último dígito de la comparación.

I[13:3] = Le-1 => R[13:3] + O[13:3] + ~Le = 11..10 I[13:3] = Le => R[13:3] + O[13:3] + ~Le = 11..11

 R 13 ... R 6 R 5 R 4 R 3 O 13 ... O 6 O 5 O 4 O 3 L 13 ... L 6 L 5 L 4 L 3 -------------------------- S 13 ... S 6 S 5 S 4 S 3 C 14 C 13 ... C 6 C 5 C 4

Antes de eliminar la redundancia entre filas, revise:

Cada fila de cada decodificador para cada uno de los dos bancos implementa un conjunto de sumadores completos que reducen los tres números a sumar (R[13:3], O[13:3] y L) a dos números (S[14:4] y C[13:3]). El bit menos significativo (==S[3]) se descarta. El acarreo de salida (==C[14]) también se descarta. La fila coincide si S[13:4] == ~C[13:4], que es &( xor(S[13:4], C[13:4])).

Es posible especializar parcialmente los sumadores completos a operaciones AND, OR, XOR y XNOR de dos entradas, ya que la entrada L es constante. Las expresiones resultantes son comunes a todas las líneas del decodificador y se pueden recopilar al final.

S 0;i  = S(R i , O i , 0) = R i xor O i S 1;i  = S(R i , O i , 1) = R i xnor O i C 0;i+1 = C(R i , O i , 0) = R i y O i C 1;i+1 = C(R i , O i , 1) = R i o O i .

En cada posición de dígito, solo hay dos posibles S _i , dos posibles C _i , y cuatro posibles XOR entre ellos:

L i =0 y L i-1 =0: X 0;0;i = S 0;i xor C 0;i = R i xor O i xor (R i-1 y O i-1 ) L i =0 y L i-1 =1: X 0;1;i = S 0;i xor C 1;i = R i xor O i xor (R i-1 o O i-1 ) L i =1 y L i-1 =0: X 1;0;i = S 1;i xor C 0;i = R i xnor O i xor (R i-1 y O i-1 ) = !X 0;0;i L i =1 y L i-1 =1: X 1;1;i = S 1;i xor C 1;i = R i xnor O i xor (R i-1 o O i-1 ) = !X 0;1;i

Un posible decodificador para el ejemplo podría calcular estas cuatro expresiones para cada uno de los bits 4 a 13 y enviar las señales a través de los 40 cables del decodificador. Cada línea del decodificador seleccionaría uno de los cuatro cables para cada bit y consistiría en una compuerta AND de 10 entradas.

Una ruta de caché de datos más sencilla consistiría en un sumador seguido de un decodificador tradicional. Para nuestro subsistema de caché de ejemplo, la ruta crítica sería un sumador de 14 bits, que produce valores verdaderos y complementarios, seguido de una puerta AND de 11 bits para cada fila del decodificador.

En el diseño con direccionamiento por suma, la puerta AND final del decodificador se mantiene, aunque con un ancho de 10 bits en lugar de 11. El sumador se ha sustituido por una expresión lógica de cuatro entradas en cada bit. El ahorro de latencia proviene de la diferencia de velocidad entre el sumador y dicha expresión de cuatro entradas, un ahorro equivalente a quizás tres puertas CMOS sencillas .

Si el lector considera que esto supuso una cantidad desmesurada de trabajo compulsivo para una mejora de tres puertas en una ruta crítica de múltiples ciclos, entonces comprenderá mejor el nivel de optimización de las CPU modernas.

Muchos diseños de decodificadores evitan las compuertas AND de alta entrada en la propia línea de decodificación mediante una etapa de predecodificación. Por ejemplo, un decodificador de 11 bits podría predecodificarse en tres grupos de 4, 4 y 3 bits cada uno. Cada grupo de 3 bits controlaría 8 cables en la matriz de decodificación principal, mientras que cada grupo de 4 bits controlaría 16 cables. La línea de decodificación se convierte entonces en una compuerta AND de 3 entradas. Esta reorganización permite ahorrar una cantidad considerable de espacio y energía.

Esta misma reorganización puede aplicarse al decodificador con direccionamiento por suma. En la formulación anterior sin predecodificación, cada bit puede considerarse como una suma local de dos bits. Con la predecodificación, cada grupo de predecodificación es una suma local de tres, cuatro o incluso cinco bits, con un bit de solapamiento entre los grupos.

La predecodificación generalmente aumenta la cantidad de cables que atraviesan el decodificador, y los decodificadores con direccionamiento por suma suelen tener aproximadamente el doble de cables que un decodificador simple equivalente. Estos cables pueden ser el factor limitante en la cantidad de predecodificación factible.

• Paul Demone ofrece una explicación sobre las cachés con direcciones suma en un artículo de realworldtech .
• Heald et al. ^{[ 1 ]} tienen un artículo en ISSCC 1998 que explica cuál puede ser la caché original direccionada por suma en el Ultrasparc III.
• La memoria direccionada por suma se describe en

Patente de Estados Unidos n.º 5.754.819 , 19 de mayo de 1998, Método y estructura de indexación de memoria de baja latencia . Inventores: Lynch; William L. (Palo Alto, CA), Lauterbach; Gary R. (Los Altos, CA); Titular: Sun Microsystems, Inc. (Mountain View, CA), Fecha de presentación: 28 de julio de 1994

• Al menos uno de los inventores mencionados en una patente relacionada con la decodificación de direcciones sin acarreo atribuye el mérito a la siguiente publicación:

Evaluación de condiciones A + B = K sin propagación de acarreo (1992) Jordi Cortadella, Jose M. Llaberia IEEE Transactions on Computers ,

• La siguiente patente amplía este trabajo para utilizar aritmética de forma redundante en todo el procesador y, por lo tanto, evitar la sobrecarga de propagación de acarreo incluso en operaciones de la ALU, o cuando una operación de la ALU se omite y se dirige a una dirección de memoria:

Patente de Estados Unidos 5,619,664, Procesador con arquitectura para la segmentación mejorada de instrucciones aritméticas mediante el reenvío de formas de datos intermedios redundantes , otorgada el 18 de abril de 1997, Inventor: Andrew F. Glew (Hillsboro, OR); Cesionario: Intel Corporation (Santa Clara, CA), N.° de solicitud: 08/402,322, Presentada: 10 de marzo de 1995