Download - ModelosDeRendimiento algoritmos
-
Presentacin 1 Ranilla J. 2009
Tema
Modelos de Rendimiento
Jos Ranilla Pastor
http://lear.inforg.uniovi.es/CyP
-
Presentacin 2 Ranilla J. 2009
NDICE
1. Motivacin
2. Mtricas absolutas: Tiempo de ejecucin
Definicin
Partes fundamentales
3. Mtricas Relativas
Incremento de Velocidad (SpeedUp)
Eficiencia
Coste
4. Un ejemplo
-
Presentacin 3 Ranilla J. 2009
Motivacin
Disponer de herramientas que permitan evaluar las prestaciones de losalgoritmos paralelos de forma fiable y precisa.
Dispones de una herramienta que permita comparar el rendimiento delos algoritmos paralelos (y secuenciales).
Modelo de computacin paralelo adoptado: MIMD-MD basado en pasode mensajes. Parte de lo aqu expuesto es aplicable a otros modelos.
Enfoque muy bsico.
-
Presentacin 4 Ranilla J. 2009
Paso previo: Relativo a cmo medir El error mximo que se comete al estimar la duracin de un evento
pertenece al intervalo (-t, t), siendo t el periodo.
Repetir los experimentos un nmero de veces adecuado controlandolos posibles efectos colaterales (nan, excepciones, etc.) en los flopsrealizados.
Tiempo de ejecucin
-
Presentacin 5 Ranilla J. 2009
Tiempo de ejecucin
Definicin Tiempo transcurrido desde que el primer procesador inicia la
ejecucin del algoritmo hasta que el ltimo la finaliza.
Depende de varios factores: computacin, comunicaciones,solapamientos, esperas, etc.
-
Presentacin 6 Ranilla J. 2009
Tiempo de ejecucin
En frmulas
O bien
Globalmente
jidle
jcomu
jcomp TTTT ++=
)TTT(p1T
p
1i
iidle
p
1i
icomu
p
1i
icomp
===++=
tosolapamienidlecomucomp TTTTT ++=
-
Presentacin 7 Ranilla J. 2009
( ) idlecomucomp TT,TmaxT +=
Tiempo de ejecucin
Algoritmos sncronos
Algoritmos asncronos
0TTTT idlecomucomp ++=
comucomp TTT +
Hiptesisde Trabajo
( ) comucompcomucompcomucomp TTTTmax2TT
+++
-
Presentacin 8 Ranilla J. 2009
Tiempo de ejecucin
Tiempo de Computacin Es el tiempo que el algoritmo emplea realizando clculos.
Generalmente se expresa en flops.
Segn el enfoque terico/emprico Depende del tamao del problema y se expresa en funcin de l, y
del nmero de procesadores.
Depende del nmero de tareas por procesador, de las caractersticasde los procesadores, de los subsistemas de memoria, etc.
No olvidar Su comportamiento dinmico (efecto variable) por causas ajenas al
algoritmo pero inherentes al sistema.
-
Presentacin 9 Ranilla J. 2009
Tiempo de ejecucin
-
Presentacin 10 Ranilla J. 2009
Tiempo de ejecucin
-
Presentacin 11 Ranilla J. 2009
Tiempo de ejecucin
Tiempo de Comunicacin Tiempo que las tareas emplean en enviar/recibir.
Tipos Internas
Externas
(usamos el mismo para ambos tipos de comunicaciones)
Modelos PRAM: poco realista.
LogP y LogGP: complejos para este curso.
-: el que usaremos.
-
Presentacin 12 Ranilla J. 2009
Tiempo de ejecucin
Latencia y Ancho de Banda o - Parmetros
Latencia de la red.
coste por word (1 / ancho de banda).
Tiem
po
N
+= NT
>>
-
Presentacin 13 Ranilla J. 2009
Tiempo de ejecucin
Algunos valores experimentales
en seg. en seg. por Byte
Entorno
T3E/MPI 6.7 0.003
IBM/MPI 7.6 0.004
Quadrics/MPI 7.3 0.005
Myrinet/MPI 7.2 0.006
Dolphin/MPI 7.8 0.005
GigE/MPI 5.9 0.009
-
Presentacin 14 Ranilla J. 2009
Tiempo de ejecucin
Problemas del modelo - Conduce a estimaciones poco finas en:
Entornos heterogneos.
En computadoras donde las comunicaciones internas estnaltamente optimizadas.
Necesidad de que los valores de las constantes sean reales.
Algunas recomendaciones para el modelo - Constantes con efecto variable segn el tipo de red, el trfico,
Disminuir los efectos de la constante de establecimiento. Unmensaje grande es ms barato que muchos pequeos:
+ n
-
Presentacin 15 Ranilla J. 2009
Problemas del Tiempo de ejecucin Mtrica Absoluta
Depende, al menos, del tamao del problema Normalizar
Estas alternativas son/representan Mtricas Relativas
Estiman la efectividad con que los algoritmos usan los recursos
SpeedUp, Eficiencia
Dificultad para comparar algoritmos
Permiten comparar algoritmos
-
Presentacin 16 Ranilla J. 2009
Speedup, Eficiencia
Definicin El incremento de velocidad (o Speedup) de un algoritmo paralelo
cuando se ejecuta sobre p procesadores es:
El incremento de velocidad (o Speedup) de un algoritmo paralelocuando se ejecuta sobre p procesadores respecto al mejor algoritmosecuencial es:
( )esprocesador p en ejecucin de Tiempo
procesador un sobre ejecucin de Tiempop;nS =
Representa la bondad del diseo paralelo
( )esprocesador p en paralelo del ejecucin de Tiempo
rapido ms secuencial del ejecucin de Tiempop;nS' =
Indica la eficacia (prestaciones) del algoritmo paralelo
-
Presentacin 17 Ranilla J. 2009
Definicin La eficiencia de un algoritmo paralelo, respecto a s mismo, es:
Siendo la eficiencia respecto al mejor algoritmo secuencial:
Evidentemente:
Objetivo Algoritmos ptimos
Algoritmos eficientes
Speedup, Eficiencia
( ) ( )p
p;nSp;nE =
( ) ( )p
p;nSp;nE'
' =
( ) ( ) 1p;nEp;nE'
( ) )1(p;nE' ( ) ( )n log1' p;nE
-
Presentacin 18 Ranilla J. 2009
Coste
Definicin Relacin entre el tiempo de ejecucin del secuencial ptimo y el
tiempo de ejecucin paralelo, multiplicado por el nmero deprocesadores.
Propiedad Un algoritmo paralelo es de coste-ptimo, eficiencia mxima, si el
tiempo para resolver un problema en una computadora paralela esproporcional al tiempo de resolucin del mismo problema por elalgoritmo secuencial ptimo.
( ) ( )( )pp;nT1;nTp;nC =
-
Presentacin 19 Ranilla J. 2009
Un ejemplo
El problema Dominio definido por una malla de N*N*Z puntos.
Sea ts la constante que denota el coste computacional paraactualizar cada punto de la malla en cada etapa.
Z
N
N
-
Presentacin 20 Ranilla J. 2009
El problema Descomposicin y/o mapeado realizado: (N*N*Z)/P puntos por
procesador.
Comunicaciones locales.
Un ejemplo
P1 P2 P3 P4
-
Presentacin 21 Ranilla J. 2009
Un ejemplo
El estudio del rendimiento Tiempo de computacin
Desde la versin secuencial
Observando un procesador arbitrario
P)Z2N(st
P)ZNN(st
PSecuencialT
compT
=
==
P)Z2N(stj
compTcompT
==
-
Presentacin 22 Ranilla J. 2009
Un ejemplo
El estudio del rendimiento Tiempo de comunicacin
Comunicaciones en un slo plano; 2 por iteracin.
El tamao del mensaje es el nmero de puntos que poseecada procesador en sus fronteras, es decir, N*Z
)NZ(2jcomuT +=
-
Presentacin 23 Ranilla J. 2009
Un ejemplo
El estudio del rendimiento Tiempo de comunicacin
Como todos los procesadores realizan las mismas operacionesde entrada/salida y, adems, de forma simultanea:
Tiempo de inactividad
Todas las iteraciones son iguales.
Cada procesador es responsable de la misma carga decomputacin y comunicaciones.
Ejecucin sincronizada con sus vecinos.
)NZ(2comuT +=
-
Presentacin 24 Ranilla J. 2009
Un ejemplo
El estudio del rendimiento En resumen
En el lmite
Respecto al secuencial
[ ] 0)NZ(2P
)Z2N(stT +++=
PZ2N
TNlim
P
PN
NZ
Z2N
ParaleloTSecuencialT ==
-
Presentacin 25 Ranilla J. 2009
Un ejemplo
El estudio del rendimiento Speedup
Eficiencia
Coste
)NZ(p2)NZ(2
)Z2N(st s2
s2
s2
ZtNZtpN
p
ZtN)p;N(S+
+++
==
)NZ(p2s2
s2
ZtNZtN
p)p;N(S)p;N(E
++==
)NZ(p2s2
s22
ZtNZtNpp)p;N(S)p;N(C
++==
-
Presentacin 26 Ranilla J. 2009
Un ejemplo
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
512 256 128 64 32 16 8 4 2 1
Tiem
po (S
egun
dos)
Procesadores
SecuencialParalelo
El estudio del rendimiento ts=1E-8, =6.3E-5, =1.1E-6, Z=128, N=1024, k[1, 512]
-
Presentacin 27 Ranilla J. 2009
Un ejemplo
El estudio del rendimiento Z=128, N=1024, p[1, 1024]
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
1024 512 256 128 64 32 16 8 4 2 1
Efic
ienc
ia
Procesadores
EUITIGDPTINF
IBM SP2
-
Presentacin 28 Ranilla J. 2009
Funcin de sobrecarga
El estudio del rendimiento N[512, 1E+07], Z=N, p[1, 1024]
10242566416411000
10000
100000
1e+006
1e+007
1
0.8
0.6
0.4
0.2Efic
ienc
ia
0.90.80.70.60.50.40.30.20.1
p
N
-
Presentacin 29 Ranilla J. 2009
Funcin de sobrecarga
El estudio del rendimiento N[512, 1E+07], Z=N, p[1, 1024]
10242566416411000
10000
100000
1e+006
1e+007
1
0.8
0.6
0.4
0.2
Efic
ienc
ia
0.90.80.70.60.50.40.30.20.1
p
N
Slide Number 1NDICEMotivacinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinTiempo de ejecucinSpeedUp, EficienciaSpeedup, EficienciaSpeedup, EficienciaCosteUn ejemploUn ejemploUn ejemploUn ejemploUn ejemploUn ejemploUn ejemploUn ejemploUn ejemploFuncin de sobrecargaFuncin de sobrecarga