An lisis de algoritmos paralelosdis.um.es/~domingo/apuntes/AlgProPar/1718/analisis.pdf ·...

Analisis de algoritmos paralelos

Metodologıa de la Programacion Paralela


Referencias

Libro de Introduccion a la Programacion Paralela, capıtulo 4

Foster, cap 3

Kumar, Grama, Gupta, Karypis, cap 4

Wilkinson, Allen, cap 2.3 y 2.4

Quinn


Ideas generales

Los procesadores paralelos se usan para acelerar la resolucion deproblemas de alto coste computacional.

La finalidad principal consiste en reducir el tiempo de ejecucion:

si el tiempo secuencial es t(n)

con p procesadores se intenta reducir el tiempo a t(n)p

En esta sesion, ver algunas medidas que dan idea de la “bondad”de un algoritmo paralelo.


Tiempo secuencial

El tiempo de ejecucion de un programa secuencial depende de:

tamano de la entrada

compilador

maquina

programador...

si nos olvidamos de valores constantes dependientes del sistema(por ejemplo, el coste de una operacion aritmetica en la maquinadonde ejecutamos el programa) podemos considerar el tiempofuncion del tamano de la entrada: t(n).

Es el tiempo desde que empieza la ejecucion del programa hastaque acaba.


Tiempo de ejecucion paralela

En un programa paralelo la estimacion del tiempo es mas compleja.

Ademas de los parametros anteriores, depende de:

numero de elementos de proceso: t(n, p)

la manera en que estan conectados entre sı (topologıa)

y con los modulos de memoria (memoria compartida odistribuida)

Es el tiempo transcurrido desde que empieza la ejecucion delprimero de los procesadores hasta que acaba el ultimo de ellos.


Dificultades para estimar tiempo de ejecucion paralelo

No siempre es facil determinar el orden en que losprocesadores empiezan y acaban.

A lo largo de la ejecucion de un programa paralelo hay puntosde sincronizacion de los que no siempre podemos determinarsu duracion al no saber en el orden en que van a llegar losdistintos procesos (o hilos) a estos puntos.


Modelado del tiempo de ejecucion paralelo

Esquema basico de programa paralelo:

Computacion 1Comunicacion 1 (sincronizacion en memoria compartida)Computacion 2Comunicacion 2...

t(n, p) = ta(n, p) + tc(n, p)

donde:ta(n, p) : suma de los tiempos de las distintas partes decomputaciontc(n, p) : suma de los tiempos de las distintas partes decomunicacion


Tiempo de ejecucion paralelo - ejemplo 1

Programa paralelo en dos procesadores:

Si se suman los tiempos de los elementos de proceso por separadoy se toma el mayor:

t(n, p) = ta(n, p) + tc(n, p) = 7

Si se suman los maximos de los tiempos de cada computacion ycomunicacion:

treal(n, p) = ta(n, p) + tc(n, p) + toverhead(n, p) = 8


Tiempo de ejecucion paralelo - ejemplo 2

Si se suman los maximos de los tiempos de cada computacion ycomunicacion:

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


Tiempo de ejecucion paralelo - resumen

Overhead debido a:

sincronizacionpuesta en marcha de los procesossobrecarga de la red de comunicacion...

Solapamiento de computacion y comunicacion.

Modelo de tiempo de ejecucion:

t(n, p) = ta(n, p) + tc(n, p) + to(n, p)− ts(n, p)

Minimizar el tiempo de overhead.

Maximizar el solapamiento.


Ejemplo - suma de n numeros

Secuencial: t(n) = n − 1

Paralelo con n2 elementos de proceso, como mınimo t(n)

n/2 = 2

En cada Pi , i = 0, 1, . . . , n/2− 1inicio = 2 ∗ idesplazamiento = 1activo = true

para k = 1, 2, . . . , log nsi activo

a[inicio] = a[inicio] + a[inicio + desplazamiento]desplazamiento = desplazamiento ∗ 2

finsi

si i mod desplazamiento 6= 0activo = false

finsi

finpara


Ejemplo - suma de n numeros, tiempo

Pasos: log n

Trabajo adicional (overhead):

Comprobacion de si el procesador trabaja.

Uso de las variables.

Actualizacion 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.


Ejemplo - suma de n numeros, en hipercubo logico



Cada procesador tiene dos valores, a y bEn cada Pi , i = 0, 1, . . . , n/2− 1

desplazamiento = 1activo = true

para k = 1, 2, . . . , log n − 1si activo

a = a+ b

desplazamiento = desplazamiento ∗ 2si i mod desplazamiento 6= 0

activo = false

enviar a a i − desplazamiento/2en otro caso

recibir en b de i + desplazamiento/2finsi

finsi

finpara

si i = 0a = a+ b

finsiAnalisis de algoritmos paralelos


Pasos: log n

Trabajo adicional (overhead):

Comprobacion de si el procesador trabaja.

Uso de las variables.

Actualizacion de las variables.

Comprobacion de enviar o recibir.

Envıo o recepcion.

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 operacion aritmetica, de envıo de un dato (word-sending time) y de inicio de unacomunicacion (starting-time).


Ejemplo - suma de n numeros, en hipercubo logico, sobreotras topologıas fısicas

Aumentarıa el coste de las comunicaciones:

Malla Anillo

pero la gestion de los mensajes por el sistema hace quepracticamente no se note⇒

centrarnos en topologıa logica del algoritmo.


Apunte de Metodologıa

Problema de poco coste y no apropiado para resolver en paralelo,granularidad pequena, solo como ayuda para disenar un programapero no como programa final.

Pasos de metodologıa de diseno de algoritmos paralelos (Foster):

Particionado: descomponer en muchas tareas pequenas.

Comunicacion: determinar los patrones de comunicacion ysincronizacion entre tareas.

Agrupacion: estudiar formas de agrupar tareas parabalancear el trabajo y reducir comunicaciones.

Mapeo: asignacion de las tareas al sistema computacional.


Reduccion de las prestaciones I

Contencion de memoria (Mapeo):En memoria compartida el acceso a datos comunes o queestan en el mismo bloque de memoria produce contencion.Si los datos son de lectura puede no haber ese problema.En el ejemplo los procesadores escriben en zonas distintas. Nohay problema de coherencia, pero puede haber de contencionsi hay datos en los mismos bloques de memoria.

Codigo secuencial:Puede haber parte imposible de paralelizar, como la I/O.En el ejemplo la inicializacion de variables. Ademas, si losdatos estan inicialmente en un procesador hay que difundirlos.

Tiempo de gestion de procesos o hilos (Agrupacion):El coste de creacion de los procesos puede ser importante si lagranularidad es pequena.La gestion de procesos e hilos tiene coste importante si haymuchos.


Reduccion de las prestaciones II

Computacion extra:Si se obtiene programa paralelo a partir de secuencial, sonnecesarias computaciones adicionales por:

uso de variables de control,comprobacion de identificadores de proceso,calculos adicionales o comunicaciones para obtener datoscalculados por otro procesador...

Tiempo de sincronizacion (Comunicacion):Cuando un proceso tiene que esperar a que esten disponiblesdatos procesados por otro.Conlleva comunicaciones en memoria distribuida.


Reduccion de las prestaciones III

Desbalanceo de la carga (Agrupacion):El volumen total de la computacion no se distribuye por igualentre todos los procesadores,motivos:

en el ejemplo, en el primer paso trabajan todos pero en lospasos siguientes va disminuyendo el numero de procesadoresque trabajan,tambien es posible que partamos de una entrada que no sepuede balancear, por ejemplo si tenemos 12 datos para 8procesadores,o que el volumen de datos varıe a lo largo de la ejecucion, conlo que se necesitarıa balanceo dinamico.


Reduccion de las prestaciones IV

Comunicaciones (Comunicacion y Mapeo):En memoria distribuida, es tiempo adicional al aritmetico.Pueden implicar trabajo de procesadores intermedios.En Mapeo se puede reducir el coste de las comunicacionesasignando datos que se comunican frecuentemente a procesadoresvecinos. Evita comunicaciones, congestion de la red y colisiones.

Malla Anillo


Granularidad

Uso de muchos elementos de proceso no es realista:

No dispondremos de tantos.

Aunque dispongamos de ellos hay caıda de las prestaciones.

La granularidad del sistema (fısico+algoritmo) indica la cantidad decomputacion y datos asignados a cada elemento de proceso:

Grano fino: a cada elemento se asignan pocos datos o se realizapoca computacion entre comunicaciones.

Grano grueso: si a cada elemento se asignan muchos datos o serealiza mucha computacion entre comunicaciones.

En la fase de Agrupacion aumentar el grano de los trabajos:

Interesa programacion paralela cuando el paralelismo es de granogrueso.

A partir de que punto interesa depende de los costes en el sistema.

Mas granularidad en el orden: paso de mensajes, memoriacompartida, GPU.


Ejemplo - suma de n numeros con p procesos

En cada Pi , i = 0, 1, . . . , p − 1suma = 0para j = i ∗ n/p, . . . , (i + 1) ∗ n/p − 1

suma = suma+ a[j ]finpara //Agrupacion

sincronizacion

a[i ] = suma

inicio = i

desplazamiento = 1activo = true

si i mod 2 6= 0activo = false

finsi

para k = 1, 2, . . . , log p − 1si activo

a[inicio] = a[inicio] + a[inicio + desplazamiento]desplazamiento = desplazamiento ∗ 2si i mod (desplazamiento ∗ 2) 6= 0

activo = false

finsi

finsi

finpara


Ejemplo - suma de n numeros con p procesos (mensajes)

En cada Pi , i = 0, 1, . . . , p − 1suma = 0para j = 0, . . . , n/p − 1

suma = suma + a[j ]finpara //Agrupacion

si i mod 2 = 0recibir en b de Pi+1activo = true

en otro caso

enviar suma a Pi−1activo = false

finsi

desplazamiento = 2para k = 1, 2, . . . , log p − 2

si activo

suma = suma + b

desplazamiento = desplazamiento ∗ 2si i mod desplazamiento 6= 0

activo = false

enviar suma a Pi−desplazamiento/2en otro caso

recibir en b de Pi+desplazamiento/2finsi

finsi

finpara //Comunicacion en estructura de arbol. Considerarlo en Mapeo

si i = 0suma = suma + b

finsi


Ejemplo - suma de n numeros con p procesos

En memoria compartida todas las variables son locales salvo elarray a.

En memoria distribuida la sincronizacion por el paso demensajes, y el array a local de tamano n

p.

El tamano del problema (n) es multiplo del del sistema (p).Se puede generalizar.

t(n, p) = 2tcn

p+ (log p − 1) (6 + ts + tw )

si p <<< n podemos tener en cuenta solo los terminos de mayororden 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 obtienenumero de procesos optimo: popt =

2tcnlog 3(6+ts+tw )


Speed-up

Mide la ganancia de velocidad que se obtiene con unprograma paralelo.

Es el cociente entre el tiempo secuencial y el paralelo:S(n, p) = t(n)

t(n,p)

¿Que t(n)?

El del mejor algoritmo secuencial que resuelve el problema,pero cual es el “mejor algoritmo secuencial” depende deltamano de la entrada, distribucion de los datos, maquina..., ypuede no conocerse (Por ejemplo, ¿cual es el coste de lamultiplicacion de matrices?)El del mejor algoritmo secuencial conocido. Pero depende delos mismos parametros.Tiempo de ejecucion en un procesador del algoritmo paralelo.Pero puede que el mejor esquema para paralelizar no sea buenoen secuencial.El tiempo de ejecucion de un algoritmo secuencial“razonablemente bueno”. Habra que indicar cual se usa.


Speed-up

El speed-up sera menor que el numero de procesadores. Si no,podrıa hacerse un algoritmo secuencial mejor que el que seusa, simulando el algoritmo paralelo.En algunos casos puede haber speed-up superlineal pormejor gestion de la memoria al usar mas procesadores.

Para un tamanode problema fijose aleja del valoroptimo alaumentar elnumero deprocesadores.

Para un numerode procesadoresfijo aumenta alaumentar eltamano delproblema.


Speed-up de suma de n numeros

Con n2 elementos de proceso:

En memoria compartida: S = k1nk2 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

k1np+(k2+ts+tw ) log p

→ p

que es la ganancia maxima con p elementos de proceso.


Eficiencia

Da idea de la porcion de tiempo que los elementos de procesose dedican a trabajo util.Es el speed-up partido por el numero de elementos:E (n, p) = S(n,p)

p= t(n)

pt(n,p)Valor entre 0 y 1.

Para un tamanode problema fijose aleja del valoroptimo (1) alaumentar elnumero deprocesadores.

Para un numerode procesadoresfijo aumenta conel tamano delproblema.


Eficiencia de suma de n numeros

Con n2 elementos de proceso:

S = k1nn2k2 log n

→ 0

Aunque el speed-up indicaba una buena paralelizacion, laeficiencia muestra que no.

Con p elementos de proceso:limn→∞,p fijo S = k1n

p(

k1np+(k2+ts+tw ) log p

) → 1

que es la eficiencia maxima.


Coste

Representa el tiempo (el trabajo) realizado por todo elsistema en la resolucion del problema.

Es el tiempo de ejecucion por el numero de elementos deproceso: C (n, p) = pt(n, p)

En algoritmo optimo coincidira con el tiempo secuencial, peroen general es mayor.

La diferencia se llama funcion overhead:to(n, p) = C (n, p)− t(n) = pt(n, p)− t(n)Es distinto de la idea de overhead vista anteriormente ydifıcilmente medible.

En suma de n numeros con p elementos de proceso

C (n, p) = p(

k1np+ (k2 + ts + tw ) log p

)

to(n, p) = (k2 + ts + tw ) p log p


Escalabilidad

Para un sistema paralelo interesa que las prestaciones se siganmanteniendo en cierta medida al aumentar el tamano delsistema.

No se puede seguir manteniendo las prestaciones con eltamano del problema fijo y aumentando el numero deelementos de proceso.

Se trata de mantener las prestaciones al aumentar el tamanodel sistema pero aumentando tambien el tamano del problema.

Los sistemas (fısicos o logicos) que mantienen las prestacionesen esas condiciones se dice que son escalables.

La idea es, para un determinado programa, ser capaces dedeterminar si en el futuro, cuando aumente el numero deelementos de proceso y se quiera resolver problemas mayores,se seguiran manteniendo las prestaciones.


Funcion de Isoeficiencia

Da idea de como debe crecer la entrada del problema en funciun delnumero 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 como debe crecer n en funcion de p para

mantener la eficiencia constante basta comparar el tiempo secuencial con

la funcion overhead.Analisis de algoritmos paralelos

Funcion de Isoeficiencia de suma de n numeros con p

procesadores

Se hacen los calculos 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 funcion de isoeficiencia comparando con cada uno de lossumandos y es el que da mayor relacion 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 ∝ p32

En anillo sin comunicaciones directas y en red:t(n) = n ∝ to(n, p) = n + p log p + p

2

n ∝ p2


Funcion de Isoeficiencia de suma de n numeros con p

procesadores

Para mantener las prestaciones al aumentar de p1 a p2 elementosde proceso, el tamano debe aumentar proporcionalmente a f (p2)

f (p1)

Aumento elementos de proceso TotalIsoeficiencia 4 a 16 16 a 64 64 a 256 4 a 256

p log p 8 6 5.33 256

p32 8 8 8 512

p2 16 16 16 4096

Todos escalables, pero los que tienen funcion de isoeficiencia conmenor orden escalan mejor.


Estudio experimental de la escalabilidad

Se estudia el numero de operaciones por segundo (flops) porelemento de proceso:

Variando el tamano de la entrada al variar el numero deprocesadores.

O utilizando el maximo tamano de la entrada que cabe en lamemoria del sistema.

Buena escalabilidadEP tam. flops

1 100 1005 500 9925 2500 96125 12500 91

Peor escalabilidadEP tam. flops

1 100 1005 500 10225 2500 90125 12500 46


Estudio experimental

Diseno de experimentos que permitan obtener conclusiones:

Determinar que tipo de conclusiones se quiere obtener: encuanto a speed-up, escalabilidad...

Definir el rango de los experimentos: numero de elementos deproceso y tamano del problema.

Comparar los resultados experimentales con los teoricos.Si no coinciden, revisar los estudios teoricos o la forma en quese han hecho los experimentos.

Pueden consistir en:

Estudiar el programa completo.

Estudiar el comportamiento en los distintos elementos deproceso: balanceo de la carga, sincronizacion...

Dividir el programa en partes para estudiarlas por separado.

Hay herramientas de analisis: profilers, graficas, Vtune, MPE...Analisis de algoritmos paralelos

Ajuste teorico / experimental

Se pueden estimar los valores constantes en las formulas teoricas:

ts y tw se pueden estimar con un ping-pong, o pueden tenervalores distintos para distintas operaciones de comunicacion.

El coste de la computacion se puede estimar ejecutando partedel programa en un procesador.

Ajuste del modelo teorico con datos experimentales:

Obtener valores constantes del estudio teorico con ajuste pormınimos cuadrados con resultados experimentales.

Estudio asintotico: comportamiento teniendo en cuenta eltermino de mayor orden de la formula teorica, compararlo conla grafica experimental.


Date post:	16-Aug-2020
Category:	Documents
Upload:	others
View:	8 times
Download:	0 times

An lisis de algoritmos paralelosdis.um.es/~domingo/apuntes/AlgProPar/1718/analisis.pdf ·...

Documents