AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Operaciones de comunicación
Curso 2011-2012
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Índice • Importancia de las operaciones colectivas de comunicación. • Difusión Uno-a-Todos. • Reducción Todos-a-Uno. • Difusión y Reducción Todos-a-Todos. • Reducción total y Suma acumulada. • Dispersión y Agrupación. • Todos-a-Todos personalizada. • Desplazamiento circular.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Operaciones colectivas de comunicación • Patrones de comunicación habituales realizados por algoritmos paralelos. • La eficiencia de los algoritmos depende de la implementación óptima de estas operaciones. • Son válidas tanto para plataformas distribuidas como para memoria compartida. • Muchas operaciones son estándar en la mayoría de librerías paralelas.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Ejemplo: Operaciones en MPI
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión Uno-a-Todos y Reducción Todos-a-Uno • Difusión Uno-a-Todos: Un dato, inicialmente en un solo procesador, se distribuye al resto. • Reducción Todos-a-Uno: Distintos datos, en varios procesadores, se combinan en uno solo. (¿Cómo?: Operador asociativo).
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión en un anillo
1
•Los nodos destino de una etapa, se convierten en fuente en la siguiente: minimización del tiempo de difusión. •Cuidado con la congestión de los enlaces.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Reducción en un anillo
Reducción progresiva, a fin de evitar congestión de los enlaces.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión en una malla
Difusión en 4 etapas: •Primero, difusión en fila inicial. •Segundo, difusión a las columnas en paralelo.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión en un hipercubo
La difusión en un hipercubo de dimensión d siempre se produce en d etapas.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión en un hipercubo: Inicio fijo Inicio: Procesador 0
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión en un hipercubo: Inicio arbitrario Inicio: Procesador source
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión y Reducción Todos-a-Todos • Extensión de las operaciones, en las que todos los procesadores son a la vez fuente y destino.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión Todos-a-Todos para un anillo
Difusión en un anillo de p nodos
Reducción en un anillo de p nodos
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión Todos-a-Todos para una malla
Los nodos que se comunican en cada fase aparecen recuadrados con línea punteada. Las filas y columna se tratan como arrays lineales independientes. Aplicando el algoritmo anterior en dos etapas, se consigue la difusión.
Difusiónen enuna unamalla malla de deppnodos nodos Difusión
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Difusión Todos-a-Todos para un hipercubo
Difusión en un hipercubo
Reducción en un hipercubo
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Reducción Total y Suma Acumulada •Reducción total: - Operación de Reducción Todos-a-Uno más Difusión Uno-a-Todos. - Se puede conseguir mediante Difusión Todos-a-Todos. - Distintas: Reducción Todos-A-Uno, Reducción Todos-aTodos y Reducción Total.
•Suma acumulada - Producción de sumas acumuladas en los nodos intermedios. - El nodo final almacena la suma total del conjunto. - Se puede conseguir mediante Difusión Todos-a-Todos.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Ejemplo: Suma acumulada en hipercubo
Suma acumulada en un hipercubo
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Dispersión y Agrupamiento • Dispersión: Varios datos almacenados en un único nodo, se reparten entre distintos procesadores (un dato por procesador). • Agrupamiento: Varios datos almacenados en distintos procesadores, se almacenan simultáneamente en un único nodo (sin combinarse).
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Operación de dispersión en un hipercubo
Dispersión en un hipercubo de 8 nodos
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Todos-a-Todos personalizada (Transposición)
Comunicación personalizada Todos-a-Todos
Transposición de una matriz 4x4 usando cuatro procesos
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Todos-a-Todos personalizada en un anillo
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Todos-a-Todos personalizada en una malla
Distribución de datos al comienzo de la primera fase Distribución de datos al comienzo de la segunda fase
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Todos-a-Todos personalizada en un hipercubo
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Desplazamiento circular en una malla q mod
q p
p
Compensación (de las columnas que han salido por la derecha)
Desplazamiento circular de 5 posiciones
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Desplazamiento circular en un hipercubo
• Construcción hipercubo por código Gray reflejado. • Desplazamiento circular de 5: 22 + 20 = 4 + 1. • 22 = 4: Dos desplazamientos por atajo hacia el “4”. • 20 = 1: Un desplazamiento normal incremental.
AT5128 – Arquitectura e Ingeniería de Computadores II Juan Antonio Maestro (2004/05)
Complejidad Complejidad de las comunicaciones para p procesadores y mensajes de tamaño m, en un hipercubo.