documentt5

Tema 5. Memoria Caché

ESTRUCTURA DE COMPUTADORES

Grupo de Arquitectura de Computadores (GAC)

EC Tema 5 curso 2014/2015 1 / 41

Índice

1 Introducción

2 Organización de un sistema cachéCorrespondencia directaTotalmente asociativaAsociativa por conjuntosEscritura en la caché

3 Rendimiento de la caché

4 Técnicas de optimizaciónCachés de datos e instruccionesReducción de la tasa de fallosReducción de la penalización de falloReducción del tiempo de acierto

EC Tema 5 curso 2014/2015 2 / 41

Índice

1 Introducción

2 Organización de un sistema caché


4 Técnicas de optimización

EC Tema 5 curso 2014/2015 3 / 41

Introducción

EC Tema 5 curso 2014/2015 4 / 41

Introducción

La memoria caché es una memoria pequeña y rápida que se sitúaentre la CPU y la memoria principalAlmacena la información actualmente en uso de la memoria principalEl término caché es utilizado por primera vez por Conti, Gibson yPitowsky en 1968El primer computador comercial con memoria caché fue el IBM360/85El principio de localidad justifica el éxito de la memoria caché

EC Tema 5 curso 2014/2015 5 / 41

Operación de un sistema caché

EC Tema 5 curso 2014/2015 6 / 41

Operación de un sistema caché

Estructura general de una memoriacaché:

I Directorio: contieneinformación sobre las líneas(bloques) de la zona dealmacenamiento

I Zona de almacenamiento:contiene la copia de algunaslíneas de memoria principal

El directorio contiene un conjuntode etiquetas para identificar si unapalabra de la caché se correspondecon la palabra buscada

El bit de validez permite conocer siun bloque de la caché no tieneinformación válida

EC Tema 5 curso 2014/2015 7 / 41

Índice

1 Introducción

2 Organización de un sistema cachéCorrespondencia directaTotalmente asociativaAsociativa por conjuntosEscritura en la caché



EC Tema 5 curso 2014/2015 8 / 41

Organización de un sistema caché

Existen tres categorías de organización dependiendo de la función decorrespondencia (algoritmo que hace corresponder bloques dememoria principal a líneas cache)

I Correspondencia directa: hace corresponder cada bloque de memoriaprincipal a sólo una línea posible de caché.

I Asociativa: permite que el bloque de memoria pueda cargarse encualquier línea de la caché.

I Asociativa por conjuntos: solución de compromiso que recoge lopositivo de las dos soluciones anteriores

EC Tema 5 curso 2014/2015 9 / 41


Caché de correspondencia directaEs el tipo más sencillo de memoria cache así que la utilizaremos paracomenzar a introducir conceptosFísicamente, una cache de correspondencia directa es una pequeña yrápida memoria estática de acceso aleatorioSu principal característica es que cada dato tiene asignada unaposición fija en la cache

EC Tema 5 curso 2014/2015 10 / 41

Organización de un sistema cachéCaché de correspondencia directa

Dada una cache de asignacióndirecta con p posiciones, undato almacenado en la direcciónd sólo podrá alojarse en laposición d módulo p de lacaché

EC Tema 5 curso 2014/2015 11 / 41


Líneas de una cachéLlamamos línea a cada una de las posiciones de una cacheCada línea puede contener 1 ó más palabrasLlamamos tamaño de línea al número de bytes que contiene una líneade la cacheLa línea es la unidad indivisible dentro de una cacheNo es posible cargar ni quitar porciones de una líneaCuando se carga una palabra en la cache, se carga una línea completaEsto permite aprovechar la localidad espacialEn una caché con correspondencia directa, para un tamaño de línea l ,el byte b buscado estará en la posición b mod l

EC Tema 5 curso 2014/2015 12 / 41

Organización de un sistema cachéTamaño de línea

Para un mismo tamaño de caché3 A mayor tamaño de línea

mejor aprovechamiento de lalocalidad espacial

7 A mayor tamaño de líneamenos líneas en la caché

EC Tema 5 curso 2014/2015 13 / 41


Etiquetas y datosEn la cache se almacenan datos, por lo que cada línea dispone deespacio para ellosLos datos almacenados en una línea pueden provenir de cualquierdirección de memoria a la que esté asignada esa líneaPor tanto, no está claro el origen de un dato almacenado en la cachePara resolver este problema, cada línea almacena también unaetiqueta, que indica la dirección en memoria del dato que contieneEjemplo: Una cache de 16 lineas de un solo byte

I El dato en la dirección 0010 1001 0101 1011 es: 0000 0000 1111 0000I Si ese dato entra en la cache lo hará en la línea 1011I La etiqueta será: 0010 1001 0101I El dato será 0000 0000 1111 0000

EC Tema 5 curso 2014/2015 14 / 41

Organización de un sistema cachéReemplazos y validez

En un principio la cache está vacíaCada línea tiene un bit de validez que indica si la línea contienedatos válidos ó noA medida que se llena la cache se van activando los bits de validez

En una caché decorrespondencia directa,cuando una línea estáocupada y se intentaintroducir un nuevo dato esnecesario realizar unreemplazo

01101

01110110

11

01

(000)(001)(010)(011)

(101)

(111)

01100

11101

01110110

01

01

(000)(001)(010)(011)

(101)

(111)

00111

011101100111

01

(000)(001)(010)(011)(100)(101)

(111)

11000

01111

011101100111

00

(000)(001)(010)(011)(100)(101)

(111)

Entrada de01101

La línea 101ya está ocupada

Habrá un reemplazo

Salida de11101

Entrada de01100

La línea 100está vacíaNo habrá

reemplazo

Entrada de00111


Habrá un reemplazo

Entrada de11000


Habrá un reemplazo

EC Tema 5 curso 2014/2015 15 / 41


EficienciaLa principal medida de la eficiencia de una cache es la relación entreaciertos y fallos

I Las caches de asignación directa tienen una tasa de fallos relativamentealta en algunas aplicaciones debido a su poca de flexibilidad

I Por ello veremos otros tipos de cache más flexiblesPero existen otras medidas de eficiencia

I Las caches de asignación directa son baratas y rápidas y consumenpoca energía

I Por ello son utilizadas en procesadores empotrados, como los existentesen los móviles

EC Tema 5 curso 2014/2015 16 / 41


AsociatividadLas caches de asignación directa pueden ser poco eficientes ya que:

I En caso de reemplazo la línea a sustituir está predefinida de antemanoI Esto hace que se pueda sustituir una línea que produce muchos aciertosI Otras líneas poco utilizadas podrían no ser sustituidas nunca

Es necesario introducir un mecanismo que haga posible elegir quelínea se va a sustituirLa asociatividad es el primer paso

EC Tema 5 curso 2014/2015 17 / 41


Caché totalmente asociativaPermite que un bloque de memoria principal se cargue en cualquierlínea de la memoria cacheMientras la cache no está llena la asignación de línea no está fijadaCuando está llena se necesita un algoritmo de reemplazoTécnicamente, una cache asociativa es una memoria direccionable porcontenidoEn lugar de utilizar una dirección, se utiliza una etiqueta, y lamemoria la buscará en su directorio y devolverá el dato asociadoEsto es muy complejo y costoso porque todas las comparaciones serealizan en paralelo

EC Tema 5 curso 2014/2015 18 / 41


Algoritmos de reemplazoSu función es decidir qué línea sale de la cache cuando es necesarioun reemplazoSon algoritmos sencillos que se implementan en hardware

I FIFO (primero en entrar, primero en salir)I LRU (utilizado menos recientemente)I LFU (utilizado con menos frecuencia)I Aleatorio

EC Tema 5 curso 2014/2015 19 / 41


Asociatividad por conjuntosConsiste en dividir la cache en conjuntos de varias líneasDentro de cada conjunto la asociatividad es totalAl número de líneas por conjunto le llamamos número de víasCada dirección de memoria tiene asignado un conjunto de formadirecta, pero dentro de ese conjunto puede ir a cualquier líneaEs una solución intermedia entre la asociatividad total y lacorrespondencia directaConsigue resultados próximos a la asociatividad total con un costerazonable

EC Tema 5 curso 2014/2015 20 / 41


Resumen: formatos de las direcciones

EC Tema 5 curso 2014/2015 21 / 41

Escritura en la cachéCuando un programa escribe en memoria y el dato antiguo ya está enla cache:

I Se escribe sólo en la cache (Post-escritura ó write-back) y se indicaque esa línea ha sido modificada (mediante un bit de modificación)de forma que solo se escribe en niveles inferiores en caso de reemplazo

I Se escribe en la cache y en los niveles inferiores de la jerarquía dememoria (Escritura directa ó write-through)

Post-escritura reduce el número de escrituras a memoria principalporque:

I Si el valor se modifica varias veces sólo se copiará 1 vez a los otrosniveles de memoria

I Si se escriben palabras sueltas no se copiará toda la líneaEscritura directa puede resultar más segura porque:

I Siempre habrá una copia del dato actualizado en la memoria principal(consistencia cache)

I Cuando se produce un reemplazo con post-escritura es necesario copiarel nuevo valor a memoria al mismo tiempo que se lee el nuevo

EC Tema 5 curso 2014/2015 22 / 41

Escritura en la caché

Cuando un programa escribe en memoria y el dato antiguo no estáen la cache:

I La línea se carga (ubicar en escritura) y siguen las acciones de aciertode escritura (en post-escritura).

F Se busca que las escrituras subsiguientes en la línea no provoquen fallosI Se escribe directamente en otro nivel y la línea nunca viene a la cache

(no ubicar en escritura)F Las escrituras subsiguientes en la línea provocarán escrituras a memoriaF Este es un modo avanzado que requiere intervención del programador.

Se utiliza en programas que generan gran cantidad de resultados y enlos que la localidad temporal no se cumple de forma satisfactoria, p.e.muchos programas multimedia

EC Tema 5 curso 2014/2015 23 / 41

Índice

1 Introducción




EC Tema 5 curso 2014/2015 24 / 41

Rendimiento de la caché

Tipos de fallosForzosos:

I Se producen la primera vez que se referencia un dato/instrucciónI Se pueden reducir aumentando el tamaño de línea

De capacidad:I Cuando es referencia un dato que fue reemplazado porque la cache

estaba llenaI Se pueden reducir aumentando el tamaño de la cache

De conflicto (o de colisión):I En correspondencia directa ó asociativas por conjuntos cuando 2 líneas

compiten por la misma posición en la cacheI Se reducen aumentado la asociatividad de la cache

Esta clasificación se conoce como las 3 C (compulsory, capacity,conflict)

EC Tema 5 curso 2014/2015 25 / 41


MétricasTasa de aciertos: número de aciertos /total de referencias (h)Tasa de fallos: número de fallos / total de referencias (1 − h)Tiempo de acierto: tiempo de acceso a la caché (tca)Tiempo de fallo (tf ): tiempo de acceso a la caché (tca) +penalización por fallo (tp)Tiempo medio de acceso a memoria: tiempo de acierto + (tasa defallos × penalización por fallo)Ta = h × tca + (1 − h) × tf = tca + (1 − h) × tp

TCPU = NI × (CPIejecucion + (Accesos_memoriaInstrucciones ) × (1 − h) × tp) × Tciclo

EC Tema 5 curso 2014/2015 26 / 41


Posibilidades de configuraciónTamaño de la memoria cacheTamaño de líneaAsociatividad

I Correspondencia directaI Totalmente asociativa o por conjuntos

F Elección del algoritmo de reemplazo

Caches de datos e instruccionesCaches en varios nivelesPolítica de escritura

EC Tema 5 curso 2014/2015 27 / 41

Índice

1 Introducción



4 Técnicas de optimizaciónCachés de datos e instruccionesReducción de la tasa de fallosReducción de la penalización de falloReducción del tiempo de acierto

EC Tema 5 curso 2014/2015 28 / 41

Cachés de datos e instrucciones

Las cachés unificadas o mixtas, que contienen instrucciones ydatos, pueden ser un cuello de botella (instrucciones load y store)La CPU sabe si está emitiendo la dirección de una instrucción o undato, pudiendo separar puertosVentajas de las cachés separadas:

I Casi doblan el ancho de banda entre la CPU y la jerarquía de memoriaI Optimización por separado de cada cachéI Elimina fallos de conflicto entre instrucciones y datos

Inconvenientes:I Espacio fijo para instrucciones y datos: peor tasa de aciertosI Inconsistencia: instrucciones y datos en la misma línea, instrucciones

modificables

EC Tema 5 curso 2014/2015 29 / 41

Reducción de la tasa de fallosIncrementar el tamaño de línea

A mayor tamaño de línea:I Mayores oportunidades de aprovechar la localidad espacial (secuencial)

F Reduce los fallos forzososI A igual tamaño de cache, menor número de líneas

F Aumenta el número de reemplazos y puede incrementar los fallos deconflicto y los de capacidad

I Incrementa la penalización por fallo: mayor coste temporal de transferiruna línea

EC Tema 5 curso 2014/2015 30 / 41

Reducción de la tasa de fallos

Incrementar la asociatividadA mayor asociatividad:

I Menor número de fallos de conflictoI Caché más lenta: mayor tiempo de aciertoI Mayor coste

En la práctica, una caché asociativa por conjuntos de 8 vías es casitan efectiva como una caché totalmente asociativaUna caché de correspondencia directa tiene aproximadamente lamisma tasa de fallos que una caché asociativa por conjuntos de 2 víasde la mitad de tamaño

EC Tema 5 curso 2014/2015 31 / 41


Caché víctima

Caché pequeña totalmenteasociativaGuarda las líneas eliminadas dela caché en un falloAnte un fallo caché, si la línearequerida se encuentra en ella,se intercambia con una línea dela cachéEspecialmente útiles comocomplemento de caché de datospequeñas de correspondenciadirecta

EC Tema 5 curso 2014/2015 32 / 41


Cachés pseudo-asociativas

En un fallo, antes de ir al nivel inferior de la jerarquía de memoria, secomprueba otra línea de la memoria (pseudo-conjunto)Existen por tanto dos tiempos de aciertoPara no degradar el rendimiento, las líneas con aciertos de segundavez suelen moverse a su ubicación por defecto

EC Tema 5 curso 2014/2015 33 / 41


Optimizaciones en tiempo de compilaciónI Fusión de arraysI Intercambio de lazosI Fusión de lazosI Blocking

Prebúsqueda hardware/software

Estas técnicas se ven en las sesiones prácticas

EC Tema 5 curso 2014/2015 34 / 41

Reducción de la penalización de fallo

No esperar a almacenar toda la líneaRearranque anticipado: cuando llega la palabra se envía a la CPU ycontinúa la ejecuciónBúsqueda fuera de orden: requerir la palabra que falla y enviarla a laCPU. Esta continúa la ejecución mientras se llena la línea

Los beneficios dependen del tamaño de la línea y de la probabilidad deacceso a otra palabra de la misma línea

EC Tema 5 curso 2014/2015 35 / 41

Reducción de la penalización de falloCaché libre de bloqueo

Opciones:I Acierto bajo falloI Acierto bajo múltiples fallosI Fallo bajo fallo (bancos de memoria independientes)

Incrementa la complejidad del controlador de cachéNo afecta al tiempo de acierto

EC Tema 5 curso 2014/2015 36 / 41


Caché de dos niveles

Caché de primer nivel de velocidad comparable a la de la CPUCaché de segundo nivel de gran tamaño para capturar la mayoría delos fallos que irían a memoria principalLa ganancia radica en que la penalización de fallo del primer nivel decaché es el tiempo medio de acceso de la de segundo nivelLa velocidad de la caché del primer nivel afecta a la velocidad de relojde la CPU, y la de segundo nivel a la penalización de fallo de la deprimer nivelEl aumento de la asociatividad en el segundo nivel tiene poco impactoen el tiempo de acierto en este nivel, pero el aumento de la capacidaddisminuye también los fallos de conflicto y por tanto los beneficios dela asociatividad

EC Tema 5 curso 2014/2015 37 / 41



Caché de primer nivel de velocidad comparable a la de la CPUCaché de segundo nivel de gran tamaño para capturar la mayoría delos fallos que irían a memoria principalLa ganancia radica en que la penalización de fallo del primer nivel decaché es el tiempo medio de acceso de la de segundo nivelLa velocidad de la caché del primer nivel afecta a la velocidad de relojde la CPU, y la de segundo nivel a la penalización de fallo de la deprimer nivelEl aumento de la asociatividad en el segundo nivel tiene poco impactoen el tiempo de acierto en este nivel, pero el aumento de la capacidaddisminuye también los fallos de conflicto y por tanto los beneficios dela asociatividad

EC Tema 5 curso 2014/2015 38 / 41


Caché de dos nivelesGrandes tamaños llevan a incrementar el tamaño de la línea

I Distintos niveles de caché pueden tener distinto tamaño de líneaPropiedad de inclusión multinivel

I Todos los datos de la caché de primer nivel están en la del segundonivel

I Deseable para mantener la consistenciaI Algunos sistemas la cumplen y otros noI Se puede mantener con distintos tamaños de línea en las cachés

(mediante invalidación de líneas de primer nivel)En las cachés del segundo nivel, el énfasis se hace en la reducción defallos, usando cachés grandes, alta asociatividad y líneas grandes

EC Tema 5 curso 2014/2015 39 / 41



Tasa de fallos global

EC Tema 5 curso 2014/2015 40 / 41

Reducción del tiempo de acierto

Caché pequeñas y simples

El hardware pequeño es más rápidoEn una caché de correspondencia directa se puede solapar el chequeode la etiqueta con la transmisión de los datos

EC Tema 5 curso 2014/2015 41 / 41

documentt5

Documents