Proyecto Universidad-Secundaria Incorporaci n de ...dis.um.es/~domingo/apuntes/FP14/ProgMP.pdf ·...

ProcesosElementos de Programacion Multiproceso

Entornos de Programacion Multiproceso

Proyecto Universidad-SecundariaIncorporacion de contenidos de programacion paralela en

la rama de tecnologıas informaticas

Facultad Informatica, Universidad de Murcia eInstituto de Ensenanza Secundaria Ingeniero Juan de la Cierva

Programacion Multiproceso

Univ de Murcia-IES Ing. de la Cierva Paralelismo en la rama de tecnologıas informaticas



Posible utilizacion

Modulo de Programacion de servicios y procesos, segundode Desarrollo de Aplicaciones Multiplataforma

Parcialmente se podrıa usar en Tecnologıas de la Informaciony de las Comunicaciones, primero de Bachillerato




Contenido

1 Procesos

2 Elementos de Programacion Multiproceso

3 Entornos de Programacion MultiprocesoUso de pipe en C/C++Captura de flujo de I/O en JavaMPI




Concepto de proceso

Un proceso es una instancia de un programa que se ejecuta:

Programa: Coleccion de instrucciones.Proceso: Ejecucion de las instrucciones.

se pueden ejecutar varias instancias (procesos) del mismoprograma,

varios procesos (del mismo o distinto programa) puedencolaborar en la resolucion de un problema, compartiendo losrecursos del sistema computacional,

se necesitan mecanismos de comunicacion y sincronizacion.




Recursos asociados a un proceso

Cada proceso tiene asociados una serie de recursos del sistema:

Una imagen del codigo maquina del programa

Una parte de memoria, para almacenar el codigo, los datosdel proceso, la pila de llamadas de sus rutinas...

Descriptores de los recursos del sistema asociados alproceso (por ejemplo, descriptores de ficheros)

El contexto del proceso: contenido de los registros,direcciones de memoria...

El sistema operativo almacena la informacion de los procesosactivos en bloques de control de procesos.




Estados de un proceso

Inicialmente se crea el proceso: se cargade memoria secundaria a principal.

Despues pasa a estado de esperando,hasta que el scheduler del sistema loasigna a un procesador.

Pasa a estado de ejecutandose.

Cuando necesita esperar a que unrecurso este disponible pasa abloqueado, y cuando ya tiene el recursopasa a esperando y de ahı aejecutandose.

Finalmente pasa a terminado.




Planificacion de procesos

El sistema operativo puede mantener varias instanciasprogramas al mismo tiempo: puede haber programas deusuarios distintos, varias instancias del mismo programa...

Un nucleo ejecuta solo un proceso en un instante de tiempo.En sistemas con varios nucleos o procesadores se puedenasignar procesos distintos a nucleos distintos (ejecucionconcurrente).

La asignacion y desasignacion de procesos a nucleos debehacerla el sistema operativo de forma rapida.

Los procesos pueden cambiar de estado por interrupcionessoftware o hardware.

Un cambio de contexto ocurre cuando un proceso en unnucleo para y se le asigna otro proceso.




Procesos versus hilos

Un proceso puede tener subprocesos o hilos, que sonsecuencias independientes de ejecucion dentro del codigo deun proceso.

Los hilos son las secuencias mas pequenas de instruccionesque el sistema operativo puede manejar de formaindependiente.

Los hilos dentro de un proceso comparten mas recursos quelos procesos: la memoria, la ultima instruccion del codigo,valores de las variables...

La gestion de hilos por el sistema operativo sera mas rapidaque la de procesos.




Programacion concurrente, paralela y distribuida

Programacion Concurrente

Cuando varios elementos de proceso (hilos, procesos)trabajan de forma conjunta en la resolucion de un problema.Puede ser en un unico procesador o nucleo.

Programacion Paralela

Es programacion concurrente cuando se utiliza para acelerarla resolucion de los problemas,normalmente usando varios procesadores o nucleos.

Programacion Distribuida

Es programacion paralela cuando los sistemas estandistribuidos,por ejemplo una red de procesadores,con lo que hay que usar paso de mensajes.




Necesarios mecanismos de

creacion

ejecucion

finalizacion

comunicacion

sincronizacion

de procesos.




Creacion

Se ordena al sistema poner en marcha procesos, y cada proceso tieneasociadas sus zonas de memoria:

En C:Con fork se crea un proceso hijo, que tiene una copia de las variables delproceso padre.

En MPI:Al lanzar la ejecucion con mpicc -np X programa se ponen en marcha Xprocesos que ejecutan el mismo codigo programa y cada uno tiene en sumemoria asociada copias distintas de las variables del programa.Los procesos pueden empezar a colaborar cuando se inicializa MPI, conMPI Init.

En Java:Esta la clase ProcessBuilder, y se inicializan con el metodo start.Tambien se pueden poner en marcha desde otro proceso conRuntime.getRuntime().exec("programa").Y se pueden usar RMI (Java Remote Method Invocation) para invocarmetodos de forma remota, para aplicaciones cliente-servidor.




Ejecucion

Una vez puestos en marcha, los procesos trabajan de formaindependiente, ejecutando el mismo o distinto programa, ycada uno con los datos a el asociados.

Si ejecutan el mismo programa, aunque las variables sellaman igual, cada proceso trabaja con una copia distinta deellas, por lo que la misma variable tiene valores distintos enprocesos distintos.

Hay mecanismos para sincronizar los procesos.

Cuando un proceso necesita datos de otro proceso el accesoa esos datos se realiza con comunicaciones.




Finalizacion

La finalizacion de un proceso supone la liberacion de los recursos que sele asociaron (memoria, variables, descriptores de fichero...).

En C:

Con wait el proceso padre espera a que finalice un proceso hijo.

En MPI:

Los procesos que se lanzaron con mpicc -np X programa acabancuando llegan al final del programa.

Al ejecutar MPI Finalize se liberan los recursos generados paragestionar procesos a traves de MPI, y los procesos dejan de podercolaborar.

En Java:

En la clase ProcessBuilder se pueden usar los metodosfinalize, wait, notify y notifyAll heredados de la claseObject.




Comunicacion

Los procesos acceden a datos asociados a otros procesos pormedio de comunicaciones.

En C:Los procesos padre e hijo emparentados al ejecutar forkpueden comunicarse a traves de una tuberıa usando lafuncion pipe.

En MPI:Hay comunicaciones punto a punto (MPI Send, MPI Recv, yotras versiones) y comunicaciones colectivas (MPI Bcast,MPI Gather...)

En Java:Ofrece multitud de posibilidades: colas de mensajes, canales,RMI, sockets, redireccionamiento de flujos de entrada/salida.




Sincronizacion

Los procesos se sincronizan al comunicarse,pero tambien al acabar la ejecucion, por ejemplo si unproceso espera a otro en un wait.

En las comunicaciones puede haber sincronizacion entre dosprocesos (comunicaciones punto a punto, o tuberıasasociadas a dos procesos) o entre varios procesos(comunicaciones colectivas).

Puede ser necesaria sincronizacion sin comunicar datos, porejemplo para esperar que todos los procesos lleguen a unpunto de la ejecucion para seguir trabajando juntos. Seutilizan barreras, en MPI con la funcion MPI Barrier.




Uso de pipe en C/C++Captura de flujo de I/O en JavaMPI

Veremos ejemplos basicos de programacion multiproceso:

Uso de pipe en C/C++

Captura de flujo de I/O en Java

MPIveremos programacion por paso de mensajes en MPIcon versiones nuevas de los ejemplos vistos en laIntroduccion a la Programacion Paralela,y se podra trabajar con la prueba PP-FP2014 de la pagina delConcurso de Programacion Paralela.





Se crea una tuberıa con una llamada a la funcion pipe(td),donde td es un array de dos enteros.

Se escribe en la tuberıa con write(td[1],dir,tam), condir la direccion de comienzo de los datos, y tam la cantidadde memoria a mandar.

Se recibe a traves de la tuberıa con read(td[0],dir,tam).

Compilar y ejecutar el programa pipe-basico.c,que suma 10 numeros utilizando dos procesos.

A diferencia del ejemplo anterior de uso de fork, donde losprocesos se comunicaban a traves de la memoria,en este ejemplo se comunican con la tuberıa, con una especie depaso de mensajes.





Ejemplo: ordenacion con dos procesos mandandomensajes por tuberıa

El programa en programas/C/pipe-ordenacion.cpp realiza unaordenacion con dos procesos,a diferencia del ejemplofork.cpp en este caso no se compartememoria,sino que se usa una tuberıa para comunicar datos entre losprocesos.

Las tuberıas tienen un tamano por defecto,por lo que a partir de un tamano de envıo el programa nofuncionarıa.Para evitar esto, se usa la funcion fcntl para cambiar el tamanomaximo de los mensajes por la tuberıa.





En los programas maestro.java y esclavo.java tenemos unejemplo basico de colaboracion entre procesos,con comuniacion a traves de los flujos de I/O:

El proceso que ejecuta el programa maestro pone en marchala ejecucion del esclavo con una llamada aRuntime.getRuntime().exec

y declara un flujo de entrada para hacer lectura por bufferinStream = new BufferedReader(new

InputStreamReader(esclavo.getInputStream())

Compilar y ejecutar el programa:

Compilar maestro.java y esclavo.java

Ejecutar maestro N, que pone en marcha esclavo N (dondeN sera un numero).





Ejemplo: ordenacion con proceso maestro y esclavo

Siguiendo el mismo esquema del ejemplo basico anterior, los programasmaestroOrdenar.java y esclavo.Ordenar.java realizan una ordenacion denumeros enteros comunicandose con el flujo de entrada.

El numero de datos a ordenar se pasa como argumento al maestro.

El esclavo es el que genera los datos, envıa al maestro la primera mitad, ordenala segunda mitad y la pasa al maestro ordenada.El maestro ordena la primera mitad, recibe la segunda ordenada y mezcla lasdos mitades.

Los datos se pasan como cadenas de caracteres, por lo que se hace conversionde cadenas a enteros.

Analizar la evolucion de los tiempos de ejecucion secuencial y paraleloaumentando el tamano del problema.

El alto coste de las comunicaciones hace que ahora sea necesario aumentar

considerablemente el tamano de problema para acercarnos a una aceleracion de

cuatro veces mas rapida la version paralela respecto a la secuencial.





MPI (Message Passing Interface) es el estandar de factoactual para programacion en sistemas de memoriadistribuida.

Es una especificacion para paso de mensajes.La primera librerıa de paso de mensajes estandar y portable.Realizada por consenso (MPI Forum), con participacion deunas 40 organizaciones.Acabado y publicado en mayo 1994. Actualizado en junio1995.

Hay varias versiones y variantes: MPI2, HMPI, FT-MPI...algunas de ellas libres: MPICH, LAM/MPI, OpenMPI...

Previamente PVM: Parallel Virtual Machine (aprox. 1993).





Caracterısticas generales

Recordamos los aspectos de MPI vistos en el ejemplocodigo6-16.c:

Se usa la librerıa mpi.h

Es un programa C con llamadas a la librerıa MPI.

Las funciones empiezan con MPI .... Hay funciones de:

inicializacion (MPI Init) y finalizacion (MPI Finalize),para obtener el numero de procesos (MPI Comm size) y elidentificador de proceso (MPI Comm rank),de sincronizacion (MPI Barrier),de envıo (MPI Send) y recepcion (MPI Recv)

Se compila con mpicc -O3 codigo6-16.c

Se ejecuta con mpirun -np X ./a.out tam, donde X indicael numero de procesos a usar, y tam el numero de datos aordenar.





Forma de las funciones

Las funciones tienen la forma:error=MPI nombre(parametros)

La de inicializacion de MPI esint MPI Init ( int *argc , char ***argv )

y la de finalizacionint MPI Finalize ( )

En algunas funciones aparece la constante MPIMPI COMM WORD.Varios procesos MPI se agrupan en un comunicador, yMPI COMM WORD identifica el comunicador formado por todoslos procesos MPI.





Funciones de identificacion

Procesos en el comunicador:MPI Comm size ( MPI Comm comm , int *size)

devuelve en size el numero de procesos en el comunicadorcomm.Si la llamamos con el comunicador MPI COMM WORD devuelveel numero de procesos MPI puestos en marcha.

Identificacion de procesos:MPI Comm rank ( MPI Comm comm , int *rank)

devuelve en rank un identificador para cada proceso.Los procesos se numeran de 0 al numero de procesos menos1.





Mensajes

En un mensaje se envıa un cierto numero de elementos de un tipoMPI.

Hay tipos basicosTipo MPI tipo CMPI CHAR signed charMPI SHORT signed short intMPI INT signed intMPI LONG signed long intMPI UNSIGNED CHAR unsigned charMPI UNSIGNED SHOT unsigned short intMPI UNSIGNED unsigned intMPI UNSIGNED LONG unsigned long intMPI FLOAT floatMPI DOUBLE doubleMPI LONG DOUBLE long doubleMPI BYTEMPI PACKED

y derivados, que los construye el programador.





Mensajes punto a punto

Interviene un proceso que envıa y otro que recibe:

Funcion de envıo

int MPI Send ( void *buffer , int contador , MPI Datatype

tipo , int destino , int tag , MPI Comm comunicador )

Funcion de recepcion:

int MPI Recv ( void *buffer , int contador , MPI Datatype

tipo , int origen , int tag , MPI Comm comunicador ,

MPI Status *estado)

Se envıa el numero de datos indicado por contador, empezando en la zona dememoria senalada por el puntero buffer.Se indica el identificador de proceso que envıa (origen) y que recibe (destino).Se puede indicar que se recibe de cualquiera poniendo como origen la constanteMPI ANY SOURCE.El parametro tag sirve para diferenciar mensajes. Tiene que tener el mismovalor en el proceso que envıa y en el que recibe. Con MPI ANY TAG se indica quese recibe un mensaje con cualquier valor en ese parametro.





Comunicaciones sıncronas

Con las funciones de comunicacion punto a punto anteriores las comunicacionesson sıncronas:

El proceso que envıa sigue trabajando despues de llamar a la funcion.

El proceso que recibe lee el mensaje si ya ha sido enviado, pero si noqueda a las espera de que se le envıe.

La funcion de recepcion es siempre MPI Recv,pero hay varias funciones de envıo segun el grado de sincronizacion en el envıoy donde queden los datos una vez enviados:

MPI Send: el proceso que envıa sigue cuando el buffer de salida estadisponible para usarlo.

MPI Rsend: se ejecuta solo si ya se ha realizado la llamada a recepcion, sino da error.

MPI Ssend: el proceso que envıa espera hasta que empieza la recepcion.

MPI Bsend: cuando se sabe que hay espacio en el buffer de salida. Sepuede reservar espacio con la funcion MPI Buffer attach.





Comunicaciones asıncronas

En las comunicaciones asıncronas no espera ninguno de los dosprocesos. Las funciones son:

int MPI Isend ( void *buffer , int contador ,

MPI Datatype tipo , int destino , int tag ,

MPI Comm comunicador , MPI Request *request )

int MPI Irecv ( void *buffer , int contador ,

MPI Datatype tipo , int origen , int tag ,

MPI Comm comunicador , MPI Request *request)

Donde en request se guarda una etiqueta que identifica laoperacion. Se puede trabajar con ella:

int MPI Wait ( MPI Request *request , MPI Status

*status ): espera hasta que esta disponible la operacion.int MPI Test ( MPI Request *request , int *flag ,

MPI Status *status ): comprueba si esta disponible.





Comunicaciones asıncronas - Ejemplo

En el directorio programas/MPI/D-Asincrono hay un ejemplo deuso de comunicaciones asıncronas.

Se trata del ejemplo de multiplicacion de matrices visto en laIntroduccion a la Programacion Paralela y que corresponde alproblema D de la prueba PP FP1024 de la pagina del Concurso deProgramacion Paralela.

Se puede analizar su funcionamiento y ejecutarlo en el concurso.

Puede que se observe una ligera reduccion en el tiempo deejecucion respecto a la version sıncrona, pero en cualquier caso lareduccion no sera importante debido a la clara estructura delprograma.Se puede realizar una version asıncrona del problema C, quecorresponde a una ordenacion, y probarla en el concurso.





Comunicaciones colectivas

En ellas intervienen todos los procesos en el comunicador. En el ejemploanterior hemos visto MPI Bcast, con la que se envıan datos de un proceso (raız)a todos los demas. Otras operaciones colectivas:

MPI Barrier: no comunica datos, pero bloquea los procesos hasta que lallaman todos.

MPI Gather: para recibir valores de todos los procesos.

MPI Scatter: para distribuir un buffer entre los procesos.

MPI Alltoall: para enviar datos de todos los procesos a todos.

MPI Reduce: combina valores de todos los procesos en un proceso.

MPI Reduce scatter: combina valores de todos los procesos y distribuyea todos.

Las operaciones que se pueden hacer en las rutinas de reduccion son: maximo (MPI MAX),

mınimo (MPI MIN), suma (MPI SUM), producto (MPI PROD), and logico (MPI LAND), and bit a

bit (MPI BAND), or logico (MPI LOR), or bit a bit (MPI BOR), or exclusivo logico (MPI LXOR), or

exclusivo bit a bit (MPI BXOR), maximo y su posicion (MPI MAXLOC), mınimo y su posicion

(MPI MINLOC).





Comunicaciones colectivas - Ejemplo

En el directorio programas/MPI/D-Colectivas hay un ejemplode uso de comunicaciones colectivas, donde se ve elfuncionamiento de las funciones MPI Scatter y MPI Gather.

Es el mismo ejemplo de multiplicacion de matrices anterior.


La principal ventaja de las comunicaciones colectivas es quefacilitan la programacion,y pueden acelerar la ejecucion si se usa una implementacion deMPI que tenga optimizadas estas funciones para el sistema dondeestamos trabajando.

Se puede realizar una version con comunicaciones colectivas delproblema C y probarla en el concurso.





Empaquetamiento de datos

Se pueden empaquetar datos para enviarlos juntos. Por cada dato aempaquetar se llama a:

int MPI Pack( void *datos, int contador, MPI Datatype tipo,

void *buffer, int tambuffer, int *posicion ptr, MPI Comm

comm)

Se empaquetan en buffer contador datos de tipo tipo que seencuentran en datos.

El tamano del buffer (tambuffer) puede ser mayor al que se va a ocupar.

posicion ptr es de entrada-salida. A la entrada apunta a la posicion delbuffer donde se van a copiar los datos, y a la salida a la posicion siguienteal ultimo dato empaquetado.

El proceso que recibe desempaqueta los datos en el mismo orden en quese empaquetaron, llamando por cada dato a la rutina

int MPI Unpack( void *buffer, int tambuffer, int

*posicion ptr, void *datos, int contador, MPI Datatype tipo,

MPI Comm comm)





Empaquetamiento de datos - Ejemplo

En el directorio programas/MPI/D-Empaquetar hay un ejemplode uso de comunicacion con empaquetamiento, donde se ve elfuncionamiento de las funciones MPI Pack y MPI Unpack.

Es el mismo ejemplo de multiplicacion de matrices anterior.


Empaquetar varios datos para transferirlos juntos permite reducirel numero de comunicaciones, y puede producir una reduccion deltiempo de ejecucion, ya que las comunicaciones son muycostosas.Por otro lado, el empaquetamiento tambien tiene un coste degestion de los datos, lo que produce una sobrecarga, y ademasmientras el proceso que envıa esta empaquetando el resto estan ala espera. Por tanto no podemos asegurar que siempre sea mejorempaquetar varios datos para mandarlos juntos.





MPI - Otras caracterısticas

Hemos visto las caracterısticas principales de MPI.Con las funciones estudiadas se puede realizar cualquier programa de paso demensajes, pero MPI ofrece muchas mas funciones (mas de 120).Otras posibilidades de MPI:

Tipos derivados: los crea el usuario en tiempo de ejecucion. En el ejemploanterior se podrıa crear un tipo formado por una porcion de la matriz A ytoda la matriz B, y a partir de ahı se podrıan enviar elementos de ese tipo.

Se pueden crear comunicadores con menos procesos de los que hay enmarcha (menos que MPI COMM WORLD) y hacer comunicaciones colectivasen ese comunicador, sin necesidad de que se participen el resto deprocesos.

Se pueden definir topologıas, que son patrones de comunicacion entre losprocesos. Hay topologıas mas adecuadas que otras para distintosesquemas de programa y distintas conexiones de los procesadores, y unabuena seleccion de la topologıa puede contribuir a reducir el tiempo deejecucion.


Date post:	17-Mar-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Proyecto Universidad-Secundaria Incorporaci n de ...dis.um.es/~domingo/apuntes/FP14/ProgMP.pdf ·...

Documents