Computación de Altas Prestaciones

1

EJERCICIOS DEL TEMA 4 SISTEMAS MULTIPROCESADOR (MEMORIA COMPARTIDA)

1. Se diseña un procesador con un único nivel de memoria caché con tasa de fallos del 6% y tamaño de bloque de 256 palabras de 64 bits cada una. Este procesador funciona con una frecuencia de reloj de 1 GHz y realiza en media 1.25 accesos a memoria en cada ciclo de reloj. Se desea diseñar una arquitectura de memoria compartida con estos procesadores. a) ¿Cuál es el ancho de banda mínimo que debe proporcionar el bus compartido de esta arquitectura si se quieren incluir 4 procesadores? b) ¿Qué ocurre si se duplica el tamaño del bloque de la cache? c) ¿Cuál debería ser la tasa de fallos de la memoria caché de cada procesador para que se puedan conectar hasta 8 procesadores si se vuelve al tamaño de bloque inicial y al ancho de banda obtenido con él? 2. Se diseña una arquitectura de memoria compartida de 4 procesadores con cachés de postescritura que utiliza un protocolo de coherencia de caché snoopy con invalidación de 4 estados:  INVÁLIDO: Bloque inválido, no presente en la memoria caché (provoca un fallo cuando se intenta acceder a él).  EXCLUSIVO: Única copia del sistema, coherente con memoria principal.  COMPARTIDO: Varias copias en el sistema, coherentes entre sí y con la memoria principal.  MODIFICADO: Única copia válida del sistema, no coherente con la memoria principal. Para el funcionamiento correcto de este protocolo se utiliza una señal S (Shared) en el bus compartido que sirve para distinguir los datos compartidos de los privados. A esta señal, que funciona mediante un OR cableado, están conectados todos los controladores de caché de manera que cada vez que observan un evento en el bus relacionado con un determinado bloque, vuelcan un 1 si tienen copia de dicho bloque y un 0 si no la tienen. Los comandos de este protocolo son Miss e Inv, y las acciones con WB (volcado de bloque a memoria principal) e Invalidar (invalidación en memoria caché local). a) Deducir el diagrama de transición de estados que muestra la evolución de los bloques en una memoria caché del sistema según este protocolo.

Computación de Altas Prestaciones

2

b) Mostrar la evolución de las memorias cachés implicadas, los eventos y acciones que se producen y los comandos que se envían por el bus cuando se produce la siguiente secuencia de lectura y escrituras.        

P0 lee del bloque 0. P3 lee del bloque 2. P1 lee del bloque 0. P2 escribe en el bloque 1. P0 escribe en el bloque 1. P2 lee el bloque 0. P3 escribe en el bloque 2. P0 escribe en el bloque 0.

Suponer que el estado inicial de las cachés es vacío y utilizar una tabla de este tipo: EVENTO

COMANDOS/ACCIONES

ESTADO DE LAS CACHÉS Pi Pj Pk

Pi: Pj:

3. Repetir el problema anterior si los fallos de caché, en lugar de resolverlos siempre la memoria principal, los resuelven otras memorias caché siempre que sea posible. Nota: Se puede utilizar la acción WB para volcar el bloque completo al bus compartido y resolver así el fallo de otra memoria caché. 4. En la siguiente tabla se detallan los tiempos que supone en cada una de las implementaciones de los dos problemas anteriores resolver un fallo desde la memoria principal (TfalloMP), desde otra memoria caché (TfalloMC), invalidar un bloque (TINV) y hacer un Writeback de un bloque a memoria principal (TWB). La implementación 1 corresponde al caso en el que los fallos se resuelven siempre desde la memoria principal y la implementación 2 al caso en el que se pueden resolver desde otra memoria caché siempre y cuando sea posible. Para el ejemplo concreto de código que se ha utilizado en ambos problemas, discutir acerca de la conveniencia de una y otra implementación. ¿Se pueden generalizar las conclusiones obtenidas?

TfalloMP TfalloMC TINV TWB

Implementación 1 100 ns 140 ns 10 ns 60 ns

Implementación 2 100 ns 30 ns 10 ns 120 ns

Computación de Altas Prestaciones

3

5. Se diseña una arquitectura de memoria compartida de 4 procesadores con cachés híbridas de escritura directa y post-escritura que utiliza un protocolo de coherencia de caché snoopy con invalidación de 4 estados:  Inválido: Bloque invalidado.  Válido: Coherente con MP y con otras copias posibles en MC.  Reservado: El bloque se ha escrito solamente una vez, es la única copia del sistema y es coherente con MP. Es decir, cuando se escribe sólo una vez sobre un bloque, se utiliza escritura directa para actualizar la MP.  Sucio: El bloque se ha escrito dos o más veces y es la única copia válida del sistema, no está coherente con MP. Los comandos de este protocolo son RMiss y WMiss, y las acciones con WB (volcado de bloque a memoria principal), ED (escritura directa de una única palabra a memoria principal) e Invalidar (invalidación en memoria caché local). a) Deducir el diagrama de transición de estados que muestra la evolución de los bloques en una memoria caché del sistema según este protocolo. b) Mostrar la evolución de las memorias cachés implicadas, los eventos y acciones que se producen y los comandos que se envían por el bus cuando se produce la siguiente secuencia de lectura y escrituras:      

P0 lee el bloque 3. P1 escribe en el bloque 3. P2 escribe en el bloque 4. P1 escribe en el bloque 3. P2 escribe en el bloque 3. P3 lee el bloque 4.

Suponer que el estado inicial de las cachés es el siguiente: P0: Vacío P1: Bloque 3 válido, bloque 4 reservado. P2: Bloque 3 válido. P3: Vacío

Utilizar una tabla de este tipo: EVENTO

COMANDOS/ACCIONES Pi: Pj:

ESTADO DE LAS CACHÉS Pi Pj Pk

Computación de Altas Prestaciones

4

6. Se diseña una arquitectura de memoria compartida de 4 procesadores con cachés de postescritura que utiliza un protocolo de coherencia de caché snoopy con actualización de 4 estados:  Estado inicial o uncached (U): El bloque no está en la caché, por lo que cuando el procesador lo solicita para leer o para escribir se produce un fallo.  Exclusivo (E): El bloque está en la caché y no ha sido modificado mediante escrituras locales. Es la única copia en el sistema.  Válido (V): El bloque está en la caché y no ha sido modificado mediante escrituras locales. Existen otras copias en las cachés de otros procesadores, todas ellas coherentes entre sí (pero no tienen por qué estarlo con memoria principal).  Modificado (M): El bloque está en la caché y no es coherente con la memoria principal porque el procesador local ha realizado al menos una escritura sobre él. Puede que existan otras copias en las cachés de otros procesadores, todas ellas coherentes entre sí.

Para el funcionamiento correcto de este protocolo se utiliza una señal S (Shared) en el bus compartido que sirve para distinguir los datos compartidos de los privados. A esta señal, que funciona mediante un OR cableado, están conectados todos los controladores de caché de manera que cada vez que observan un evento en el bus relacionado con un determinado bloque, vuelcan un 1 si tienen copia de dicho bloque y un 0 si no la tienen. Los comandos de este protocolo son RMiss, WMiss y Upd, y las acciones con WB (volcado de bloque a memoria principal) y Actualizar_MC (actualización local con los contenidos de un comando Upd). a) Deducir el diagrama de transición de estados que muestra la evolución de los bloques en una memoria caché del sistema según este protocolo. b) Mostrar la evolución de las memorias cachés implicadas, los eventos y acciones que se producen y los comandos que se envían por el bus cuando se produce la misma secuencia de lecturas y escrituras que en el problema 2. Suponer también que el estado inicial de las cachés es vacío y utilizar el mismo tipo de tabla y nomenclatura. c) Comparar para este ejemplo el rendimiento de los protocolos de invalidación y actualización. ¿Se pueden generalizar las conclusiones extraídas de esta comparación? 7. Un sistema de memoria compartida-distribuida con 4 procesadores y cachés privadas asociadas a cada procesador, utiliza un protocolo de directorio de invalidación para garantizar la coherencia de las cachés. Este protocolo se basa en la utilización de tres estados para el directorio y para las memorias caché:

Computación de Altas Prestaciones

5



Inválido (I): Bloque invalidado. Este estado en el directorio se denomina No Cacheado (NC), es decir, cuando no hay ninguna caché en el sistema con copia del bloque.



Compartido (C): Una o varias copias del bloque coherentes entre sí y con la memoria principal.



Exclusiva (E): Una única copia en el sistema, no coherente con memoria principal.

Las cachés poseen el siguiente estado inicial: P0: Vacío P1: Bloque 3 compartido, bloque 1 exclusivo P2: Bloques 0 y 3 compartidos P3: Vacío

Además se pueden enviar mensajes con el formato (etiqueta, bloque, destino), siendo las etiquetas posibles RMiss (fallo de lectura), WHit (acierto de escritura), WMiss (fallo de escritura), WB (volcado de bloque u orden de volcado de bloque) e Inv (invalidación). El campo bloque indica qué bloque está implicado en la operación y el campo destino indica a qué procesador se le envía el mensaje. Si los bloques 0, 1, 2 y 3 se encuentran en la memoria principal del procesador P0, su directorio en la situación inicial es: B0 B1 B2 B3

0010 0100 0000 0110

C E NC C

Mostrar en una tabla como la siguiente la evolución de las cachés y del directorio de P0, y todos los mensajes que se envían, con las siguientes lecturas y escrituras:     

EVENTO

P3 lee del bloque 3. P1 lee del bloque 1. P2 escribe en el bloque 3. P3 lee del bloque 1. P1 escribe en el bloque 3. MENSAJES

DIRECTORIO

ESTADO DE LAS CACHÉS Pi Pj Pk

Computación de Altas Prestaciones

6

8. Se diseña una arquitectura de memoria compartida-distribuida de 8 procesadores que utiliza un protocolo de coherencia de cachés basado en directorio. Este protocolos utiliza los siguientes 4 estados para los bloques en las memorias caché y en el directorio:  INVÁLIDO: Bloque inválido.  EXCLUSIVO: Única copia del sistema, coherente con memoria principal.  COMPARTIDO: Varias copias en el sistema, coherentes entre sí y con la memoria principal.  MODIFICADO: Única copia válida del sistema, no coherente con la memoria principal. Los mensajes que se pueden enviar con este protocolo tienen el formato (etiqueta, bloque, destino). El campo bloque indica qué bloque está implicado en la operación y el campo destino indica a qué procesador se le envía el mensaje. a) Utilizando el conjunto de etiquetas propuesto en el tema 4 de teoría para los protocolos basados en directorio distribuido como punto de partida, definir el conjunto de etiquetas necesario para implementar este protocolo. b) Deducir el diagrama de transición de estados que muestra la evolución de los bloques en el directorio del sistema según este protocolo c) Mostrar la evolución del directorio y de las cachés con la secuencia de lecturas y escrituras del problema anterior. Suponer que el propietario de todos los bloques involucrados en las operaciones de lectura y escritura es P0 y que las cachés están vacías inicialmente.

EVENTO

MENSAJES

DIRECTORIO

ESTADO DE LAS CACHÉS Pi Pj Pk

9. Se diseña una arquitectura de memoria compartida-distribuida de 8 procesadores que utiliza un protocolo de coherencia de cachés basado en directorio. Este protocolo utiliza los siguientes 4 estados:  INVÁLIDO: Bloque inválido.  EXCLUSIVO: Única copia del sistema, coherente con memoria principal.  COMPARTIDO: Varias copias en el sistema, coherentes entre sí y con la memoria principal.

Computación de Altas Prestaciones

7

 MODIFICADO: Única copia válida del sistema, no coherente con la memoria principal. Los mensajes que se pueden enviar con este protocolo tienen el formato (etiqueta, bloque, destino). El campo bloque indica qué bloque está implicado en la operación y el campo destino indica a qué procesador se le envía el mensaje. a) Definir el conjunto de etiquetas posibles para este protocolo si el directorio está centralizado. b) Si el directorio se almacena en la memoria del procesador P7, mostrar la evolución del directorio y de las cachés con la secuencia de lecturas y escrituras del problema anterior. Suponer que el propietario de todos los bloques involucrados en las operaciones de lectura y escritura es P0 y que las cachés están vacías inicialmente.

EVENTO

MENSAJES

DIRECTORIO

ESTADO DE LAS CACHÉS Pi Pj Pk