Pontificia Universidad Católica de Chile
Escuela de Ingeniería
Departamento de Ciencia de la Computación
[ Arquitectura de Computadores ]
MULTIPROCESADOR Y
ARQUITECTURAS ALTERNATIVAS
IIC 2342
Semestre 2006-2
Domingo Mery
Präsentat
ion
D.Mery
1
Arquitectura de Computadores
[ Índice ]
7.1 SIMD, MIMD, VLIW, EPIC
7.2 Arquitectura sistólica
7.3 Sistemas de memoria compartida
7.4 Coherencia de caché
7.5 Modelos de memoria y consistencia
D.Mery
2
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
7.1 SIMD, MIMD, VLIW, EPIC
7.2 Arquitectura sistólica
7.3 Sistemas de memoria compartida
7.4 Coherencia de caché
7.5 Modelos de memoria y consistencia
D.Mery
3
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
Paralelismo:
D.Mery
4
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
Paralelismo:
 a 11

a
 21
 

 a m1
a 12

a 22


am2

a 1 n   x1   b1 
   
a2n x2
b
    2 
      
   
a mn   x n   b m 
Esta multiplicación es “paralelizable” fácilmente empleando
m procesadores, cada uno se ocupa de multiplicar una fila
de la matriz A con el vector x.
D.Mery
5
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
SISD:
Single Instruction Single Data, es una secuencia de
instrucciones y una secuencia de datos.
Un único procesador interpreta una única secuencia de
instrucciones, para operar con los datos almacenados en
una única memoria. Los computadores monoprocesador
caen en esta categoría.
D.Mery
6
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
SISD:
Unidad de SI Unidad de
control
proceso
D.Mery
7
SD Unidad de
memoria
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
SISD:
Instructions
Data Input
D.Mery
Processor
8
Data Output
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
SIMD:
Single Instruction Multiple Data, es una secuencia de
instrucciones y múltiples secuencias de datos.
Una única instrucción de máquina controla paso a paso la
ejecución simultánea y sincronizada de un cierto número de
elementos de proceso. Cada elemento de proceso tiene una
memoria asociada, de forma que cada instrucción es
ejecutada por cada procesador, con un conjunto de datos
diferentes. Los procesadores matriciales y vectoriales
pertenecen a esta categoría.
D.Mery
9
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
SIMD:
Unidad de
control
D.Mery
SI
Elemento SD
de proceso 1
Memoria
Local 1
Elemento SD
de proceso 2
Memoria
Local 2
Elemento SD
de proceso n
Memoria
Local n
10
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
Instruction
Stream
SIMD:
Data Input
stream A
Data Input
stream B
Data Output
stream A
Processor
A
B
Processor
Data Input
stream C
D.Mery
Data Output
stream B
Processor
C
11
Data Output
stream C
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MISD:
Multiple Instruction Single Data, son múltiples secuencias de
instrucciones y una secuencia de datos.
Se transmite una secuencia de datos a un conjunto de
procesadores, cada uno de los cuales ejecuta una
secuencia de instrucciones diferente. Esta estructura ha sido
implementada sólo con fines de investigación.
D.Mery
12
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MISD:
Instruction
Stream A
Instruction
Stream B
Instruction Stream C
Processor
Data
Output
Stream
A
Data
Input
Stream
Processor
B
Processor
C
Esto es más un ejercicio intelectual que un ejercicio práctico.
D.Mery
13
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MIMD:
Multiple Instruction Multiple Data, son múltiples secuencias
de instrucciones y múltiples secuencias de datos.
Un conjunto de procesadores ejecuta simultáneamente
secuencias de instrucciones diferentes con conjuntos de
datos diferentes. Los clusters son ejemplos de esta
categoría.
D.Mery
14
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MIMD:
Instruction Instruction Instruction
Stream A Stream B Stream C
Data Input
stream A
Data Input
stream B
Data Output
stream A
Processor
A
Processor
B
Processor
Data Input
stream C
D.Mery
Data Output
stream B
C
15
Data Output
stream C
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MIMD (con memoria compartida):
Unidad de
Control 1
SI
Elemento SD
de proceso 1
Unidad de
Control 2
SI
Elemento SD
de proceso 2
Unidad de
Control n
SI
Elemento SD
de proceso n
D.Mery
16
Memoria
Compartida
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MIMD (con memoria distribuida):
Unidad de
Control 1
SI
Elemento SD
de proceso 1
Memoria
Local 1
Unidad de
Control 2
SI
Elemento SD
de proceso 2
Memoria
Local 2
Unidad de
Control n
SI
Elemento SD
de proceso n
Memoria
Local n
D.Mery
17
Red de
Interconexión
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
MIMD (con memoria compartida y caché):
Los datos pueden ser
modificados y guardadados
en la caché
D.Mery
18
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
VLIW:
Very Long Instruction Word,
La idea es que el compilador empaquete muchas
instrucciones (de 4 a 8) en una sola palabra de instrucción
muy larga. Esta palabra corresponde a un conjunto de
unidades funcionales (FU). VLIW corresponde a una
arquitectura superescalar.
instrucción
operation 1 operation 2 operation 3 operation 4 operation 5
D.Mery
19
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
VLIW:
IF
D.Mery
RF1
EX1
WB1
RF2
EX2
WB2
RFk
EXk
WBk
DC
20
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
VLIW:
D.Mery
21
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
Tradicional vs. VLIW:
En VLIW, la decisión del orden de las ejecuciones la toma el
compilador. En el superescalar la decisión la toma el
hardware.
D.Mery
22
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
EPIC: (Es el nombre que Intel le puso a VLIW):
Explicitly Parallel Instruction Computing, se basa en
innovaciones como predicción, especulación y paralelismo
explícito. Es un método para ordenar las instrucciones de tal
forma que puedan ejecutarse de manera paralela.
D.Mery
23
Arquitectura de Computadores
Präsentat
ion
SIMD, MIMD, …
[ Multiprocesadores ]
Paralelismo explícito:
Ejemplo de un banco con recibidor que envía al cliente a
hacer cola a cualquier ventanilla (el cliente no es atendido
correctamente) vs. un recibidor inteligente que envía al
cliente a la ventanilla adecuada.
D.Mery
24
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
7.1 SIMD, MIMD, VLIW, EPIC
7.2 Arquitectura sistólica
7.3 Sistemas de memoria compartida
7.4 Coherencia de caché
7.5 Modelos de memoria y consistencia
D.Mery
25
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
Un arreglo sistólico es un conjunto de procesadores
dispuestos de una manera regular (por lo general
rectangular) donde los datos fluyen sincrónicamente a través
del arreglo entre sus vecinos.
Cada procesador toma en cada paso toma datos de sus
vecinos (por lo general Norte y Oeste), los procesa y se los
entrega a sus procesadores vecinos (por lo general Sur y
Este).
D.Mery
26
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
D.Mery
Arquitectura sistólica
27
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Ejemplos:
Arquitectura sistólica
procesamiento digital de señales,
procesamiento digital de imágenes,
multiplicación de matrices,
evaluación de polinomios
etc.
Rápidos en estas operaciones, sin embargo están limitados
a estas aplicaciones, para otras operaciones no son
prácticos.
D.Mery
28
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
• Arreglo lineal de procesadores
• La comunicación fluye a la derecha y a la izquierda.
D.Mery
29
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
• La evaluación polinomial es simple
– Se usa la regla de Horner:
y = ((((anx + an-1)*x + an-2)*x + an-3)*x …… a1)*x + a0
– Los elementos de proceso (PE) se colocan en pareja
• Se multiplica una entrada por ,
• El resultado se pasa a la derecha
• Se suma aj al resultado de la izquierda
• Se pasa el resultado a la derecha
D.Mery
30
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
TOPOLOGÍAS:
• 1D, 2D, 3D y 4D
D.Mery
31
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
Procesadores vectoriales y matriciales: diseñados para
operaciones con vectores y matrices.
D.Mery
32
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
• Ejemplo:
– Producto punto
• Se hace fetch a cada elemento del vector.
D.Mery
33
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
• Ejemplo:
– Producto matricial
D.Mery
34
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Arquitectura sistólica
Operación:
A*B+ C
El resultado (A*B)
se realimenta en un
registro vectorial
D.Mery
35
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
7.1 SIMD, MIMD, VLIW, EPIC
7.2 Arquitectura sistólica
7.3 Sistemas de memoria compartida
7.4 Coherencia de caché
7.5 Modelos de memoria y consistencia
D.Mery
36
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
Accesos a la memoria:
• Memoria distribuida
D.Mery
P
P
M
M
37
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
Accesos a la memoria:
• Memoria compartida
P
D.Mery
M
P
38
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
Sistema con memoria compartida:
Unidad de
Control 1
SI
Elemento SD
de proceso 1
Unidad de
Control 2
SI
Elemento SD
de proceso 2
Unidad de
Control n
SI
Elemento SD
de proceso n
D.Mery
39
Memoria
Compartida
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
El principal problema es
cuando todos los
procesadores intentan
acceder a la memoria
global al mismo tiempo
(cuello de botella)
Memoria
Red de interconexión
Procesadores
D.Mery
40
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
Solución:
•Dividir la Memoria en Módulos
Memoria
• Cada módulo conectado a los
procesadores por una red de
switching de alta performance
Red de interconexión
• Este enfoque tiende a trasladar
el cuello de botella a la red
Procesadores
D.Mery
41
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
Características:
•
Un espacio de direcciones único y común.
•
Comunicación vía read & write
•
Sincronización vía bloqueos (locks).
D.Mery
42
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Memoria compartida
Sección crítica
D.Mery
43
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
7.1 SIMD, MIMD, VLIW, EPIC
7.2 Arquitectura sistólica
7.3 Sistemas de memoria compartida
7.4 Coherencia de caché
7.5 Modelos de memoria y consistencia
D.Mery
44
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
En los sistemas multiprocesador se disponen de varios
niveles de caché asociados a cada procesador. Esta
organización es esencial para obtener un buen
desempeño.
Sin embargo, esto ocasiona el problema conocido como
coherencia de caché…
D.Mery
45
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
coherencia de caché…
Pueden existir varias copias del mismo dato
simultáneamente en cachés diferentes y, si los
procesadores actualizan sus copias, puede producirse
una visión inconsistente de la memoria.
D.Mery
46
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Los datos pueden ser
modificados y guardadados
en la caché
Qué pasa si otro
procesador quiere esos
datos?
El procesador
lee los datos
antiguos!
D.Mery
47
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Existen dos técnicas principales
1.
Escritura directa
2.
Post-escritura
D.Mery
48
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Escritura directa:
Todas las operaciones de escritura se hacen tanto en la
caché como en la memoria principal inmediatamente. Así se
asegura que el contenido de la memoria sea siempre válido.
Desventaja: se genera un gran tráfico a la memoria principal
que puede disminuir el desempeño.
D.Mery
49
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Post-escritura:
Cada bloque de la caché posee un bit de actualización que
se inicializa en ‘0’ cuando se carga un bloque nuevo en la
caché.
Cada vez que se escriba en el bloque el bit de actualización
se pone en ‘1’.
Cuando se desee reemplazar el bloque, el bloque se copia
a la memoria principal sólo si el bit de actualización es ‘1’.
Desventaja: muchas veces hay porciones de la memoria
principal que no son válidos.
D.Mery
50
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Soluciones por Software
Intentan evitar la necesidad de circuitería y lógica hardware
adicional, dejando que el compilador y el sistema operativo se
encarguen del problema.
Ventaja: transfiere el costo de la detección de posibles
problemas desde el hardware al software.
Desventaja: el compilador toma a veces decisiones
conservadoras que pueden ocasionar una utilización
ineficiente de la caché.
D.Mery
51
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Soluciones por Software
El compilador realiza un análisis del código para determinar
qué datos puedan dar problemas al pasar a la caché y los
marca como “non-cachable”. Luego, el sistema operativo (o el
hardware) impide que se pasen a la caché estos datos
marcados.
D.Mery
52
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Soluciones por Software
El enfoque más simple consiste en impedir que cualquier dato
compartido pase a la caché!!
Otras soluciones analizan el código y determinan periodos
seguros para las variables compartidas, es decir, se detectan
las regiones críticas de los programas (en los cuales los
programas acceden a variables compartidas) y no se permite
que dos programas estén simultáneamente en la misma
región crítica.
D.Mery
53
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Soluciones por Hardware
Permiten reconocer en el momento de la ejecución las
situaciones de inconsistencias potenciales.
Puesto que el problema se considera sólo en el momento en
que aparece, existe un uso más efectivo de las cachés,
mejorándose el desempeño en relación a las soluciones por
software.
Además, estas soluciones son transparentes para el
programador y el compilador, reduciendo la complejidad en el
desarrollo del software.
D.Mery
54
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Protocolos de directorio (Soluciones por Hardware):
Recogen y mantienen la información acerca de dónde residen
las copias de las líneas de la memoria. Por lo general, existe
un controlador centralizado que es parte del controlador de
memoria principal y un directorio que se almacena en la
memoria principal.
El directorio contiene información de estado global en relación
con los contenidos de las diferentes cachés locales.
Cuando el controlador individual de una caché hace una
petición, el controlador centralizado comprueba y emite las
órdenes precisas para la transferencia entre memoria y caché
(o entre distintas cachés).
D.Mery
55
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Protocolos de directorio (Soluciones por Hardware):
Antes de que un procesador pueda escribir en una copia local
de una línea, debe solicitar al controlador acceso exclusivo a
dicha línea. Antes de ceder este acceso exclusivo, el
controlador envía un mensaje a todos los procesadores.
Después de recibir el reconocimiento de cada unos de esos
procesadores el controlador cede el acceso exclusivo al
procesador que lo solicitó.
D.Mery
56
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Protocolos de directorio (Soluciones por Hardware):
Cuando otro procesador intenta leer una línea cedida para
acceso exclusivo de otro procesador, enviará una notificación
de fallo de caché al controlador. Entonces, el controlador
manda una orden al procesador que posee la línea requerida,
para que lo vuelva a escribir en memoria principal. Ahora, la
línea puede compartirse para lectura por el procesador original
y el que solicita el acceso.
D.Mery
57
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Protocolos de directorio (Soluciones por Hardware):
Desventaja de este método: se puede generar un cuello de
botella ya que puede haber un exceso de comunicación entre
los controladores locales y el controlador de la memoria
principal.
D.Mery
58
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Protocolos de sondeo o “Snoopy” (Soluciones por Hardware):
Distribuyen la responsabilidad de mantener coherencia de
caché entre todos los controladores de caché multiprocesador.
Una caché debe reconocer cuándo una línea de las que tiene
está siendo compartida con otras cachés. Cuando se realiza
una actualización en una línea de caché compartida, debe
anunciarse a todas las otras cachés mediante un mecanismo
de difusión (broadcast). Cada controlador de caché es capaz
de sondear la red para observar las notificaciones que se
difunden y reaccionar adecuadamente.
D.Mery
59
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Protocolos de sondeo MESI (Soluciones por Hardware):
La caché de datos incluye dos bits de estado que indican uno
de los cuatro siguientes estados:
• Modified:
la línea de caché ha sido modificada (es distinta a su
valor en memoria prinicipal), y está disponible sólo en esta caché.
• Exclusive: la línea de caché tiene el mismo contenido que en
memoria principal, y no está presente en ninguna otra caché.
• Shared: la línea caché tiene el mismo contenido que en memoria
principal, y puede estar presente en otra caché.
• Invalid: la línea de caché no contiene datos validos.
D.Mery
60
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Coherencia de caché
Línea de caché en procesador que inicia transferencia
D.Mery
RH
Acierto de lectura
Escribir en memoria la línea de
caché modificada
RMS
Fallo de lectura, compartida
Invalida transacción
RME
Fallo de lectura, exclusiva
WH
Acierto de escritura
WM
Fallo de escritura
Lectura para modificación
Cargar línea de caché
61
Arquitectura de Computadores
Präsentat
ion
[ Índice ]
7.1 SIMD, MIMD, VLIW, EPIC
7.2 Arquitectura sistólica
7.3 Sistemas de memoria compartida
7.4 Coherencia de caché
7.5 Modelos de memoria y consistencia
D.Mery
62
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Modelo de Memoria:
Especifica cómo se resuelven los conflictos de acceso a la
memoria. Estos conflictos suceden sólo cuando la memoria
es compartida.
D.Mery
63
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
El acceso a la memoria compartida puede ser visto como
un contrato entre el hardware y el software de memoria. Si
el software acepta cumplir con ciertas reglas, la memoria
conviene en entregar ciertos resultados. La discusión se
centra en la naturaleza de las reglas. Estas reglas se
denomina “modelos de consistencia”.
D.Mery
64
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Ejemplo:
CPU-0 escribe ‘1’ en la posición X de la memoria.
luego…
CPU-1 escribe ‘2’ en la posición X.
luego...
CPU-2 lee la posición X y obtiene ‘1’
¿algo falló??? Todo depende de lo que la memoria
prometió en su contrato!
D.Mery
65
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Modelos posibles:
• Consistencia estricta
• Consistencia secuencial
• Consistencia de procesador
• Consistencia débil
• Consistencia de liberación
D.Mery
66
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia estricta:
Cualquier lectura de una posición X siempre devuelve el
valor de la escritura más reciente de X.
En la práctica este modelo es imposible de implementar de
otra manera que no sea tener un solo módulo de memoria
que atiende todas las solicitudes bajo el régimen de
primero llega-primero se atiende, sin uso de cachés ni
repetición de datos.
Una implementación así convertiría a la memoria en un
enorme cuello de botella y por ello este modelo no es
recomendable.
D.Mery
67
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia secuencial:
En presencia de múltiples solicitudes de lectura y escritura,
el hardware escoge (de forma no determinista) cierta
intercalación de todas las solicitudes, pero todas las CPU
perciben el mismo orden.
D.Mery
68
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia secuencial:
Ejemplo:
1. CPU-1 escribe 100 en posición X
2. 1 ns después: CPU-2 escribe 200 en X
3. 1 ns después: CPU-3 y CPU-4 leen dos veces posición X
CPU 1
(X)100
D.Mery
2
(X)200
3y4
lee X, lee X
(dos veces)
69
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia secuencial:
Secuencias posibles:
E100
E200
L3 = 200
L3 = 200
L4 = 200
L4 = 200
CPU 1
(X)100
D.Mery
E100
L3 = 100
E200
L4 = 200
L3 = 200
L4 = 200
E200
L4 = 200
E100
L3 = 100
L4 = 100
L3 = 100
2
(X)200
3y4
lee X, lee X
(dos veces)
70
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia secuencial:
Secuencias posibles:
E100
E200
L3 = 200
L3 = 200
L4 = 200
L4 = 200
E100
L3 = 100
E200
L4 = 200
L3 = 200
L4 = 200
E200
L4 = 200
E100
L3 = 100
L4 = 100
L3 = 100
Pase lo que pase, una memoria secuencialmente
consistente nunca permitirá que la CPU-3
obtenga (100,200) mientras la CPU-4 obtiene
(200,100).
D.Mery
71
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia secuencial:
Se garantiza que hay un solo ordenamiento global de todas
las escrituras que todas las CPU ven igual.
Cuando suceden varias cosas al mismo tiempo, existe un
orden verdadero en el que ocurren, tal vez determinados por
los tiempos y la casualidad, pero todos los procesadores
observan este mismo orden.
D.Mery
72
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia del procesador:
Este modelo tiene dos propiedades:
1. Todas las CPU ven las escrituras de cualquier CPU en
el orden que se emitieron.
2. Para cada palabra de memoria, todas las CPU ven
todas las escrituras en ella en el mismo orden.
D.Mery
73
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia del procesador:
Este modelo tiene dos propiedades:
1. Todas las CPU ven las escrituras de cualquier CPU en
el orden que se emitieron.
Ejemplo: si la CPU-1 emite escrituras con los valores 1A,
1B y 1C a la posición X en ese orden, entonces todos
los demás procesadores las verán en ese orden
también. Esto es, una CPU no verá en la posición X el
valor 1B y luego el 1A.
D.Mery
74
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia del procesador:
Este modelo tiene dos propiedades:
2. Para cada palabra de memoria, todas las CPU ven
todas las escrituras en ella en el mismo orden.
Este punto asegura que cada localidad de memoria tendrá
un valor inequívoco después de que varias CPU
escriben en ella y después se detienen. Todos deben
estar de acuerdo en quién fue el último.
D.Mery
75
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia del procesador:
Ejemplo:
CPU-1 escribe 1A, 1B, 1C en X
CPU-2 escribe 2A, 2B, 2C en X
CPU-3 lee continuamente X como:
1A, 1B, 2A, 2B, 1C, 2C ó
2A, 1A, 2B, 2C, 1B, 1C ó etc.
No se garantiza que toda CPU verá el mismo ordenamiento
(esto es consistencia secuencial). PERO sí se garantiza
verá una secuencia en la que 1B ocurra antes que 1B (el
orden en que cada CPU realiza sus escrituras se observa
en todas las otras CPU.
D.Mery
76
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia débil:
No se garantiza que las escrituras de una sola CPU se
verán en orden. En el ejemplo anterior pudiera ser que una
CPU lea 1B antes que 1A.
Sin embargo, existen algunas variables de sincronización o
una operación de sincronización, con la que todas las
escrituras pendientes de terminan y no se inicia ninguna
nueva hasta que todas las viejas se lleven a cabo y la
sincronización termina. El vaciado si es secuencialmente
consistente.
D.Mery
77
Arquitectura de Computadores
Präsentat
ion
[ Multiprocesadores ]
Modelo de memoria
Consistencia de liberación:
La consistencia débil tiene el problema de que es muy
ineficiente porque debe terminar todas las operaciones de
memoria pendiente y detener las nuevas hasta que
terminen las actuales.
La idea de la consistencia de liberación se basa en que
cuando un proceso sale de una sección crítica no es
necesario hacer que todas las escrituras se lleven a cabo
independientemente; sólo es necesario asegurarse de que
terminen antes de que cualquier programa ingrese otra vez
a esa sección crítica.
D.Mery
78
Arquitectura de Computadores
Präsentat
ion
Descargar

Kein Folientitel