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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Problema de coherencia de cache
Invalidación
Actualización
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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)
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
RICs estáticas y dinámicas
Estática Dinámica
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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).
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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).
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Métricas y redes dinámicas
El ancho de El ancho de bisección es 4, independientemente de la zona de corte
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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).
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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).
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Topologías de red (III): Multi-etapa
Caso particular: Red Omega (Ω) p procesadores ⇒ log p etapas ⇒ p/2 conmutadores por etapa
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Topologías de red (IV): Completa y estrella
Red completamente conectada (8 nodos)
Red conectada en estrella (9 nodos)
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Topologías de red (V): Estructuras cartesianas
Arrays lineales
Anillo
Mallas 2-D y 3-D
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Topologías de red (VII): Árboles
•Sólo hay un camino entre cada par de nodos.•Casos particulares:
•Array lineal•Estrella
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Métricas de rendimiento: Resumen
Resumen de características
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Enrutamiento Cut-through: Interbloqueos
Mensaje 0 → Nodo AMensaje 0 → Nodo AMensaje 1 → Nodo BMensaje 2 → Nodo CMensaje 3 → Nodo D
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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.
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
Malla 2-D a Hipercubo
Malla 4x4 a Hipercubo 4-D Malla 2x4 a Hipercubo 3-D
AT5128 – Arquitectura e Ingeniería de Computadores IIJuan Antonio Maestro (2004/05)
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