1

Capítulo 15.

Memoria. Todos los programas gastan la mayor parte de su tiempo accesando a la memoria, debido a esto el sistema de memoria es un factor principal en el comportamiento de un procesador. Además su diseño está fuertemente relacionado con la forma en que el sistema operativo maneja la memoria y la entrada-salida; la forma en que los compiladores generan el direccionamiento de las variables y funciones; y también con las aplicaciones que se ejecutarán en el procesador.

15.1. Organización de memorias estáticas. Los chips de memoria estática de acceso aleatorio (SRAM) están configuradas en términos de localizaciones direccionables (dado por el ancho del bus de direcciones) y ancho de palabra direccionable (dado por el bus de datos de entrada y el de salida). Por ejemplo una configuración de 32KB (32K*8 bits), requiere 15 líneas de dirección (215 = 25 * 210 = 32K) y el largo de palabra es 8 bits o 1 Byte. Suelen tener tres líneas de control: Output enable, que habilita una salida en tercer estado; Write enable, que permite escribir en una palabra; y Chip Select (o Chip Enable), que habilita o deshabilita al chip completo. De este modo la configuración anterior requiere 36 pines (15 +8 +8 + 3 + 2), donde los dos últimos corresponden a tierra y Vcc. Las líneas de salida son compartidas por todas las palabras almacenadas, y sólo se conecta al bus de salida aquella palabra que está direccionada, mediante la habilitación de tercer estado. Esto permite compartir el bus de salida sin emplear un multiplexor. El siguiente diagrama muestra una memoria estática de 4*2.

Profesor Leopoldo Silva Bijit

18-07-2007

2

Estructuras de Computadores Digitales MemWr MemRd

D

OE C

Q

D

Q

D

Q

D

OE Q C

0

Decodificador.

D

OE C

OE C

Q

1

Add[1]

2a4 D

Add[0]

OE

OE C

C

Q

2

D

OE Q C

D

OE C

Q

3

Dout[0] Dout[1]

Din[1] Din[0]

Figura 15.1 Esquema memoria estática, de 4*2. En memorias físicas, lo usual es que el bus de datos sea bidireccional, de este modo se reduce el número de pines del circuito. Se tienen ahora el bus de datos (formado por las conexiones en los pines de entrada-salida); el bus de direcciones (de entrada); y el bus de control (formado por tres señales de entrada, de lógica negativa).

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

3 CE’ WE’

OE’

Control Memoria

Dir

Arreglo

Decodificador

Dout

I/O

Din

Figura 15.2 Esquema de memoria. Cuando CE’ está alta la memoria entra en modo standby de bajo consumo. La señal CE (chip enable) permite una sencilla expansión de la memoria en organización de múltiples bancos. Los drivers de salida permanecen en estado de alta impedancia cuando CE’ o OE’ están altas; o cuando WE’ está baja. 15.1.1. Ciclo de lectura controlado por el cambio de dirección. Con WE’ alta, CE’ y OE’ bajas, al cambiar la dirección, después de un tiempo se tienen datos válidos en la salida.

Datos inválidos

Figura 15.3 Ciclo de lectura. Con tAA, tiempo de acceso por cambio de dirección.

Profesor Leopoldo Silva Bijit

18-07-2007

4

Estructuras de Computadores Digitales

15.1.2. Ciclo de lectura controlado por señales de control. Para leer se coloca la dirección en el bus, luego se activa el Chip Enable y el Output Enable (con WE’ alto y CE’ y OE’ bajas), después del tiempo de acceso (típico de 5 ns, año 1999) se tienen datos válidos en el bus Dout.

Salida en alta impedancia Dirección estable Figura 15.4 Ciclo de lectura, controlado por señales de control. 15.1.3. Ciclo de escritura controlado por WE. Para escribir: Se colocan los datos en Din, y la dirección en el bus; luego se activan Chip Enable (CE’ baja) y Write Enable, luego del tiempo de acceso se tiene grabado el nuevo contenido. Los datos son escritos en el canto de subida de WE’. La señal Write Enable es un pulso con requerimientos de ancho mínimo, más que un reloj. Adicionalmente deben cumplirse tiempos de set-up y hold. El dispositivo externo debe colocar datos en el bus bidireccional, después que los drivers de salida se han puesto en tercer estado con el canto de bajada de WE’ (después de tWZ, en el diagrama)

Salida

de

Figura 15.5 Ciclo de escritura controlado por WE.

Profesor Leopoldo Silva Bijit

18-07-2007

memoria

en

alta

Memoria

5

15.1.4. Decodificación en dos niveles. La organización anterior tiene el problema de requerir un gran decodificador (y por lo tanto un gran número de líneas de palabra). Para evitar esto en las memorias de gran capacidad se decodifica en dos niveles. El bus de dirección puede considerarse dividido en dos campos, uno entra a un decodificador (con menos líneas de palabras) y se leen simultáneamente varios arreglos (tantos como sea el ancho de la palabra); el otro campo comanda un conjunto de multiplexores que seleccionan un bit de cada arreglo. Lo cual se ilustra a continuación para una memoria de 32K*4. La cual se organiza dividiendo las 15 líneas (necesarias para 32K) de dirección en 9 líneas, para ser decodificadas en 512 (29) líneas de palabra; y 6 líneas, que seleccionan un bit de los 64(26), que componen la palabra de salida de cada arreglo, que ingresan a cada multiplexor. Add[14..6]

Decodificador

512*64

512*64

512*64

64

64

64

Dout[2]

Dout[1]

Dout[0]

512*64

512

9 a 512

64 Add[5..0]

Dout[3]

Figura 15.6 Decodificación en dos niveles. Nótese que esta organización permite disponer de 256 bits (64*4) en un tiempo de acceso. Y agregando controles adicionales podría leerse direcciones secuenciales variando la dirección aplicada al multiplexor. Es decir el acceso a 64 direcciones secuenciales podría realizarse en menor tiempo que uno de acceso. Para esto se requiere un reloj interno a la ram (por esto se denominan ram sincrónicas), que transfiera los bis sucesivos de una ráfaga a partir de una dirección de inicio y de la especificación del largo de la secuencia (esto se logra variando internamente las direcciones aplicadas al multiplexor, en cada reloj interno). Es usual que se empleen dos compuertas inversoras para formar el latch interno que almacena un bit; para esto se requieren de cuatro a seis transistores por bit. Lo anterior permite almacenar (en forma estática) un bit mientras se tenga aplicada polarización a los transistores.

15.2. Organización de memorias dinámicas. En las RAM dinámicas, el valor del bit se almacena como carga en un condensador, y sólo se requiere un transistor para sensar o recargar la carga almacenada. El menor número de transistores requerido permite aumentar la densidad de la memoria y disminuir el costo por bit, pero como la carga no puede mantenerse indefinidamente debe ser refrescada periódicamente, por esta razón se denominan memorias dinámicas. Para refrescar el contenido se lee una palabra Profesor Leopoldo Silva Bijit

18-07-2007

6

Estructuras de Computadores Digitales

y se la vuelve a escribir; para disminuir el tiempo dedicado al refresco se emplea, una decodificación de la dirección en dos niveles. Se refresca una fila completa con un ciclo de lectura seguido por uno de escritura. Esta organización permite que la operación de refrescar la DRAM completa ocupe de 1 a 2% de los ciclos activos totales que puedan efectuarse en la memoria. La dirección se descompone en columnas y renglones y comparte en tiempo el bus de direcciones. Esto logra disminuir el número de pines dedicados a la dirección a la mitad, también implica un solo arreglo cuadrado, como se ilustra a continuación, para una DRAM se 1M*1:

1024*1024

Decodificador

Add[9..0]

1024

10 a 1024

1024 Latch Columna

Dout Figura 15.7 Renglones y columnas en DRAM. Para direccionar un Mega se requieren 20 líneas de dirección, en la figura se muestra un bus de 10 líneas. En una lectura: se coloca primero en el bus la dirección del renglón, el decodificador activa una de las 1024 líneas de palabra, y después de un tiempo de acceso al renglón, el contenido del renglón se captura en un registro, denominado latch de columna; luego se coloca en el bus de direcciones los 10 bits de la columna, lo cual activa una de las 1024 entradas al mux, permitiendo obtener después del tiempo de acceso a la columna el bit direccionado. Estas memorias poseen controles, denominados: Row access strobe (RAS) y Column access strobe (CAS) para indicar a la RAM si se tiene la dirección de un renglón o una columna en el bus de dirección. Se refresca un renglón completo en cada operación de refresco, leyendo el registro de columna y reescribiéndolo en la memoria. La organización de la DRAM, si bien disminuye el número de pines para establecer una dirección, aumenta el tiempo de acceso por un orden de magnitud relativa al de la SRAM (típico 50 ns, año 1999). Se permite cambiar la dirección de la columna sin cambiar la dirección del renglón, lo cual permite (en el modo página o modo de columna estática) accesar a múltiples bits de un renglón cambiando solamente la dirección de la columna (mediante la red combinacional del mux, que suele operar más rápido que la lectura de la memoria). Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

7

En el modo denominado nibble se leen 4 bits secuenciales, por cada acceso a un renglón; para esto la RAM genera internamente las siguientes tres direcciones de las columnas. Las memorias DRAM tipo EDO (por extended data out, actualmente obsoletas) en 1997, lograron tiempos de acceso al renglón de 25 ns. Actualmente, se tienen RAM sincrónicas, que transfieren una secuencia de largo dado de bits, a partir de una dirección dada mediante el control de un reloj interno, el cual va generando las direcciones de las columnas en forma sucesiva.

15.3. Localidad. Un programa no requiere leer todas sus instrucciones ni accesar a la zona de variables estáticas (en su segmento de datos) ni a la zona dinámica (stack) con igual probabilidad. En general un programa accesa a una porción relativamente pequeña de su espacio de direcciones (instrucciones y datos) es decir existe cierta localidad. Se denomina localidad espacial al hecho de que si se accesa a cierta dirección es muy probable que, muy próximamente en tiempo, se referencien direcciones cercanas a dicha dirección. Las instrucciones de un programa tienen localidad espacial, también los elementos de un arreglo o estructura, y también los argumentos y variables locales en el stack. Se denomina localidad temporal al hecho de que si se accesa a cierta dirección es muy probable que se la referencie nuevamente muy próximamente en el tiempo. Es el caso de las instrucciones que forman un lazo de repetición y de las variables que son manipuladas en el lazo. Se diseñan entonces los sistemas de memoria en forma jerárquica, aprovechando la localidad temporal, manteniendo los datos más recientemente accesados más cercanos al procesador. Y considerando la localidad espacial moviendo bloques, formados por varias celdas adyacentes de memoria, desde los niveles inferiores.

15.4. Memoria cache. Una memoria rápida en acceso a sus componentes, relativamente pequeña en su número de componentes, y por el momento costosa en dinero, se denomina cache e interactúa directamente con el procesador. Suele ser memoria estática SRAM (por static random access memory, memoria estática de acceso aleatorio) y recientemente SSRAM (memoria estática sincrónica de acceso aleatorio). La memoria cache está organizada en bloques, y además de ser accesada directamente por el procesador ésta puede accesar al siguiente elemento de la jerarquía que es la memoria denominada principal, formada por un gran número de componentes de mayor tiempo de acceso y de menor costo en dinero. La memoria principal suele estar diseñada mediante DRAM (memoria dinámica de acceso aleatorio) y también está organizada en bloques. El nivel siguiente suele ser el cache del sistema de discos duros y luego los discos duros. En todos los niveles existen bloques. Pero los datos son copiados solamente entre dos niveles adyacentes en un tiempo dado.

Profesor Leopoldo Silva Bijit

18-07-2007

8

Estructuras de Computadores Digitales

Si la dirección buscada está en la cache, se dice que existe un éxito (hit) y si no se encuentra, existe un fallo (miss). Una medida del comportamiento del sistema jerárquico es la tasa de éxitos, que es la fracción de accesos a memoria que se encuentran en el nivel superior; la tasa de fallos es (1 - tasa de éxitos). La tasa de fallos suele ser tipo 5 %. Para reducir esta tasa es preciso aumentar el tamaño de la memoria cache, o emplear un nivel adicional de cache denominado secundario, siempre que la penalización de la cache secundaria sea menor que el acceso a memoria principal. También es importante el tiempo de un éxito de acceso, que se mide como el tiempo empleado para determinar que el ítem se encuentra en el nivel. En caso de fallo, debe accesarse el nivel inferior de la jerarquía, y esto se mide con la penalización por fallo que se descompone en el tiempo de latencia (para encontrar la dirección en el nivel inferior) y el tiempo de transferencia empleado para mover el bloque hacia el nivel superior. 15.4.1. Cache de mapeo directo. Tamaño de bloque igual a uno. Cada localización de memoria se mapea exactamente en una localización de la cache. La manera más simple es emplear la fórmula: (Dirección del bloque) módulo (Número de bloques totales de la cache) Un esquema electrónico para lograr el direccionamiento es el siguiente: Offset bytes (2)

Dirección

V

marca

Dato

Indice (i )

Marca (m ) Comparador

Exito Figura 15.8 Cache de mapeo directo. Bloque unitario.

Profesor Leopoldo Silva Bijit

18-07-2007

Dato

Memoria

9

Se desagrega el bus de direcciones en tres campos: El campo empleado para determinar un byte o media palabra dentro de una palabra, los dos menos significativos. Un campo denominado índice, que establece el número de direcciones de la cache ( 2i celdas). Y el resto que se denomina marca. La celda de la cache tiene también tres campos: uno con el dato (es el espacio para almacenar la palabra); el campo marca de igual ancho que el campo de igual nombre del bus de direcciones; y un bit denominado válido. Existen muchas direcciones que tienen igual campo índice y se almacenarán en la misma dirección de la cache, esto implementa el mecanismo de acceso denominado directo. Al inicio se marcan todas las celdas de la cache como invalidas (campo V igual a cero), al intentar leer una dirección se producirá un fallo, entonces se leerá desde la memoria principal y se traerá el contenido al campo dato de la cache; y se escribirá el campo marca con los m bits más significativos del bus de dirección en la dirección en la celda con dirección índice de la caché y se marcará como válida (v=1). Si más adelante se desea leer una dirección que tenga el mismo índice pero con diferente marca se producirá un fallo. Y se reescribe la marca (desde el bus de dirección) y el nuevo dato que se trae desde la memoria principal. Cuando se escribe un dato en la cache, el procesador escribe los campos: válido, marca y dato en la cache (no requiere leer la memoria principal), y debe proceder a escribir en la memoria principal sino ésta queda inconsistente con la cache. Un método empleado es el de escritura directa, en el cual siempre que se escribe en la cache, se escribe en la principal; otro método es utilizar un buffer de escritura. En éste se encolan los datos que deben ser escritos en la memoria principal, de este modo el procesador no debe esperar la escritura física en la memoria principal y puede seguir procesando. En forma autónoma se escriben los datos del buffer en la memoria y se los marca como disponibles, de esta forma el procesador sólo debe detenerse cuando el buffer no tenga casillas disponibles. 15.4.1.1 Diseño de un buffer de escritura: De teoría de colas se tienen las siguientes fórmulas: Utilización = Velocidad de requerimientos / Velocidad de Servicio. Largo promedio de la cola= Utilización / (1 - Utilización) Probabilidad de rebalse de una cola de N-entradas = (Utilización)N

Palabras que deben escribirse

Palabras escritas Figura 15.9 Buffer de escritura.

Se tiene que el CPI promedio es de 1,3 y el ciclo del reloj es de 20 ns. En la mezcla de instrucciones que se ejecutan existe un 15 % de instrucciones store word.

Profesor Leopoldo Silva Bijit

18-07-2007

10

Estructuras de Computadores Digitales

La velocidad de llegada de palabras que deben escribirse puede calcularse según: Velocidad promedio de ejecución de instrucciones = 1 / (1.3 * 20ns) = 3.846 x 107 [instr./seg] Y la frecuencia de almacenamientos es = 0,15 * (3,846 * 107) = 5,769 x 106 stores/seg Con una DRAM de tiempo de ciclo de escritura de 100 ns, se tiene que la velocidad de servicio en escritura es de 1/100ns = 1,0* 107 [escrituras/seg] Con estos valores se puede calcular la utilización y el largo de la cola: Utilización = 5,769*106/107= 0,5769 Largo promedio de la cola = 0,5769 / (1 - 0,5769) = 1,363 Puede determinarse el número de elementos en el buffer de escritura para tener una probabilidad de rebalse menor que un número dado. Si el buffer tiene cuatro posiciones, la probabilidad de saturación es (0,5769)4 = 0,11 Lo cual implica un 11%. Si el buffer tiene seis posiciones, la probabilidad de saturación es (0,5769)6 = 0,038 Lo cual implica un 3,8%. 15.4.1.2. Ejemplo cache acceso directo. Las instrucciones de un procesador tienen un CPI promedio de 1,2. El CPI indicado es para memorias ideales, tanto de datos como de instrucciones. Es decir se asume que no hay fallos en los accesos a memoria. Se desea calcular el CPI promedio, empleando una memoria cache para los datos, para un programa de prueba, en el cual el 20 % de las instrucciones son de transferencias. Suponer una memoria cache de 4 Kbytes, de acceso directo. Con un tiempo de éxito igual a un ciclo de reloj, una tasa de fallos del 8 % y con una penalidad por fallos de 4 ciclos de reloj (considerando incorporado, en este último valor, el tiempo para determinar que es un fallo). El nuevo CPI promedio se calcula descomponiendo las instrucciones del programa de prueba en dos grupos: las que no accesan a la memoria de datos (y por ende conservan el CPI para memorias ideales) y el segundo grupo, las instrucciones de lectura y escritura en memoria de datos (load word y store word). A su vez las que accesan la memoria son descompuestas en los accesos exitosos (direcciones que se encuentran en la cache), que incrementan en un ciclo la ejecución; y las que no están en la caché que agregan los ciclos de penalización. CPI = (1-0,20) * 1.2 + 0.2 * ( (1.2+1) * (1-0,08) + (1.2 + 4) * 0,08) = 1.264 CPI = 0,96 + 0,2*(2,024 + 0,416 ) = 1,448 Si el tiempo de ciclo de la memoria es de 20 ns (es mayor que el tiempo de acceso, es el tiempo entre dos operaciones en la memoria), el tiempo promedio por instrucción es:

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

11

Tiempo promedio por instrucción = 1,448 * 20 = 28,96 [ns/instrucción] 15.4.2. Cache de mapeo directo. Tamaño de bloque igual a una potencia de dos. Para aprovechar la localidad espacial el bloque de la cache contiene varias palabras adyacentes (una potencia de dos). En el ejemplo que se ilustra se dispone un bloque formado por cuatro palabras de la memoria. Esto reduce el campo marca necesario y agrega un mux de cuatro entradas, que es controlado por el campo offset de bloque del bus de dirección. Los bits dedicados a la administración de la cache (válido, marca) disminuyen al aumentar el tamaño del bloque. Offset bytes (2)

V marca

Dato

Offset bloque (2)

Dirección Indice (i )

Marca (m ) Comparador

Mux Exito

Dato

Offset bloque (2)

Figura 15.10 Cache de mapeo directo. Bloques de 4. Si se produce un fallo (de lectura), deben ahora traerse desde la memoria principal cuatro palabras adyacentes. Con esta organización si al escribir, las marcas son iguales es un éxito en escritura y se puede continuar, pero si no son iguales hay un fallo de escritura y se debe leer el bloque desde memoria principal y volver a escribir la palabra dentro del bloque, junto a las adyacentes. Al aumentar el tamaño del bloque disminuye la tasa de fallos, este efecto es más notable en la cache de instrucciones, debido a la mejor localidad espacial. Manteniendo constante la capacidad en bytes de la cache, si se aumenta mucho el tamaño del bloque, será menor el número de bloques que se pueden colocar en la cache y existirá mayor competencia por los bloques. Esto implica que la tasa de fallos tiende a aumentar.

Profesor Leopoldo Silva Bijit

18-07-2007

12

Estructuras de Computadores Digitales

Por otro lado al aumentar el tamaño del bloque aumenta la penalización por fallos, ya que aumenta el tiempo necesario buscar el bloque para efectuar las transferencias. 15.4.2.1 Interleaving. Para disminuir la penalización por fallos suele organizarse la memoria primaria con un bus más ancho o en bancos (interleaving). Si para el bloque de cache de tamaño cuatro, se emplea un ancho de palabra de memoria primaria de cuatro palabras, se reduce la latencia y la transferencia. El costo es un bus más ancho y el tiempo de propagación y control del mux entre la cache y el procesador. 15.4.2.2. Bancos. La segunda solución, para un tamaño de bloque de la cache de 4 palabras, es disponer de 4 bancos de memoria (de ancho igual a una palabra) que puedan ser leídos o escritos en un tiempo de acceso. El bus entre la cache y los bancos de memoria no requiere ser más ancho que el de una palabra. Se logra disminuir el tiempo de latencia, ya que en caso de fallo de lectura se envía una dirección y se leen simultáneamente los bancos, pero el tiempo de transferencia se multiplica por el número de palabras de un bloque de la cache. El tener los bancos separados facilita las escrituras en memoria principal, ya que pueden iniciarse ciclos de escritura, en cada banco, en el mismo tiempo. La dificultad del empleo de bancos o memoria entrelazada es que la configuración mínima de memoria aumenta. Esto debido a que los diseños de memorias comerciales tienden a tener bajo número de bits de salida (típicamente 1 a 4). Por ejemplo si se emplean chips de 4Mbit*1, se requieren 32 chips para formar una palabra de 32 bits, y con esto un banco de 16 Mbytes ( 4*220*32 bits = 16*220 Bytes). Y si se emplean 4 bancos se tendrá una memoria primaria de 64Mbytes, constituida por 128 chips. Si se emplearan chips de 16 Mbits*1 para formar un banco se requieren 32 chips para formar una palabra de 32 bits, y los 4 bancos entrelazados tendrían una capacidad de 256 Mbytes. Si se emplearan chips de 4Mbits*4 para formar un banco se requieren 8 chips para formar una palabra de 32 bits, y los 4 bancos entrelazados tendrían una capacidad de 64 Mbytes, con 32 chips. 15.4.2.3. Modo paginado. Para mejorar la velocidad de transferencia se emplean el modo paginado del que disponen las DRAM. Estas memorias dinámicas están organizadas como arreglos cuadrados y el tiempo de acceso está dividido en tiempo de acceso al renglón y a la columna (por el mismo bus de direcciones que se multiplexa en tiempo, para disminuir el número de pines). Se dispone un buffer de renglón, y mediante un mux se selecciona la columna, y puede mediante señales especiales de control accesarse a dicho buffer sin tener que volver a leer el renglón (esto se emplea en el refresco). Es decir se lee por página (un renglón completo). Si por ejemplo el tiempo de acceso al renglón y la columna es de 120 ns, el acceso a la página es de 60 ns. Las RAM tipo EDO (extended data out, de corta vigencia tecnológica) lograron tener un acceso tipo 25 ns a palabras adyacentes dentro de la página. En la actualidad se emplean las SDRAM (por sincrónica) que permiten un acceso a direcciones secuenciales de memoria,

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

13

dándoles como dato de entrada la dirección de la primera dirección y el número de palabras a leer. La SDRAM emplea un reloj propio logrando tiempos de acceso tipo 8 ns. por palabra. 15.4.2.4 Ejemplo: El bloque de la memoria cache es de 32 Bytes. En caso de un fallo se desea llenar el bloque de la cache en dos ciclos de lectura de la memoria principal. Determinar la capacidad de la memoria si se emplean chip de 256K*8bits. Solución. Para cumplir la especificación de tiempo el ancho del bus entre la cache y la DRAM está dado por: 32Bytes/2 = 16 bytes = 128 bits de ancho. Si se dispone de chips de 256 K*8 se requieren 128/8 = 16 chips, resultando una capacidad de memoria de 256Kbytes/chip*16chips = 4 Mbytes. 15.4.2.5. Ejemplo: Para SDRAM, si el tiempo de acceso al renglón es tRAC = 60 ns y el tiempo de acceso en modo página es de tCAC =35 ns, con un reloj de 66 MHz, determinar los ciclos necesarios para disponer de cuatro palabras. Solución: Como el período del reloj es de 15,15 ns, se requieren 4 ciclos para el primer acceso. Para los siguientes accesos secuenciales se requieren 3 ciclos ( 3*15,15 = 45,45 >35 ns; dos ciclos equivalen a 30,30 ns y es menor que el tiempo tCAC.) Esto suele anotarse: 4-3-3-3 (nomenclatura que aparece en algunos setups). Para buses de memoria con igual frecuencia si se emplearan SBSRAM (synchronous burst sram) con tiempos de acceso entre 8,5 y 12 ns se obtendría la secuencia 2-1-1-1 para accesar 4 palabras de la cache.

15.4.3. Cache asociativa. En la cache de mapeo directo un bloque sólo puede estar localizado en un solo lugar de la cache, para flexibilizar la colocación de los bloques la cache asociativa de n vías, permite colocar un bloque en n posiciones. Se denomina asociativa por conjuntos, y cada conjunto tiene n posiciones donde puede colocarse un bloque. Cada bloque de la memoria se mapea a un único conjunto en la cache, y puede colocarse en cualquier elemento del conjunto. El diagrama siguiente ilustra una cache asociativa por conjuntos de dos vías y muestra la comparación necesaria, realizada en paralelo, para ubicar a un bloque que ahora puede estar en dos posiciones. Sólo pueden estar en la cache dos bloques que tengan igual índice; en caso de requerir colocar un tercero, con igual índice, debe aplicarse alguna política de reemplazo. El método aleatorio sustituye cualquiera; el menos recientemente usado reemplaza al bloque que haya estado más tiempo sin usarse y es complejo de implementar electrónicamente en caso de que la cache sea de varias vías.

Profesor Leopoldo Silva Bijit

18-07-2007

14

Estructuras de Computadores Digitales

Offset bytes (2)

Dirección

V

marca

Dato

V

marca

Dato

Indice (i )

Marca (m )

Compad

Mux Exito

Dato

Figura 15.11 Cache asociativa por conjuntos de dos vías. También puede diseñarse una cache completamente asociativa, en la cual un bloque de la memoria puede asociarse con cualquier entrada de la cache. En este caso debe existir un comparador asociado con cada entrada de la cache y efectuar la comparación en paralelo; esto implica gran costo y no suele emplearse. Se podrían colocar varias palabras en un bloque, en este caso se requiere un mux adicional para seleccionar la palabra dentro del bloque; y también se agregaría un campo en el bus de dirección con el offset dentro del bloque. Si el tamaño de la cache se mantiene constante, al aumentar (en un factor de dos) la asociatividad se aumenta el número de bloques por conjunto, así también el número de comparaciones simultáneas que deben realizarse en paralelo y por ende disminuye (en un factor de dos) el número de conjuntos posibles. El índice disminuye en un bit, y el campo marca aumenta en un bit. El conjunto que contiene un bloque de memoria está determinado por: (Número de bloque) módulo (número de conjuntos en la cache). Esto se ilustra para una memoria cache de 8 bloques:

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

15

Bloque Marca Datos 0 1 2 3 4 5 6 7 Mapeo directo. Asociativa de una vía

Set Marca Dato Marca Dato 0 1 2 3 Asociativa de dos vías

set Marca Dato Marca Dato Marca Dato Marca Dato 0 1 Asociativa de 4 vías. M

D

M

D

M

D

M

D

M

D

M

D

M

D

M

D

Completamente asociativa. Asociativa de 8 vías. Figura 15.12 Cache asociativas de una, dos, cuatro y ocho vías. 15.4.3.1. Ejemplo: Se tiene una cache de 4 bloques de una palabra. a) Determinar las direcciones de las entradas para una organización de acceso directo y para una cache asociativa por conjuntos de dos vías, para los bloques: 0, 6, 8. Para acceso directo se tienen: 0 módulo 4 = 0; 6 módulo 4 = 2; 8 módulo 4 = 0 Para cache de dos vías, hay dos conjuntos. En cada conjunto se tienen bloques. Entonces: 0 módulo 2 = 0; 6 módulo 2 = 0; 8 módulo 2 = 0 b) Para las organizaciones anteriores, determinar el número de fallos para cargar en la cache la secuencia de bloques: 0, 8, 0, 6, 8. Para la de acceso directo: colocar el primer bloque genera un fallo, el segundo también es fallo ya que está ocupada la entrada 0; luego vuelve a sobrescribirse la entrada 0, lo cual es otro fallo; como se asume vacía originalmente la cache, la siguiente entrada se coloca en la entrada dos, pero con un fallo; finalmente el último bloque genera otro fallo. Para cache de acceso directo, la secuencia produce 5 fallos. Para la asociativa: los dos primeros son fallos, y se completa el conjunto cero; el ingreso de la tercera entrada es exitoso; el cuarto ingreso sobrescribe el bloque 8, si se aplica la técnica de reemplazo del menos recientemente usado, provocando un fallo; el último ingreso sobrescribe el bloque 0 con el contenido del bloque 8, y también es un fallo.

Profesor Leopoldo Silva Bijit

18-07-2007

16

Estructuras de Computadores Digitales

Para cache asociativa de dos vías, la secuencia produce 4 fallos. c) Para la misma secuencia anterior determinar el número de fallos si la cache es completamente asociativa. Los dos primeros ingresos producen fallos; el tercero es un éxito, ya que encuentra el bloque 0; el cuarto es un fallo al almacenar el bloque 6; finalmente encuentra el bloque 8 con éxito. Para cache completamente asociativa, la secuencia produce 3 fallos. 15.4.3.2. Ejemplo: Se tienen tres máquinas con distintas configuraciones de memoria caché, como se aprecia en el cuadro siguiente: Máquina I Máquina II Máquina III

Correspondencia directa con bloque de una palabra Correspondencia directa con bloque de cuatro palabras 2 vías asociativa por conjuntos con bloques de cuatro palabras

Para cada una de estas máquinas la penalización de escritura en la caché es de 6 ciclos más 1 ciclo por cada palabra del bloque. (La máquina III es equivalente a la máquina II en la escritura de una palabra en un bloque, ya que se asume ideal la selección del conjunto en que se escribe). Además una aplicación cualquiera posee los siguientes porcentajes de instrucciones: Branch 20% Load 13% Store 12% Inmediatas 20% Tipo R 35% Se tienen las siguientes tasa de fallos en memoria caché: Máquina Tasa de fallos de Instrucciones I 4% II 2% II 1.5%

Tasa de fallos de Datos 20% 16% 14%

Por último, CPI total para la máquina I es de 3.0 (ejecución + penalización) Calcular la penalización total (instrucciones + datos) para las tres máquinas e indique cuál máquina es la que ocupa mayor tiempo en los accesos a memoria. Ciclos de detención en memoria de instrucciones = Instrucciones * Tasa de fallos* Penalización por fallos Ciclos de detención en memoria de datos = Instrucciones que accesan memoria*Tasa de fallos * Penalización por fallos Penalización total = Ciclos de detención-memoria-instrucciones + Ciclos de detención-memoria -datos Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

17

Loads y Store = 25% (Instrucciones/programa) Penalización por fallo: Máquina I = 6 +1 = 7 ciclos Maquina II y III = 6 + 4 = 10 ciclos Penalización total I = 1.00*0.04 * 7 + 0.25 * 0.20 * 7 = 0.28 + 0.35 Penalización total II = 1.00*0.02 * 10 + 0.25 * 0.16 * 10 = 0.20 + 0.4 Penalización total III = 1.00*0.015 * 10 + 0.25 * 0.14 * 10= 0.15 + 0.35

= 0.63 = 0.60 = 0.50

Máquina I posee una mayor espera en los accesos a memoria. a) Cuál es el CPI de las Máquinas II y III CPI base = CPI (Máquina I) – penalización = 3.0 – 0.63 = 2.37 CPI II = 2.37 + 0.6 = 2.97 CPI III = 2.37 + 0.5 = 2.87 b) Suponga que la velocidad de estas máquinas es de 100Mhz. (10 ns por ciclo), cual es el tiempo promedio de acceso a memoria para estas máquinas asumiendo que las máquinas I y II poseen un tiempo de éxito de 1 ciclo y que la máquina tres posee un tiempo de éxito de 2 ciclos. Nota: Por cada 100 instrucciones, 25 accesan memoria, entonces 25/125 (el 20%) de los accesos son de datos y el 100/125 (el 80%) son de instrucciones. Máquina I = 10ns [0.80 * (1 + 0.04 * 7) + 0.2 * (1 + 0.2 * 7)] = 1.504 ns Máquina II = 10ns [0.80 * (1 + 0.02 * 7) + 0.2 * (1 + 0.16 * 7)] = 1.48 ns Máquina III= 10ns [0.80 * (2 + 0.015 * 7) + 0.2 * (2 + 0.14 * 7)] = 24 ns Ejemplo: Se tienen tres máquinas con distintas configuraciones de memoria caché, como se aprecia en el cuadro siguiente: Máquina I Máquina II Máquina III

Correspondencia directa con bloque de una palabra Correspondencia directa con bloque de cuatro palabras 2 vías asociativa por conjuntos con bloques de cuatro palabras

Para cada una de estas máquinas la penalización de escritura en la caché es de 4 ciclos más 1 ciclo por cada palabra del bloque. (La máquina III es equivalente a la máquina II en la escritura de una palabra en un bloque, ya que se asume ideal la selección del conjunto en que se escribe). Además una aplicación cualquiera posee los siguientes porcentajes de instrucciones: Branch 15% Load 15% Store 10% Inmediatas 25% Tipo R 35% Profesor Leopoldo Silva Bijit

18-07-2007

18

Estructuras de Computadores Digitales

Se tienen las siguientes tasa de fallos en memoria caché: Máquina Tasa de fallos de Instrucciones I 4% II 2% III 1.5%

Tasa de fallos de Datos 20% 16% 14%

Por último, CPI total para la máquina I es de 3.0 (ejecución + penalización) c) Calcular la penalización total (instrucciones + datos) para las tres máquinas e indique cuál máquina es la que ocupa mayor tiempo en los accesos a memoria. Ciclos de detención en memoria de instrucciones = Instrucciones * Tasa de fallos* Penalización por fallos

Ciclos de detención en memoria de datos = Instrucciones que accesan memoria*Tasa de fallos * Penalización por fallos Penalización total = Ciclos de detención-memoria-instrucciones + Ciclos de detención-memoria -datos Loads y Store = 25% (Instrucciones/programa) Penalización por fallo: Máquina I = 4 +1 = 5 ciclos Maquina II y III = 4 + 4 = 8 ciclos Penalización total I = 1.00*0.04 * 5 + 0.25 * 0.20 * 5 = 0.2 + 0.25 Penalización total II = 1.00*0.02 * 8 + 0.25 * 0.16 * 8 = 0.16 + 0.32 Penalización total III = 1.00*0.015 * 8 + 0.25 * 0.14 * 8= 0.12 + 0.28

= 0.45 = 0.48 = 0.40

Máquina I posee una mayor espera en los accesos a memoria. Si se incrementa la asociatividad de la máquina III, manteniendo el tamaño del bloque constante, esto produce que la tasa de fallos de instrucciones sea cero y si el CPI total para esta máquina es de 2.75, Cuál es la nueva tasa de fallos de datos ?. CPI base = CPI (Máquina I) – penalización = 3.0 – 0.45 = 2.55 Penalización total por acceso a memoria = 2.75 – 2.55 = 0.2 0.2 = 8*(0.1 + 0.15)* tasa fallos de datos tasa de fallos de datos = 10%

15.5. Memoria Virtual. La memoria principal actúa como una cache para el almacenamiento secundario en discos magnéticos. Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

19

Se desea disponer de un ambiente eficiente y seguro para compartir la memoria entre diversos programas y disponer de una memoria mayor que la física para la ejecución de programas y procesamiento de los datos. Esto puede lograrse ya que si se tienen varios programas en ejecución, éstos sólo usan (en un cierto intervalo de tiempo) una pequeña parte de la memoria que requieren, a pesar de que la suma de los requerimientos totales de memoria, de todos ellos, puedan exceder la memoria física disponible. El sistema operativo debe permitir a los programas compartir la memoria y garantizar que cada programa no invada el espacio que ocupan los otros. Además las direcciones físicas que serán asignadas a los segmentos activos de los programas pueden ir cambiando en el tiempo; para permitir esta forma de emplear la memoria, cada programa, al ser compilado, emplea un espacio propio de direcciones. La memoria virtual es responsable de traducir las direcciones del programa a direcciones físicas. Esto también permite que el espacio de direcciones del programa sea mayor que el espacio de direcciones físico. Uno podría considerar que el programa compilado reside en disco, y que sólo parte de esas direcciones del programa están mapeadas en direcciones físicas. Por esta razón un programa podría ser tan grande como el espacio en disco que se le permita ocupar (lo cual podría ser mucho mayor que la memoria física). Esta "ilusión" de una memoria, prácticamente ilimitada, la provee el sistema de memoria virtual. La organización de memoria virtual y memoria cache es similar. Pero, por razones históricas se emplea el concepto de página en lugar de bloque. La dirección de las instrucciones y datos de un programa se denominan direcciones virtuales, las cuales son traducidas a direcciones físicas. Se requiere un hardware dedicado y segmentos del sistema operativo para efectuar eficientemente el mapeo de páginas virtuales a páginas físicas. Para esto una dirección está dividida en campos: el número de página y la posición dentro de la página. El ancho del campo para el offset dentro de la página define el tamaño de ésta, y toma el mismo valor para la dirección virtual y física. Obviamente los bits dedicados al número de página en una dirección virtual son mayores que los de las direcciones físicas. Con 12 bits, para el offset, las páginas son de 4KB. En la actualidad las páginas tienden a ser de 32KB y mayores. Esto implica una enorme penalización en caso de falla de página (pueden ser millones de ciclos), considerando los tiempos de latencia electromecánicos involucrados y las tasas de transferencia entre el disco y la memoria. Suele emplearse escritura postergada en el disco, en caso de escritura; y técnicas de colocación de página totalmente asociativas. Además algoritmos que tiendan a reducir las fallas de página, ya que el costo temporal de la ejecución de éstos es muchísimo menor que el requerido por una falla de página (que requiere mover varios KB desde el disco hacia la memoria). 15.5.1. Tabla de páginas.

Para lograr la completa asociatividad se emplea una Tabla de Páginas residente en memoria, que tiene como índice el número de página virtual y como contenido el número de página física, Profesor Leopoldo Silva Bijit

18-07-2007

20

Estructuras de Computadores Digitales

además de un bit para indicar si la página está o no presente en la memoria. Cada programa tiene su propia tabla de páginas, y se dispone un registro en el procesador para apuntar a la tabla de página activa. Dirección virtual

Número página virtual

offset en página

v V Número de página física.

Puntero a TP

o

Tabla de Páginas f Dirección física

Número página física

offset en página

Figura 15.13 Tabla de páginas. Un programa en ejecución, se denomina proceso, y requiere una tabla de página y el valor de los registros (adicionalmente información sobre prioridad de ejecución, estado del proceso, archivos que emplea, etc.), el sistema operativo es responsable de asignar memoria física y actualizar la tablas de página de tal modo que los diferentes procesos funcionen con sus propios espacios(es decir los programas sólo pueden leer y escribir las porciones de memoria principal que tienen asignadas). El sistema operativo también es responsable de ir activando, con cierta política de itineración los diferentes procesos, de tal modo que sólo uno esté activo durante cierto intervalo de tiempo, para esto basta que mantenga información del estado de los diferentes procesos. Específicamente para activar el espacio de direcciones basta actualizar el registro que apunta a la tabla de páginas del proceso. En caso de producirse una falla de página, se genera excepción. El sistema operativo debe encontrar la página en el disco y decidir dónde colocarla en la memoria principal. Para facilitar esta tarea cuando se crea un proceso se almacena en una zona del disco todas las páginas de un proceso y a la vez una estructura de datos que asocie la página virtual con la dirección física del disco donde ésta se encuentra. Esta estructura puede ser la misma tabla de páginas del proceso. 15.5.2. Ejemplo: Con un espacio virtual de direcciones de 32 bits, con páginas de 4 Kbytes calcular el tamaño de la tabla de páginas de un proceso. Se tienen 12 líneas para el offset de página y 20 para direccionar la tabla de páginas, es decir, 1M de entradas a la tabla de páginas. Si el espacio físico es de 1 giga, se requieren 18 bits para

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

21

el número de página física, más un bit para marcar si la página está o no en memoria. Podría agregarse un bit, para indicar que la página ha sido modificada y que debe ser escrita hacia el disco, para mantener consistentes los niveles. Además suele agregarse bits para implementar mecanismos de protección, y también la dirección física de la ubicación de la página en el disco. Si se contemplan 32 bits por entrada, se tendrá que la tabla de páginas requiere: 220 * 32 bits = 1M * 4 Bytes = 4 MBytes. Si se desea que una máquina pueda tener una serie de procesos activos, la mayor parte de la memoria principal debería estar dedicada a almacenar las tablas de página. Esto implica desarrollar un método para reducir el almacenamiento necesario para almacenar las tablas de página. 15.5.3. TLB Para mejorar el tiempo requerido para efectuar las traducciones de direcciones virtuales a físicas los diseños actuales agregan una pequeña cache totalmente asociativa, denominada TLB (translation-lookaside buffer) que podríamos traducir por: almacén de traducciones recientes, la cual guarda las últimas traducciones realizadas. Dirección virtual

Número página virtual v V

offset en página

TLB Marca Número de página física.

Tabla de Páginas V N° bloque N° página disco. física.

Puntero a TP

Dirección física

o

f

offset en página

Número página física Marca para cache

índice cache

Direccionamiento Figura 15.14 TBL. Direcciones físicas y virtuales. Efectuar una traducción requiere dos accesos a memoria: uno a la tabla de páginas para encontrar la dirección física (siempre que ésta esté totalmente en memoria) y otro para obtener Profesor Leopoldo Silva Bijit

18-07-2007

22

Estructuras de Computadores Digitales

el dato. Debido a que cuando se requiere una traducción, lo más probable es que en el futuro se la vuelva a requerir, debido a que las referencias a esa página tienen localidad temporal y espacial, es razonable introducir la cache denominada TLB. Cuando se requiere una referencia a memoria, se busca el número de la página virtual en la tabla de traducciones recientes (TLB), si es un éxito, con el número de página física del TLB se forma la dirección física, se marca el bit de página válida; si es un referencia de escritura se marca otro bit (dirty bit), para indicar que la página deberá ser escrita posteriormente en el disco. Si se produce un fallo en TLB, se accesa la tabla de páginas y se determina si la página está en memoria (con el bit de validez de la tabla de páginas) si está, se carga la dirección física en el TLB(es un fallo de TLB y no de página) y se vuelve a intentar la referencia. En caso de fallo de página se genera excepción, se registra el estado de los bits de estado de la entrada al TLB (dejando la entrada disponible) y se busca en el disco la página que falta; se actualiza la tabla de páginas (manteniendo los bits de estado), se busca una entrada en el TLB donde se graban la dirección física la marca y los bit de estado, y se vuelve a intentar la referencia. Copiar los bits de estado de TBL en la Tabla de páginas sólo en caso de fallo posterga lo más posible la escritura a disco. Con TLB de unas 64 entradas, y bloques de dos referencias a páginas físicas por entrada, se logran tiempos de un ciclo para determinar el éxito o fallo de TLB, con una penalización adicional de unos 20 ciclos de reloj, para reponer la entrada. Con estas características se logran tasas menores al 1% de fallos de TLB. Debe considerarse que la tasa de fallos de una cache es menor que el 10%, y que la tasa de fallas de página típicas son menores que el 0,0001%. En el caso del procesador MIPS existen instrucciones del repertorio y registros dedicados que permiten actualizar el TLB. Debido al sistema jerárquico de la memoria, si un dato está en la cache también debe estar en la memoria principal. Si un bloque de la cache, en el cual se han cambiado sus valores (tiene marcado el bit de escritura, dirty bit) requiere ser reutilizado con otro bloque, antes de disponer del espacio debe escribirse en la página en memoria. Si el espacio de memoria física en que está una página es reutilizado con otra, antes de sobreescribir en ella, si la página tiene marca de haber sido modificada, deberá ser escrita en el disco. Por la estructura jerárquica descrita no puede ocurrir un fallo de página y un éxito en el TLB. Ya que no puede existir la traducción si la página no está presente en memoria. Si se produce un éxito en TLB la tabla de páginas correspondiente debe estar en la memoria.

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

23

Tampoco puede existir un éxito en la cache si la página no está en memoria.

Profesor Leopoldo Silva Bijit

18-07-2007

24

Estructuras de Computadores Digitales

Índice general. CAPÍTULO 15. ...........................................................................................................................................1 MEMORIA..................................................................................................................................................1 15.1. ORGANIZACIÓN DE MEMORIAS ESTÁTICAS. ......................................................................................1 15.1.1. Ciclo de lectura controlado por el cambio de dirección..........................................................3 15.1.2. Ciclo de lectura controlado por señales de control. ................................................................4 15.1.3. Ciclo de escritura controlado por WE. ....................................................................................4 15.1.4. Decodificación en dos niveles..................................................................................................5 15.2. ORGANIZACIÓN DE MEMORIAS DINÁMICAS. .....................................................................................5 15.3. LOCALIDAD. .....................................................................................................................................7 15.4. MEMORIA CACHE. ............................................................................................................................7 15.4.1. Cache de mapeo directo...........................................................................................................8 15.4.1.1 Diseño de un buffer de escritura:........................................................................................................9 15.4.1.2. Ejemplo cache acceso directo..........................................................................................................10

15.4.2. Cache de mapeo directo.........................................................................................................11 15.4.2.1 Interleaving. .....................................................................................................................................12 15.4.2.2. Bancos.............................................................................................................................................12 15.4.2.3. Modo paginado................................................................................................................................12 15.4.2.4 Ejemplo:...........................................................................................................................................13 15.4.2.5. Ejemplo:..........................................................................................................................................13

15.4.3. Cache asociativa. ...................................................................................................................13 15.4.3.1. Ejemplo:..........................................................................................................................................15 15.4.3.2. Ejemplo:..........................................................................................................................................16

15.5. MEMORIA VIRTUAL........................................................................................................................18 15.5.1. Tabla de páginas....................................................................................................................19 15.5.2. Ejemplo:.................................................................................................................................20 15.5.3. TLB.........................................................................................................................................21 ÍNDICE GENERAL. ....................................................................................................................................24 ÍNDICE DE FIGURAS. ................................................................................................................................25

Profesor Leopoldo Silva Bijit

18-07-2007

Memoria

25

Índice de figuras. FIGURA 15.1 ESQUEMA MEMORIA ESTÁTICA, DE 4*2.................................................................................... 2 FIGURA 15.2 ESQUEMA DE MEMORIA............................................................................................................ 3 FIGURA 15.3 CICLO DE LECTURA. ................................................................................................................. 3 FIGURA 15.4 CICLO DE LECTURA, CONTROLADO POR SEÑALES DE CONTROL. ............................................... 4 FIGURA 15.5 CICLO DE ESCRITURA CONTROLADO POR WE. ......................................................................... 4 FIGURA 15.6 DECODIFICACIÓN EN DOS NIVELES........................................................................................... 5 FIGURA 15.7 RENGLONES Y COLUMNAS EN DRAM...................................................................................... 6 FIGURA 15.8 CACHE DE MAPEO DIRECTO. BLOQUE UNITARIO. ..................................................................... 8 FIGURA 15.9 BUFFER DE ESCRITURA............................................................................................................. 9 FIGURA 15.10 CACHE DE MAPEO DIRECTO. BLOQUES DE 4. ........................................................................ 11 FIGURA 15.11 CACHE ASOCIATIVA POR CONJUNTOS DE DOS VÍAS. ............................................................. 14 FIGURA 15.12 CACHE ASOCIATIVAS DE UNA, DOS, CUATRO Y OCHO VÍAS................................................... 15 FIGURA 15.13 TABLA DE PÁGINAS. ............................................................................................................. 20 FIGURA 15.14 TBL. DIRECCIONES FÍSICAS Y VIRTUALES............................................................................ 21

Profesor Leopoldo Silva Bijit

18-07-2007