analisis_algoritmosParalelos

Vista previa del material en texto

Análisis de algoritmos paralelos
Metodoloǵıa de la Programación Paralela
Análisis de algoritmos paralelos
Referencias
Libro de Introducción a la Programación Paralela, caṕıtulo 4
Foster, cap 3
Kumar, Grama, Gupta, Karypis, cap 4
Wilkinson, Allen, cap 2.3 y 2.4
Quinn
Análisis de algoritmos paralelos
Ideas generales
Los procesadores paralelos se usan para acelerar la resolución de
problemas de alto coste computacional.
La finalidad principal consiste en reducir el tiempo de ejecución:
si el tiempo secuencial es t(n)
con p procesadores se intenta reducir el tiempo a t(n)
p
En esta sesión, ver algunas medidas que dan idea de la “bondad”
de un algoritmo paralelo.
Análisis de algoritmos paralelos
Tiempo secuencial
El tiempo de ejecución de un programa secuencial depende de:
tamaño de la entrada
compilador
máquina
programador...
si nos olvidamos de valores constantes dependientes del sistema
(por ejemplo, el coste de una operación aritmética en la máquina
donde ejecutamos el programa) podemos considerar el tiempo
función del tamaño de la entrada: t(n).
Es el tiempo desde que empieza la ejecución del programa hasta
que acaba.
Análisis de algoritmos paralelos
Tiempo de ejecución paralela
En un programa paralelo la estimación del tiempo es más compleja.
Además de los parámetros anteriores, depende de:
número de elementos de proceso: t(n, p)
la manera en que están conectados entre śı (topoloǵıa)
y con los módulos de memoria (memoria compartida o
distribuida)
Es el tiempo transcurrido desde que empieza la ejecución del
primero de los procesadores hasta que acaba el último de ellos.
Análisis de algoritmos paralelos
Dificultades para estimar tiempo de ejecución paralelo
No siempre es fácil determinar el orden en que los
procesadores empiezan y acaban.
A lo largo de la ejecución de un programa paralelo hay puntos
de sincronización de los que no siempre podemos determinar
su duración al no saber en el orden en que van a llegar los
distintos procesos (o hilos) a estos puntos.
Análisis de algoritmos paralelos
Modelado del tiempo de ejecución paralelo
Esquema básico de programa paralelo:
Computación 1
Comunicación 1 (sincronización en memoria compartida)
Computación 2
Comunicación 2
...
t(n, p) = ta(n, p) + tc(n, p)
donde:
ta(n, p) : suma de los tiempos de las distintas partes de
computación
tc(n, p) : suma de los tiempos de las distintas partes de
comunicación
Análisis de algoritmos paralelos
Tiempo de ejecución paralelo - ejemplo 1
Programa paralelo en dos procesadores:
Si se suman los tiempos de los elementos de proceso por separado
y se toma el mayor:
t(n, p) = ta(n, p) + tc(n, p) = 7
Si se suman los máximos de los tiempos de cada computación y
comunicación:
treal(n, p) = ta(n, p) + tc(n, p) + toverhead(n, p) = 8
Análisis de algoritmos paralelos
Tiempo de ejecución paralelo - ejemplo 2
Si se suman los máximos de los tiempos de cada computación y
comunicación:
t(n, p) = ta(n, p) + tc(n, p) = 15
Pero el solapamiento puede reducir el tiempo:
treal(n, p) = ta(n, p) + tc(n, p)− tsolapamiento(n, p) = 14
Análisis de algoritmos paralelos
Tiempo de ejecución paralelo - resumen
Overhead debido a:
sincronización
puesta en marcha de los procesos
sobrecarga de la red de comunicación...
Solapamiento de computación y comunicación.
Modelo de tiempo de ejecución:
t(n, p) = ta(n, p) + tc(n, p) + to(n, p)− ts(n, p)
Minimizar el tiempo de overhead.
Maximizar el solapamiento.
Análisis de algoritmos paralelos
Ejemplo - suma de n números
Secuencial: t(n) = n − 1
Paralelo con n2 elementos de proceso, como ḿınimo
t(n)
n/2 = 2
En cada Pi , i = 0, 1, . . . , n/2− 1
inicio = 2 ∗ i
desplazamiento = 1
activo = true
para k = 1, 2, . . . , log n
si activo
a[inicio] = a[inicio] + a[inicio + desplazamiento]
desplazamiento = desplazamiento ∗ 2
finsi
si i mod desplazamiento 6= 0
activo = false
finsi
finpara
Análisis de algoritmos paralelos
Ejemplo - suma de n números, tiempo
Pasos: log n
Trabajo adicional (overhead):
Comprobación de si el procesador trabaja.
Uso de las variables.
Actualización de las variables.
Con n = 64
si cada paso secuencial y paralelo igual coste: t(n) = 64,
t(n, p) = 6, t(n) ≃ 10.5 ∗ t(n, p)
si cada paso secuencial coste 2 y paralelo coste 6: t(n) = 128,
t(n, p) = 36, t(n) ≃ 3.5 ∗ t(n, p)
Y en memoria distribuida problema de acceso a los datos.
Análisis de algoritmos paralelos
Ejemplo - suma de n números, en hipercubo lógico
Análisis de algoritmos paralelos
Ejemplo - suma de n números, en hipercubo lógico
Cada procesador tiene dos valores, a y b
En cada Pi , i = 0, 1, . . . , n/2− 1
desplazamiento = 1
activo = true
para k = 1, 2, . . . , log n − 1
si activo
a = a+ b
desplazamiento = desplazamiento ∗ 2
si i mod desplazamiento 6= 0
activo = false
enviar a a i − desplazamiento/2
en otro caso
recibir en b de i + desplazamiento/2
finsi
finsi
finpara
si i = 0
a = a+ b
finsi
Análisis de algoritmos paralelos
Ejemplo - suma de n números, en hipercubo lógico
Pasos: log n
Trabajo adicional (overhead):
Comprobación de si el procesador trabaja.
Uso de las variables.
Actualización de las variables.
Comprobación de enviar o recibir.
Env́ıo o recepción.
Con n = 64
si cada paso secuencial coste 2 y paralelo coste 7: t(n) = 128,
t(n, p) ≃ 42, t(n) ≃ 3 ∗ t(n, p)
si tw = 2tc y ts = 2tw : t(n) = 128, t(n, p) ≃ 72,
t(n) ≃ 1.5 ∗ t(n, p)
si tw = 10tc y ts = 10tw : t(n) = 128, t(n, p) ≃ 696,
t(n) ≃ 0.18 ∗ t(n, p)
tc , tw y ts tiempo de operación aritmética, de env́ıo de un dato (word-sending time) y de inicio de una
comunicación (starting-time).
Análisis de algoritmos paralelos
Ejemplo - suma de n números, en hipercubo lógico, sobre
otras topoloǵıas f́ısicas
Aumentaŕıa el coste de las comunicaciones:
Malla Anillo
pero la gestión de los mensajes por el sistema hace que
prácticamente no se note
⇒
centrarnos en topoloǵıa lógica del algoritmo.
Análisis de algoritmos paralelos
Apunte de Metodoloǵıa
Problema de poco coste y no apropiado para resolver en paralelo,
granularidad pequeña, sólo como ayuda para diseñar un programa
pero no como programa final.
Pasos de metodoloǵıa de diseño de algoritmos paralelos (Foster):
Particionado: descomponer en muchas tareas pequeñas.
Comunicación: determinar los patrones de comunicación y
sincronización entre tareas.
Agrupación: estudiar formas de agrupar tareas para
balancear el trabajo y reducir comunicaciones.
Mapeo: asignación de las tareas al sistema computacional.
Análisis de algoritmos paralelos
Reducción de las prestaciones I
Contención de memoria (Mapeo):
En memoria compartida el acceso a datos comunes o que
están en el mismo bloque de memoria produce contención.
Si los datos son de lectura puede no haber ese problema.
En el ejemplo los procesadores escriben en zonas distintas. No
hay problema de coherencia, pero puede haber de contención
si hay datos en los mismos bloques de memoria.
Código secuencial:
Puede haber parte imposible de paralelizar, como la I/O.
En el ejemplo la inicialización de variables. Además, si los
datos están inicialmente en un procesador hay que difundirlos.
Tiempo de gestión de procesos o hilos (Agrupación):
El coste de creación de los procesos puede ser importante si la
granularidad es pequeña.
La gestión de procesos e hilos tiene coste importante si hay
muchos.
Análisis de algoritmos paralelos
Reducción de las prestaciones II
Computación extra:
Si se obtiene programa paralelo a partir de secuencial, son
necesarias computaciones adicionales por:
uso de variables de control,
comprobación de identificadores de proceso,
cálculos adicionales o comunicaciones para obtener datos
calculados por otro procesador...
Tiempo de sincronización (Comunicación):
Cuando un proceso tiene que esperar a que estén disponibles
datos procesados por otro.
Conlleva comunicaciones en memoria distribuida.
Análisisde algoritmos paralelos
Reducción de las prestaciones III
Desbalanceo de la carga (Agrupación):
El volumen total de la computación no se distribuye por igual
entre todos los procesadores,
motivos:
en el ejemplo, en el primer paso trabajan todos pero en los
pasos siguientes va disminuyendo el número de procesadores
que trabajan,
también es posible que partamos de una entrada que no se
puede balancear, por ejemplo si tenemos 12 datos para 8
procesadores,
o que el volumen de datos vaŕıe a lo largo de la ejecución, con
lo que se necesitaŕıa balanceo dinámico.
Análisis de algoritmos paralelos
Reducción de las prestaciones IV
Comunicaciones (Comunicación y Mapeo):
En memoria distribuida, es tiempo adicional al aritmético.
Pueden implicar trabajo de procesadores intermedios.
En Mapeo se puede reducir el coste de las comunicaciones
asignando datos que se comunican frecuentemente a procesadores
vecinos. Evita comunicaciones, congestión de la red y colisiones.
Malla Anillo
Análisis de algoritmos paralelos
Granularidad
Uso de muchos elementos de proceso no es realista:
No dispondremos de tantos.
Aunque dispongamos de ellos hay cáıda de las prestaciones.
La granularidad del sistema (f́ısico+algoritmo) indica la cantidad de
computación y datos asignados a cada elemento de proceso:
Grano fino: a cada elemento se asignan pocos datos o se realiza
poca computación entre comunicaciones.
Grano grueso: si a cada elemento se asignan muchos datos o se
realiza mucha computación entre comunicaciones.
En la fase de Agrupación aumentar el grano de los trabajos:
Interesa programación paralela cuando el paralelismo es de grano
grueso.
A partir de qué punto interesa depende de los costes en el sistema.
Más granularidad en el orden: paso de mensajes, memoria
compartida, GPU.
Análisis de algoritmos paralelos
Ejemplo - suma de n números con p procesos
En cada Pi , i = 0, 1, . . . , p − 1
suma = 0
para j = i ∗ n/p, . . . , (i + 1) ∗ n/p − 1
suma = suma+ a[j ]
finpara //Agrupación
sincronización
a[i ] = suma
inicio = i
desplazamiento = 1
activo = true
si i mod 2 6= 0
activo = false
finsi
para k = 1, 2, . . . , log p − 1
si activo
a[inicio] = a[inicio] + a[inicio + desplazamiento]
desplazamiento = desplazamiento ∗ 2
si i mod (desplazamiento ∗ 2) 6= 0
activo = false
finsi
finsi
finpara
Análisis de algoritmos paralelos
Ejemplo - suma de n números con p procesos (mensajes)
En cada Pi , i = 0, 1, . . . , p − 1
suma = 0
para j = 0, . . . , n/p − 1
suma = suma + a[j ]
finpara //Agrupación
si i mod 2 = 0
recibir en b de Pi+1
activo = true
en otro caso
enviar suma a Pi−1
activo = false
finsi
desplazamiento = 2
para k = 1, 2, . . . , log p − 2
si activo
suma = suma + b
desplazamiento = desplazamiento ∗ 2
si i mod desplazamiento 6= 0
activo = false
enviar suma a Pi−desplazamiento/2
en otro caso
recibir en b de Pi+desplazamiento/2
finsi
finsi
finpara //Comunicación en estructura de árbol. Considerarlo en Mapeo
si i = 0
suma = suma + b
finsi
Análisis de algoritmos paralelos
Ejemplo - suma de n números con p procesos
En memoria compartida todas las variables son locales salvo el
array a.
En memoria distribuida la sincronización por el paso de
mensajes, y el array a local de tamaño n
p
.
El tamaño del problema (n) es múltiplo del del sistema (p).
Se puede generalizar.
t(n, p) = 2tc
n
p
+ (log p − 1) (6 + ts + tw )
si p <<< n podemos tener en cuenta sólo los términos de mayor
orden y t(n)
t(n,p) = p, que es lo mejor que se puede obtener.
Derivando t(n, p) respecto a p e igualando a cero se obtiene
número de procesos óptimo: popt =
2tcn
log 3(6+ts+tw )
Análisis de algoritmos paralelos
Speed-up
Mide la ganancia de velocidad que se obtiene con un
programa paralelo.
Es el cociente entre el tiempo secuencial y el paralelo:
S(n, p) = t(n)
t(n,p)
¿Qué t(n)?
El del mejor algoritmo secuencial que resuelve el problema,
pero cuál es el “mejor algoritmo secuencial” depende del
tamaño de la entrada, distribución de los datos, máquina..., y
puede no conocerse (Por ejemplo, ¿cuál es el coste de la
multiplicación de matrices?)
El del mejor algoritmo secuencial conocido. Pero depende de
los mismos parámetros.
Tiempo de ejecución en un procesador del algoritmo paralelo.
Pero puede que el mejor esquema para paralelizar no sea bueno
en secuencial.
El tiempo de ejecución de un algoritmo secuencial
“razonablemente bueno”. Habrá que indicar cuál se usa.
Análisis de algoritmos paralelos
Speed-up
El speed-up será menor que el número de procesadores. Si no,
podŕıa hacerse un algoritmo secuencial mejor que el que se
usa, simulando el algoritmo paralelo.
En algunos casos puede haber speed-up superlineal por
mejor gestión de la memoria al usar más procesadores.
Para un tamaño
de problema fijo
se aleja del valor
óptimo al
aumentar el
número de
procesadores.
Para un número
de procesadores
fijo aumenta al
aumentar el
tamaño del
problema.
Análisis de algoritmos paralelos
Speed-up de suma de n números
Con n2 elementos de proceso:
En memoria compartida: S = k1n
k2 log n
→ ∞
En hipercubo: S = k1n(k2+ts+tw ) log n → ∞
En anillo sin comunicaciones directas y en red:
S = k1n
k2 log n+(k3+ts+tw )n
→ 1
k3+ts+tw
Con p elementos de proceso:
limn→∞,p fijo S =
k1n
k1
n
p
+(k2+ts+tw ) log p
→ p
que es la ganancia máxima con p elementos de proceso.
Análisis de algoritmos paralelos
Eficiencia
Da idea de la porción de tiempo que los elementos de proceso
se dedican a trabajo útil.
Es el speed-up partido por el número de elementos:
E (n, p) = S(n,p)
p
= t(n)
pt(n,p)
Valor entre 0 y 1.
Para un tamaño
de problema fijo
se aleja del valor
óptimo (1) al
aumentar el
número de
procesadores.
Para un número
de procesadores
fijo aumenta con
el tamaño del
problema.
Análisis de algoritmos paralelos
Eficiencia de suma de n números
Con n2 elementos de proceso:
S = k1nn
2
k2 log n
→ 0
Aunque el speed-up indicaba una buena paralelización, la
eficiencia muestra que no.
Con p elementos de proceso:
limn→∞,p fijo S =
k1n
p
(
k1
n
p
+(k2+ts+tw ) log p
) → 1
que es la eficiencia máxima.
Análisis de algoritmos paralelos
Coste
Representa el tiempo (el trabajo) realizado por todo el
sistema en la resolución del problema.
Es el tiempo de ejecución por el número de elementos de
proceso: C (n, p) = pt(n, p)
En algoritmo óptimo coincidirá con el tiempo secuencial, pero
en general es mayor.
La diferencia se llama función overhead:
to(n, p) = C (n, p)− t(n) = pt(n, p)− t(n)
Es distinto de la idea de overhead vista anteriormente y
dif́ıcilmente medible.
En suma de n números con p elementos de proceso
C (n, p) = p
(
k1
n
p
+ (k2 + ts + tw ) log p
)
to(n, p) = (k2 + ts + tw ) p log p
Análisis de algoritmos paralelos
Escalabilidad
Para un sistema paralelo interesa que las prestaciones se sigan
manteniendo en cierta medida al aumentar el tamaño del
sistema.
No se puede seguir manteniendo las prestaciones con el
tamaño del problema fijo y aumentando el número de
elementos de proceso.
Se trata de mantener las prestaciones al aumentar el tamaño
del sistema pero aumentando también el tamaño del problema.
Los sistemas (f́ısicos o lógicos) que mantienen las prestaciones
en esas condiciones se dice que son escalables.
La idea es, para un determinado programa, ser capaces de
determinar si en el futuro, cuando aumente el número de
elementos de proceso y se quiera resolver problemas mayores,
se seguirán manteniendo las prestaciones.
Análisis de algoritmos paralelos
Función de Isoeficiencia
Da idea de cómo debe crecer la entrada del problema en funciún del
número de elementos de proceso para mantener la eficiencia constante.
Como
E (n, p) =
t(n)
t(n, p)
y
to(n, p) = pt(n, p)− t(n)
es
E (n, p) =
t(n)
to(n, p) + t(n)
y despejando
t(n) =
E (n, p)
1− E (n, p)
to(n, p) = Kto(n, p)
Por tanto, para obtener cómo debe crecer n en función de p para
mantener la eficiencia constantebasta comparar el tiempo secuencial con
la función overhead.
Análisis de algoritmos paralelos
Función de Isoeficiencia de suma de n números con p
procesadores
Se hacen los cálculos sin constantes, pues interesa la forma en que crece
En memoria compartida o con hipercubo:
t(n) = n ∝ to(n, p) = n + p log p
Se obtiene la función de isoeficiencia comparando con cada uno de los
sumandos y es el que da mayor relación con respecto a p
n ∝ p log p
En malla sin comunicaciones directas:
t(n) = n ∝ to(n, p) = n + p log p + p
√
p
n ∝ p
3
2
En anillo sin comunicaciones directas y en red:
t(n) = n ∝ to(n, p) = n + p log p + p
2
n ∝ p
2
Análisis de algoritmos paralelos
Función de Isoeficiencia de suma de n números con p
procesadores
Para mantener las prestaciones al aumentar de p1 a p2 elementos
de proceso, el tamaño debe aumentar proporcionalmente a f (p2)
f (p1)
Aumento elementos de proceso Total
Isoeficiencia 4 a 16 16 a 64 64 a 256 4 a 256
p log p 8 6 5.33 256
p
3
2 8 8 8 512
p2 16 16 16 4096
Todos escalables, pero los que tienen función de isoeficiencia con
menor orden escalan mejor.
Análisis de algoritmos paralelos
Estudio experimental de la escalabilidad
Se estudia el número de operaciones por segundo (flops) por
elemento de proceso:
Variando el tamaño de la entrada al variar el número de
procesadores.
O utilizando el máximo tamaño de la entrada que cabe en la
memoria del sistema.
Buena escalabilidad
EP tam. flops
1 100 100
5 500 99
25 2500 96
125 12500 91
Peor escalabilidad
EP tam. flops
1 100 100
5 500 102
25 2500 90
125 12500 46
Análisis de algoritmos paralelos
Estudio experimental
Diseño de experimentos que permitan obtener conclusiones:
Determinar qué tipo de conclusiones se quiere obtener: en
cuanto a speed-up, escalabilidad...
Definir el rango de los experimentos: número de elementos de
proceso y tamaño del problema.
Comparar los resultados experimentales con los teóricos.
Si no coinciden, revisar los estudios teóricos o la forma en que
se han hecho los experimentos.
Pueden consistir en:
Estudiar el programa completo.
Estudiar el comportamiento en los distintos elementos de
proceso: balanceo de la carga, sincronización...
Dividir el programa en partes para estudiarlas por separado.
Hay herramientas de análisis: profilers, gráficas, Vtune, MPE...
Análisis de algoritmos paralelos
Ajuste teórico / experimental
Se pueden estimar los valores constantes en las fórmulas teóricas:
ts y tw se pueden estimar con un ping-pong, o pueden tener
valores distintos para distintas operaciones de comunicación.
El coste de la computación se puede estimar ejecutando parte
del programa en un procesador.
Ajuste del modelo teórico con datos experimentales:
Obtener valores constantes del estudio teórico con ajuste por
ḿınimos cuadrados con resultados experimentales.
Estudio asintótico: comportamiento teniendo en cuenta el
término de mayor orden de la fórmula teórica, compararlo con
la gráfica experimental.
Análisis de algoritmos paralelos