PDF de programación - tema 6 - Multiprocesadores: Coherencia, sincronización y consistencia

Arquitectura de Computadores

TEMA 6

Multiprocesadores: Coherencia, sincronización y

consistencia

Curso 2015-2016

Contenidos

 Jerarquía de memoria extendida
 El problema de la coherencia cache
 Protocolos de coherencia “Snoopy”

o Protocolo Snoopy de dos estados
o Protocolo MSI: invalidación de tres estados
o Protocolo MESI: invalidación de cuatro estados

 Coherencia cache basada en directorio

o Directorio plano basado en memoria
o Directorio plano basado en cache

 Sincronización
 Consistencia de memoria
 Bibliografía

o Cap 5 y 8 de [CuSi99]
o Cap 5 de [HePa12]

(Nota.- En la elaboración de este material se han utilizado contenidos previamente desarrollados por los
profesores Manuel Prieto, Luis Piñuel e Ignacio Martín. También se han utilizado figuras de HePa12 y CuSi99)

AC — Tema 6

Curso 2015-16

2

Jerarquía de memoria extendida

Mem

Caches

CPU CPU

CPU

Jerarquía de

Memoria

 Las caches privadas permiten:

o Ocultar la latencia de los accesos
o Reducir la contención

Replicación:

Problema de coherencia

Variables Compartidas

AC — Tema 6

Curso 2015-16

3

Alternativas de implementación

Escalabilidad

P1

Pn

Switch

Primer Nivel $

Memoria
Principal

Cache Compartida

P1

$

Pn

$

• Bus Compartido
• Red punto a punto

Red de Interconexión

Mem

Mem

UMA, SMP

Mem

P1

$

Pn

$

Mem

Red de Interconexión

Escalable

NUMA: Memoria Distribuida

AC — Tema 6

Curso 2015-16

4

Alternativas de implementación

 Una alternativa ampliamente usada: SMP basado en

Bus Compartido

P1

$

Bus

Pn

$

Problemas

Memoria

E/S

 Servidores departamentales

 Estaciones de trabajo

 Bloques de construcción básicos

sistemas de gran escala

 Soporte en microprocesadores de

propósito general

Coherencia

Ancho de Banda limitado

AC — Tema 6

Curso 2015-16

5

Modelo intuitivo de memoria

 Programa secuencial

o Las posiciones de memoria se utilizan para “comunicar valores” entre
distintas puntos del programa. Cuando se lee una posición se devuelve
el último valor escrito en ella

 Espacio de direcciones compartido en sistemas con un único

procesador (Multiprogramación)
o Cuando se lee una posición se devuelve el último valor escrito en ella,
independientemente del proceso (thread) que realizó la última
escritura sobre dicha posición

o Las caches no interfieren con el uso de múltiples procesos (threads)
en un procesador, ya que todos ellos ven la memoria a través de la
misma jerarquía

 Multiprocesadores de Memoria Compartida

o Objetivo: Nos gustaría que el resultado de ejecutar un programa que
usa varios procesos (threads) sea el mismo independientemente de si
los procesos se ejecutan en paralelo (multiprocesadores) o de forma
entrelazada (uniprocesador multiprogramado).

o Problema: Cuando dos o más procesos acceden a la memoria a través
de caches diferentes existe el peligro de que vean valores
inconsistentes

AC — Tema 6

Curso 2015-16

6

Problema de la coherencia cache

Transacciones

(Proc) Operac

1. (P1) Load U

2. (P3) Load U

3. (P3) Store U

4. (P1) Load U

5. (P2) Load U

Load U

P

1

U = ?

4

$

$

U: 5

P
2

Load U

U = ?

5

P

3

3

U: 5

$

U: 7

Store U

2

Load U

Dispositivos

I/O

Load U

1

U: 5

Memoria

Protocolos de coherencia de cache

Siguen la pista del estado
de cualquier bloque de
datos compartido para
evitar incoherencias

AC — Tema 6

Curso 2015-16

7

Soluciones de “Grano Grueso”

 Problemas de coherencia cache en uniprocesadores:
operaciones de E/S a través de dispositivos DMA

o Dispositivo DMA escribe en memoria: El procesador puede seguir

viendo valores antiguos en la cache.

o Dispositivo DMA lee de memoria: El DMA puede leer un valor antiguo en

el caso de que se utilice write-back

 Alternativas (dado que las operaciones de E/S son mucho

menos frecuentes que las operaciones de acceso a memoria)

o Evitar usar la cache:

 Los segmentos de memoria involucrados en operaciones de E/S se

marcan como No-Cacheables o bien se utilizan operaciones
load/store no-cacheables

o Sacar de la cache antes de E/S (soporte del SO):

 Las páginas de memoria involucradas en cualquier operación de E/S

son eliminadas de la cache (flush) previamente por el SO

o Usar la cache para E/S:

 El tráfico de E/S pasa por todos los niveles de la jerarquía de

memoria

 Problema: el contenido de la cache puede “corromperse” con datos

que no son de interés (al menos inmediato) para el procesador

AC — Tema 6

Curso 2015-16

8

Soluciones de “Grano Grueso”

 En multiprocesadores

o La escritura o lectura de variables compartidas es un

evento frecuente.

o No es práctico:

 Deshabilitar la cache para datos compartidos
 Invocar al SO en cada referencia a una variable compartida
 Todos los Procesadores actuales proporcionan

mecanismos para soportar la coherencia

o Transparente al software

AC — Tema 6

Curso 2015-16

9

Coherencia

 ¿Qué significa que un sistema de memoria es coherente?

o Una operación de lectura retorna siempre el último valor que fue
correspondiente,
escrito
independientemente del procesador que efectúa la lectura o
escritura

de memoria

posición

en

la

o Dos aspectos clave:

 1) Qué valor debe ser devuelto en una lectura Coherencia.
 2) Cuándo un valor escrito debe ser devuelto por una operación de

lectura Consistencia

 ¿Cuando un sistema de memoria es coherente?

o Una lectura del procesador P a la posición X de memoria, que sigue a una

escritura de P en X, sin ninguna otra escritura debe retornar el valor
escrito por P

o Una lectura por un procesador a la posición X que sigue a una escritura de

otro procesador en X, retorna el valor escrito si no hay ninguna otra
escritura y están suficientemente separadas en el tiempo.

o Serialización de escrituras. Todas las escrituras a la misma posición

deben verse en el orden correcto.

 Dos escrituras hechas por dos procesadores sobre la misma posición, X, son

vistas por todos los procesadores en el mismo orden.

AC — Tema 6

Curso 2015-16

10

Coherencia

 Serialización de escrituras: ejemplo

Si P1 ejecuta:
o LD R1, X

 y se obtiene en R1 el valor V1 escrito por el procesador P2 en

la posición de memoria X

Y después P1 ejecuta:

o LD R2, X

 y se obtiene en R2 el valor V2 escrito por el procesador P3 en

la posición de memoria X

…entonces es imposible que cualquier otro procesador,
Pi, que lea la posición de memoria X obtenga primero el
valor V2 y después el valor V1.

AC — Tema 6

Curso 2015-16

11

Políticas (o protocolos) para mantener la coherencia

 Invalidación en Escritura / Coherencia Dinámica

o Al escribir en un bloque se invalidan todas las otras copias

(Múltiples lectores , un solo escritor)

o Escrituras consecutivas al mismo bloque (no

necesariamente a la misma palabra) efectuadas desde el
mismo procesador se realizan localmente (No hay copias).
Sólo es necesario una transacción en el medio de
comunicaciones en múltiples escrituras al mismo dato

o ¿Qué ocurre en un fallo de lectura?

 Con write-through: la memoria esta siempre actualizada
 Con write-back: es necesario búsqueda (snoop) en caches

remotas para encontrar el último valor.

– La cache dueña del último valor lo proporciona al solicitante

(y a la Mp)

 Actualización en Escritura

o Al escribir en un bloque se actualizan todas las copias
o Típicamente con write-through, pocos procesadores
o Escrituras consecutivas a la misma palabra requiere

múltiples actualizaciones

o ¿Qué ocurre en un fallo de lectura?

 Se busca en la memoria. Siempre esta actualizada

AC — Tema 6

Curso 2015-16

12

Políticas (o protocolos) para mantener la coherencia

 Los protocolos usados para la invalidación o actualización

dependen de la red de interconexión utilizada

 Si la red de interconexión permite broadcast eficiente las
operaciones de invalidación o actualización se pueden enviar
de forma simultanea a todos los controladores.

o Protocolo Snoopy (buses): Observación del bus

 Cada controlador de cache está observando los eventos que

suceden en el bus y toma decisiones en consecuencia.

 Un controlador de cache envía eventos al bus en función de las
peticiones de acceso a memoria que recibe de su procesador 
Envía órdenes de invalidación o actualización de forma simultánea
a todos los demás controladores.

 Si

la red de interconexión no permite broadcast (o el
broadcast no es eficiente), la invalidación o la actualización
se envía únicamente a aquellas caches que tienen una copia
del bloque.

o Protocolos Basados en Directorio: Se utiliza un directorio
(centralizado o distribuido) con una entrada por cada bloque
en la que se indica en qué caches existe copia y en qué estado.

AC — Tema 6

Curso 2015-16

13

Protocolos Snoopy

 El Arbitraje del bus Impone un Orden.

o Las Transacciones del Bus son visibles en el mismo

orden por todos los controladores de cache.

 Observar/Espiar el bus

CPU

St

Ld

Directorio
de la cache

State Tag Datos

° ° °

Controlador de Cache

Transacciones

observadas

Transacciones

ordenadas

Bus

Sólo es necesario extender la funcionalidad del controlador de cache

• El estado de cada bloque mapeado en la cache sigue estando en el directorio
• Los cambios de estado son provocados por:

a) operaciones Ld/St del procesador
b) Transacciones relevantes observadas en el bus

AC — Tema 6

Curso 2015-16

14

Procolos Snoopy

 Diagrama de estados de un bloque de cache: convenio

de representación

o Cada transición es disparada por la observación de un

evento en el procesador o el bus

o Una transición puede implicar que el controlador ejecute

alguna acción sobre su cache, u ordene una cierta acción al
bus

Notación:

Op del Procesador/ Acción a realizar

o bien

Evento en BUS / Acción a realizar

S1

S2

AC — Tema 6

Curso 2015-16

15

Protocolo Snoopy de 2 Estados

 Aplicado a: Política de invalidación en escritura + Escritura

directa (write through).

o Sin Asignación en Escritura (no writeall