AIC

Prctica 4 (Paralelismo de procesos)

1. Introduccin El objetivo principal de esta prctica es que el alumno compruebe las ventajas de la programacin paralela respecto a la programacin tradicional. Tras el paralelismo a nivel de instruccin trabajado en la prctica de MMX/SSE, se va a estudiar el paralelismo a nivel de programa (o proceso), mediante los entornos de programacin paralela PVM (Parallel Virtual Machine) y MPI (Message Passing Interface). Para la realizacin de esta prctica se propone que el alumno utilice los dos entornos para que compruebe sus ventajas y desventajas. La distribucin de las tareas y el trabajo conjunto en la resolucin de los problemas son elementos claves para el correcto desarrollo de la prctica. 2. Iniciacin al PVM En esta parte de la prctica se va a introducir de forma muy breve el PVM para que los alumnos tengan una primera toma de contacto con este sistema. El funcionamiento de PVM se basa en un demonio llamado pvmd3 que tendr que estar activo en todas las mquinas que se desee que formen parte del multicomputador. Por otro lado, el entorno proporciona una biblioteca de funciones que facilitan la inicializacin de la mquina virtual, la comunicacin entre los procesos, la sincronizacin, etc. El primer paso para empezar a trabajar con PVM es definir la mquina virtual, es decir, las mquinas que forman nuestro supercomputador. Para ello ejecuta el programa pvm y entrars en el modo consola de PVM. Una forma de aadir los diferentes computadores al multicomputador es utilizar el comando add hostname en la consola de PVM. Con el comando conf obtienes la configuracin actual. Si quieres salir de la consola manteniendo activa la mquina virtual utiliza el comando quit. Si lo que quieres es cerrar tambin la mquina virtual entonces utiliza el comando halt. Para compilar los programas utilizando la librera de PVM hay que enlazar la librera pvm3 (-lpvm3). Se recomienda crear el directorio pvm3/bin/LINUX en el directorio home y colocar all los programas que se van a ir compilando y ejecutando. Utilizar el programa monitor grfico xpvm para visualizar de forma grfica los procesos y la informacin transferida entre ellos. Con este monitor se debe comprobar que la comunicacin y sincronizacin entre procesos es correcta, siendo una herramienta muy potente para analizar el buen funcionamiento de la prctica.

A continuacin se presentan dos cdigos de ejemplo, uno que corresponde a un programa maestro y otro al esclavo.
maestro.c #include #include #include #include <stdio.h> <stdlib.h> "pvm3.h" <time.h>

#define NUMPROC 8 int main() { int tids[NUMPROC]; int cc, mytid; char buf[100]; int i; long *tiempo_proceso; tiempo_proceso = (long *) calloc (NUMPROC, sizeof(long)); mytid = pvm_mytid(); printf("i'm t%x\n", mytid); cc = pvm_spawn("esclavo", (char**)0, 0, "", NUMPROC, tids); pvm_initsend (PvmDataDefault); pvm_pkint (tids, NUMPROC, 1); pvm_mcast (tids, NUMPROC, 0); if (cc > 1) { for (i=0; i <NUMPROC; i++) { cc = pvm_recv(tids[i], -1); pvm_bufinfo(cc, (int*)0, (int*)0, &tids[i]); pvm_upkstr(buf); printf("de la tarea t%x: %s\n", tids[i], buf); } for (i=0; i<NUMPROC; i++) { pvm_recv(tids[i], 0); pvm_upklong (&tiempo_proceso[i], 1, 1); printf("Tiempo del Proc[%d]=%ld\n", i, tiempo_proceso[i]); } } else printf("No puedo arrancar los esclavos, cc = %d\n", cc); free (tiempo_proceso); pvm_exit(); exit(0); } ////////////////////// Fin MAESTRO

esclavo.c #include #include #include #include <stdlib.h> <string.h> <time.h> <unistd.h>

#include "pvm3.h" #define NUMPROC 8 int main() { int mytid; int tids [NUMPROC]; int mi_pid = -1, host; char buf[100]; int i; time_t t_inicial, t_final, t_total, t_aux; t_inicial = t_final = t_total = 0; t_inicial = time (&t_aux); mytid = pvm_mytid(); host = pvm_parent();

pvm_recv (host, 0); pvm_upkint (tids, NUMPROC, 1); for (i=0; i < NUMPROC; i++) { if (mytid == tids [i]) { mi_pid = i; break; } } strcpy(buf, "hola, desde "); gethostname(buf + strlen(buf), 64); pvm_initsend(PvmDataDefault); pvm_pkstr(buf); pvm_send(host, 1); sleep (mi_pid+5); t_final = time(&t_aux); t_total = t_final - t_inicial; pvm_initsend(PvmDataDefault); pvm_pklong(&t_total, 1, 1); pvm_send(host, 0); pvm_exit(); exit(0); } ////////////////////// Fin ESCLAVO

Ejercicios:
a) Utiliza el comando ps a para verificar que se han creado mltiples procesos y que se han distribuido en los diferentes computadores. De igual forma con xpvm observa la comunicacin entre procesos. b) Explica las funciones de librera de PVM que aparecen en los cdigos maestro.c y esclavo.c c) Para qu sirve la funcin pvm_setopt()?Y la funcin pvm_config()? d) Explica de forma grfica, lo ms esquemticamente posible, el funcionamiento de PVM y su uso. e) Crea un programa paralelo mediante PVM, en donde se utilice la estructura de programa paralelo DESCOMPOSICIN DEL DOMINIO. f) Crea un programa paralelo mediante PVM, en donde se utilice la estructura de programa paralelo SEGMENTADO. g) Crea un programa paralelo mediante PVM, en donde se utilice la estructura de programa paralelo DIVIDE Y VENCERS. Nota: Deben ser programas sencillos y que reflejen perfectamente el uso de PVM, por ejemplo resolucin de algn problema matemtico que se preste a su resolucin mediante algn mtodo de paralelizacin. Analiza la ganancia obtenida con respecto a su versin secuencial para distintas cargas de trabajo. Documenta y explica cada uno de los ejercicios. Nota: La versin de PVM instalada en los laboratorios es la 3.4.5. En http://www.csm.ornl.gov/pvm/ y http://www.netlib.org/pvm3/index.html puedes obtener el cdigo y documentacin sobre el entorno PVM. 3. Iniciacin al MPI MPI significa Message Passing Interface y procede del esfuerzo de la comunidad de la computacin paralela (industria y grupos de desarrollo de software libre) por crear un estndar para programacin paralela basada en paso de mensajes. El primer estndar se public en 1994 y, posteriormente, se gener una segunda versin MPI-2 publicada en 1997. A partir de estas definiciones existen implementaciones tanto comerciales como de libre distribucin. La implementacin instalada en los laboratorios es MPICH2 (http://www.mcs.anl.gov/research/projects/mpich2/). En http://www.mpi-forum.org se puede encontrar documentacin sobre el estndar MPI. El primer paso es montar el multicomputador que en el caso de MPI se identifica con un anillo de computadores. Para indicar a MPI los computadores del anillo se utiliza un fichero situado en $HOME que se llamar mpd.hosts. En este

fichero se pueden incorporar tanto direcciones IP como hostnames. A continuacin se tiene que lanzar el demonio mpd en todos los equipos que forman el anillo; para ello se utilizar la orden mpiboot en la que el parmetro -n indica los equipos del anillos (pueden ser menos que los indicados en mpd.hosts); el parmetro f indica el nombre del fichero de hosts; el parmetro r indica que la comunicacin se har mediante rsh (nica posible en el laboratorio). Para que el comando mpiboot funcione es necesario que el mismo usuario haya abierto sesin en todos los equipos que van a formar parte del anillo. Con mpdtrace l se comprueba si el anillo est activo en cada host. Si hay problemas con mpiboot debido a restricciones de permisos (no funciona rsh por algn motivo), se puede activar el anillo manualmente utilizando mpd (hay que tener en cuenta que en las mquinas destino hay que indicar la IP origen y el puerto origen); para cerrar el anillo, en el ltimo equipo habr que lanzar dos veces el demonio mpd, una con los argumentos del equipo origen y otra para cerrar el anillo (argumento n). Para lanzar una aplicacin en el anillo se utiliza el comando mpiexec en el que el argumento n indica el nmero de procesos (por ejemplo: mpiexec n 8 programa) En el siguiente ejemplo, los diferentes procesos hijos le envan al proceso padre (proceso 0) un mensaje y el proceso padre los muestra por pantalla:
ejemplo.c #include "mpi.h" #include <stdio.h> int main( int argc, char *argv[] ) { int idproc, numprocs, namelen, i; char proc_name[MPI_MAX_PROCESSOR_NAME]; char saludo[MPI_MAX_PROCESSOR_NAME+80];

MPI_Status status; MPI_Init (&argc, &argv ); MPI_Comm_rank ( MPI_COMM_WORLD, &idproc ); MPI_Comm_size ( MPI_COMM_WORLD, &numprocs ); MPI_Get_processor_name (proc_name, &namelen ); sprintf(saludo, %s",idproc, "Mensaje del proceso %d de %d procesos en el procesador numprocs, proc_name);

if (idproc == 0) { printf("%s\n",saludo); for (i=1; i<numprocs; i++) { MPI_Recv(greeting, sizeof( greeting ), MPI_CHAR,i, 1, MPI_COMM_WORLD, &status ); printf("%s\n", saludo ); } } else { MPI_Send( greeting, strlen( greeting ) + 1, MPI_CHAR,0, 1, MPI_COMM_WORLD ); } MPI_Finalize(); return 0; }

Ejercicios:

a) Qu diferencias observas con respecto a la programacin con PVM? Indica esquemticamente el funcionamiento de MPI. b) Cmo se lanzaran en un anillo de MPI mltiples ejecutables con diferentes argumentos (utilizando la orden mpiexec)? c) Explica las funciones de librera de MPI que aparecen en el cdigo ejemplo.c d) Para qu sirve la funcin MPI_Barrier()?Y la funcin MPI_Accumulate()?Y MPI_Gather()? e) Paraleliza con MPI los mismos procesos en los ejercicios de PVM. Documntalos de igual forma.

4. Enunciado de la prctica Siguiendo con la misma dinmica que la prctica anterior, el alumno tendr que elegir un problema entre varios propuestos (ms abajo) y proponer otro problema diferente con el objetivo de evaluar el rendimiento de la programacin paralela a nivel de proceso. La resolucin de los dos problemas se har utilizando paralelismo a nivel de proceso. En la resolucin paralela se utilizar PVM para abordar uno de los problemas y MPI para resolver el otro problema. Es importante que se realice una exhaustiva batera de pruebas para analizar los rendimientos y que se expliquen las decisiones tomadas para paralelizar los problemas (argumentando estas decisiones). El anlisis de rendimientos tendr que acompaarse de grficas explicativas, en donde se observe de forma grfica y clara las ganancias obtenidas con respecto a la versin sin paralelizacin, con una batera de pruebas lo suficientemente vlida para obtener resultados significativos. El lmite mximo para comunicar al profesor de prcticas los problemas seleccionados ser la tercera sesin de prcticas. Se valorar la novedad y el inters del problema planteado, siendo el profesor el que apruebe directamente la propuesta hecha por los alumnos. Ejercicios propuestos Dado un conjunto de palabras y un texto de gran tamao, buscar cuntas veces y en qu posiciones se repiten las palabras exactas o cualquier palabra que las contengan. Por ejemplo, ante la palabra casa, tendr que contarse tambin la palabra casas o la palabra casado. Nota: el tamao del texto y el nmero de palabras de bsqueda sern los elementos que condicionarn el coste computacional (por ejemplo, a ms texto, ms se tardar en buscar).

Paraleliza la colocacin de invitados en mesas en una ceremonia en funcin de su grado de afinidad. Ante un conjunto de personas y una relacin de grado de afinidad (A es afn con B en grado 8, A con C en grado 3, B con C en grado 9), donde un nmero mayor indica mayor afinidad, distribuye a las personas en mesas de diferente tamao maximizando la afinidad global de la mesa. Nota: la cantidad de invitados y los tamaos de las mesas controlan el coste computacional.

Dados los datos climatolgicos proporcionados por AEMET (www.aemet.es), obtener datos estadsticos climatolgicos como el lugar con ms precipitaciones, el lugar con menos, la temperatura ms alta, la temperatura ms baja (y dnde y cundo se produjeron), etc.

Observaciones Las prcticas se realizarn bajo Linux. La realizacin de la prctica ser por parejas. La prctica se ir evaluando de forma continuada en el laboratorio de prcticas. La copia de cualquier programa o documentacin ajena supondr un suspenso en la asignatura. Esta prctica se entregar la semana del 4 de abril de 2011 para todos los turnos.