Date post: | 13-Feb-2015 |
Category: |
Documents |
Upload: | josefina-mosqueda |
View: | 12 times |
Download: | 0 times |
Arquitecturas ParalelasIF - EHU
Arquitecturas Paralelas
7. Coherencia de Datos en computadores DSM
- Introducción- Directorios de coherencia: MP/MC- Problemas: tráfico y atomicidad- Protocolo de coherencia Origin- Protocolo SCI (NUMA-Q)
Arquitecturas ParalelasIF - EHU
CD-DSM 27
Coherencia de los datos en sistemas de memoria compartida SMP (red de comunicación, un bus)
> Snoopy > Estados / estados transitorios...
¿Y en sistemas DSM (mallas...)?
> La memoria es compartida, pero estáfísicamente distribuida entre los
nodos del sistema.> La red no es un bus. Por tanto,
snoopy ??
Introducción
Arquitecturas ParalelasIF - EHU
CD-DSM 37
▪ El hardware no asegura la coherencia de los datos (es responsabilidad del programador):
→ NUMA
▪ El hardware sí asegura la coherencia de los datos: → cc-NUMA
Introducción
¿Cómo se mantiene la coherencia de los datos en los sistemas DSM?
¿Cómo? Directorios de coherencia.
Arquitecturas ParalelasIF - EHU
CD-DSM 47
El directorio de coherencia guarda información sobre los bloques de datos:
- estado (estables o transitorios)- dónde están las copias
Problemas:- tamaño del directorio.- tráfico generado para mantener la coherencia.
- atomicidad de las operaciones.
El directorio está repartido entre los procesadores (no es un dispositivo “central”).
Introducción
Arquitecturas ParalelasIF - EHU
CD-DSM 57
Lugar y estructura del directorio:
- junto a la MP, una palabra de coherencia por cada bloque de datos:
▪ full bit vector
▪ limited bit vector
- distribuido entre las MC (+MP), formando listas ligadas con la información de cada bloque:
▪ SCI, scalable coherent interface
Introducción
Arquitecturas ParalelasIF - EHU
CD-DSM 67
1.Full bit vector (MESI)
Estructura del directorio- un bit por procesador
(1/0) para indicar si tiene o no copia del bloque.
- bits para indicar el estado del bloque (los habituales).
Directorios de coher.: MP
> E1 0 0 0 - 0
> S1 0 1 0 - 0
> M0 0 0 1 - 1
> I0 0 0 0 - 0
> no (MESI)1 1 0 1 - 1
P0 P1 P2 P3 Es
Arquitecturas ParalelasIF - EHU
CD-DSM 77
Problemas
El tamaño del directorio crece linealmente con el número de procesadores.
- bloques de 64 bytes:
P = 64 → 65 bits (8 bytes)P = 256 → 257 bits (32 bytes)P = 1.024 → 1.025 bits (128 bytes) +200% !
Directorios de coher.: MP
Arquitecturas ParalelasIF - EHU
CD-DSM 87
Para reducir el tamaño de la palabra de coherencia:
- bloques de 128 bytes / 4 proc. por nodo:
P = 1.024 (256x4)→ 257 bits (32 bytes) +25%
1. Usar bloques de datos “más grandes”
2. Reducir el número de nodos (estructura jerárquica: snoopy SMP + directorio)
Directorios de coher.: MP
Arquitecturas ParalelasIF - EHU
CD-DSM 97
2. Limited bit vector
- se limita el número de copias de un bloque: sólo se admiten k copias.
- se guardan en la palabra de coherencia de cada bloque las direcciones (log2 P bits) de los procesadores que tienen una copia:
k × log2 P << P
Directorios de coher.: MP
@1, @2, ..., @k, estado
Arquitecturas ParalelasIF - EHU
CD-DSM 107
- 4 procesadores por nodobloques de 128 bytes / 5 copias
P = 256 (64x4) → 5 x 6 + 1 = 31 bits ≈ 4 bytes
+ 3%
P = 1.024 (256x4) → 5 x 8 + 1 = 41 bits ≈ 5 bytes
+ 4%
Directorios de coher.: MP
Arquitecturas ParalelasIF - EHU
CD-DSM 117
1 bit por proc. estado
0 ... 1 ... 0 M
L
CC = controlador de comunic.D = directorio de coherencia
L = local H = home R= remote
H
P
CCC
DMP
R
23
4
5
1
LD A
1 S
Directorios de coher.: MP
Arquitecturas ParalelasIF - EHU
CD-DSM 127
2
1 0… 1 …1 0 S
otras dos copias estadoST A
0 …0 0 M
4
4’
3
3’
1
L
CC = controlador de comunic.D = directorio de coherencia
L = local H = home R= remote
H
P
CCC
DMP
Directorios de coher.: MP
R1
R2
Arquitecturas ParalelasIF - EHU
CD-DSM 137
Directorios en MC: estructura
La información sobre cada bloque de datos no se concentra en una sola palabra en el directorio junto a MP, sino que reparte entre el directorio junto a MP y las caches, en los directorios de éstas.
La información de coherencia de cada bloque se estructura en forma de listas ligadas.
Directorios de coher.: MC
Arquitecturas ParalelasIF - EHU
CD-DSM 147
Información de coherencia (por bloque)
Directorios de coher.: MC
@cop1 / estado
“MP” →
@copi-1 / @copi+1 / estado
MC →
Arquitecturas ParalelasIF - EHU
CD-DSM 157
¿Cómo se organiza la información en colas ligadas?
Home(memoria principal)
Pj (cache) Pk (cache)Pi (cache)
Directorios de coher.: MC
Pk
*, * bl. datosbl. datos
bl. datosMP D
bl. datos
*,Pj *,Pk Pi,P
k Pj,*
Pj Pi
Arquitecturas ParalelasIF - EHU
CD-DSM 167
1. MP 5 copias, 3 bits de estadoPalabra de coherencia: 5 x 10 + 3 = 53 bits
Directorio (nodo): 53 bit x 1 M bloque = 53 Mb
2. MCEn MP: 10 + 3 = 13 bits
En caches: 2 x 10 + 3 bit = 23 bits
Total (nodo): 13 x 1 M + 23 x 4 k = 13,1 Mb
Directorios de coher.: MC
P = 1.024 / MP = 128 MB / MC = 512 kB / bl = 128 bytes
Arquitecturas ParalelasIF - EHU
CD-DSM 177
Mantener la coherencia debe generar el menor tráfico posible, tanto de paquetes de control como de paquetes de datos.
Las operaciones de coherencia deben tener la menor latencia posible.
Para ello hay que- Minimizar el número de mensajes (tráfico).- Reducir el camino crítico (latencia) de la
operación.
Problemas: tráfico de coh.
Arquitecturas ParalelasIF - EHU
CD-DSM 187
Ejemplo: el procesador L lee una variable que no está en su cache, y que corresponde a un bloque sito en la memoria del procesador H, bloque que está modificado en la cache del procesador R.
Tres protocolos para efectuar las operaciones de coherencia:
1. Pregunta / Respuesta2. Intervention Forwarding3. Reply Forwarding
Problemas: tráfico de coh.
Arquitecturas ParalelasIF - EHU
CD-DSM 197
1. Pregunta / Respuesta
L HI
R
1. Petición
2. Respuesta
4a. Respuesta (Bloque)
4b. Bloque (actual.)
3. Petición
mensajes: 5camino crítico: 4
0100 / M
M
Problemas: tráfico de coh.
Arquitecturas ParalelasIF - EHU
CD-DSM 207
2. Intervention Forwarding
L HI
R
1. Petición
4. Respuesta(Bloque)
mensajes: 4camino crítico: 4
2. Petición
3. Respuesta(Bloque)
0100 / M
M
Problemas: tráfico de coh.
Arquitecturas ParalelasIF - EHU
CD-DSM 217
3. Reply Forwarding
L HI
R
1. Petición
3a. Respuesta (Bloque)
3b. Bloque (actual.)
2. Petición
mensajes: 4camino crítico: 3
0100 / M
M
Problemas: tráfico de coh.
Arquitecturas ParalelasIF - EHU
CD-DSM 227
Las operaciones de coherencia tienen que realizarse de forma atómica, sin interferencias entre ellas.
Problemas: atomicidad
1a. INV
2b. Respuesta
1b. INV
?
R1 HS
R2S
..1..1.. / S2a→ ..1..0.. / M
→ M??→M
Arquitecturas ParalelasIF - EHU
CD-DSM 237
Para asegurar la atomicidad
Problemas: atomicidad
+ Hay que utilizar estados transitorios, busy, en las caches y en el directorio.
+ Si no se pueden procesar las peticiones o son incoherentes:- se rechazan mediante paquetes tipo
NACK.- o se guardan en un búfer para
procesarlas más tarde.
Arquitecturas ParalelasIF - EHU
CD-DSM 247
Dos ejemplos:
1. Computadores Origin → MP
2. Protocolo SCI (Numa-Q) → MC
Protocolos comerciales
Arquitecturas ParalelasIF - EHU
CD-DSM 257
▪ 512 nodos / 1.024 procesadores / hipercubo
▪ Encaminamiento adaptativo / canales virtuales
▪ Invalidación / MESI (en cache) / write-back
▪ Full bit vector / 7 estados en MPI / S / E cuidado: E = E o M (una copia única)
3 estados busy1 para otras cosas
▪ Reply forwarding / NACK
▪ Paquetes de control: Rd / INV / RdEx / ACK / NACK / Wr
Origin 2000
Algunas características de los computadores Origin 2000
Arquitecturas ParalelasIF - EHU
CD-DSM 267
Hay que analizar tres operaciones para ver cómo mantener la coherencia de los datos:
▪ Lectura de una variable (fallo)▪ Escritura de una variable (acierto / fallo)▪ Reemplazo de un bloque (actualizar MP)
Origin 2000
Arquitecturas ParalelasIF - EHU
CD-DSM 277
Lectura (fallo) Dir. = I/S
L H
1b. Rd A0000 / I
I → E/S3
1100 / S
2b. Bloque
1a→ busy
2a
→ 0001 / E
→ 1101 / S
Origin 2000
Arquitecturas ParalelasIF - EHU
CD-DSM 287
L H
1000 / E
I → S4
E/M1a→ busy
2a→ 1001 / busy
R
1b. Rd A 2c. Rd A (+@L)
3b. ACK / Bloque
3c. ACK / Wr (Bl.)
→ 1001 / S4
3a→ S2b. Bloque
(espec.)
Origin 2000
Lectura (fallo) Dir. = E
Arquitecturas ParalelasIF - EHU
CD-DSM 297
Lectura (fallo) Dir. = busy
L H
1b. Rd A
xxxx / busy
I
2. NACK
1a→ busy
Origin 2000
Arquitecturas ParalelasIF - EHU
CD-DSM 307
Escritura (acierto-INV / fallo-RdEx)
Dir.: busy
L H
1b. INV A / RdEx A
xxxx / busy
S/I
2. NACK
1a→ busy
Origin 2000
Arquitecturas ParalelasIF - EHU
CD-DSM 317
L HS/I → M
51a→ busy
2a→ 0001 / E
R1
1b. INV A / RdEx A
2b. n.cop. / +Bloque
2c. INV A (+@L)
3b. ACK
4aS → I
1101 / S1100 / S
R2
4b. ACK
2d. INV A (+@L)
3aS → I
eficiencia¡cuidado carreras!
Origin 2000
Escritura (acierto-INV / fallo-RdEx)Dir.: S
Arquitecturas ParalelasIF - EHU
CD-DSM 327
L HS/I
1a→ busy
2a→ 0001 / E
R1
1b. INV A / RdEx A
2b. n.cop. / +Bloque
2c. INV A (+@L)
1101 / S1100 / S
R2
2d. INV A (+@L)
¡Ojo! carreras
R3 R4
NACKeficiencia:guardar, no rechazar
Rd A (@R3)
?
→ 0011 / busy
Origin 2000
Escritura (acierto-INV / fallo-RdEx)Dir.: S
Arquitecturas ParalelasIF - EHU
CD-DSM 337
L H
1000 / E
I → M4
E/M1a→ busy
2a→ 0001 / busy
R
1b. RdEx A 2c. RdEx A (+@L)
3b. ACK / Bloque
3c. ACK / Wr (Bloque)
→ 0001 / E4
3a→ I2b. n.cop. +
Bloque (espec.)
Origin 2000
Escritura (fallo-RdEx)
Dir.: E
Arquitecturas ParalelasIF - EHU
CD-DSM 347
L H
1b. INV A
1000 / E
S
2. NACK
1a→ busy
Origin 2000
Escritura (acierto-INV)
Dir.: E
Arquitecturas ParalelasIF - EHU
CD-DSM 357
L H
1b. RdEx A
0000 / I
I → M3
2b. Bloque
1a→ busy
2a
→ 0001 / E
Origin 2000
Escritura (fallo-RdEx)
Dir.: I
Arquitecturas ParalelasIF - EHU
CD-DSM 367
L H
1b. INV A
0000 / I
S
2. NACK
1a→ busy
Origin 2000
Escritura (acierto-INV)
Dir.: I
Arquitecturas ParalelasIF - EHU
CD-DSM 377
L H
1b. Wr (Bloque)
0001 / E
M → x3
2b. ACK
1a→ busy
2a
→ 0000 / I
Origin 2000
Reemplazo – actualizar MPDir.: E
Arquitecturas ParalelasIF - EHU
CD-DSM 387
L H
0001 / E
→ x4
I
2a→ 1001 / busy
R
3c. ACK
1b. Rd A
2b. Bloque (espec)
→ 1000 / E3a
1a→ busy
4→ E
2c. Rd A
M2→ busy 2d. Wr
(Bloque)
3b. Bloque
Origin 2000
Reemplazo – actualizar MPDir.: busy
Arquitecturas ParalelasIF - EHU
CD-DSM 397Numa-Q
Estructura del multiprocesador NUMA-Q
PC
M S/I
PCI
S/I
IQ link
D
PC
PC
PC4P
4P
4P
4P
4P 4P
4P 4P
Arquitecturas ParalelasIF - EHU
CD-DSM 407
▪ 8 x 4 procesadores / bus (snoopy)
▪ IQ-link remote access cache
▪ Invalidación / MOESI / write-back
▪ <Petición / Respuesta> / encolado de peticiones
▪ Listas doblemente ligadas en las caches:
directorio (MP): estado / @c1
directorio MC: estado / @ci-1 / @ci+1
▪ SCI scalable coherent interface
Numa-Q
Estructura del multiprocesador NUMA-Q
Arquitecturas ParalelasIF - EHU
CD-DSM 417
Estados de los bloques:
▪ En MC: - posición: Only, Head, Mid, Tail- estado: Dirty (M), Fresh (S), Valid (S’), Exclusive (E)
Ej.: Only-Fresh, Head-Fresh, Head-Dirty, Mid-Valid...
- y estados busy
▪ En “MP”: Home (I), Fresh (E, S), Gone (M, O)
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 427
Tres funciones para mantener la coherencia de los datos:
▪ List Construction Para cargar un bloque de datos en la cache (Rd) y ponerlo en cabeza de la lista de copias.
▪ Roll-outPara eliminar un bloque de la cache (reemplazo), y quitarlo de la lista de copias.
▪ Purge Para modificar una variable (Wr), y, por tanto, invalidar el resto de copias y actualizar la lista.
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 437
Lectura: List Construction (Home)
L H
1b. LC (Rd A)
2b. Bloque1a
→ busy 2a
→ F | @L
I
Dir (MC) H | *
Dir (MP)
→ O-F|*-*
3
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 447
¿qué cambiaría si estuviera en Gone?
L H
1b. LC (Rd A)
I → H-F | *-@R
5
2b. Bloque + @R
1a
→ busy
2a→ F | @L
Dir (MC)
F | @R
Dir (MP)
R
3. New Head (@L)
4b. ACK
→ T-V | @L-*
4a
Dir (MC)
O-F | *-*
H-F | *-@R2 → M-V | @L-@R2
Protocolo de coh. SCI
Lectura: List Construction (Fresh/Gone)
Arquitecturas ParalelasIF - EHU
CD-DSM 457
Escrituras: ¡sólo en la copia de la cabecera!acierto / head → Purge
fallo → List Construction + Purge
acierto / no head → Roll-Out + L. Const. + Purge
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 467
Purge (Only-Fresh)
L H
1b. Wr (est. A)
2b. ACK1a
→ busy
2a
→ G | @L
O-F | *-*
Dir (MC)
F | @L
Dir (MP)
→ O-D | *-*
3
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 477
LH R1
1b. Wr (est. A)
2b. ACK
3. INV A
4b. ACK + @R2
R2
6b. ACK + *
5. INV A
Purge (Head-Fresh)
F | @L
Dir (MP)
→ G | @L
2a
1a
→ busy H-F | *-@R1
Dir (MC)
→ O-D | *-*
7 M-V |@L-@R2
Dir (MC)
→ I | *-*
4a
T-V |@R1-* → I | *-*
6a
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 487
Roll-Out (Wr / reempl.)
L R2
1c. RO A + @R1
3b. ACK
3a→ T-V | @R1-*T-V | @L-*
Dir (MC)
R1
1b. RO A + @R2
2b. ACK
2a→ H-D | *-@R2H-D | *-@L
Dir (MC)
1a→ busyM-V | @R1-@R2
Dir (MC)
4→ busy / I | *-*
Protocolo de coh. SCI
Arquitecturas ParalelasIF - EHU
CD-DSM 497Protocolo de coh. SCI
Problemas: atomicidad (i)
Dir (MP)G | @R1
H-D|*-@R2
H
R1 R2
T-V | @R1-*busy
L1
Dir (MP)G | @L1
H
L1
NewHead
H
L2
busy
Dir (MP)
G | @L2
HH
L1
H
L2
NewHead
HHH
M-V|@L1-@R2
R1L1L1 Ack +
bl
H-D | *-@R1
L1
M-V|@L2-@R1
L2Ack + bl
H-D | *-@L1
R1
Arquitecturas ParalelasIF - EHU
CD-DSM 507Protocolo de coh. SCI
Problemas: atomicidad (ii)
R
Dir (MP)
F | @L
H
O-F | *-*
L
busy
LC
busy
Wr
Dir (MP)
F | @R??
NACK
any questions?
Arquitecuras ParalelasIF - EHU
CD - DSM | Protocolo de coh. SCI
R
H
O-F | *-*
L
busy
LC
busy
Wr
Dir (MP)
F | @R??
NACK
Problemas: atomicidad (ii)