sistema cache - utngnudelman/cache.pdfventajas y desventajas universidad tecnológica nacional -...
Post on 09-Feb-2020
8 Views
Preview:
TRANSCRIPT
Sistema Cache
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Técnicas Digitales III Ing. Gustavo Nudelman 2012
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
RAM dinámica
• Almacena un bit como una capacidad espuria en un transistor
• La necesidad de conservar la carga y la lectura destructiva obliga el refresco de la celda
• El consumo es mínimo (1 transistor x bit)
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
RAM Estática - Cache
• Almacena un bit en un biestable (6 transistores)
• 3 transistores en conducción permanente mayor consumo
• No necesita refresco – Tiempo de acceso muy bajo.
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Evolución de la velocidad de CPU Vs Memoria
• En la década del 90 los
procesadores comienzan a
desarrollar velocidades
superiores a los tiempos de
acceso a memoria
• Se utilizan “Wait states” en
las interfaces entre buses
locales y del sistema
La solución: Memoria Cache
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Se trata de un banco SRAM que contiene una copia de parte de la
memoria DRAM para permitir un acceso mas veloz
• El arte consiste en que parte de la memoria conviene tener en esta copia
• Requiere un hardware adicional que funcionará como sistema
administración y control y que trabajará bajo las siguientes premisas:
• Principio de localidad de referencia Que copiar y cuanto copiar
• Política de ubicación En que dirección de cache se mapea
• Política de sustitución Si esta llena la cache, que debo sustituir ?
• Política de actualización Cuando actualizar en DRAM los cambios
producidos en cache
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Organización de un sistema
Costo/MB ↓
Capacidad ↑
Tiempo de acceso ↑
Frecuencia de acceso ↓
Cintas – CDs
Disco
RAM Dinámica
Cache
CPU Reg
Principio de localidad de referencia
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Los accesos a memoria que se realizan régimen de ejecución no
están distribuidos uniformemente en el espacio lineal sino que se
concentran en áreas definidas de memoria
• Vecindad Temporal: Probabilidad de repetir instrucciones
(lazos de repetición)
GUARDAR EN CACHE ANTE CUALQUIER ACCESO
• Vecindad espacial: Agrupación de los datos en memoria,
tablas – secuencia y flujo normal de un programa.
GUARDAR EL BLOQUE DE ENTORNO A LA DIRECCION ACCEDIDA
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Operación de lectura con cache
Eficiencia de memoria cache
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
)1( AMPAC PTPTT
Ejemplo Con tecnología DDR tenemos un tiempo de acceso promedio de 10nS Sea 1ns el acceso el tiempo de acceso a SRAM cache. Si la probabilidad de aciertos es del 80 %
nsnsnsT 8.2)8.01(108.01
HrateAccesos
Aciertos
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Estructura – Conceptos generales
012345
01234
c-1
Bloque 0 (k celdas)
Bloque 1
Bloque 2
Bloque m-1
Espacio Lineal Cache
•Una línea almacena el contenido de un bloque e información de referencia al mismo •Cantidad de bloques en el espacio lineal •Bloques >> Líneas M>>C •La memoria cache solo podrá estar cargada con un subconjunto de los bloques
Tag Bloque
12 n
km
n2
Estructura – Conceptos generales
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Habiendo mas bloques que líneas, cada línea o entrada de cache
no puede estar dedicada a un bloque en particular.
• Es por eso que cada línea de cache posee una etiqueta (Tag)
para identificar que bloque tiene cargado en ese momento.
• La necesidad de asignación de una línea a mas de un bloque nos
obliga a establecer una política de ubicación y en base a esta, un
hardware dedicado a establecer una función de correspondencia.
• Las 3 funciones de correspondencia que se suelen utilizar son:
• Directa
• Asociativa
• Asociativa por conjuntos
Correspondencia directa
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Es la función mas sencilla y barata de implementar por Hardware
• A cada bloque de memoria le corresponde una única línea de
cache posible
Línea Bloques de memoria principal
0 0 , C , 2C , 3C , . . . . . .
1 1 , C+1 , 2C+1 , 3C+1, . . . .
2 2 , C+2 , 2C+2 . 3C+2
……. …………..
C-1 C-1 , 2C-1 , 3C-1, . .. . .. . .
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Interpretación de la dirección entregada por la CPU
cache de 32K con bloques de 4 bytes
Tag bloque de 4 bytes
0
8191
Línea (13) Tag (17)
Comp Hit +
Offset (2)
n
Recupero bloque miss
Dir. de bloque en espacio lineal (30)
Acceso al espacio lineal
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Correspondencia Directa IA32 (cache 32K)
Ventajas y desventajas
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Hardware simple y económico
• Es posible que un programa este referenciando continuamente 2
bloques de memoria que corresponden a la misma línea de cache
con lo que se estaría en una situación de recambio continuo
aunque otras líneas estén libres.
• Es necesario poder aprovechar todas las líneas
Correspondencia asociativa
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Un bloque del espacio lineal puede estar en cualquier línea de
cache.
• Mientras la memoria cache no este llena, no hará falta hacer
ninguna sustitución
• Se debe implementar una política de sustitución para cuando la
cache este llena
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Interpretación de la dirección entregada por la CPU
cache de 32K con bloques de 4 bytes
Tag 0
Tag 1
Tag n 8191
Comp
Dir de bloque en espacio lineal (30)
Tag
Comp
Comp
Ventajas y desventajas
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Cada línea tiene un comparador asociado de manera de realizar
la comparación a la velocidad requerida. Hardware mas costoso.
• Nunca tendremos que reemplazar un bloque cargado a menos
que todas las líneas se encuentren ocupadas
• No existen expulsiones mutuas.
• Adquiere notable importancia la política de sustitución
• Con una buena política de sustitución se consigue que todos los
últimos elementos referenciados permanezcan en memoria cache
• La tasa de aciertos se incrementa notablemente
Correspondencia asociativa por conjuntos
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Es una combinación de los 2 sistemas de correspondencia vistos
hasta ahora.
• Las líneas de la memoria cache se agrupan en conjuntos o “sets”
en donde un bloque puede ocupar cualquier línea si y solo si la
línea pertenece a dicho conjunto.
• Si se tiende al limite en donde un conjunto posee una sola línea
estaríamos en el caso de correspondencia directa
• Si se tiende al limite de un solo conjunto de que contenga todas
las líneas estaríamos en el caso de correspondencia asociativa
• Normalmente se suelen utilizar de 2 a 8 líneas por conjunto
(Cache asociativa de n vías)
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Interpretación de la dirección entregada por la CPU
cache de 32K con bloques de 4 bytes
Tag 0
Tag 1
Tag n 8191
Dir. de bloque en espacio lineal (30)
Comp 1
Conjunto (12) Tag (18)
Tag 2
Tag 3
C0
C1
Comp 2
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Cache asociativo de 2 vías IA32
Ventajas y desventajas
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Con 2 líneas por conjunto se logra aumentar notablemente la tasa de
aciertos sin incrementar considerablemente la complejidad y/o costo.
• Solo se requieren 2 comparadores
• Los Pentium utilizan cache asociativa de 2 a 4 vías mientras que
procesadores como Power Pc utilizan memorias de 4 a 8 vías
• La probabilidad de expulsiones mutuas disminuye exponencialmente
con el aumento de la cantidad de vías por conjunto.
Políticas de sustitución
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• En correspondencia directa no hay elección – No se puede
establecer una política
• En correspondencia asociativa suele utilizarse:
• LRU (Last recent used) vecindad temporal Se sustituye
el que lleva menos tiempo referenciado.
• LFU (Last Frequently used) Se sustituye el menos
referenciado
• Random
• FIFO Solo tiene en cuenta el tiempo que lleva un bloque
en cache.
• No existe una política mejor que otra ya que dependen de la
política de ubicación tamaño y tipo de cache.
Coherencia de un cache
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• La coherencia de una memoria cache esta dada por la política de
actualización.
• Cuando se modifica un dato en cache el correspondiente dato en memoria
queda obsoleto.
• Cuando un dato necesita ser modificado las políticas de actualización
pueden ser:
• Write Through: El procesador escribe en DRAM y el controlador de
cache refresca el cache con el dato actualizado.
• Write Through Buffered: El procesador actualiza la SRAM cache y
luego el controlador cache realiza la copia en DRAM mientras que la
CPU puede continuar ejecutando instrucciones y accediendo a la
memoria cache.
• Copy Back: Se marcan las líneas de cache que han sido modificadas
pero son recién copiadas a DRAM cuando la línea debe ser
sustituida. En este caso el tiempo del miss correspondiente es mayor
al de acceso normal a DRAM.
Protocolo MESI
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
• Creado por INTEL para procesadores Pentium para aprovechamiento del
sistema write-back de las cache de CPU
• Se utilizan 2 bits en cada línea de cache para establecer uno de los
siguientes estados:
• M (Modified): La línea ha sido modificada – Requiere Write back
(modificar en DRAM) antes de que otro procesador acceda al dato.
• E (Exclusive): La línea esta presente solo en esta cache y coincide
con la memoria principal
• S (Shared): La línea esta presente y puede estar almacenada en
cache de otros procesadores.
• I (Invalid): La línea cache no es valida. (No corresponde a nada en
memoria)
Universidad Tecnológica Nacional - Facultad Regional Buenos Aires
Protocolo MESI . Diagrama de estados • Se puede leer de
caché en cualquier estado excepto en Inválido.
• Una escritura sólo puede ser llevada a cabo si la línea de caché está en estado Modificado o Exclusivo. Si está en estado Compartido todas las otras copias en otras cachés deben ser puestas en estado Inválido antes.
top related