Algoritmos ParalelosExamen Parcial

Prof. Jose FiestasUniversidad Nacional de Ingeniera

15/05/15

El examen dura 90 minutos los programas se grabaran en un directorio Apellido AP/ en la plataforma

(en Apellido se ingresara el apellido del alumno)

La copia del examen contendra las respuestas escritas as como todas lasanotaciones necesarias con respecto a los problemas de programacion

1 Conceptos de algoritmos paralelos

Conteste las siguientes preguntas: (puntaje se especifica al final de la pregunta)

Ilustre en un esquema (tiempo vs. numero de nodos) en que caso el tiempototal de computo (tiempo de calculo + tiempo de comunicacion) se incre-menta al incrementar el numero de nodos. Que representa el punto dondelos tiempos de calculo y comunicacion se cruzan? 1 punto

Respuesta:

1

Un codigo realiza la siguiente operacion iterando un millon de veces

(x2 + y2)/z + a3 b2 + 6 (1)

Si el calculo en 10 nodos demora 1 s, calcule los FLOPS (reales) del algo-ritmo. Si las especificaciones de cada procesador indican FLOPS (teoricos)= 2.5 TFLOPS, cual es la eficiencia real de cada procesador ?1 punto

Respuesta:

La ecuacion realiza 10 operaciones, es decir 10 106 = 107 operacionesen total. Por ello, los FLOPS= #op.tiempo=10

7/106 = 10 TFLOPS. Y porprocesador, 1 TFLOP. La eficiencia E = TrealTteorica =1/2.5 = 0.4, o 40 %

En la siguiente funcionindique en que casos (para el vector a[]) se realizara el numero maximo

y mnimo de operaciones. Note que el numero de operaciones varia solodentro de la condicion while. En el algoritmo se asume que siempre l esmenor que n.1 punto

Respuesta

El mejor caso es en el que el argumento de calculo() es positivo, ya que sia[i] >= 0, solo se realiza una operacion en while (mnimo de operaciones),mientras que si a[i] < 0, se realiza mas de una operacion (peor caso,maximo de operaciones).

El costo de un algoritmo paralelo de ordenamiento (sort) de n elementosen p procesos esta dado por

T (p) = (nlog2n

p) (2)

calcule la velocidad S(p) y eficiencia E(n, p), dado que el mejor algoritmosecuencial de ordenamiento tiene un costo (nlogn). Como depende elnumero de procesos p del numero de elementos n, si el costo S(p) es

2

constante?2 puntos

Respuesta:

La velocidad esta dada por S(p) =TseqT (p) =

(nlogn)(nlog2n/p)

= ( plogn ) La

eficiencia es E(p) =( plog )

p = (1

logn ) Y si S(p) es constante, entonces

S(p) = ( plogn ) = (1), es decir p = (logn)

2 Operaciones globales de reduccion

Programe la reduccion de datos con las siguientes condiciones

genere un vector de enteros, de dimension 10, y realize las siguientes op-eraciones con sus elementos:

promedio de todos los elementos hallar el maximo y mnimo elemento factorial de sus elementos utilize para ello funciones MPI MIN, MPI MAX, MPI SUM y MPI PROD,

en MPI Reduce

3 puntos

3 Comunicacion bloqueada

Programe comunicacion P2P (MPI Send, MPI Recv) con las siguientes condi-ciones

un proceso enva una variable real usuarios que represente el numero deusuarios del proceso actual, al proceso siguiente. Este ultimo acumula elvalor recibido con el suyo y lo enva al siguiente proceso. Por ejemplo,si el proceso rank=0 tiene 1000 usuarios y el rank=1, 2000; el procesorank=0 enviara 1000 usuarios al proceso rank=1, el rank=1 enviara 3000al rank=2, etc.

Defina el numero de usuarios por proceso como 1000+100rank. Acumuleel valor del numero de usuarios e imprima el resultado cada vez que unproceso sea llamado

ejecute el programa para 5 procesos y haga una tabla con columnas: rank,usuarios por proceso y suma acumulada

4 puntos

3

4 Ecuacion de calor en una dimension

La distribucion de temperatura (u) en un cuerpo solido en funcion del tiempo(t) y el espacio (x) esta determinada por la ecuacion

du

dt kd

2u

dx2= f(x, t) (3)

Resuelva el sistema de ecuaciones formado aplicando el metodo de de-scomposicion de dominio en n*p intervalos iguales (p=numero total deprocesos) y 400 intervalos de tiempo. Cada proceso tendra a cargo n=10intervalos. Utilize las condiciones de frontera u[0] = 100 + 10 sin(t), yu[n+ 1] = 75, donde t es el tiempo actual

El dominio total es x=[0,1], y el intervalo total de tiempo t=[0,10] Inicializela temperatura a 95 grados (constante en todo el espacio), y el tiempo encero. La constante k = 0.002. Tenga en cuenta que los lmites de intervaloen cada proceso dependen del numero del proceso (rank)

Discretizar la funcion de la siguiente manerau new[i] = u[i] + (t k/(x)2) (u[i 1] 2.0 u[i] + u[i+ 1])) (4)

new representa el ndice temporal j+1

la paralelizacion se llevara a cabo utilizando comunicacion P2P (MPI Send,MPI Recv), donde cada proceso enva la solucion de su extremo izquierdoal su vecino izquierdo, y la solucion de su extremo derecho a su vecinoderecho, y a su vez, recibe la informacion respectiva de sus vecinos. Elprimer y ultimo proceso, sin embargo, utilizan las condiciones de frontera

ejecute el problema y prepare una tabla con la distribucion de temperat-uras al final de la simulacion. I.e., columnas posicion y temperatura

8 puntos

4

5