Prác%ca3

Sesión2

1

Obje%vos•  Entenderlosalgoritmosmaestro-esclavo– Maestronocolabora– Maestrocolabora

•  Modificarunaimplementaciónparalelaenlaqueelmaestro no colabora, a otra en la que elmaestrocolabora

•  Conocer las comunicaciones punto a punto nobloqueantes:– MPI_Irecv(recepción)– MPI_Wait(espera)– MPI_Test(test)

2

Fractales(I)

•  ¿Quéesunfractal?¿Quépropiedades%ene?– Objetogeométricocuyaestructuraserepiteadiferentesescalas.

– Enalgunoscasos,sucálculopuedeconllevaruncostecomputacionalconsiderable.

– Enestaprác%casevaapar%rdeunprogramaparaleloenMPI(newton.c),queseencuentraenlaszonadetareasdePOLIFORMAT,paracalcularfractalesdeNewton,quehabráquemodificarconvenientemente.

3MaestrocolaboraMaestronocolabora

Fractales(II)

4

AlgoritmoParay=y1,...,y2

Parax=x1,...,x2

col=num_iteraciones_Newton(funcion,x,y)

Pintarelpunto(x,y)conelcolorcol

fin_para

fin_para

Fig3.f(z)=z3-1.•  Paradibujarelcolorenunpunto(x0,y0),secalculaelnúmerodeiteracionesnecesariasparaqueelmétodoitera%vodeNewtonconverja.

•  ElmétododeNewtonesunmétodoitera%voquepermiteobtenerunaraízcomplejadelaecuaciónf(x)=0,par%endodeunpunto(x0,y0).

•  Elmáximonúmerodeiteracionesseusaparaelcolorblanco.

Ejercicio1•  Compila y ejecuta el programa newton.c, para los 5

fractales básicos que puede generar: para ello u%liza lasopciones -c1, -c2, -c3, -c4 y -c5 (cada opción genera unfractalapar%rdeunadeterminadafunción)–  La opción –c5 corresponde a un fractal “no muybonito”,peroidealparaanalizarlasprestacionesdelasimplementacionesparalelasporsermáscostosoqueelresto.

–  Pruebaconlaopción-p50ocon-p-11paracolorear.•  El programa genera una imagen en escala de grises .pgm

o .ppm (o color, con la opción –p num). “num” permitevariarlapaletadecolores.

•  Elnombredelaimagensepuedecambiarconlaopción–o.5

Fractalesopciones–c1a–c4

6

Nota:•  Lospuntoscuyocálculo%eneunmayorcostecomputacionalsonlospuntosenblanco

•  -C5eselfractalmáscostoso

-C1 -C2

-C3 -C4 -C5

Fig.4Algoritmomaestro-trabajadorclásico(maestronocolabora)

7

Siyo=0entonces(soyelmaestro)siguiente_fila<-0Paraproc=1...np envíaalprocesoprocpe%cióndecalcularlafilanúmerosiguiente_fila siguiente_fila<-siguiente_fila+1fin_parafilas_hechas<-0Mientrasfilas_hechas<filas_totales recibedecualquierprocesounafilacalculada proc<-procesoquehaenviadoelmensaje num_fila<-numerodefila envíaalprocesoprocpe%cióndehacerlafilanúmerosiguiente_fila siguiente_fila<-siguiente_fila+1 copiafilacalculadaasusi%o,queeslafilanum_filadelaimagen filas_hechas<-filas_hechas+1fin_mientras

si_no(soyuntrabajador)recibenúmerodefilaahacerennum_filaMientrasnum_fila<filas_totales procesalafilanúmeronum_fila envíalafilareciencalculadaalmaestro recibenúmerodefilaahacerennum_filafin_mientras

fin_si

•  siguiente_fila(maestro):Nºdefilaquevaaserprocesada

•  filas_hechas(maestro):Nºdefilasquesehanprocesado

•  num_fila:•  Esclavo:Nºdefilaenviada

•  Maestro:Nºdefilarecibida

Ejercicio2:entendercódigomaestronocolabora

8

•  siguiente_fila(maestro):Nºdefilaquevaaserprocesada

•  filas_hechas(maestro):Nºdefilasquesehanprocesado

•  num_fila:•  Esclavo:Nºdefilaenviada

•  Maestro:Nºdefilarecibida

Fig5.Algoritmomaestro-trabajadorclásico(maestrocolabora)

siguiente_fila<-0Paraproc=1...np

envíaalprocesoprocpe%cióndehacerlafilanúmerosiguiente_filasiguiente_fila<-siguiente_fila+1

fin_parafilas_hechas<-0Mientrasfilas_hechas<filas_totales

inicialarecepciónnobloqueantedeunafilacalculadadecualquierprocesoMientrasnoseharecibidonadaysiguiente_fila<filas_totales procesalafilanúmerosiguiente_fila siguiente_fila<-siguiente_fila+1 filas_hechas<-filas_hechas+1fin_mientrasSinoseharecibidonadaentonces espera(deformabloqueante)arecibiralgofin_siproc<-procesoquehaenviadoelmensajenum_fila<-numerodefilaenvíaalprocesoprocpe%cióndehacerlafilanúmerosiguiente_filasiguiente_fila<-siguiente_fila+1copiafilacalculadaasusi%o,queeslafilanum_filadelaimagenfilas_hechas<-filas_hechas+1

fin_mientras

9

Sus%tuirestálíneaporelcódigodelrecuadroverde

Ejercicios3y4•  Modificalaimplementaciónnewton.c,llamándolaporejemplonewtoncm.c(o

newtonsol.c),paraquesigaelesquemamaestro-trabajadorendondeelmaestrotambiéntrabaja(solosemodificalapartedelmaestro)–  Sus%tuyeelcódigocorrespondientealrecuadrolaizquierdaporelcorrespondientedeladerecha–  Pruebaelcódigoimplementadoycompruebaqueseob%enenlosmismosfractalesparalasopciones

–c1a–c4.–  Calcula%emposdeejecuciónparalosdoscódigosusandolaopción–c5ycalculalosspeedupsy

eficiencias(consideralaejecuciónsecuencialaquellaenlaquehayunsolotrabajador

10

Códigodis%nto

Figura4Figura5

Ejercicio3

11

Elmaestro%enequeprocesarlasiguientefila:debesadaptarelprocesamientodelafilaquehacenlosesclavosalprocesamientodefilaque%enequehacerelmaestro,copiandolafilacalculadaensusi%o

12

13

int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int tag,MPI_Comm comm, MPI_Request *request) à Recepciónsinbloqueoint MPI_Wait(MPI_Request *request, MPI_Status *status)à Esperaarecepciónmensaje

int MPI_Test(MPI_Request *request, int *flag, MPI_Status *status)à Compruebarecepcióndemensaje•  request:iden%ficadordelarecepciónnobloqueante•  status:estadodelmensajerecibido

-status.MPI_SOURCE:iden%ficadordelprocesoqueharealizadoelenvío-status.MPI_TAG:e%quetadelmensajerecibido

•  flag:-1Elemisorharealizadoelenvío(éxito)-0Elemisornoharealizadoelenvío(aún)

RecordatoriofuncionesMPI_Irecv,MPI_Wait,MPI_Test