S04 - myTeachingURJC/Arq-computadores-01 GitHub Wiki

Sesión de Teoría 4: Jerarquía de Memorias

  • Tiempo: 2h
  • Objetivos de la sesión:
    • Concepto de Jerarquía de memorias
    • Memoria Caché
    • Ejemplos
    • Ejercicios

Contenido

Introducción

En la primera sesión vimos la Jerarquía de memorias una de las 8 grandes ideas en la Arquitectura de los computadores.

Hoy vamos a entrar con más profundidad en este concepto e introduciremos las memorias caché, cómo funcionan, sus ventajas y algunos ejemplos para entender su utilidad.

Jerarquía de memorias

Todavía no hemos explicado en profundidad cómo es un computador por dentro y cómo funciona, así que utilizaremos la definición de computador vista en la S1, donde consta de un Procesador, Memoria y Entradas y Salidas.

En la memoria es donde se almacena, tanto el programa que se ejecuta en la CPU, como los distintos datos que utiliza (variables, arrays, estructuras, ...). La CPU por lo tanto, accede a la memoria constantemente, ya sea para leer los datos de las variables que necesita, como para leer la siguiente instrucción de código que tiene que ejecutar. Por lo tanto, el acceso a memoria es una operación cŕitica para aumentar el rendimiento de un ordenador. Habitualmente, las instrucciones con un mayor CPI son las de acceso a memoria.

Sin embargo, aunque la velocidad de los procesadores aumenta progresivamente cada año, la velocidad de las memorias no lo hace al mismo ritmo.

Como podemos observar, las memorias son cada vez más lentas en comparación con los procesadores, hay que buscar una solución! Esta solución consiste en aplicar la Jerarquía de memorias.

A la hora de construir una memoria de datos, existen distintas tecnologías, cada una con sus pros y contras. Estos son los 4 tipos de memoria que podemos encontrar:

  • Registros: Son la memoria más rápida del sistema, integrados directamente en el procesador. Su capacidad es extremadamente limitada, de solo unas pocas decenas o centenas de bytes, ya que aumentar su número incrementaría mucho la complejidad y el coste del procesador. Por ello, solo se usan para almacenar datos temporales y variables de trabajo inmediato de la CPU.

  • SRAM: Es una memoria muy rápida utilizada en las cachés del procesador. Su tecnología se basa en celdas de 6 transistores por bit, lo que le permite ofrecer una latencia muy baja. El coste por bit es elevado debido al alto número de transistores y su estructura interna dificulta enormemente su escalado y la fabricación de memorias de gran tamaño. Es por esto que solo se utiliza en memorias donde la velocidad es crítica.

  • DRAM: Es la tecnología utilizada para la memoria principal de los ordenadores. Cada bit se almacena mediante un condensador y un transistor, lo que permite fabricar chips de gran capacidad (varios gigabytes) a bajo coste por bit. Sin embargo, el condensador se descarga con el tiempo, por lo que la DRAM necesita ser refrescada constantemente, lo que aumenta su latencia respecto a la SRAM. Aunque es mucho más lenta que la caché, su relación capacidad/precio es óptima para grandes cantidades de memoria.

  • Memoria Flash/Disco Magnético: Ofrecen una capacidad muy alta y un coste por bit muy bajo, lo que las hace ideales para almacenamiento masivo. Sin embargo, su latencia y velocidad de acceso son mucho menores que las de la memoria principal, por lo que se utilizan para guardar datos de forma permanente y no como memoria de trabajo del procesador.

Tipo de Memoria Capacidad Latencia Costo/GB
Registro Miles de bits 20 ps €€€€
SRAM ~10 KB - 10 MB 1-10 ns ~€1000
DRAM ~10 GB 80 ns ~€10
Flash ~100 GB 100 µs ~€1
Disco Magnético ~1 TB 10 ms ~€0.10

Con estos datos de los distintos tipos de memorias existentes, podemos observar que no existe una opción adecuada que cumpla los requisitos que necesitamos: Gran capacidad, Baja latencia y Bajo coste. Sin embargo, podemos combinarlas todas para obtener una memoria tan rápida como la SRAM y con la capacidad de almacenamiento y el precio de una Flash, utilizando la Jerarquía de memorias

IMAGEN JERARQUIA

Memoria caché

La memoria caché consiste en añadir a la memoria principal, otra memoria de menor capacidad, pero con muy baja latencia, ya que utilizará la tecnología SRAM

¿Por qué funciona?

Vamos a ver una representación de los accesos a memoria de un programa. Normalmente los programas contienen bucles, que hacen que se repitan una serie de instrucciones que están una detrás de otra, y acceden a datos y estructuras de datos como arrays, que tienen sus valores uno al lado del otro

Fijate como, en un intervalo de tiempo corto, las posiciones de memoria a las que se accede están habitualmente cerca unas de otras. A esta propiedad se le conoce como Localidad de Referencia, y es de dos tipos:

  • Localidad Espacial: Las zonas de memoria próximas a las zonas ya referenciadas, tienen una alta probabilidad de ser referenciadas en un futuro cercano.

  • Localidad Temporal: Las zonas de memoria accedidas recientemente, tienen una alta probabilidad de ser referenciadas en un futuro cercano.

Por la tanto, si este principio se cumple en la mayor parte de los casos, almacenar la parte de la memoria que se está utilizando y las zonas contiguas debería acelerará el acceso a memoria.

Funcionamiento Memoria Caché

El funcionamiento del acceso a memoria utilizando caché es el siguiente:

  • Se requiere un acceso a memoria.

  • Se intenta leer de la caché.

  • Si está en la caché (acierto), se devuelve el valor.

  • Si no está en la caché (fallo), se lee de la memoria principal, se devuelve el dato y se actualiza la caché.

Para saber en qué medida mejora la caché el tiempo de acceso a memoria, necesitamos conocer el número de veces que se requiere un acceso a memoria Nr, el número de veces que ese dato está en la caché, o número de aciertos Na y el número de veces que no está y hay que leer de la memoria principal, o número de fallos Nf.

Con estos datos, calcularemos las tasas de acierto y de fallo de la siguiente manera:

El tiempo medio de acceso a memoria dependerá del tiempo que se tarda en acceder a la caché T_acceso y de la penalización que conlleva fallar (no poder acceder al dato en la caché), y tener que leer de la memoria principal, mucho más lenta T_penalizacion

Cachés de varios niveles.

Como hemos visto, el tiempo de acceso a la caché depende también de su tamaño: en general, las cachés de menor capacidad tienen una latencia más baja que las de mayor capacidad. Esto se debe, entre otros factores, a que gestionar y buscar datos en una caché más grande implica una mayor complejidad interna y, en algunos casos, comprobar más direcciones posibles. Este comportamiento recuerda al problema de las distintas tecnologías de memoria: las SRAM son rápidas pero costosas y de poca capacidad, mientras que las DRAM son más lentas pero permiten mayor densidad y menor precio. De forma similar, la memoria caché está organizada en una jerarquía de varios niveles (normalmente 3): las de menor tamaño (L1) son las más rápidas y cercanas al procesador, y las de mayor tamaño (L2, L3) son más lentas pero pueden almacenar más información. Así, el concepto de jerarquía de memorias se aplica tanto entre diferentes tecnologías como dentro de la propia caché del sistema.

El funcionamiento de una caché de varios niveles es similar al de la caché que habíamos visto anterioremente: Si se requiere un dato que no está en L1 (fallo), se intenta recuperar de L2, si no está de L3 y si tampoco está, se obbtiene finalmente de la memoria principal.

EL tiempo de acceso total, se puede obtener con la misma expresión anterior, ampliada de forma recursiva de la siguiente manera:

Elementos de diseño

A la hora de analizar una memoria caché, existen distintos aspectos de diseño que influyen en su rendimiento y que definen la forma en que se almacenan y actualizan los datos en la memoria caché. De entre todos los elementos de diseño, sólo veremos brevemente la Función de correspondencia y los Algoritmos de sustitución.

Función de correspondencia

Esta función determina en qué posición de la Memoria Caché (Mc) se almacenará un bloque de datos de la Memoria Principal (Mp). Existen 3 tipos de funciones de correspondencia:

  • Correspondencia Directa: El bloque de la Mp se ubica en la dirección de memoria del bloque, a la cual se le aplica el módulo con el tamaño de la Mc. Los datos almacenados en la Mc tendrán que tener una etiqueta con el resto de la dirección para conocer la dirección real del dato almacenado. Ejemplo: Tenemos una Mp que tiene capacidad para 1.000 bloques y una Mc para 100. Si queremos guardar el bloque de la Mp con dirección 435, se guardará en la dirección 435 mod 100 = 35 de la memoria caché. La etiqueta que tendrá dicho dato sera "4". De igual forma, si almacenamos el dato con dirección de la Mp 213, se almacenará en la posición 13 de la Mc con etiqueta "2".

  • Correspondencia Asociativa: El bloque de la Mp se puede ubicar en cualquier dirección de la Mc. Ejemplo: El dato de la Mp en la posición 435, se podrá almacenar en cualquier posición de la Mc con etiqueta "435".

  • Correspondencia Asociativa por conjuntos: Combina las dos anteriores. La Mc se divide en V conjuntos de k bloques. El tamaño de la Mc es v * k. Un bloque se almacenará en el conjunto dirección modulo v. Ejemplo: Ahora, la Mc tiene 10 conjuntos de 10 bloques, v = 10, k = 10. Si queremos guardar el bloque de la Mp con dirección 435, se guardará en el bloque 5, con etiqueta "43".

Algoritmos de sustitución

Definen qué dato de la memoria caché se debe sobreescribir para almacenar un nuevo bloque de memoria.

Para las funciones de correspondencia Asociativa y Asociativa por conjuntos, la posición concreta dentro de la memoria caché se puede asignar siguiento distintos algoritmos, como son: De forma aleatoria, sustituyendo al bloque que más tiempo lleva sin usarse (LRU), al que lleva más tiempo en la caché o al menos referenciado. La elección de qué algoritmo usar hay que evaluarla para cada caso concreto, ya que un algoritmo puede hacer que la Mc mantenga datos más relevantes, pero si es demasiado complejo, puede aumentar el retardo y coste/complejidad de la memoria. Ejemplo: El algoritmo aleatorio puede borrar un bloque muy utilizado que convendría mantener, pero es muy rápido y fácil de implementar, mientras que el que sustituye el bloque menos utilizado, implica implementar un contador para cada bloque.

Para la Función de Correspondencia Directa, cada bloque de datos tiene ya asignada una posición en la MC, por lo que no tiene sentido hablar de algoritmos de sustitución.

Ejemplos reales y aplicaciones.

A continuación, vamos a ver ejemplos reales de cómo puede afectar la forma en la que programamos, con cómo se gestiona la memoria caché, y cómo esto puede afectar al rendimiento.

Código optimizado para memoria caché

En este primer ejemplo, vamos a ejecutar dos bucles que hacen exactamente lo mismo, recorrer una matriz. En el primer bucle, buscaremos recorrer la matriz de forma que los elementos a los que se accede estén en zonas de memoria cercanas, mientras que en el segundo ejemplo, buscaremos justo lo contrario, acceder a los elemntos de la matriz dando saltos en la memoria.

Para entender mejor este ejemplo, es necesario saber, que una matriz 2D, se almacena en memoria fila a fila de manera contigua, de tal forma que todos los elementos de una fila están juntos. Conociendo esto, si recorremos la matriz por filas, al estar los elementos más próximos unos de otros, se aprovechará mejor la caché, y será maś rápido que recorrer la matriz por columnas.

Copia el siguiente código en tu ordenador, ejecútalo, y evalúa los tiempos que tarda cada bucle.

# Ejemplo de la diferencia de rendimiento al acceder a arrays por filas o columnas

import time
import random

N = 3000 

# Crear una matriz 2D con números aleatorios
A = [[random.random() for _ in range(N)] for _ in range(N)]

# Acceso por filas
start = time.time()
suma_filas = 0
for i in range(N):
    for j in range(N):
        suma_filas += A[i][j]
print("Tiempo por filas:", time.time() - start)

# Acceso por columnas
start = time.time()
suma_columnas = 0
for j in range(N):
    for i in range(N):
        suma_columnas += A[i][j]
print("Tiempo por columnas:", time.time() - start)

El resultado obtenido debería ser algo parecido a esto:

Tiempo por filas: 0.500237226486206
Tiempo por columnas: 1.1540553569793701

Fíjate cómo se duplica el tiempo de ejecución simplemente por acceder a elementos contiguos y hacer un buen uso de la caché.

Aplicación del concepto de memoria caché a la programación.

El concepto de jerarquía de memorias y memoria caché, ha demostrado ser muy útil para acelerar el acceso a memoria de los procesadores. Sin embargo, este concepto es una de las 8 Grandes ideas que se pueden aplicar a todo tipo de problemas. El siguiente código, muestra un ejemplo de un programa que tiene que obtener datos de una BBDD. El acceso a la base de datos se realiza con get_data(key), y conlleva una espera simulada. El acceso se realiza varias veces en un bucle. Vamos a modificar el siguiente ejemplo de python, añadiendo una "caché", para intentar acelerar el proceso. Como puedes ver, el bucle principal está repetido, y al final del programa se muestra el tiempo de ejecución de cada uno. Añade la caché en el segundo bucle para mejorar su tiempo.

# Simulación de acceso a base de datos y mejora utilizando caché

import time
import random

# Simulamos la base de datos: acceso lento
def get_data(key):
    time.sleep(0.005)  # Simula la latencia (50 ms)
    return key**2      # Simula dato devuelto

# Lista de claves que consultaremos
keys = [k + random.randint(1, 5) for k in range(1000)]

# Primer bucle: sin caché
start = time.time()
results_no_cache = []
for key in keys:
    result = get_data(key)
    results_no_cache.append(result)
time_no_cache = time.time() - start

print(f"Tiempo sin caché: {time_no_cache:.2f} segundos")

#--- Modificalo para añadir una caché  ---#
cache = []
def get_data_cache(key):
    return get_data(key)

#-----------------------------------------#


# Segundo bucle: con caché
start = time.time()
results_cache = []
for key in keys:
    result = get_data_cache(key) 
    results_cache.append(result)
time_cache = time.time() - start

print(f"Tiempo con caché: {time_cache:.2f} segundos")

Analizar el rendimiento de la memoria caché en RARS

Desde el RARS se puede simular el rendimiento de una memoria caché para un programa.

Para ello ve a Tools>Data Cache Simulator

Aquí puedes configurar distintos aspectos de la MC, como el tamaño de la MC, el tamaño del bloque, la Función de Correspondencia o el Algoritmo de Sustitución

Un vez configurado, pulsa en Connect to Program y ejecuta el código que quieras probar.

Cuando termina de ejecutarse, podrás ver las estadísticas de aciertos y fallos de la ejecución.

Ejercicios

Ejercicios para practicar los conceptos. Hazlos. Busca qué ecuaciones necesitas. Practica. Una vez hechos comprueba tus resultados con las soluciones

Ejercicio 1

Un procesador que funciona a 2 GHz ejecuta 100 instrucciones. El procesador tiene 2 MC, una de instrucciones (MI) y otra de datos (MD) y el retardo de lectura en ambas es de 8ns.

La MI tiene una tasa de fallos del 4% y una penalización por fallo de 100 ns. La MD tiene una talla se fallos del 8% y una penalización por fallo de 115 ns

Para ejecutar las 100 instrucciones hacen falta 100 accesos a la memoria de instrucciones y 25 a la de datos

¿Cuánto tiempo de acceso a memoria provocarán las 100 instrucciones?

Ejercicio 2

Tenemos un procesador con una Memoria Caché de dos niveles (L1 y L2) con las siguientes características:

  • El tiempo de acceso de L1 es de 1 ns.

  • La tasa de fallos de L1 es del 10%.

  • El tiempo de acceso de L2 es de 12 ns.

  • La tasa de fallos de L2 es del 5%.

  • El tiempo de acceso a Mp es de 110ns.

a) Calcula el tiempo medio de acceso a memoria.

b) Si la memoria caché no tuviera el segundo nivel, es decir, sólo incluyera L1 y Mp, ¿Cuál sería el tiempo medio de acceso a memoria? ¿Merece la pena incluir el segundo nivel?

Ejercicio 3

Tenemos un procesador con una Memoria Caché de un solo nivel con las siguientes características:

  • El tiempo de acceso a MC es de 8 ns.

  • El tiempo de acceso a MP es de 110ns.

Calcula la tasa de fallos máxima que podemos tener para que nos compense el uso de esta memoria caché.

Referencias

Resolución de los Ejercicios de PRACTICAS

Resolución de los ejercicios de la sesión 2 de Prácticas

Recuerda que las soluciones están disponibles, por si las quieres ver por tu cuenta

Autores

Licencia

Enlaces