TEMA 4 PROCESAMIENTO PARALELO

Tipos de plataformas de computación paralela

Organización lógica
Organización física
Sistemas de memoria compartida
Sistemas de memoria distribuida
 Tipos de plataformas de computación
paralela
• El procesamiento paralelo es el método de organización
de las operaciones en un sistema de computación donde
más de una operación es realizada de manera
simultánea. CARACTERÍSTICAS:
– Compuesto por dos o más procesadores
– Los procesadores deben compartir el acceso a una memoria
común
– Los procesadores deben compartir el acceso a canales de
E/S, unidades de control y dispositivos
– El sistema es controlado por un único sistema operativo
 Estructura de los Tipos de plataformas
de computación paralela
Dependerá de:
• Organización lógica. Visión que tiene el programador
– La estructura de control
• Maestro/Esclavo
• SPMD (Single Program Multiple Data)
– Modelo de comunicación entre tareas
• Espacio de direcciones único y compartido (Memoria compartida)
• El paso de mensajes
• Organización física. Según la forma de acceso en un sistema multiprocesador a
la región de memoria común a todos los procesadores
– Sistema de memoria compartido: un único sistema de memoria es compartido por todos
los procesadores
– Sistema de memoria distribuida: cada procesador tiene su propia memoria física,
inaccesible por el resto.
SISTEMAS DE MEMORIA COMPARTIDA
• Organización física de las plataformas paralelas. Según la forma de acceso en un
sistema multiprocesador a la región de memoria común a todos los procesadores
– Sistema de memoria compartido: un único sistema de memoria es compartido por todos los
procesadores
– Sistema de memoria distribuida: cada procesador tiene su propia memoria física, inaccesible
por el resto.

• Para diseñarla hay que tener en cuenta

– La organización de la memoria principal (Maestro/Esclavo y SPMD)
– El diseño de la red de interconexión
• Redes estáticas
• Redes dinámicas
– El diseño del protocolo de coherencia de la caché
SISTEMAS DE MEMORIA COMPARTIDA.
REDES ESTÁTICAS
• Una red estática, también denominada red directa, es una red cuya
topología queda definida de manera definitiva y estable durante la
construcción de la máquina paralela.
• En general, las redes estáticas pueden presentar distintas
topologías en función de las conexiones punto a punto que se
establezcan entre sus procesadores. Se pueden dividir en cuatro
tipos básicos:
– redes unidimensionales
– bidimensionales
– tridimensionales
– hipercubos
 Redes unidimensionales
• Un procesador puede enviar un mensaje
simultáneamente a un procesador situado a su izquierda y
a otro a su derecha.
• Esta topología es muy simple pero presenta problemas de
comunicación cuando el número de procesadores es
elevado.
 Redes Bidimensionales
• La red sistólica es una malla con conexión en una diagonal entre los
procesadores de un cuadrado
• Red completamente conectada es el esquema de interconexión
ideal.
 Redes Bidimensionales
• Las redes de árboles tienen la desventaja de que las
comunicaciones pueden verse comprometidas en un
nodo cuando el número de procesadores es grande y
se realizan comunicaciones entre procesadores
situados en los niveles superiores.
 Redes Bidimensionales
• Una estrategia comúnmente para aliviar esta desventaja usada consiste en
aumentar el número de conexiones de comunicación entre los
procesadores de menor nivel, es decir, los cercanos a la raíz.
 Redes Bidimensionales
• Las redes mesh bidimensionales cada procesador se conecta
directamente con otros cuatro procesadores salvo en los extremos.
• Como se hace con los arreglos lineales para forma un anillo. A esta
topología se le denomina mesh cerrada o toro.
 Redes Tridimensionales
• La topología mesh tridimensional, que de
nuevo puede establecerse con los
procesadores periféricos conectados o no
conectados.
•
Hipercubo
Los hipercubos pueden construirse de forma recursiva teniendo en cuenta que un
hipercubo de dimensión cero consta de un único procesador, uno de dimensión
uno se forma conectando dos hipercubos de dimensión cero, y así sucesivamente,
de manera que:
• Un hipercubo de dimensión l se forma conectando los procesadores
correspondientes de dos hipercubos de dimensión I - 1.
 Hipercubos
• Los hipercubos presentan propiedades especialmente interesantes, entre
las que destacan las siguientes:
– Dos procesadores se conectan entre sí, si y sólo si sus etiquetas, en binario,
tienen exactamente un bit distinto en una posición determinada
– Un procesador de un hipercubo de dimensión d se conecta directamente a d
procesadores.
– Todo hipercubo de dimensión d puede dividirse en dos de dimensión d-1.
Para ello se selecciona la posición de un bit y se agrupan todos los
procesadores que tengan un cero en esa posición. Todos ellos forman una
partición y el resto forma la segunda partición.
 Hipercubos
• Un parámetro de especial interés
es la denominada distancia de
Hamming, que se define como el
número total de posiciones de
bits para los que las etiquetas de
dos procesadores son diferentes.
• La distancia de Hamming entre
dos procesadores de etiquetas a y
b es el número de bits a 1 que hay
tras el resultado de la operación
a@ b, donde @ es la or-exclusiva.
 Caracterización de redes estáticas
• Son cuatro los parámetros que caracterizan una red
estática:
– el diámetro: máxima distancia entre dos procesadores
cualesquiera, entendiéndose por distancia el mínimo
camino entre ellos.
– la conectividad: medida de la multiplicidad de caminos
entre dos procesadores.
– ancho de bisección: mínimo número de enlaces de
comunicación que deben eliminarse para que la red quede
dividida en dos partes iguales.
– el coste: medida del número de enlaces de comunicación
o la cantidad de cableado necesario en la red.
Caracterización de redes estáticas
ej 1 2ª semana 2013
ej 1 c) 2ª semana 2013
SISTEMAS DE MEMORIA COMPARTIDA
• Organización física de las plataformas paralelas. Según la forma de
acceso en un sistema multiprocesador a la región de memoria común a
todos los procesadores
– Sistema de memoria compartido: un único sistema de memoria es
compartido por todos los procesadores
– Sistema de memoria distribuida: cada procesador tiene su propia memoria
física, inaccesible por el resto.

• Para diseñarla hay que tener en cuenta

– La organización de la memoria principal (Maestro/Esclavo y SPMD)
– El diseño de la red de interconexión
• Redes estáticas
• Redes dinámicas
– El diseño del protocolo de coherencia de la caché
 REDES DINÁMICAS
Recomendables para el diseño de sistemas de
propósito general
• Redes basadas en bus
• Redes crossbar (o matriciales)
• Redes multietapa
 Redes basadas en bus
La colisión de peticiones de acceso al bus se soluciona usando una lógica de arbitraje o
módulo de arbitraje
• Prioridad fija
• FIFO
• LRU

Se puede mejorar el rendimiento incluyendo una memoria caché en cada

procesador
 Redes crossbar (o matriciales)
Redes de tipo no bloqueantes. La latencia de comunicación entre elementos es constante.
Ej3 septiembre 2012
 Redes multietapa
• Conectan dispositivos de entrada a
dispositivos de salida a través de un
conjunto de etapas de conmutadores,
donde cada conmutador es una red de
barra cruzada.
• Existe una serie de etapas Gi
compuestas de conmutadores
conectados a las etapas adyacentes
mediante conexiones estáticas Cj.
• El número de etapas y los patrones de
conexión entre etapas determinan la
capacidad de encaminamiento de las
redes.
 Redes multietapa
• Los bloques básicos de construcción de
una red multietapa unidireccional son los
conmutadores unidireccionales.
• La figura muestra los cuatro posibles
estados de un conmutador 2 × 2. Los
últimos dos estados se usan para soportar
las comunicaciones uno a muchos y uno a
todos.
• Se puede reconfigurar dinámicamente los
modos de conmutación de las distintas
etapas otorgando a estas redes una gran
flexibilidad.
 Ejemplo redes multietapa: Redes omega
• La permutación por baraje perfecto realiza un desplazamiento cíclico hacia la izquierda de los
dígitos de X en una posición. Para k = 2 (conmutadores 2x2), esta acción se corresponde con el barajado
perfecto de una baraja de N cartas
2ª parte ej3 septiembre 2013

0
 Ejemplo redes multietapa: Redes
omega
• 16 entradas y 16 salidas
 Ejemplo redes multietapa: Redes omega
• 16 entradas y 16 salidas
• Ej3 septiembre reserva 2012

1
1

0
0
 Ejemplo redes multietapa: Redes omega
• 16 entradas y 16 salidas
• Ej3 septiembre reserva 2012

Al fastidiarse el tercer conmutador de la segunda

etapa, haría que 4 procesadores no pudieran
comunicarse con 8 elementos de memoria. 32
conexiones no realizables.
32/(16*16)=2/16=1/8=12,5%
 Ejemplo redes multietapa: Redes
omega
• Se usan conmutadores binarios
• Son redes bloqueantes (ciertas conexiones pueden bloquear otras conexiones)
como todas las redes multietapa
 Ejemplo redes multietapa: Redes
omega
• El baraje perfecto inverso realiza la acción contraria (rotación a derechas)
Ejemplo redes multietapa: Red baseline
i
Ejemplo redes multietapa: Red
3
baseline
2 1 0
Ejemplo redes multietapa: Red butterfly
k
Ejemplo redes multietapa: Red
0 1
butterfly
2 3
Comparación del rendimiento de redes
dinámicas
SISTEMAS DE MEMORIA COMPARTIDA
• Organización física de las plataformas paralelas. Según la forma de acceso en un
sistema multiprocesador a la región de memoria común a todos los procesadores
– Sistema de memoria compartido: un único sistema de memoria es compartido por todos los
procesadores
– Sistema de memoria distribuida: cada procesador tiene su propia memoria física, inaccesible
por el resto.

• Para diseñarla hay que tener en cuenta

– La organización de la memoria principal (Maestro/Esclavo y SPMD)
– El diseño de la red de interconexión
• Redes estáticas
• Redes dinámicas
– El diseño del protocolo de coherencia de la caché
Protocolos de coherencia de caché
• El uso de memorias caché para mejorar el rendimiento
está generalizado.
• Un sistema de memoria es coherente si cualquier lectura
de un dato devuelve el valor más recientemente escrito de
ese dato.
• Los problemas de coherencia se deben a
– Modificar datos compartidos
– Migración de procesos
– Uso de Entrada/Salida mediante Acceso Directo a Memoria
 Protocolos de coherencia de caché
Opciones para solucionar la incoherencia de caché
• Invalidar: invalidar las copias en las cachés del dato modificado

• Actualizar: actualizar todas las copias en las cachés del dato que se
acaba de modificar
 Invalidación de datos (monitorizando el número de copias
Protocolos de existentes y el estado de cada copia)
coherencia de caché ESTADO DE LAS COPIAS
INVÁLIDO: bloque de datos no cargado en caché
COMPARTIDO: bloque de datos cargado en caché y válido
SUCIO: bloque de datos cargado en caché, válido para mi
pero no para el resto de cachés

como consecuencia de las señales de

control que aparecen en el bus, debidas a
lecturas y escrituras de otros procesadores
• Cuando el procesador lee una
LECTURA
variable que está en la cache (bien
en compartido o sucio), el estado
del bloque no se modifica ni se
generan señales de control.
 Veamos ahora las consecuencias de las operaciones realizadas por otros procesadores y
que se detectan en el bus.
• Un procesador ha solicitado un bloque
C_LECTURA
de datos, del cual no disponía (estado
inválido), para lo que activado la señal
C_lectura. El bloque solicitado podría
estar en la cache local, en estado
COMPARTIDO o SUCIO.
– Si está en estado COMPARTIDO, no hay
que hacer nada: a las copias que ya había
antes, coherentes, se le añade una más.

Carga x
Veamos ahora las consecuencias de las operaciones realizadas por otros procesadores y
que se detectan en el bus. C_LECTURA
– Pero si está en estado SUCIO, es decir, si la
copia local es la única y no está datos sucios
actualizada, hay que modificar su estado. A
partir de ahora habrá dos copias en el
sistema, y la única opción en este
protocolo es pasar al estado COMPARTIDO,
es decir, pasar a ser coherente: el nuevo
estado es COMPARTIDO y hay que
actualizar (escribir) el bloque en la
memoria principal.

Carga x

2
• En caso de escritura, el estado del bloque pasará a ser
sucio: una única copia y modificada (write-back).
ESCRITURA
• Si ya estaba en estado sucio no hay que hacer nada;
• pero si estaba en estado compartido hay que invalidar
todas las posibles copias.
• Finalmente, si se detecta la señal C_escritura en el bus, la decisión es muy simple: si el bloque de datos
está en la cache, hay que eliminarlo (Inválido). Dado su efecto, la señal de invalidación C_escritura tiene
preferencia frente a la señal C_lectura cuando ambas se activan a la vez.
• Como la política de escritura es write-through, es posible que el bloque que hay que borrar esté en estado
sucio, en cuyo caso habrá que actualizar su contenido en MP.

C_ESCRITURA
DATOS COMPARTIDOS
inválido
• Finalmente, si se detecta la señal C_escritura en el bus, la decisión es muy simple: si el bloque de datos
está en la cache, hay que eliminarlo (Inválido). Dado su efecto, la señal de invalidación C_escritura tiene
preferencia frente a la señal C_lectura cuando ambas se activan a la vez.
• Como la política de escritura es write-through, es posible que el bloque que hay que borrar esté en estado
sucio, en cuyo caso habrá que actualizar su contenido en MP.

C_ESCRITURA
DATOS COMPARTIDOS

inválido
• Finalmente, si se detecta la señal C_escritura en el bus, la decisión es muy simple: si el bloque de datos
está en la cache, hay que eliminarlo (Inválido). Dado su efecto, la señal de invalidación C_escritura tiene
preferencia frente a la señal C_lectura cuando ambas se activan a la vez.
• Como la política de escritura es write-through, es posible que el bloque que hay que borrar esté en estado
sucio, en cuyo caso habrá que actualizar su contenido en MP.

C_ESCRITURA
DATOS SUCIOS

inválido
• Finalmente, si se detecta la señal C_escritura en el bus, la decisión es muy simple: si el bloque de datos
está en la cache, hay que eliminarlo (Inválido). Dado su efecto, la señal de invalidación C_escritura tiene
preferencia frente a la señal C_lectura cuando ambas se activan a la vez.
• Como la política de escritura es write-through, es posible que el bloque que hay que borrar esté en estado
sucio, en cuyo caso habrá que actualizar su contenido en MP.

C_ESCRITURA
DATOS SUCIOS

inválido
Protocolos de sondeo o snoopy (medio
compartido)
• El snoopy debe controlar las peticiones y avisos que le lleguen de su
procesador local o del resto a través del bus, y, en función de ellas
– decidir el estado de los bloques de datos
– generar las señales de control adecuadas.
Ej3 2ª semana 2012
Ej3 2ª semana 2012
Ej3 2ª semana 2012

Leer x

Leer x
 Ej3 2ª semana 2012

Leer x

Escribe #2 x
2
Invalido sucio

2 2
2
Protocolos basados en
directorio
• Se pueden dividir
– directorio centralizado
– directorio distribuido.
• En ambos grupos se permite que
existan varias copias
compartidas de la misma línea
de caché para mejorar el
rendimiento del
multiprocesador sin incrementar
demasiado el tráfico en la red.
Protocolos basados en
directorio
• Directorio centralizado: Consiste en
un único directorio o tabla
centralizada donde se guarda
información sobre el lugar donde se
encuentra cada copia de la caché.
Este directorio centralizado es
normalmente bastante grande por lo
que la búsqueda se realiza de forma
asociativa.
• Inconvenientes
– La competencia por el acceso al
directorio (contención)
– Largos tiempos de búsqueda
Protocolos basados en
directorio
• Directorio distribuido: En
el directorio se guarda el
estado de la caché así
como su presencia. El
estado es local, pero la
presencia indica qué
cachés tienen una copia
del bloque.