En el diseño de CPU , el uso de un decodificador de suma direccionada (SAD) o de memoria direccionada (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 memoria caché SRAM .
La caché de datos L1 normalmente debería estar en el recurso de CPU más crítico, porque pocas cosas mejoran las instrucciones por ciclo (IPC) tan directamente como una caché de datos más grande, ya que se tarda más en acceder a una caché de datos más grande y la segmentación de la caché de datos empeora la IPC. Una forma de reducir la latencia del 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 memoria SRAM de la caché.
Aún se debe realizar la operación de suma de generación de direcciones, ya que otras unidades en el conducto de memoria utilizarán la dirección virtual resultante. Esa suma se realizará en paralelo con la suma/descodificación fusionada que se describe aquí.
La recurrencia más rentable para acelerar es una carga, seguida de un uso de esa carga en una cadena de operaciones con números enteros que conducen a otra carga. Suponiendo que los resultados de la carga se pasan por alto con la misma prioridad que los resultados con números 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 tener un 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 adiciones de múltiples entradas se pueden reducir a una adición de dos entradas con sumadores de ahorro de acarreo, 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 de SRAM, la(s) línea(s) de bits de SRAM, el(los) amplificador(es) de detección, los muxes de direccionamiento de bytes y los muxes de derivación.
En este ejemplo, se supone que se trata de una caché de datos de 16 KB con mapeo directo que devuelve valores alineados con palabras dobles (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 palabras decodificadas. Se activa una línea de palabras en respuesta a cada valor único de Addr[13:3].
En la forma más simple del decodificador, cada una de las 2048 líneas es lógicamente una compuerta AND . Los 11 bits (llamémoslos A[13:3]) y sus complementos (llamémoslos B[13:3]) se activan en el decodificador. Para cada línea, se introducen 11 bits o complementos en una compuerta AND de 11 entradas. Por ejemplo, 1026 decimal es igual a 10000000010 binario. La función para la línea 1026 sería:
línea de palabra[1026] = A[13] y B[12] y B[11] y B[10] y B[9] y B[8] y B[7] y B[6] y B[5] y A[4] y B[3]
Tanto la cadena de transporte del sumador como la del decodificador combinan información de todo el ancho de la porción de índice de la dirección. Combinar información de todo el ancho dos veces es redundante. Una SRAM con dirección de suma combina la información solo una vez implementando el sumador y el decodificador juntos en una estructura.
Recuerde que la SRAM se indexa con el resultado de una suma. Llamemos a los sumandos R (para el registro) y O (para el desplazamiento hasta ese registro). El decodificador direccionado por suma va a decodificar R+O. Para cada línea del decodificador, llamemos al número de línea L.
Supongamos que nuestro decodificador controlara tanto R como O en cada línea del decodificador, y que cada línea del decodificador implementara:
línea de palabra[L] = (R+O)==L
(R+O)==L <=> R+OL==0 <=> R+O+~L+1==0 <=> R+O+~L==-1==11..1.
Se puede utilizar un conjunto de sumadores completos para reducir R+O+~L a S+C (esta es una suma con acarreo). S+C==11..1 <=> S==~C. No habrá acarreos en la suma final. Tenga en cuenta 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 es un conjunto de sumadores completos que reducen el registro base, el desplazamiento y el número de fila a un formato de acarreo y almacenamiento, y un comparador. La mayor parte de este hardware se demostrará redundante más adelante, pero por ahora es más sencillo pensar que todo existe 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 más grande, en nuestro ejemplo, la de un bloque de 8 bytes. Es preferible ignorar algunos de los LSB de la dirección. Sin embargo, los LSB de los dos sumandos no se pueden ignorar porque pueden producir un acarreo que cambiaría la palabra doble a la que se dirige.
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 carry-out. Tanto I como I+1 se pueden obtener 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 carry-out de R[2:0]+O[2:0] se puede utilizar entonces para seleccionar la palabra doble par o impar que se obtendrá más tarde.
Tenga en cuenta que obtener datos de dos bancos de SRAM de la mitad de tamaño disipará más energía que obtenerlos de un banco de tamaño completo, ya que provoca más cambios en los amperios de detección y la lógica de dirección de datos.
En referencia al diagrama adyacente, el banco par buscará la línea 110 cuando I[13:3]==101 o I[13:3]==110. El banco impar buscará la línea 101 cuando I[13:3]==100 o I[13:3]==101.
En general, el banco SRAM impar debe buscar la línea Lo==2N+1 cuando I[13:3]==2N o I[13:3]==2N+1. Las dos condiciones se pueden escribir de la siguiente manera:
I[13:3] = Lo-1 => R[13:3] + O[13:3] + ~Lo+1 = 11..11 => R[13:3] + O[13:3] + ~Lo = 11..10I[13:3] = Lo => R[13:3] + O[13:3] + ~Lo = 11..11
Ignore 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 de la siguiente manera 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..10I[13:3] = Le => R[13:3] + O[13:3] + ~Le = 11..11
R13 ... R6R5R4R3O13 ... O6O5O4O3L13 ... L6L5L4L3 -------------------------- 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 LSB (==S[3]) se descarta. El acarreo (==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 en AND, OR, XOR y XNOR de 2 entradas porque la entrada L es constante. Las expresiones resultantes son comunes a todas las líneas del decodificador y se pueden recopilar en la parte inferior.
S 0;i = S(R i , O i , 0) = R i x o O i S 1;i = S(R i , O i , 1) = R i x o 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 x o C 0;i = R i x o O i x o (R i-1 y O i-1 )L i = 0 y L i-1 = 1: X 0;1;i = S 0;i x o C 1;i = R i x o O i x o (R i-1 o O i-1 )L i = 1 y L i-1 = 0: X 1;0;i = S 1;i x o C 0;i = R i x ni O i x o (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 x o C 1;i = R i x ni O i x o (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..13 y hacer pasar los 40 cables por el decodificador. Cada línea del decodificador seleccionaría uno de los cuatro cables para cada bit y consistiría en un AND de 10 entradas.
Una ruta de caché de datos más simple tendría 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 compuerta AND de 11 bits para cada fila del decodificador.
En el diseño con dirección de suma, la puerta AND final del decodificador permanece, aunque con 10 bits de ancho en lugar de 11. El sumador ha sido reemplazado por una expresión lógica de cuatro entradas en cada bit. El ahorro en latencia proviene de la diferencia de velocidad entre el sumador y esa expresión de cuatro entradas, un ahorro de quizás tres puertas CMOS simples.
Si el lector considera que se trató de una cantidad excesiva de trabajo mental para una mejora de tres puertas en una ruta crítica de múltiples ciclos, entonces tendrá una mejor apreciación del nivel al que están optimizadas las CPU modernas.
Muchos diseños de decodificadores evitan las puertas AND con gran cantidad de entradas en la línea de decodificación empleando 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 impulsaría 8 cables hasta la matriz de decodificación principal, y cada grupo de 4 bits impulsaría 16 cables. La línea de decodificación se convierte entonces en una puerta AND de 3 entradas. Esta reorganización puede ahorrar un área de implementación significativa y algo de energía.
Esta misma reorganización se puede aplicar al decodificador con dirección de suma. Cada bit de la formulación no predecodificada anterior se puede considerar 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, en la que los grupos de predecodificación se superponen en un bit.
La predecodificación generalmente aumenta la cantidad de cables que atraviesan el decodificador, y los decodificadores con direcciones de suma generalmente tienen aproximadamente el doble de cables que el decodificador simple equivalente. Estos cables pueden ser el factor limitante de la cantidad de predecodificación posible.
Patente de Estados Unidos 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); Cesionario: Sun Microsystems, Inc. (Mountain View, CA), Presentada: 28 de julio de 1994
Evaluación de condiciones A + B = K sin propagación de acarreo (1992) Jordi Cortadella, Jose M. Llaberia IEEE Transactions on Computers , [1] [2]
Patente de Estados Unidos 5.619.664, Procesador con arquitectura para una mejor canalización de instrucciones aritméticas mediante el reenvío de formas de datos intermedias redundantes , otorgada el 18 de abril de 1997, Inventor: Glew; Andrew F. (Hillsboro, OR); Cesionario: Intel Corporation (Santa Clara, CA), N.º de solicitud: 08/402.322, Presentada: 10 de marzo de 1995