PDF de programación - Sistemas de Procesadores paralelos_PARTE II

Sistemas de Procesadores

Paralelos

(Multiprocesadores y Multicomputadoras)

PARTE II

Profesor: Mag. Marcelo Tosini
Cátedra: Arquitectura de Computadoras y técnicas Digitales
Carrera: Ingeniería de Sistemas
Ciclo: 4º año

1

Modelos de consistencia,

coherencia y sincronización

para multiprocesadores

Antecedentes

• En un procesador tradicional (escalar), todas las instrucciones se ejecutan en

orden (particularmente escrituras y lecturas)

• En un superescalar, debido a la ejecución fuera de orden y a las optimizaciones

de acceso a memoria de datos,

• Las escrituras se consideran completas aún cuando no se hayan escrito

realmente en memoria, y

• Se pueden realizar lecturas de posiciones de memoria aún cuando la

escritura correspondiente aún no haya realizado la modificación de memoria

(Aún así, el procesador lleva traza del orden secuencial en que debieron ser

ejecutadas las operaciones de acceso a memoria ya que sólo es necesario preservar las
dependencias entre los accesos a la misma localización de la memoria)

• En un multiprocesador, es más complejo coordinar la secuencia correcta de

operaciones de lectura y de escritura que preserva el orden secuencial de
ejecución debido a que:

• Las variables están replicadas en memoria, en múltiples cachés y en, al

menos, un store-buffer de algún procesador

• distintos procesadores están a diferentes distancias de la memoria por lo

que ven los cambios de la misma en distintos momentos

3

Tipos de consistencia de memoria

Consistencia estricta

Consistencia secuencial: define el orden de accesos a memoria en términos

del orden impuesto por el programa fuente

Modelos relajados: permiten implementaciones de mayor rendimiento con un

modelo de programación mas complejo y restrictivo y con
una semántica de ejecución idéntica a la de un modelo de
consistencia secuencial

Consistencia causal

Consistencia PRAM (Pipelined RAM)

Partial Storage Ordering (PSO)

Consistencia de caché (coherencia)

• Modelos de acceso sincronizado

• Consistencia débil

•Consistencia de liberación

4

Tipos de consistencia de memoria

Estricta
Estricta

Secuencial

Causal

PRAM

PSO

de caché

• También llamada consistencia atómica (Atomic Consistency - AC)

• Caso ideal

• Cualquier escritura se ve instantáneamente por cualquier

lectura posterior (cualquier lectura de una posición de memoria
devuelve el valor almacenado por la escritura mas reciente)

P1

RAM

P2

SW mem[100], 55

demora = 0

demora = 0

LD B, mem[100]

Tiempo i

SW mem[100], 55

Tiempo i + 0

mem[100] = 55

Tiempo i + 0

LD B, mem[100] ; B = 55

5

Tipos de consistencia de memoria

Estricta
Estricta

Secuencial

Causal

PRAM

PSO

de caché

•En la práctica existen demoras de propagación que no

permiten sincronizar correctamente a procesadores distantes

P1

SW mem[100], 55

demora = 3

RAM

38

P2

demora = 1

LD B, mem[100]

Tiempo i

SW mem[100], 55

Tiempo i + 1

LD B, mem[100] ; B = 38

Tiempo i + 3

mem[100] = 55

I n c o rr e c t o !!

6

Tipos de consistencia de memoria

Estricta
Estricta

Secuencial

Causal

PRAM

PSO

de caché

r1(x)1

r1(x)2

p1

p2

w2(x)1

w2(x)2

7

Tipos de consistencia de memoria

Estricta

Secuencial
Secuencial

Causal

PRAM

PSO

de caché

Condiciones de preservación

1.

2.

Todo proceso emite las peticiones a la memoria en el orden especificado por
el programa

Luego de emitir una operación de escritura, el proceso que la emitió espera
que se haya realizado la escritura en la memoria antes de emitir su
siguiente operación (lectura de la misma posición o nueva escritura)

3. Después de emitir una operación de lectura, el proceso que la emitió espera

a que la lectura se haya completado, y espera también que se complete la
escritura que generó el valor devuelto por la lectura, antes de emitir su
siguiente operación (el procesador debe esperar a que la escritura se haya
realizado respecto a todos los procesadores , o sea, sea vista por todos)

8

Tipos de consistencia de memoria

Estricta

Secuencial
Secuencial

Causal

PRAM

PSO

de caché

Ejemplo: Tres tareas sincronizadas mediante 2 variables A y B (inicialmente en 0).

En una ejecución secuencial, P3 imprimirá un “1” cuando A sea 1 en P1

Procesador 1

Procesador 2

Procesador 3

task 1 {
A = 1
X = A
A = 2

}

task 2 {

while (A==0);
B = 1

}

task 3 {

while (B==0);
printf A

}

Por lema 2: la operación “X = A” en task 1 debe esperar a que la escritura de A (A = 1) se

escriba efectivamente en memoria

Por lema 3: Cualquier futura operación en P1 requiere esperar a que la última escritura (A = 1)

sea vista en todos los procesadores de la red
Esto asegura que B se vuelva 1 y, transitivamente, se imprima 1 el P3

9

Tipos de consistencia de memoria

Estricta

Secuencial
Secuencial

Causal

PRAM

PSO

de caché

Ordenaciones exigibles al modelo

1. R → R: Una lectura seguida de una lectura
1. R → R: Una lectura seguida de una lectura

2. R → W: Una lectura seguida de una escritura. Siempre se preserva si las
2. R → W: Una lectura seguida de una escritura. Siempre se preserva si las

operaciones se realizan sobre una misma dirección (antidependencia)
operaciones se realizan sobre una misma dirección (antidependencia)

3. W → W: Una escritura seguida de otra escritura. Siempre se preserva si las
3. W → W: Una escritura seguida de otra escritura. Siempre se preserva si las

operaciones se realizan sobre una misma dirección (dependencia
operaciones se realizan sobre una misma dirección (dependencia
de salida)
de salida)

4. W → R: Una escritura seguida de una lectura. Siempre se preserva si las
4. W → R: Una escritura seguida de una lectura. Siempre se preserva si las
operaciones se realizan sobre una misma dirección (dependencia
operaciones se realizan sobre una misma dirección (dependencia
verdadera)
verdadera)

10

Tipos de consistencia de memoria

Estricta

Secuencial
Secuencial

Causal

PRAM

PSO

de caché

hv1:

w2(x)1

a

1 r1(x)1

a

1 w2(x)2

r1(x)1

p1

p2

w2(x)1

w2(x)2

hv2:

w2(x)1 a

2 w2(x)2

11

Tipos de consistencia de memoria

• Los modelos “relajados” permiten relajar una o mas de las ordenaciones
• Los modelos “relajados” permiten relajar una o mas de las ordenaciones

respecto al modelo de consistencia secuencial
respecto al modelo de consistencia secuencial

• Relajar una ordenación significa permitir la finalización anticipada de
• Relajar una ordenación significa permitir la finalización anticipada de

una operación por parte de un procesador
una operación por parte de un procesador

Ejemplo: Relajar la ordenación W → R implica permitir que la lectura
Ejemplo: Relajar la ordenación W → R implica permitir que la lectura

termine antes que la escritura de la cual depende
termine antes que la escritura de la cual depende

(En un entorno multiprocesador, una escritura no se completa hasta que se han
(En un entorno multiprocesador, una escritura no se completa hasta que se han
completado todas las invalidaciones a todas las caché del sistema)
completado todas las invalidaciones a todas las caché del sistema)

• Además de las ordenaciones basadas en las operaciones R y W, se
• Además de las ordenaciones basadas en las operaciones R y W, se
deben considerar aquellas surgidas de los accesos a variables de
deben considerar aquellas surgidas de los accesos a variables de
sincronización:
sincronización:

• S → W: Escritura dentro de un área de memoria compartida
• S → W: Escritura dentro de un área de memoria compartida
• S → R: Lectura dentro de un área de memoria compartida
• S → R: Lectura dentro de un área de memoria compartida
• W → S: Escritura antes de entrar a un área compartida
• W → S: Escritura antes de entrar a un área compartida
• R → S: Lectura anterior al ingreso a un área compartida
• R → S: Lectura anterior al ingreso a un área compartida

12

Tipos de consistencia de memoria

Estricta

Secuencial

Causal
Causal

PRAM

PSO

de caché

• Definido originalmente para pasaje de mensajes en un sist. distribuido

• Un mensaje m1 precederá causalmente a otro mensaje m2 (m1 → m2)

si se cumple alguna de las siguientes condiciones:

• m1 ym2 son enviados por el mismo proceso y m2 es enviado luego

de m1

• m1 es entregado en el proceso emisor de m2 antes de que m2 sea

enviado

• Existe un mensaje x tal que m1 < x y x < m2

• En memoria compartida el envío de un mensaje equivale a una escritura

y la recepción de un mensaje a una lectura

13

Tipos de consistencia de memoria

Estricta

Secuencial

Causal
Causal

PRAM

PSO

de caché

hv1:

w1(x)2

a

1 w1(y)1

a

1 w2(x)1

a

1 r1(x)1

w1(x)2

w1(y)1

r1(x)1

p1

p2

w2(x)1

r2(y)1

r2(x)2

hv2:

w2(x)1 a

2 w1(x)2

a

2 w1(y)1

a

2 r2(y)1

a

2 r2(x)2

14

Tipos de consistencia de memoria

Estricta

Secuencial

Causal

PRAM
PRAM

PSO

de caché

• Similar al modelo de consistencia de procesador aunque más relajado

• También llamado Total Storage Ordering - TSO

• Relaja la ordenación W → R a direcciones diferentes

• Permite almacenar las escrituras en buffers que pueden ser

sobrepasados por las lecturas (se permite proceder una lectura antes que
una escritura anterior haya sido vista por todos los procesadores)

• Permite a la máquina ocultar la latencia de las operaciones W

• Para forzar la ordenación relajada (W → R) se debe sincronizar vía

software (W → S → R)

• Todos los procesadores observan las operaciones de escritura generadas

por un mismo procesador en el mismo orden, mientras que las
escrituras generadas por procesadores distintos podrán ser percibidas
en distinto orden

15

Tipos de consistencia de memoria

Estricta

Secuencial

Causal

PRAM
PRAM

PSO

de caché

w1(x)1 w1(y)1

p1

p2

p3

w2(x)2

r2(y)1

Orden

alterado

r3(x)2

r3(x)1

16

Tipos de consistencia de memoria

Estricta

Secuencial

Causal

PRAM

PSOPSO

de caché

• Llamado también Ordenamiento parcial de almacenamiento

(Partial Storage Ordering - PSO)

• Relaja la ordenación W → W a direcciones diferentes (escrituras