plataformas paralelas

AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)

Plataformas paralelas

AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro

Curso 2011-2012


Elementos de un computador paralelo

• Hardware:– Múltiples procesadores

– Múltiples memorias

– Redes de interconexión– Redes de interconexión

• Software:– Sistemas Operativos paralelos

– Programas orientados a concurrencia

• Objetivo: Utilizar estos elementos para– Mejorar el Speed-up: Tp = Ts / p

– Abordar problemas con alta demanda de memoria


Plataformas para procesamiento paralelo

• Organización lógica: Visión que tiene el usuario de la máquina, desde el punto de vista del software del sistema.

• Organización física: La arquitectura hardware real.

• La Arquitectura física es, hasta cierto punto, independiente de la arquitectura lógica.


Elementos de la organización lógica

• Control (Taxonomía de Flynn):– SISD/SIMD/MIMD/MISD.

– SPMD: Single Program -Multiple Data

SIMD MIMD Falta de eficiencia en SIMD


Elementos de la organización lógica

• Dos alternativas diferenciadas:

–Plataformas de paso de mensajes.–Plataformas de paso de mensajes.

–Plataformas con espacio de memoria compartida.


Paso de mensajes

Paso de mensajes:– Cada procesador tiene un espacio de memoria

propio e independiente.

– La comunicación se produce a través de mensajes – La comunicación se produce a través de mensajes entre el procesador emisor y el receptor.

– Operaciones básicas: send y receive.

– Estándares: MPI, PVM.

– Ejemplos: IBM SP, SGI Origin 2000, clusters de estaciones de trabajo.


Espacio de memoria compartida

Espacio de memoria compartida– UMA: Acceso a memoria uniforme.

– NUMA: Acceso a memoria no uniforme.

– ccNUMA: Acceso a memoria no uniforme con coherencia de cache.

UMA UMA NUMA


Problema de coherencia de cache

• Problema de coherencia de cache en los sistemas de memoria compartida:– Se debe mantener la coherencia en múltiples

copias de los mismos datos.copias de los mismos datos.

– Imprescindible para mantener la semántica de los programas.

– Protocolos para respetar la coherencia de cache:• Invalidación

• Actualización


Problema de coherencia de cache

Invalidación

Actualización


Protocolos de Invalidación / Actualización

• El protocolo óptimo depende de las características de cada aplicación: Frecuencia de operaciones de lectura / escritura.

• Problemas con compartición falsa: Líneas de • Problemas con compartición falsa: Líneas de cache comunes actualizadas en palabras distintas.

• Equilibrio entre costes de comunicación (actualización) y ciclos de espera (invalidación).

• Los esquemas actuales se basan en el protocolode invalidación.


Invalidación: Coherencia de datos

• Compartido: Dato que está presente en la memoria cache de más de un procesador, pero que aún no ha sido modificado.

• No-válido: Dato en la memoria cache de un • No-válido: Dato en la memoria cache de un procesador, que ha sido modificado por otro.

• Sucio: Dato en la memoria cache de un procesador que lo ha modificado. Toda referencia a este dato será servida por este procesador, y no por la memoria principal.


Coherencia de datos: Protocolo snoopy

• Orientado al uso de bus común.

• Cada procesador mantiene la información de datos compartidos / no-válidos / sucios.

• Se realiza una escucha activa del bus, y cuando se detecta una escritura sobre un dato compartido, se actualiza su estado.escritura sobre un dato compartido, se actualiza su estado.

• Problema: Genera mucho tráfico en el bus, ya que cada escritura hay que declararla.


Coherencia de datos: Basado en directorio

• La memoria global es la que mantiene actualizada la información de datos compartidos / no-válidos / sucios.

• Mantiene una lista de todos los • Mantiene una lista de todos los procesadores que comparten un cierto dato.

• Cuando un procesador modifica un dato, lo comunica a la memoria principal, y esta a los procesadores que lo comparten.

• Problema: La memoria principal se convierte en cuello de botella.


Organización física

• Arquitectura paralela ideal:– PRAM (Parallel Random Access Machine).

• Modelos de PRAM:– EREW/ERCW/CREW/CRCW

(Exclusivo/Concurrente Lectura/Escritura)

– Resolución de escritura concurrente: Común, Arbitrario, Prioridad y Suma.


Organización física

• Redes de interconexión (RICs):– Proporcionar conexión entre los distintos procesadores y

memorias del sistemas.

• Tipo de redes– Estática:– Estática:

• Enlaces punto a punto

• Históricamente usada para conectar procesadores (memoria distribuida)

– Dinámica:• Formada por elementos de conmutación

• Históricamente usada para conectar procesadores con memorias (memoria compartida)


RICs estáticas y dinámicas

Estática Dinámica


Métricas de evaluación para RICs (I)

• Diámetro: Distancia máxima entre cualquier par de nodos. (Cuanto más pequeño mejor).

• Conectividad: Mínimo número de arcos que hay que eliminar para convertir la red en dos sub-que eliminar para convertir la red en dos sub-redes desconectadas. (Cuanto más grande mejor).

• Ancho de Bisección: Mínimo número de arcos que hay que eliminar para dividir la red en dos mitades iguales. (Cuanto más grande mejor).


Métricas de evaluación para RICs (II)

• Ancho de Banda de Bisección: Mínimo volumen de comunicación permitido entre dos mitades cualesquiera de la red. (Cuanto más grande

mejor).• Coste: Número de enlaces en la red. (Cuanto más

pequeño mejor).


Métricas y redes dinámicas

El ancho de El ancho de bisección es 4, independientemente de la zona de corte


Topologías de red (I): Bus

•Medio compartido.

•La información es difundida.

•Diámetro: O(1).

•Conectividad: O(1).

•Ancho de bisección: O(1).

•Coste: O(p).


Topologías de red (II): Red matricial

•Basada en conmutación.

•Soporta conexiones simultáneas.

•Diámetro: O(1).

•Conectividad: O(1)?

•Ancho de bisección: O(p)?

•Coste: O(p2).


Topologías de red (III): Multi-etapa

Caso particular: Red Omega (Ω) p procesadores ⇒ log p etapas ⇒ p/2 conmutadores por etapa


Arquitecturas de conmutación multi-etapa

Paso

Red omega completa de 8 entradas y 8 salidas.

3 etapas y 4 conmutadores por etapa.

Paso

Cruce


Bloqueo en conmutación multi-etapa

•Comparación a nivel de bit de fuente y destino.•Acierto: Pasa.•Acierto: Pasa.•Fallo: Cruza

Ejemplo de bloqueo en red omega: uno de los mensajes se bloquea en el enlace AB.


Topologías de red (IV): Completa y estrella

Red completamente conectada (8 nodos)

Red conectada en estrella (9 nodos)


Topologías de red (V): Estructuras cartesianas

Arrays lineales

Anillo

Mallas 2-D y 3-D


Topologías de red (VI): Hipercubos

Hipercubo: Malla con 2 nodos por dimensión y log p dimensiones

Construcción de hipercubos a partir de otros con dimensiones inferiores.


Topologías de red (VII): Árboles

•Sólo hay un camino entre cada par de nodos.•Casos particulares:

•Array lineal•Estrella


Métricas de rendimiento: Resumen

Resumen de características


Costes de comunicación en sistemas paralelos

• Paso de mensajes. El coste de comunicación de una operación de transferencia depende de:– Tiempo de inicio ts: Añadir cabecera, corrección de

errores, ejecución del algoritmo de enrutamiento, errores, ejecución del algoritmo de enrutamiento, conexión entre fuente y destino.

– Tiempo de salto th: Tiempo de desplazamiento entre dos nodos conectados directamente.

– Tiempo de transferencia de palabra tw: Inverso del ancho del canal de comunicación.


Store-and-forward y Cut-through

Mensaje no dividido

tcom = ts + (m·tw + th)·l

tcom = ts + m·l·tw

Dividido en 2 partes

Dividido en 4 partes

tcom = ts + l·th + tw·m


Enrutamiento Cut-through: Interbloqueos

Mensaje 0 → Nodo AMensaje 0 → Nodo AMensaje 1 → Nodo BMensaje 2 → Nodo CMensaje 3 → Nodo D


Modelo de coste de comunicaciones

• Coste del envío de un mensaje de tamaño m:

tcom= ts + tw·m

• ts es mucho más grande que th, y en la mayoría de los casos, tw·m es más grande que th·l.


Mecanismos de enrutamiento

• Enrutamiento:– Algoritmo para determinar el camino que un mensaje

tomará desde la fuente hasta el destino.

• Varias clasificaciones:• Varias clasificaciones:– Mínimo vs. No-mínimo.

– Determinista vs. Adaptativo.


Enrutamiento ordenado por dimensión

• Orden predefinido de las dimensiones.

• Los mensajes se encaminan por cada dimensión, en el orden establecido, hasta que no es posible continuar:continuar:– X-Y para mallas

– E-cubo para hipercubos


Transformaciones en la Topologías

• Mapeo entre redes:– Util en los comienzos de la computación paralela,

cuando los algoritmos dependían de las topologías.

• Métricas de calidad de las transformaciones:– Congestión: Máximo número de enlaces de la topología inicial

mapeados en un único enlace de la topología final.

– Dilatación: Máximo número de enlaces de la topología final, sobre los que se mapea un único enlace de la topología inicial.

– Expansión: Relación entre el número de nodos de ambas topologías.


Anillo a Hipercubo

•Los nodos del anillo se mapean al hipercubo siguiendo el código Gray reflejado.

•La dilatación y congestión es 1.


Malla 2-D a Hipercubo

Malla 4x4 a Hipercubo 4-D Malla 2x4 a Hipercubo 3-D


Array lineal a Malla 2-D

Array lineal a Malla 2-DCongestión: 1

Malla 2-D a Array lineal Congestión: 5 )1( +p

plataformas paralelas

Documents