Tema 2 Definiciones y conceptos básicos



Descargar 424.76 Kb.
Página5/8
Fecha de conversión12.11.2017
Tamaño424.76 Kb.
1   2   3   4   5   6   7   8

Tabla 2.12: Parámetros del ejemplo propuesto con organización con correspondencia totalmente asociativa



Figura 2.43: Ejemplo de correspondencia totalmente asociativa
Cuando se lee un nuevo bloque con la correspondencia totalmente asociativa es posible decidir por cuál se va a sustituir en la memoria caché. Los algoritmos de reemplazamiento, que se ven posteriormente, se diseñan con el fin de optimizar la probabilidad de encontrar la palabra solicitada en la Mca. La principal desventaja de este procedimiento es la necesidad de una circuitería, bastante compleja, para examinar en paralelo los campos de etiqueta de todas los bloques de la memoria caché.
Correspondencia asociativa por conjuntos

Esta técnica es un compromiso que trata de aunar las ventajas de los dos métodos anteriores. Para su aplicación, la memoria caché se divide en g conjuntos, cada uno de los cuales consta de r bloques. Se tiene que:

C=q × r

i = j módulo q


donde

q = número de conjuntos en los que se divide la Mca

r = número de bloques que contiene cada uno de los conjuntos

i = número de bloque de la Mca

j = número de bloque de la Mp

C = número de bloques que contiene la Mca

Cada bloque de la memoria principal puede ubicarse en uno de los r bloques de la memoria caché que componen cada conjunto. Este número r define el grado de asociatividad de la Mca. Con este algoritmo, el bloque j de la Mp se puede almacenar en un bloque cualquiera del conjunto que tiene asociado en la Mca. En la Figura 2.44 se muestra un ejemplo para el caso en que r = 2 (por lo que q = C/2). La correspondencia asociativa por conjuntos se puede ver como una correspondencia directa entre los bloque de la Mp y los conjuntos de la Mca y como una correspondencia totalmente asociativa entre los bloques de un mismo conjunto.



Figura 2.44: Asignación de bloques de la Mp en la Mca con correspondencia asociativa por conjuntos
La Figura 2.45 ilustra el mecanismo general de la correspondencia asociativa por conjuntos. Cuando la CPU genera una dirección para acceder a una palabra de la Mp, su formato desde el punto de vista de la Mca, se divide en tres campos: etiqueta, conjunto y palabra. El número de bits de cada uno de estos campos viene dado por las relaciones siguientes:

campo palabra: p =log2(k) campo conjunto: c = log2(q) campo etiqueta: e = n - p - c (2.6)
Los c bits del campo conjunto especifican uno de entre q = 2C conjuntos en los que se divide la Mca. Los e + c bits de los campos de etiqueta y conjunto especifican uno de los M = 2n-p bloques de Mp. Cada bloque en cada conjunto tiene una etiqueta almacenada que conjuntamente con el número del conjunto completa la identificación del bloque de la Mca El funcionamiento de la correspondencia asociativa por conjuntos se puede describir en los términos que siguen:

1) En primer lugar se utiliza el número de conjunto de la dirección solicitada por el procesador para acceder al conjunto correspondiente de la Mca.

2) Se comparan simultáneamente todas las etiquetas del conjunto seleccionado con la etiqueta de la dirección solicitada. Si coinciden entonces se accede a la palabra pedida en la Mca, en caso contrario se produce un fallo y habrá que ir a buscar la palabra a Mp.



Figura 2.45: Organización de una memoria caché con correspondencia asociativa por conjuntos

En el ejemplo que se considera (ver Figura 2.46) hay 32 conjuntos con 2 bloques/conjunto (q = 32 = 25, r = 2). Los cinco bits del campo conjunto (q = 25  c = 5), identifican a un único conjunto de dos bloques dentro de la Mca. También indica el número del bloque (módulo 25) de la Mp que se transfiere al bloque correspondiente de la memoria caché. Así los bloques 00008, 00408, 01008, 01408,… (expresados en base octal) de la memoria principal se transforman en el conjunto 0 de la memoria caché (i = 0), ya que:

00008=010  i=010mod3210=0

00408=3210  i=3210mod3210=0

01008 = 64l0 i = 6410 mod 3210 = 0, etc.

Como este conjunto contiene 2 bloques, los bloques de la Mp se pueden cargar en cualquiera de ellos. Ninguno de los dos bloques que se transforman en el mismo conjunto de la Mca pueden tener números de etiquetas iguales. En una operación de lectura, los cinco bits del campo conjunto se utilizan para determinar que conjunto de dos bloques hay que examinar. Después se comprueban los dos bloques del conjunto que corresponda para ver si hay coincidencia con el número de etiqueta de la dirección a la que se desea acceder.





Figura 2.46: Correspondencia asociativa por conjuntos
La correspondencia asociativa por conjuntos contiene las dos técnicas anteriores como casos particulares:

a) q = C, r = 1 => correspondencia directa

b) q = 1, r = C => correspondencia totalmente asociativa

La utilización de q = C/2, r = 2 (es decir, 2 bloques por conjunto), es la organización más usual en la correspondencia asociativa por conjuntos. En este caso, se mejora significativamente el rendimiento de la caché frente a la transformación directa. También se emplea q = C/4, r = 4 (es decir, 4 bloques por conjunto) que proporciona una relativa mejora a un coste moderado. A partir de este valor, el beneficio marginal que se obtiene al aumentar el número de particiones por conjunto no compensa, por el mayor coste que supone.


2.4.4 Algoritmos de reemplazamiento

Cuando un nuevo bloque se transfiere a la memoria caché debe sustituir a uno de los ya existentes. En el caso de la correspondencia directa la partición está determinada unívocamente y por lo tanto no se puede realizar ninguna elección. Por el contrario, en las técnicas de tipo asociativo es necesario un algoritmo de reemplazamiento. Este mecanismo de sustitución debe realizarse totalmente por hardware y preferiblemente de manera que la selección se haga toda ella durante el ciclo de memoria principal de búsqueda del nuevo bloque. Lo ideal sería que el bloque sustituido no se necesitase utilizar otra vez en el futuro, sin embargo estas circunstancias no pueden conocerse a priori y la decisión de qué bloque hay que reemplazar debe basarse sobre hechos conocidos en el momento de tomarla. Deforma general los algoritmos de sustitución de bloques de la Mca se pueden clasificar en dos grandes grupos: los que están basados en su utilización y aquellos que no toman en cuenta esta consideración. No obstante en los dos casos un factor crítico es a menudo la cantidad de hardware que se necesita para implementar el algoritmo.

Para una Mca con organización totalmente asociativa cualquier algoritmo de reemplazamiento que se base en la utilización de los bloques debe considerar como posibles candidatos todos los bloques en el momento de tomar la decisión. Por el contrario si la organización de la Mca es asociativa por conjuntos sólo deberá considerar los bloques de un determinado conjunto (aunque será preciso mantener un cierto registro del uso relativo de los bloques en cada conjunto). Del razonamiento expuesto se sigue sin embargo que cualquiera que sea el algoritmo empleado (basado en la utilización de los bloques o no), hay generalmente menos bloques que considerar en una Mca asociativa por conjuntos que en una totalmente asociativa y por lo tanto se requerirá un hardware más simple. El caso límite es cuando hay dos bloques/conjunto (r = 2) que sólo requiere un bit adicional por conjunto para indicar que bloque se debe reemplazar. El grado de asociatividad de las cachés, como ya se ha dicho anteriormente es pequeño (r = 2 ó 4). Entre los diferentes algoritmos que se han propuesto merecen destacarse los cuatro siguientes:

a) Bloque elegido de forma aleatoria

b) Bloque utilizado menos frecuentemente. Algoritmo LFU (Least Frequently Used)

c) Bloque más antiguo en memoria caché. Algoritmo FIFO (First In First Out)

d) Bloque estilizado menos recientemente. Algoritmo LRU (Least Recently Used)
Bloque elegido de forma aleatoria

Este método toma de forma aleatoria un bloque de la Mca y lo sustituye por el bloque de la Mp que contiene a la palabra a la que se acaba de acceder. Es muy fácil de implementar en hardware y es más rápido que la mayoría de los otros algoritmos. Su desventaja obvia es que el bloque que es más probable que se vaya a utilizar otra vez tiene la misma probabilidad de ser sustituido que cualquier otro bloque. Esta desventaja se ve mitigada cuando el tamaño de la Mca aumenta.


Bloque utilizado menos frecuentemente
Este método supone que los bloques que no se referencian con frecuencia no se necesitan tanto. Cada bloque de la Mca incorpora un contador que almacena el número de veces que dicho bloque se ha utilizado desde que fue transferido a la memoria caché. El bloque que tenga el mínimo valor en su contador es el que se sustituye. La ventaja que presenta este algoritmo de reemplazamiento es que el bloque que se utiliza frecuentemente es más probable que permanezca en la Mca y no así el que no se referencia a menudo. Una desventaja que es consustancial a este método es que penaliza en exceso a los bloques que se han transferido recientemente a la MU« ya que necesariamente tendrán un contador con un valor muy bajo a pesar de que es probable que serán utilizados otra vez en el futuro inmediato. Otra desventaja es que el método es más difícil de implementar en términos de hardware y es por lo tanto más costoso.
Bloque más antiguo en memoria caché

Este método elimina de la Mca el bloque que ha permanecido durante más tiempo. El algoritmo de primero en entrar primero en .salir se realiza de forma natural con una cola de direcciones de bloques, sin embargo se puede implementar más fácilmente con contadores. En una Mca totalmente asociativa sólo es preciso un contador y para una Mca asociativa por conjuntos se requiere un contador por cada conjunto. En ambos casos los contadores deberán tener un número suficiente de bits para identificar completamente al bloque.


Bloque utilizado menos recientemente

Este método tiene el mejor rendimiento en relación con su coste cuando se le compara con las otras técnicas y es el que más se utiliza en los sistemas reales. La idea en la que se fundamenta el algoritmo es que un bloque que no se ha utilizado durante un largo período de tiempo tiene una probabilidad menor de ser utilizado en el futuro inmediato de acuerdo con el principio de localidad temporal. Así, este método retiene bloques en la Mca que son más probables que puedan ser utilizados otra vez. Para lograrlo se emplea un mecanismo que almacena qué bloques han sido accedidos más recientemente. El bloque que se elimina de la Mca es el que no se ha referenciado durante el período más largo de tiempo. Una forma de implementar esta técnica es asignar un contador a cada bloque de la Mca. Cada vez que se accede a la Mca cada contador de bloque se incrementa en uno salvo el contador del bloque al que se accedió que se inicializa a cero. De esta forma el bloque cuyo contador tiene el máximo valor es el utilizado menos recientemente. El valor de cada contador indica así la edad de un bloque desde la última vez que se referenció.



El algoritmo para estos registros de envejecimiento se puede modificar para tomar en cuenta el hecho de que los contadores tienen un número fijo de bits y que sólo se precisa la edad relativa entre ellos. Si no se tuviese esto en cuenta se produciría un desbordamiento del contador que alteraría el resultado convirtiendo al bloque que más tiempo hace que se utiliza en el que menos. El algoritmo es el siguiente:
1) Cuando ocurre un acierto, el contador asociado con ese bloque se inicializa a cero, lo que indica que es el que se ha utilizado más recientemente. Todos los contadores que tienen un valor más pequeño que el que tenía el contador del bloque accedido se incrementan en uno. Todos los contadores que tienen un valor mayor que el que tenía el contador del bloque accedido no se modifican.
2) Cuando ocurre un fallo y la Mca no está llena, el contador asociado con el bloque que proviene de la Mp se inicializa a cero y todos los otros contadores se incrementan en uno. Si la Mca está llena, entonces se sustituye el bloque que tiene el contador con el máximo valor (p. ej. 3 para un contador de 2 bits) y se inicializa a cero su contador; todos los otros contadores se incrementan en uno.
Con este algoritmo el contador con el máximo valor identifica al bloque utilizado menos recientemente.
En la Tabla 2.13 se muestra un ejemplo de una Mca asociativa por conjuntos con 4 bloques/conjunto (q = 4). Un contador de 2 bits es suficiente para cada bloque y C0, C1, C2 y C3, representan los contadores en un conjunto. Al comienzo del algoritmo todos los contadores se inicializan a cero. Se observa que cuando un bloque de la Mp sustituye a otro en la Mca cambia el valor de la etiqueta que referencia de forma unívoca a cada bloque.

N° acceso

Etiqueta

Acierto/Fallo

C0

C1

C2

C3

Acciones










0

0

0

0

Inicialización

1

5

Fallo

0

1

1

1

Bloque 0 rellenado

2

6

Fallo

1

0

2

2

Bloque 1 rellenado

3

5

Acierto

0

1

2

2

Bloque 0 accedido

4

7

Fallo

1

2

0

3

Bloque 2 rellenado

5

8

Fallo

2

3

1

0

Bloque 3 rellenado

6

6

Acierto

3

0

2

1

Bloque 1 accedido

7

9

Fallo

0

1

3

2

Bloque 0 sustituido

8

10

Fallo

1

2

0

3

Bloque 2 sustituido

Tabla 2.13: Algoritmo LRU utilizando contadores
2.4.5 Estrategia de escritura

Para que pueda reemplazarse un bloque residente en la memoria caché, es necesario considerar si ha sido modificado en la Mca pero no en la Mp. Si no lo ha sido, se puede reescribir sobre el bloque antiguo de la memoria caché. Si se ha modificado el bloque, significa que al menos se ha realizado una operación de escritura sobre una palabra de ese bloque de la memoria caché y se debe actualizar la memoria principal. Hay una serie de estrategias de escritura, cada una de ellas con un coste y un rendimiento asociado. En general se plantean dos problemas.


a) Más de un dispositivo puede tener acceso a la memoria principal. Por ejemplo, un módulo de E/S puede ser capaz de leer/escribir directamente a memoria. Si una palabra ha sido modificada solamente en la memoria caché, entonces la palabra de memoria principal correspondiente ya no es válida. Por otra parte, si el dispositivo de E/S lo que ha alterado es la memoria principal, no es válido el contenido de dicha palabra en la memoria caché.
b) Varias CPU's se conectan a un mismo bus y cada una de ellas tiene su propia memoria caché local. En este caso, si se cambia una palabra en una memoria caché podría invalidar una palabra en otras memorias cachés.

La técnica más simple se denomina escritura inmediata (write through). Consiste en efectuar todas las operaciones de escritura tanto en la memoria principal como en la memoria caché, lo que asegura que sus contenidos son siempre válidos. Cualquier otro módulo CPU-memoria caché puede supervisar el tráfico con la memoria principal, para mantener la consistencia dentro de su propia memoria caché. La principal desventaja de esta técnica es que genera un tráfico elevado con la memoria y esto puede crear una saturación que disminuye significativamente el rendimiento del sistema.

Una técnica alternativa que minimiza las escrituras en memoria, consiste en realizar las actualizaciones sólo en la memoria caché. Este método se conoce como post-escritura (write back). Cuando se produce una modificación se pone a 1 un "bit de actualización" asociado con cada bloque de la memoria caché. Si se reemplaza un bloque se reescribe en la memoria principal si y sólo si el bit de actualización está a 1. El problema que hay con esta técnica es saber qué partes de la memoria principal no son válidas. Para obviar esta dificultad, los accesos de los módulos de E/S se permiten únicamente a través de la memoria caché.

En una organización de bus en la que más de un dispositivo (normalmente una CPU) tiene una memoria caché asociada y se comparte la memoria principal aparece un nuevo problema. Si se modifica una palabra de la memoria caché se invalida, además de la palabra correspondiente en la memoria principal, la misma palabra en otras memorias cachés (si ocurre que algunas de las memorias cachés contienen esa misma palabra). Incluso, con la estrategia de escritura inmediata, las otras memorias cachés pueden contener datos inválidos. Un sistema que evita este problema se dice que mantiene la coherencia de la Mca.


2.4.6 Tamaño del bloque

Otro elemento en el diseño de una memoria caché es el tamaño del bloque. Cuando se transfiere un bloque de la memoria principal a la memoria caché, con la palabra deseada se mueve un conjunto de palabras adyacentes. Por esta razón, cuando se va aumentando el tamaño del bloque a partir de valores muy pequeños la tasa de acierto inicialmente aumentará a causa del principio de localidad, ya que se incrementa la probabilidad de que sean accedidos, en el futuro inmediato, datos próximos a la palabra referenciada. Sin embargo, a partir de un cierto tamaño del bloque la tasa de acierto comienza a disminuir, debido a que la probabilidad de utilizar la información contenida en el bloque se hace menor que la probabilidad de reusar la información que se tiene que reemplazar. Aparecen pues dos efectos específicos:


1) Cuanto mayor sea el tamaño de los bloques, menor será el número de éstos que es posible tener en la memoria caché. Como cada búsqueda de un bloque en la memoria principal lleva consigo su escritura en la memoria caché, si el número de bloques es pequeño aumenta la frecuencia de utilización del algoritmo de reemplazamiento de bloques.
2) Cuando crece el tamaño de un bloque, cada nueva palabra añadida a ese bloque estará a mayor distancia de la palabra requerida por la CPU, y por lo tanto es menos probable que sea necesitada a corto plazo.

La relación entre tamaño de bloque y tasa de acierto es compleja, y depende de las características de localidad de cada programa en particular. Por este motivo no se ha encontrado un valor óptimo definitivo, sin embargo, una elección razonable es un tamaño entre 4 y 8 palabras.


2.4.7 Número de cachés

Cuando la Mca se integra en el propio procesador, puede resultar imposible aumentar su tamaño si el rendimiento del sistema no es el adecuado. En cualquier caso ampliar el tamaño de la Mca puede producir una caché que sea más lenta que la original, Una alternativa que se está utilizando cada vez más es introducir una segunda caché de mayor capacidad que se localiza entre la primera caché y la memoria principal tal como se muestra en la Figura 2.47. Esta caché de segundo nivel se denomina algunas veces caché secundaria. Su tamaño suele ser un orden de magnitud mayor que el de la caché de primer nivel, por ejemplo 512K y 64K para las Mca de segundo y primer nivel respectivamente.





Figura 2.47: Memoria caché de dos niveles
En una referencia a memoria, el procesador accederá a la caché de primer nivel. Si la información no se encuentra allí (se dice que ocurre un fallo en la Mca de primer nivel), se accede a la caché de segundo nivel. Si tampoco la información solicitada se encuentra allí (se dice que ocurre un fallo en la Mca de segundo nivel) habrá que acceder a la Mp. El bloque de memoria correspondiente se transfiere a la caché de segundo nivel y luego a la del primer nivel de forma que existen al menos inicialmente dos copias del bloque de memoria. Esto quiere decir que todos los bloques transferidos a la caché de segundo nivel también existen en la caché de primer nivel. Esto se conoce como principio de inclusión. Por supuesto que las copias de los bloques de la caché de segundo nivel nunca se necesitarán cuando se encuentran en la caché del primer nivel.

La política de reemplazamiento y la estrategia de escritura practicada en ambas cachés normalmente suelen ser respectivamente el algoritmo LRU y la escritura inmediata para mantener las copias duplicadas. El tamaño del bloque de la caché de segundo nivel será igual o mayor que el tamaño del bloque de la caché de primer nivel ya que en el caso contrario si se produce un fallo en esta última se necesitarían transferir más de un bloque de la primera.

El rendimiento de una Mca visto en el apartado 2.4.1 se puede extender a una caché de dos niveles. En este caso se obtiene la expresión siguiente:

donde


tca1 = tiempo de acceso a la Mca de primer nivel

tca2 = tiempo de acceso a la Mca de segundo nivel

tp = tiempo de acceso a la Mp

h1 = tasa de acierto de la Mca de primer nivel

h2 = tasa de acierto combinada de las Mca de primer y segundo nivel

para la determinación de ta en (2.6) se ha considerado que las dos cachés son homogéneas. La tasa de acierto h1 será mayor que la tasa de acierto h2.

La mayoría de las familias de microprocesadores proporcionan cachés de segundo nivel que emplean controladores independientes para las cachés externas a la CPU. Así el Intel 486 dispone del circuito controlador de caché 8291 y el Pentium del 82491. Motorola también posee controladores de cachés análogos.



Compartir con tus amigos:
1   2   3   4   5   6   7   8


La base de datos está protegida por derechos de autor ©composi.info 2017
enviar mensaje

    Página principal