Arquitectura de Computadores
Clase 20
Memoria Caché: Elementos de Diseño
IIC 2342Semestre 2008-2
Rubén Mitnik
Pontificia Universidad Católica de ChileEscuela de IngenieríaDepartamento de Ciencia de la Computación
Determinan qué línea hay que sobreescribir cuando la memoria caché se llena y se requiere escribir un bloque de memoria principal en la caché
R.Mitnik Arquitectura de Computadores3
Memoria CachéCapítulo 5 : Sistemas de Memoria – Memoria Caché
Algoritmos de ReemplazoAlgoritmos de Reemplazo
R.Mitnik Arquitectura de Computadores
Para el esquema directo no hay elección ya que cada bloque de memoria sólo puede estar en un sitio.
Para los otros esquemas : LRU (least recently used) FIFO (first in first out) LFU (least frequently used) Random
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
4
LRU (least recently used: menos recientemente usada): Probablemente los bloques usados más
recientemente seguirán usándose en el futuro cercano.
Probablemente los bloques no usados en mucho tiempo no se usarán mucho en el futuro cercano.
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
5
LRU (least recently used: menos recientemente usada): Con esta política se desaloja de la caché el bloque
que tiene más tiempo sin usarse.
Implementación por hardware Cada vez que se usa un bloque se debe almacenar alguna
referencia al tiempo (timestamp) Se sustituye aquel bloque que tenga la referencia más
antigua.
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
6
FIFO (first input first output): Se hace una lista con la secuencia de entrada de los
bloques a la memoria caché. Se desaloja el bloque más antiguo.
Nota: no se desaloja el bloque cuyo uso sea el más antiguo (eso es LRU), se desaloja aquella que su ingreso a la caché es el más antiguo. Es decir se sustituye aquel bloque que ha estado más
tiempo en la caché (aún cuando se haya usado recientemente)
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
7
FIFO (first input first output):
Implementación: se usa una lista circular con una manecilla que indica el más antiguo.
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
8
LFU (least frecuently used: utilizado menos frecuentemente):
Se sustituye aquel bloque que ha experimentado menos referencias.
Implementación: cada bloque posee un contador, el que se incrementa cada vez que el bloque ha sido referenciado. Se sustituye aquel que tenga el contador más bajo.
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
9
Random (aleatorio):
Se sustituye un bloque cualquiera según una función aleatoria.
Estudios realizados mediante simulación han mostrado que la sustitución aleatoria proporciona un desempeño ligeramente menor a un algoritmo de reemplazo como los anteriores (basados en el grado de utilización).
R.Mitnik Arquitectura de Computadores
Algoritmos de reemplazoCapítulo 5 : Sistemas de Memoria – Memoria Caché
10
Antes de que pueda ser reemplazado un bloque de la caché es necesario comprobar si ha sido alterado en la caché y no en la memoria principal. Si la memoria principal se encuentra actualizada, el bloque puede ser sobre-escrito. En caso contrario habrá que actualizar la memoria principal antes de sobre-escribir el bloque.
R.Mitnik Arquitectura de Computadores11
Memoria CachéCapítulo 5 : Sistemas de Memoria – Memoria Caché
Políticas de escrituraPolíticas de escritura
R.Mitnik Arquitectura de Computadores
Hay dos técnicas principales Write-through (inmediatamente) Write-back (post-escritura)
R.Mitnik Arquitectura de Computadores
Políticas de escrituraCapítulo 5 : Sistemas de Memoria – Memoria Caché
12
Write-through (escritura inmediata):
Todas las operaciones de escritura se hacen tanto en la caché como en la memoria principal inmediatamente.
Así se asegura que el contenido de la memoria principal sea siempre válido.
R.Mitnik Arquitectura de Computadores
Políticas de escrituraCapítulo 5 : Sistemas de Memoria – Memoria Caché
13
Write-through (escritura inmediata):
Desventaja: se genera un tráfico sustancial a la memoria principal que puede disminuir el desempeño.
Estudios señalan que el porcentaje de referencias a memoria para escritura es del orden del 15%.
R.Mitnik Arquitectura de Computadores
Políticas de escrituraCapítulo 5 : Sistemas de Memoria – Memoria Caché
14
Write-back (post-escritura):
La línea se copia a memoria cuando se va a reemplazar (sólo si fue modificada).
Bit de actualización: inicializado en ‘0’ (al cargarse la línea) seteado en ‘1’ al modificarse la línea.
R.Mitnik Arquitectura de Computadores
Políticas de escrituraCapítulo 5 : Sistemas de Memoria – Memoria Caché
15
Problemas de diseño:
1ns 5 ns 100 ns 5 ms
1KB 256 KB 1 GB 80 GB
R.Mitnik Arquitectura de Computadores
Políticas de escrituraCapítulo 5 : Sistemas de Memoria – Memoria Caché
16
Write-back (post-escritura):
Desventaja: Porciones de la memoria principal pueden no ser válidos. Los
módulos de I/O necesitarían acceder a ella a través de la caché.
puede generar problemas de coherencia de memoria
R.Mitnik Arquitectura de Computadores
Políticas de escrituraCapítulo 5 : Sistemas de Memoria – Memoria Caché
17
R.Mitnik Arquitectura de Computadores18
Memoria CachéCapítulo 5 : Sistemas de Memoria – Memoria Caché
Número y Niveles de CachéNúmero y Niveles de Caché
R.Mitnik Arquitectura de Computadores
Incialmente, se usaba sólo una caché externa (off-chip) a la CPU. Luego se desarrollaron caches on-chip.
Se hicieron estudios de performance para determinar si una sola cache es suficiente.
El resultado de estas investigaciones indican que el desempeño aumenta si se emplean distintos niveles de caché.
R.Mitnik Arquitectura de Computadores
Número y Niveles de cachesCapítulo 5 : Sistemas de Memoria – Memoria Caché
19
Actualmente se tienen sistemas de con caches on-chip (L1 y L2) y off-chip (L3).
R.Mitnik Arquitectura de Computadores
Número y Niveles de cachesCapítulo 5 : Sistemas de Memoria – Memoria Caché
20
R.Mitnik Arquitectura de Computadores21
Memoria CachéCapítulo 5 : Sistemas de Memoria – Memoria Caché
Tipos de CachésTipos de Cachés
R.Mitnik Arquitectura de Computadores
Unified: instrucciones y datos juntos
Split: instrucciones y datos separados
Specific: usos específicos (trace cache, victim cache)
CPU
InstructionCache
DataCache
L2 Cache
L3 Cache
Main Memory
L1CACHE
R.Mitnik Arquitectura de Computadores
Tipos de cachesCapítulo 5 : Sistemas de Memoria – Memoria Caché
22
R.Mitnik Arquitectura de Computadores
Número, Niveles y Tipos de cachesCapítulo 5 : Sistemas de Memoria – Memoria Caché
23
R.Mitnik Arquitectura de Computadores24
Memoria CachéCapítulo 5 : Sistemas de Memoria – Memoria Caché
CoherenciaCoherencia
R.Mitnik Arquitectura de Computadores
El uso de diversos caches genera problemas de coherencia entre ellos, tanto utilizando politicas write-through como write-back.
Problemas de coherencia: Entre caches del mismo core o CPU Entre caches de distintos cores o CPUs
Soluciones: Vigilancia del bus (con write-through)
invalidación de datos
Transparencia de hardware actualización en todas las caches
Memoria excluida de cache memoria compartida no se transfiere a cache
R.Mitnik Arquitectura de Computadores
CoherenciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
25
Soluciones: Protocolo MESI (Modified / Exclusive / Shared /
Invalid) agrega dos bits de control por línea
Modificada: distinta de memoria principal y no existe en otras caches.
Exclusiva: coincide con memoria principal y no existe en otras caches.
Compartida: coincide con memoria principal y puede estar presente en otras caches.
Inválida: datos no son válidos.R.Mitnik Arquitectura de Computadores
CoherenciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
26
Cuando se carga una palabra en la caché, se carga también palabras contiguas con la idea de que posteriormente van a ser también referenciadas.
R.Mitnik Arquitectura de Computadores27
Memoria CachéCapítulo 5 : Sistemas de Memoria – Memoria Caché
Tamaño del bloqueTamaño del bloque
R.Mitnik Arquitectura de Computadores
¿Qué tan grande debe ser el bloque?
¿Cuántas palabras contiguas deben cargarse en la caché?
Ni pocas, ni muchas: La tasa de aciertos aumenta a medida que aumenta
el tamaño del bloque, pero empieza a disminiuir si aumenta demasiado
En bloques muy grandes las palabras dejan de estar tan contiguas y nunca o casi nunca son referenciadas.
Ej: Pentium 4 y AMD Athlon 64 usan líneas de 64 bytes
R.Mitnik Arquitectura de Computadores
Tamaño del bloqueCapítulo 5 : Sistemas de Memoria – Memoria Caché
28
R.Mitnik Arquitectura de Computadores
Tamaño del bloqueCapítulo 5 : Sistemas de Memoria – Memoria Caché
29
Tamaño del código
Optimización para velocidad tamaño
Código optimizado para tamaño puede llegar a ejecutarse más rápido que código optimizado para velocidad.
R.Mitnik Arquitectura de Computadores
Efectos: eficienciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
30
R.Mitnik Arquitectura de Computadores
Efectos: eficienciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
31
R.Mitnik Arquitectura de Computadores
Efectos: eficienciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
32
R.Mitnik Arquitectura de Computadores
Efectos: eficienciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
33
R.Mitnik Arquitectura de Computadores
Efectos: eficienciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
34
R.Mitnik Arquitectura de Computadores
Efectos: eficienciaCapítulo 5 : Sistemas de Memoria – Memoria Caché
35
Resumen
Existen diversos elementos de diseño los cuales determinan la funcionalidad y desempeño de las memorias caché
Algoritmos de reemplazo Políticas de escritura Número y niveles de caché Tipos de caché Coherencia Tamaño de las líneas
La correcta selección de éstos permite optimizar la funcionalidad de la memoria caché para usos específicos
R.Mitnik 36 Arquitectura de Computadores
Resumen
Capítulo 5 : Sistemas de Memoria – Memoria Caché
R.Mitnik Arquitectura de Computadores