Apunte jerarquia de memorias PDF

Preview

Summary

Apunte jerarquia de memorias...

Description

Ingeniería Informática

Organización y Arquitectura de Computadoras

Instituto de Ingeniería - UNAJ

Jerarquía de Memoria

Cátedra de Organización y Arquitectura de Computadoras Ingeniería Informática

Autor: Ing. Jorge R. Osio Ing. Daniel Martín Morales Ing. Valentín Guarepi

Abril de 2013 Jerarquía de Memoria

Versión 1.0 Página 1

Ingeniería Informática

Organización y Arquitectura de Computadoras

INDICE. 1. Jerarquía de Memoria 2. Memoria CACHE 2.1.Impacto de la localidad temporal 2.2.Impacto de la localidad Espacial 2.3.Impacto combinado de la localidad temporal y espacial 2.4.Organización de la memoria cache.

Jerarquía de Memoria

Página 2

Ingeniería Informática

Organización y Arquitectura de Computadoras

Introducción Este apunte se encarga de definir la Jerarquía de Memoria en todo Sistema Computacional, en donde la representación de la jerarquía se puede definir como una pirámide en donde en la parte superior se encuentran los registros, como los elementos más cercanos al procesador, seguida a ellos La memoria cache, luego la memoria principal y por último el las memoria secundarias a las cuales se puede acceder por medio del módulo I/O.

Jerarquía de Memoria

Página 3

Ingeniería Informática

Organización y Arquitectura de Computadoras

1. Jerarquía de memoria Una jerarquía de memoria típica comienza con una unidad pequeña, cara, y relativamente rápida, llamada la memoria caché, seguida por una unidad de memoria principal más grande, menos costosa, y relativamente lenta. La Caché y la memoria principal se construyen utilizando material semiconductor de estado sólido (normalmente transistores CMOS). Es común llamar al nivel de memoria rápida la memoria primaria. La memoria de estado sólido es seguida por memoria más grande, menos costosa, y memorias magnéticas mucho más lentas que consisten típicamente en el disco (duro) y la cinta. Es común llamar al disco “memoria secundaria”, mientras que la cinta se llama convencionalmente memoria terciaria. El objetivo detrás del diseño de una jerarquía de memoria es tener un sistema de memoria que se comporta como si consistiera íntegramente de la unidad más rápida y cuyo costo está dominado por el costo de la unidad más lenta. La jerarquía de memoria se puede caracterizar por una serie de parámetros. Estos parámetros son el tipo de acceso, la capacidad, el tiempo de ciclo, la latencia, el ancho de banda, y el costo. El acceso se refiere a la acción que se lleva a cabo físicamente durante una operación de lectura o escritura. La capacidad de un nivel de memoria por lo general se mide en bytes. El tiempo de ciclo se define como el tiempo transcurrido desde el inicio de una operación de lectura hasta el inicio de una lectura posterior. La latencia se define como el intervalo de tiempo entre la solicitud de información y el acceso al primer bit de la información. El ancho de banda proporciona una medida del número de bits por segundo que puede ser accedido. El costo de un nivel de memoria por lo general se especifica en dólares por megabytes. El término acceso aleatorio se refiere al hecho de que cualquier acceso a cualquier ubicación de memoria necesita la misma cantidad de tiempo fijo, independientemente de la ubicación real de la memoria y / o la secuencia de accesos que se lleva a cabo. Por ejemplo, si una operación de escritura a la posición de memoria 100 toma 15 ns y si esta operación es seguida por una operación de lectura a la posición de memoria 3000, entonces la última operación también tomará 15 ns. Esto se puede comparar con el acceso secuencial en el que el acceso a la ubicación 100 toma 500 ns, y un acceso consecutivo a la ubicación 101 toma 505 ns, entonces se espera que un acceso a la ubicación 300 demande 1.500 ns. Esto es debido a que la memoria tiene que desplazarse a través de ubicaciones 100 a 300, por cada ubicación donde se requieren 5 ns. La eficacia de una jerarquía de memoria depende del principio de mover la información a la memoria rápida con poca frecuencia y acceder a ella muchas veces antes de realizar la sustitución por nueva información. Este principio es posible debido a un fenómeno llamado Jerarquía de Memoria

Página 4

Ingeniería Informática Organización y Arquitectura de Computadoras localidad de referencia, es decir, dentro de un período determinado de tiempo, los programas tienden a hacer referencia a un área relativamente confinada de memoria repetidamente. Existen dos formas de localidad, la localidad espacial y temporal. La Localidad espacial se refiere al fenómeno de que cuando se ha hecho referencia a una dirección dada, es muy probable que se haga referencia a las direcciones más cercanas en un corto período de tiempo; por ejemplo, instrucciones consecutivas en un programa secuencial sin saltos. La Localidad temporal, por otra parte, se refiere al fenómeno de que una vez que se ha hecho referencia a un ítem de memoria particular, es más probable que se haga referencia a dicho ítem nuevamente a continuación; por ejemplo, una instrucción en un bucle de programa. La secuencia de eventos que tiene lugar cuando el procesador realiza una solicitud a un elemento es la siguiente. En primer lugar, el elemento se busca en el primer nivel de la memoria de la jerarquía de memoria. La probabilidad de encontrar el elemento solicitado en el primer nivel se denomina la proporción de aciertos, h1. La probabilidad de no encontrar (falla) el elemento solicitado en el primer nivel de la jerarquía de memoria se llama proporción de falla (1 - h1). Cuando el elemento solicitado tiene una "fralla" se busca en el siguiente nivel de memoria posterior. La probabilidad de encontrar el elemento solicitado en el segundo nivel de memoria, está dado por la proporción de aciertos del segundo nivel h2. La proporción de falla en el segundo nivel de memoria es (1 - h2). El proceso se repite hasta que encontrar el elemento. Al encontrar el elemento solicitado, se copia y se envía al procesador. En una jerarquía de memoria que consta de tres niveles, el tiempo de acceso medio a la memoria se puede expresar de la siguiente manera:

El tiempo de acceso promedio de un nivel de memoria se define como el tiempo necesario para acceder a una palabra en ese nivel. En esta ecuación, t1, t2, t3 representan, respectivamente, los tiempos de acceso de los tres niveles.

2. Memoria CACHE La memoria caché debe su introducción a Wilkes en 1965. En ese momento, Wilkes se distingue entre dos tipos de memoria principal: La convencionales y la memoria de slave. En la terminología Wilkes, una memoria slave es un segundo nivel de memoria de alta Jerarquía de Memoria

Página 5

Ingeniería Informática Organización y Arquitectura de Computadoras velocidad convencional, que en la actualidad corresponde a lo que se llama la memoria cache (el término cache significa: un lugar seguro para esconder o almacenar cosas). La idea detrás de usar una memoria caché como el primer nivel de la jerarquía de memoria es para mantener la información que deba utilizarse con más frecuencia por la CPU en la memoria caché, la cual es una pequeña memoria de alta velocidad que está cerca de la CPU. El resultado final es que en un momento dado una parte activa de la memoria principal se duplica en la memoria caché. Por lo tanto, cuando el procesador realiza una solicitud a una referencia a la memoria, la solicitud se busca primero en la memoria caché. Si la solicitud corresponde a un elemento que actualmente reside en la caché, la llamamos un acierto de caché. Por otro lado, si la solicitud corresponde a un elemento que no está actualmente en la memoria caché, la llamamos error de caché. Una proporción de aciertos de caché, hc, se define como la probabilidad de encontrar el elemento solicitado en la caché. Una relación de falla de cache (1- hc) se define como la probabilidad de no hallar el elemento solicitado en la caché. En el caso de que el elemento solicitado no se encuentre en la memoria caché, tiene que ser traído de un nivel de memoria subsiguiente en la jerarquía de memoria. Suponiendo que existe el elemento en el siguiente nivel de memoria, es decir, la memoria principal, entonces tiene que ser copiado y se coloca en la memoria caché. Con la expectativa de que el siguiente elemento solicitado resida en la localidad vecina del elemento solicitado actual (localidad espacial), luego de un fallo de caché lo que realmente se copia de la memoria principal es un bloque de elementos que contiene el elemento solicitado. La ventaja de la transferencia de un bloque de la memoria principal a la memoria caché sería visible si se pudiera transferir tal bloque en el tiempo de acceso a la memoria principal. Esta posibilidad podría lograrse mediante el aumento de la velocidad a la que la información puede ser transferida entre la memoria principal y la memoria caché. Una posible técnica que se utiliza para aumentar el ancho de banda es el entrelazado (intercalado) de memoria. Para lograr mejores resultados, se puede asumir que el bloque traído desde la memoria principal a la memoria caché, en un fallo de caché, se compone de elementos que se almacenan en diferentes módulos de memoria, es decir, mediante el cual las direcciones consecutivas de memoria se almacenan en módulos de memoria sucesivas. La figura siguiente ilustra el caso simple de una memoria principal que consta de ocho módulos de memoria. Se supone en este caso que el bloque consta de 8 bytes.

Jerarquía de Memoria

Página 6

Ingeniería Informática

Organización y Arquitectura de Computadoras

Figura 1. Entrelazado de memoria usando 8 módulos Después de haber introducido la idea básica que lleva a la utilización de una memoria caché, nos gustaría evaluar el impacto de la localidad temporal y espacial en el rendimiento de la jerarquía de memoria. Para hacer este tipo de evaluación, limitaremos nuestra aplicación a un caso simple de una jerarquía que consta sólo de dos niveles, es decir, la memoria caché y la memoria principal. Se supone que el tiempo de acceso a la memoria principal es tm y el tiempo de acceso a la caché es tc. Vamos a medir el impacto de la localidad en cuanto al tiempo de acceso medio, que se define como el tiempo medio necesario para acceder a un elemento (una palabra) solicitada por el procesador de tal jerarquía de dos niveles. 2.1.Impacto de la localidad temporal En este caso, se supone que las instrucciones de bucles en un programa, que se ejecutan en muchas ocasiones, por ejemplo, n veces, una vez cargadas en la memoria caché, se utilizan más de una vez antes de ser reemplazadas por nuevas instrucciones. El tiempo medio de acceso, tav, en este caso está dado por

Jerarquía de Memoria

Página 7

Ingeniería Informática Organización y Arquitectura de Computadoras Al derivar la expresión anterior, se supone que el elemento de memoria solicitado ha provocado un fallo de búsqueda en caché, lo que conduce a la transferencia de un bloque de memoria principal en el tiempo tm. Después de eso, se realizaron n accesos al mismo elemento, en donde cada uno consumió un tiempo tc. La expresión anterior revela que a medida que el número de accesos al mismo elemento, n, aumenta, disminuye el promedio de tiempo de acceso, lo que es una característica deseable de la jerarquía de memoria. 2.2.Impacto de la localidad Espacial En este caso, se asume que el tamaño del bloque transferido desde la memoria principal a la memoria caché, luego de un fallo de búsqueda en la caché, es de m elementos. También asumimos que debido a la localidad espacial, fueron solicitados los m elementos, uno a la vez, por el procesador. Con base en estos supuestos, el tiempo promedio de acceso, tav, está dado por

Al derivar la expresión anterior, se supone que el elemento de memoria solicitado ha tenido un fallo de búsqueda en la cache, lo que conduce a la transferencia de un bloque de memoria principal, que consta de m elementos, en el tiempo tm. Después de eso, se hicieron m accesos, cada una a uno de los elementos que constituyen el bloque,. La expresión anterior revela que a medida que el número de elementos en un bloque, m, aumenta, disminuye el tiempo de acceso medio, una característica deseable de la jerarquía de memoria. 2.3.Impacto combinado de la localidad temporal y espacial En este caso, se supone que el elemento solicitado por el procesador tiene un fallo en la memoria caché que conduce a la transferencia de un bloque, que consta de m elementos, a la memoria caché (que lleva tm). Ahora, debido a la localidad espacial, el procesador requiere ejecutar todos los elementos que constituyen un bloque m, uno a la vez, (lo que requiere mtc). Después de eso, se accede al el elemento solicitado originalmente (n - 1) veces (localidad temporal), es decir, se produce un total de n veces el acceso a ese elemento. Con base en estos supuestos, el tiempo de acceso medio, tav, está dado por

Jerarquía de Memoria

Página 8

Ingeniería Informática

Organización y Arquitectura de Computadoras

Suponiendo que tm es ¼ de mtc. La expresión queda:

2.4.Organización de la memoria cache. Existen tres diferentes técnicas de organización utilizadas para la memoria caché. Las tres técnicas se discuten a continuación. Estas técnicas difieren en dos aspectos principales: 1. El criterio utilizado para la ubicación, en la memoria caché, de un bloque entrante desde la memoria principal. 2. El criterio utilizado para reemplazar un bloque de caché por un bloque de entrada (en caché completo). Mapeo directo: Este es el más simple entre las tres técnicas. Su simplicidad deriva del hecho de que se coloca un bloque de memoria principal entrante en una ubicación específica de un bloque de caché fijo. La ubicación se realiza sobre la base de una relación fija entre el número de bloque entrante, i, el número de bloque de caché, j, y el número de bloques de caché, N:

Ejemplo 1: Consideremos, por ejemplo, el caso de una memoria principal que consta de bloques de 4K, una memoria caché que consta de 128 bloques, y un tamaño de bloque de 16 palabras. La Figura siguiente muestra la división de la memoria principal y la memoria caché según la técnica de caché de asignación directa. Como muestra la figura, hay un total de 32 bloques de memoria principal que se asignan a un bloque de caché determinado. Por ejemplo, los bloques de memoria principal 0, 128, 256, 384,. . . , 3968 se asignan al bloque 0 de la cache. Por ello, llamamos técnica de asignación directa a una técnica de asignación de varios a uno. La principal ventaja de la técnica de asignación directa es su simplicidad para determinar dónde colocar un bloque de memoria principal de entrada en la caché. Su principal desventaja es el uso ineficiente de la memoria caché. Esto es porque de acuerdo con esta técnica, un número de bloques de Jerarquía de Memoria

Página 9

Ingeniería Informática Organización y Arquitectura de Computadoras memoria principal puede competir por un bloque de caché determinado incluso si existen otros bloques de caché vacíos. Esta desventaja puede llevar a lograr una proporción de aciertos de caché baja.

Figura 2. Mapeo de bloque de cache a bloque de memoria principal De acuerdo con la técnica de asignación directa la MMU interpreta la dirección emitida por el procesador dividiendo la dirección en tres campos como se muestra en la Figura anterior. Las longitudes, en bits, de cada uno de los campos son: 1. Campo palabra = log2 B, donde B es el tamaño del bloque es palabras. 2. Campo bloque = log2 N, donde N es el tamaño del bloque en la cache. 3. Campo etiqueta = log2 (M/N), donde M es el tamaño de la memoria principal en bloques. 4. El número de bits en la dirección de memoria principal = log2 (B x M) Cabe señalar que el número total de bits computado por las tres primeras ecuaciones debe agregarse a la longitud de la dirección de memoria principal. Esto se puede utilizar como un control para la corrección del cálculo. Ejemplo 2: Calculo de los cuatro parámetros anteriores para el Ejemplo 1. Campo de palabra = log2 B = log2 16 = log2 24 = 4 bits Campo bloque = log2 N = log2 128 = log2 27 = 7 bits Campo etiqueta= log2(M/N) = log2(22 x 210/27) = 5 bits El número de bits en la dirección de memoria principal = log2 (B x M) = log2 (24 x 212) = 16 bits.

Jerarquía de Memoria

Página 10

Ingeniería Informática

Organización y Arquitectura de Computadoras

Figura 3. Campos de direcciones de mapeo directo Mapeo asociativo: De acuerdo con esta técnica, un bloque de memoria principal de entrada se puede colocar en cualquier bloque de caché disponible. Por lo tanto, la dirección emitida por el procesador sólo necesita tener dos campos. Estos son los campos de palabra y etiqueta. El primero identifica el bloque durante su residencia en la memoria caché. El segundo campo identifica el elemento dentro del bloque que es solicitado por el procesador. La MMU interpreta la dirección emitida por el procesador dividiéndolo en dos campos tal como se muestra en la siguiente. La longitud, en bits, de cada uno de los campos están dados por: 1. Campo palabra = log2 B, donde B es el tamaño del bloque en palabras. 2. Campo etiqueta = log2 (M), donde M es el tamaño de la memoria principal en bloques. 3. El número de bits en la dirección de memoria principal = log2 (B x M) Cabe señalar que el número total de bits computado por las dos primeras ecuaciones debe agregarse a la longitud de la dirección de memoria principal. Esto se puede utilizar como un control para la corrección de su cálculo.

Figura 4. Campos de direccionamiento mapeo asociativo Ejemplo 3: Calcular los tres parámetros anteriores para un sistema de memoria que tiene la siguiente especificación: tamaño de la memoria principal es de bloques de 4K, el tamaño de la memoria caché es de 128 bloques, y el tamaño del bloque es de 16 palabras. Supongamos que el sistema utiliza la asignación asociativa. Campo palabra = log2 B = log2 16 = log2 24 = 4 bits Campo etiqueta = log2 M = log2 27 x 210 = 12 bits

Jerarquía de Memoria

Página 11

Ingeniería Informática Organización y Arquitectura de Computadoras El número de bit en la dirección de la memoria principal = log2 (B x M) = log2 (24 x 212) = 16 bits. Después de haber mostrado la división de la dirección de memoria principal, ahora podemos proceder a explicar el protocolo utilizado por la MMU para satisfacer una petición hecha por el procesador y así acceder a un elemento determinado. Presentamos el protocolo utilizando los parámetros indicados en el ejemplo presentado más arriba. Los pasos del protocolo son: 1. Utiliza el campo Etiqueta para buscar en la memoria coincidencia de la etiqueta con cualquiera de las etiquetas almacenadas. 2. Una coincidencia en la etiqueta de memoria indica que el bloque de caché específica la correspondencia determinada en el paso 1 con el elemento de memoria principal solicitado por el procesador, es decir, un de acierto de caché. 3. Entre los elementos contenidos en el bloque de caché, el elemento apuntado se puede seleccionar utilizando el campo Palabra. 4. Si en el paso 2, no se encuentran coincidencias, entonces esto indica un error de caché. Por lo tanto, el bloque requerido tiene que ser traído desde la memoria principal, depositado en el primer bloque de caché disponible, y el elemento apuntado (palabra) se pone a disposición del procesador. La etiqueta de la memoria caché y los bloques de la memoria caché en consecuencia tienen que actualizarse. Mapeo asociativo por conjuntos: En la técnica de asignación asociativa por conjuntos, la memoria caché se divide en un número de conjuntos. Cada conjunto consiste en un número de bloques. Un dado bloque de memoria principal a uno de memoria caché concreto se establece en función de la ecuación s = i mod S, donde S es el número de conjuntos en la memoria caché, i es el número de bloques de la memor...