View
5
Download
0
Category
Preview:
Citation preview
1
17 de Mayo 2066 Jose Luis Bosque 1
Sesión 4: Modelos de computación paralela
Jose Luis Bosque 217 de Mayo 2066
Indice1. Introducción2. Modelos de computación paralela3. Modelo LogP4. Benchmarking5. Generalización HLogP6. Resultados experimentales
2
Jose Luis Bosque 317 de Mayo 2066
IntroducciónEl diseño e implementación de algoritmos paralelos eficientes, continúa siendo problemático. La diversidad de arquitecturas, redes de interconexión, algoritmos de encaminamiento, así como la heterogeneidad de los sistemas, tienen un impacto muy fuerte en el rendimiento de los algoritmos. Cada arquitectura tiene distintas propiedades específicas de las cuales depende el rendimiento de los algoritmos. El problema está en cómo diseñar e implementar algoritmos paralelos para acomodarlos a estas diferentes especificaciones, sacando el máximo rendimiento de las mismas.
Jose Luis Bosque 417 de Mayo 2066
IntroducciónUna idea es desarrollar modelos de computación paralela prácticos y utilizarlos como guía en el diseño de los algoritmos, así como para estimar su rendimiento. Un modelo de computación paralela es una abstracción matemática de la máquina paralela que oculta los detalles de la arquitectura a los diseñadores de software. El reto es pues diseñar un modelo general de computación paralela de tal forma que sea suficientemente detallado como para reflejar aspectos realistas y que impacten en el rendimiento, al tiempo que sea suficientemente abstracto para ser independiente de la máquina y sencillo para el análisis.
3
Jose Luis Bosque 517 de Mayo 2066
IntroducciónUna característica común entre estos planteamientos es que todos son modelos paramétricos, que extraen las características de la arquitectura en varios parámetros. Utilizando estos modelos se pueden diseñar algoritmos y predecir su rendimiento, instanciando los parámetros para una máquina concreta. Debe mantenerse un equilibrio entre incorporar detalles siendo muy finos en los parámetros, y que los modelos sean prácticos y puedan proporcionar algoritmos óptimos. La identificación de los parámetros y la selección adecuada es un aspecto crítico en el diseño de modelos de computación paralela.
Jose Luis Bosque 617 de Mayo 2066
Modelos de Computación Paralela
PRAM (Parallel Random Access Machine): Modelo poco realista pero ampliamenteutilizado.Multiprocesador de memoria compartida con “p” procesadores sincronizados en el acceso a memoria compartida.Cada instrucción se ejecuta en todos losprocesadores simultáneamente en una unidadde tiempo.
4
Jose Luis Bosque 717 de Mayo 2066
Modelos de Computación Paralela
PRAM (Parallel Random Access Machine): Cada procesador tiene un flag que le permiteejecutar io no la siguiente instrucción. No puede modelar jerarquía de memoria nicomunicación mediante paso de mensajes. La sobrecarga de comunicación y sincronización es cero.
Jose Luis Bosque 817 de Mayo 2066
Modelos de Computación Paralela
P1 P2 P3 Pp
Memoria compartida
CLK
P procesadores conectados a una única memoria compartida
Programa paralelo ejecutado en MIMD
5
Jose Luis Bosque 917 de Mayo 2066
Modelos de Computación ParalelaAsynchronous PRAM (A-PRAM)Phased PRAM
Sincronización al final de cada faseLocal memory PRAM (LPRAM):
Añade memoria local a cada nodo y un costediferente a la memoria local y a la global.
Block PRAM (BPRAM)Añade al LPRAM la posibilidad de transferencai de bloques.
Jose Luis Bosque 1017 de Mayo 2066
Modelos de Computación ParalelaBSP es un modelo del memoria distribuida con comunicación punto a punto, basado en paso de mensajes y semisíncrono. Se define mediante tres atributos:
Un conjunto de componentes, cada uno desarrollando funciones de proceso y/o memoria. Un encaminador (router) que se encarga de entregar los mensajes entre pares de componentes.Capacidad de sincronización entre todos o un subconjunto de componentes a intervalos regulares de L unidades de tiempo.
6
Jose Luis Bosque 1117 de Mayo 2066
Modelos de Computación ParalelaUna aplicación consta de un conjunto de superpasos, en cada uno de los cuales se asigna una tarea a cada componente, compuesta por una combinación de cómputos locales e intercambio de mensajes con otros componentes. Después de cada periodo de L unidades de tiempo, se hace un comprobación global para determinar si todos los componentes han finalizado el superpaso.
En caso afirmativo se procede con el siguiente superpaso; En caso contrario se asigna un nuevo periodo de tiempo al superpaso actual.
Jose Luis Bosque 1217 de Mayo 2066
Modelos de Computación Paralela
Separando los componentes del encaminador se permite separar las tareas de computación y comunicación de forma que se pueden solapar.Se asume que la comunicación es exclusivamente punto a punto, sin ningún mecanismo de difusión. El mecanismo de sincronización permite realizar una sincronización global de todos o parte de los procesos en hardware, haciéndolo mucho más eficiente. Un encaminador es una abstracción de la latencia y el ancho de banda de la red.
7
Jose Luis Bosque 1317 de Mayo 2066
Modelos de Computación ParalelaLos cálculos locales incluyendo accesos a la memoria local tienen un coste unitario. La transmisión de mensajes la hace el encaminador que puede enviar y recibir un cierto número de menajes en cada superpaso (una h-relación en terminología BSP).El coste de realizar una h-relación es gh + s, donde g es el inverso del ancho de banda y s denota la latencia. Si la longitud del superpaso es L, se pueden ejecutar L operaciones locales y L/g-relaciones. Los parámetros que definen la arquitectura en este modelo son L, g y P.
Jose Luis Bosque 1417 de Mayo 2066
Modelos de Computación Paralela
Red de comunicación (g)
P M P M P M
Nodo (w) Nodo Nodo
Barrera (l)
8
Jose Luis Bosque 1517 de Mayo 2066
El Modelo LogPLos parámetros del modelo LogP son los siguientes:
Latencia de comunicación, L: límite superior de la latencia de comunicación para transmitir un mensaje de una sola palabra entre dos nodos. Sobrecarga de comunicación, o: tiempo que un procesador está dedicado a las tareas de comunicación para enviar o recibir un mensaje, no puede realizar tareas de cómputo. Intervalo entre mensajes, g: intervalo de tiempo mínimo entre la transmisión o recepción de dos mensajes consecutivos por el mismo procesador. Determina el número máximo de mensajes que un procesador puede gestionar por unidad de tiempo. Número de procesadores, P: es el número de procesadores que componen el sistema.
Jose Luis Bosque 1617 de Mayo 2066
El Modelo LogP
9
Jose Luis Bosque 1717 de Mayo 2066
El Modelo LogPEn ocasiones se pueden ignorar algunos parámetros.Modelo asíncrono.El parámetro de sobrecarga está determinado por el software de comunicación y por el coste de acceder a la tarjeta de red sobre el bus de memoria o I/O en el que esté conectado. La latencia está influenciada por el tiempo que el mensaje está en la tarjeta de red, el ancho de banda del enlace en la red y los retardos de encaminamiento en la red. El intervalo entre mensajes puede verse afectado por la sobrecarga del procesador, el tiempo empleado por la tarjeta en gestionar el mensaje y el ancho de banda de la red.
Jose Luis Bosque 1817 de Mayo 2066
El Modelo LogPPara un sistema muy grande o una red con una pobre escalabilidad, el cuello de botella puede ser el ancho de banda de la red. Sin embargo, en la práctica el cuello de botella está frecuentemente en la tarjeta de red. La operación de comunicación más sencilla, enviar un mensaje corto de un nodo a otro, consume un tiempo de L + 2o, correspondientes a las siguientes fases:
o ciclos son de sobrecarga en el origen, L ciclos en los que el mensaje está viajando por la red.
10
Jose Luis Bosque 1917 de Mayo 2066
El Modelo LogPLa distinción entre sobrecarga y latencia permite que se diseñen algoritmos en los que se pueden solapar operaciones de cómputo con operaciones de comunicación. Una operación de solicitud-respuesta consume 2L + 4o.
El procesador que hace la solicitud y el que proporciona la respuesta se ven envueltos en 2o ciclos, mientras que el resto del tiempo puede solaparse con otras operaciones.
A lo sumo ⎡L/g⎤ mensajes en la red, porque el ancho de banda es limitado.La tasa de comunicación por procesador viene dada por 1/g.
Jose Luis Bosque 2017 de Mayo 2066
El Modelo LogPDependiendo de la máquina este límite puede venir impuesto por el ancho de banda de la red, o bien por otros factores de diseño como el interfaz o tarjeta de red. Transferir n mensajes cortos de forma consecutiva de un procesador a otro, requiere o + (n - 1)g + L + o, donde cada procesador invierte solamente n*o ciclos. Se usa la misma fórmula para transferencias simultáneas siempre que los destinos sean distintos. Sin embargo, si k procesadores quieren enviar un mensaje al mismo destino la tasa de comunicación efectiva de cada emisor se reduce a 1/k*g.
11
Jose Luis Bosque 2117 de Mayo 2066
El Modelo LogPEl modelo LogP mejora el diseño de algoritmos paralelos, favoreciendo una serie de técnicas de diseño como son:
Coordinar la asignación de tareas con la ubicación de los datos, de forma que se reducen las necesidades del ancho de banda de comunicaciones y la frecuencia de accesos remotos. Asegurar la planificación adecuada de computación y el solape de comunicación y computación. La limitación del ancho de banda también obliga a los diseñadores a buscar patrones de comunicación equilibrados en los cuales ningún procesador se ve inundado de mensajes.
Jose Luis Bosque 2217 de Mayo 2066
El Modelo LogPElimina una serie de problemas que no se abordan en otros modelos:
Muchos algoritmos basados en PRAM tienen una grano excesivamente fino, ya que PRAM no penaliza la comunicación entre procesadores. Esto conlleva unos ratios entre el tiempo de comunicación y de ejecución muy altos. En ocasiones se utiliza la técnica de multithreadingpara enmascarar la latencia. En la práctica, esta técnica está limitada por la tasa de comunicación y por la sobrecarga de los cambios de contexto.Las restricciones de capacidad permiten que el multithreading se utilice sólo por encima del límite de L/g procesadores virtuales.
12
Jose Luis Bosque 2317 de Mayo 2066
El Modelo LogP
Emisor
Receptor
o
L
g
o
t
Jose Luis Bosque 2417 de Mayo 2066
El Modelo LogP
P0
P1
osend
L
orecv
P0
P1
osend
orecv
EEL = osend + L + orecv EEL = f(osend, L, orecv)
13
Jose Luis Bosque 2517 de Mayo 2066
El Modelo LogPP0
P1
osendgap
gap
Jose Luis Bosque 2617 de Mayo 2066
El Modelo LogP
14
Jose Luis Bosque 2717 de Mayo 2066
El Modelo LogP
168.50.5
===
PsgsL
µµ
Jose Luis Bosque 2817 de Mayo 2066
El Modelo LogP
169.20.5
===
PsosL
µµ
15
Jose Luis Bosque 2917 de Mayo 2066
El Modelo LogP
168.59.2
===
Psgsoµµ
Jose Luis Bosque 3017 de Mayo 2066
El Modelo LogP
168.59.20.5
====
PsgsosL
µµµ
16
Jose Luis Bosque 3117 de Mayo 2066
Benchmarking
TIPO DE NODO PROCESADOR CONEXIÓN NODOSBS Pentium III 733 MHz Switch c1, c2AS Pentium III 550 MHz Switch c7, c8BH Pentium III 733 MHz Hub c3, c4AH Pentium III 550 MHz Hub c5, c6
Switch
Hub
BS c1 BS c2 AS c4AS c3
AH c8AH c7BH c5 BH c6BH c6
Jose Luis Bosque 3217 de Mayo 2066
BenchmarkingLatencia y sobrecargas:
Os = {Enviar1, Enviar2}Or = {Recibir1}Lat = {Recibir2 - Recibir1}
Proceso_1:For (i=0;i<n;i++){ Enviar1
Sleep Recibir1 }
Proceso_2:For (i=0;i<n;i++){ Recibir2 Enviar2 }
17
Jose Luis Bosque 3317 de Mayo 2066
Benchmarking
Ancho de banda:
Potencia de cómputo: Cualquier programa, se mide su duración, y se calcula la inversa.
Proceso_1:For (i=0;i<n;i++) Enviar1
Proceso_2:For (i=0;i<n;i++) Recibir2
Jose Luis Bosque 3417 de Mayo 2066
Benchmarking
Sobrecarga de envío para nodos BS
Sobrecarga de envío para nodos AS
18
Jose Luis Bosque 3517 de Mayo 2066
Benchmarking
Sobrecarga de recepción para nodos BS
Sobrecarga de recepción para nodos BH
Jose Luis Bosque 3617 de Mayo 2066
Benchmarking
Latencia para nodos BS
Latencia para nodos BH
19
Jose Luis Bosque 3717 de Mayo 2066
Benchmarking
Tramo Switch-Switch
Gap entre mensajes
Jose Luis Bosque 3817 de Mayo 2066
Benchmarking
Potencia de cómputo:
Máquina c1 c2 c3 c4 c5 c6 c7 c8
Potencia Cómputo 0,586218 0,557226 0,571186 0,562448 0,428100 0,428081 0,427589 0,430768
20
Jose Luis Bosque 3917 de Mayo 2066
Generalización HLogPJustificación de la elección de LogGP:
La arquitectura subyacente es muy similar a un cluster.Elimina las necesidades de sincronización entre los nodos. Favorece el diseño de algoritmos que solapen operaciones de cómputo y comunicación. Permite modelar mensajes de cualquier tamaño.Considera una capacidad de comunicación de la red limitada.Favorece el diseño de algoritmos con patrones de comunicación sencillos y equilibrados.
Jose Luis Bosque 4017 de Mayo 2066
Generalización HLogPModelo HLogGP:
Matriz de latencia.Vector de sobrecarga de envío.Vector de sobrecarga de recepción.Vector de intervalo entre mensajes.Matriz de ancho de banda.Potencia de cómputo del sistema.
21
Jose Luis Bosque 4117 de Mayo 2066
Resultados experimentalesParametrización de un cluster heterogéneo.
Diseño e implementación de programas para medir todos los parámetros del modelo. Los resultados demuestran gran variación en los valores tanto en los nodos como en los caminos de comunicación.
Jose Luis Bosque 4217 de Mayo 2066
Resultados experimentales
22
Jose Luis Bosque 4317 de Mayo 2066
Resultados experimentalesAnálisis teórico de tiempos de ejecución:
Primera fase:
Segunda fase:
Tercera fase:
NOsTTT mPackLeer ⋅++= )(1
)1()2
1(
,,
,,12
−⋅⋅+++++
+++++=
−
=
isiMEscMUnpackMsisiPack
sisiUnpackmMPackLeer
Ni
FLTTOrOsTP
TOsTTmaxT
∑= − +++++++=N
i siMMEscMUnpackMMsisisiPack LOsTTOrLOsTT1 ,,,3 )()(
Jose Luis Bosque 4417 de Mayo 2066
Resultados experimentalesDimensión Tiempo
EstimadoTiempo
RealError Error
Relativo100 3,651297 3,697518 0,046221 0,012659
150 11,699385 12,031179 0,331794 0,028360
200 31,556688 32,049994 0,493306 0,015632
250 68,702048 69,184308 0,482260 0,007020
Recommended