Programación paralela: implementación de clúster para laresolución de multiplicación de matrices

Gonzalo R. Zenón1 & Ricardo G. Apaza

1 & Walter C. Tejerina

1

(1) Grupo de investigación Clustear, Facultad de Ingeniería, Universidad Nacional de Jujuy.zenewlight@hotmail.com, linux_perico@hotmail.com & walterct87@hotmail.com

RESUMEN: La multiplicación de matrices es una de las operaciones más representativas para muchasaplicaciones, ya que involucran un elevado cálculo de datos con complejidad creciente de acuerdo a lasdimensiones de las mismas. En la actualidad, dependiendo de las necesidades de cada aplicación, puedenencontrarse métodos variados para estos cálculos. En el presente trabajo se mostrará las diferencias entreun entorno paralelo, mediante una interfaz de paso de mensajes, tanto con un solo computador como conun arreglo de procesadores interconectados.

1 INTRODUCCIÓN

Casi desde el principio de la aplicación delprocesamiento paralelo a los problemasnuméricos se han estudiado, diseñado,implementado y experimentado distintas formasde paralelizar la multiplicación de matrices.Desde el punto de vista del problema mismo, esmuy útil tener una optimización de esta operaciónmatricial, ya que siempre es posible encontrarlaen las distintas aplicaciones que se deben resolveren el ámbito numérico.Desde un punto de vista más cercano a lainvestigación, este problema tiene muchascaracterísticas que lo hacen adecuado para suestudio extensivo e intensivo. Las dos másimportantes son su simplicidad, y la posibilidadde extender sus resultados a otras operacionessimilares.La multiplicación de matrices es utilizadaampliamente en distintas aéreas de computo,donde la cantidad de cálculos en un corto tiempoes crucial, ya que esto conlleva un alto costo deprocesamiento, y más si de estos cálculosdependen otros sistemas por lo que se busca unarespuesta ágil a estas operaciones. En este ámbitola búsqueda de la mayor eficiencia a partir de laparalelización, ha sido el centro de un granesfuerzo en el tiempo.El presente documento, fue realizado basándonosen un algoritmo de cálculo de multiplicación dematrices, mediante la interfaz de paso demensajes entre un proceso padre y los esclavos.

2 ESPECIFICACIÓN DE HARDWARE

Las características de las dos computadorasutilizadas para la realización de dicho trabajo,pueden observarse en la Tabla 1.

Tabla 1. Características más resaltantes de lascomputadoras utilizadas durante las pruebas

realizadas.Maquina1 Maquina2

Memoria 2GB 512 MB

Procesador Intel DualCore1.86 Ghz

Intel Celeron1.7 Ghz

Disco Duro 250 Gb 10 Gb

Los componentes utilizados para el armado de lared de trabajo fueron, un router wifi TPLink de 4salidas y 2 cable utp categoría 5 de 1 metro delongitud cada uno.

2.1 Métricas utilizadas

Las métrica utilizada para nuestra comparaciónde rendimiento en este trabajo fue el tiempo deejecución de multiplicación de matrices en clustery en una maquina común (notebook)Para la realización de las pruebas se construyóuna red con dos computadoras, una de escritorio yuna notebook obviamente de distintascaracterísticas interconectadas entre sí por mediode una Lan Ethernet sencilla como se muestra enla Figura 1. Se hicieron correr distintos procesosen cada máquina, teniendo de esta manera un

total de 9 procesos para la realización de laspruebas.Para llegar a ciertas conclusiones con respecto altiempo lo primero que debemos hacer es analizarlos resultados obtenidos en las ejecuciones de losalgoritmos. Sólo de este modo podremosdemostrar la utilidad y potencialidad delprocesamiento paralelo ejecutado en redes. Caberesaltar que dicha configuración se realizó bajo elentorno LinuxEl diagrama de conexión utilizado para larealización del cluster, es el que se muestra en laFig. 1.

Figura 1. Diagrama de conexión utilizado para lacomunicación entre las computadoras

3 CONFIGURACIÓN DE CLUSTER

Para la configuración del clúster se optó por unmodelo de clúster heterogéneo, debido a que sedisponía de computadores con diferentescaracterísticas de hardware, y con sistemasoperativos Linux de diferentes versiones (Ubuntu12.04 y 11.10).Además se utilizó el tipo de configuraciónbeowulf, debido a que este usa una red comúnpara realizar la comunicación. De esta forma seobtuvo un clúster económico.Para lograr la configuración del clúster, seprocedió con la ejecución de una serie de pasos,como lo muestra la página web configuración deun cluster y ejecución de aplicaciones paralelas.Es importante aclara que cada instructivo, seencontraba incompleto, es por ello que seprocedió con la combinación de algunos pasos dedichos instructivos, logrando de esta formaconfigurar el clúster.Las herramientas necesarias para configurar elclúster fueron, según lo muestra la página webmultiprocesamiento: Nfs-kernel-server es unprotocolo de sistemas de ficheros en red quepermite a un usuario en un ordenador clienteacceder a ficheros en red. En este caso sirve paraque los nodos esclavos tengan acceso al nodoservidor, Build-Essential es un paquete que sirve

para ejecutar el compilador de C++ (g++),Openssh-Server sirve para realizarcomunicaciones cifradas a través de la red entrenodo maestro y nodos esclavos, usando elprotocolo ssh, Mpich2 es una implementación dempi, una norma estándar de paso de mensajespara aplicaciones de memoria distribuida queutilizan computación paralela, y Nfs-Common esun paquete que se instala en los nodos esclavos,para lograr que estos se conecten con los recursosnfs del servidor.

4 PRESENTACIÓN DEL PROBLEMA:MULTIPLICACIÓN DE MATRICES

La multiplicación de matrices no es muycomplicada, por lo que se detalla a continuación.Dada una matriz A(m x r) de m filas y r columnas,donde cada uno de sus elementos se define comoaij con 1 i m, y 1 j r; y una matriz B(r x n)

de r filas y n columnas, donde cada uno de suselementos se denota bij con 1 i r, y 1 j n;la matriz C resultante de la operación demultiplicación de las matrices A y B, C = A B,es tal que cada uno de sus elementos que sedenota como cij con 1 i m, y 1 j n, y secalcula a través de la ecuación (1).

Analizando, se puede observar que este tipo deoperaciones se adaptan perfectamente aprocesamientos paralelos porque los cálculosnecesarios para multiplicar matrices no sontotalmente dependientes de otros resultados.En nuestro caso como estamos multiplicandomatrices cuadradas de orden n, podemos calcularla cantidad de operaciones necesarias para llegara la matriz resultante, y es exactamente como lomuestra Tinetti (2003):Cantidad de operaciones = 2n3 - n2

Donde n es la dimensión de las matricescuadradas en este caso.Esta cantidad de operaciones es la quenormalmente se conoce como complejidad de lamultiplicación de matrices. Esto es importante yaque depende de esto el tiempo que un computadornecesitara para resolver esta multiplicación.Si estas operaciones se realizarían en uncomputador que ejecuta programas secuencialesbasados en asignaciones teniendo en cuenta quela multiplicación se realiza como se indica en laecuación (2).

Cij = cij + aik x bkj; (2)

Cij: Matriz resultante, i: número de fila y j:número de columna.

(1)

Implicaría la ejecución de 2n3 operacionesaritméticas. Como se observa generalmente nosiempre coinciden con la formula anterior cuandode ejecuciones de programas se refiere, ya queesta última tarda más en obtener los resultados.El presente trabajo trata mejorar los tiempos derespuestas en este tipo de problemas obteniendoresultados óptimos en base a la ejecuciónconcurrente de procesos y computadores.

5 DISEÑO DEL ALGORITMO

Se utilizó la multiplicación de matrices comunesNxN, una implementación se realizara en unasola máquina y veremos si es posible agilizarlomediante la paralelización de tareas utilizando uncluster maestro y otras Pcs llamadas nodosesclavos. En dicho algoritmo definimos en formaconstante el número de filas y columnas de lasmatrices, luego en distintas compilaciones ledamos distintos tamaños para obtener distintasmedidas de tiempos. Se realizaron los cálculoscon nueve procesos, a cada uno se reparte unaporción de la matriz y se realiza la multiplicación,luego los resultados son devueltos al nodomaestro que realiza la impresión de la matriz finalen un archivo de texto. Las funciones del estándarMpi como lo muestra Puerta (2003), pararealizar dichos cálculos fueron:MPI_Comm_rank: Retorna el identificador de unproceso dentro de un comunicador.MPI_Comm_size: Determina el número deprocesos pertenecientes al grupo asociado a uncomunicador.MPI_Get_processor_name: Retorna el nombredel procesador donde está ubicado el proceso.MPI_Isend: Inicializa el envío de un mensaje nobloqueante a un proceso, esto quiere decir que laejecución del programa no se bloquea con laejecución de la llamada.MPI_Recv: Esta función recibe mensajes de tipobloqueante, esto quiere decir que la ejecución delprograma se bloquea hasta que el mensaje ha sidorecibido.En otras palabras, para que el proceso A mandeun mensaje al proceso B el argumentocomunicador que A usa en MPI_Isend() debe seridéntico al argumento que B usa en MPI_Recv().MPI_Bcast: Envía un mismo mensaje desde unproceso a todos los demás. Es una operación decomunicación colectiva.Habrá un proceso maestro con identificador cero,que enviara las tareas a los esclavos, los cualestendrán un identificador distinto de cero.Este programa utiliza el paradigma de maestro-esclavo. En el paradigma maestro-esclavotenemos un thread/proceso distinguido, llamadomaestro, que pone en marcha otros procesos,

llamados esclavos, les asigna trabajo y recolectalas soluciones parciales que generan. Estosprocesos son independientes unos de otros.

6 DISTRIBUCIÓN DEL TRABAJO

El proceso maestro es quien organiza el trabajo arealizar, inicializando los operandos demultiplicación y lo va distribuyendo entre losprocesos esclavos, es decir lo que realiza elmaestro es calcular la porción para cada uno delos esclavos, sin incluirse. Si las filas de la matrizA no son divisibles por la cantidad de esclavos,el último esclavo recibe las filas excedentes, casocontrario las filas serán repartidas de igual formapara todos los procesos esclavos. A continuaciónse envían los datos necesarios para calcular lacantidad de filas en los procesos. Luego setransmite los datos de la matriz B a todos losprocesos, se procede con la ejecución de losprocesos esclavos, en donde se recibirán losdatos necesarios para calcular la matriz Cresultante, iterando de acuerdo a los datosrecibidos y enviando los datos procesados almaestro. El proceso maestro es quien reúne losdatos procesados por los esclavos, culminandode esta forma con la multiplicación de lasmatrices en forma paralela.

7 ANALISIS DEL PROBLEMA

Por lo general cuando se resuelve problemas demultiplicación de matrices se realizan en formasecuencial, tomando elementos de la primeramatriz y la segunda siguiendo un ordendeterminado para obtener la matriz resultante.Pero en nuestro caso de estudio la cuestión secomplica, cuando las dimensiones de las mismasaumentan exponencialmente y más si se quiereresolver mediante un programa computacionalcon los paradigmas clásicos secuenciales.Una solución al problema de ejecución secuencialde una multiplicación de matrices seria,aprovechar de la idea de un cierto paralelismoque ofrecen los hilos, es decir, crear variosprocesos ligeros que comparten un espaciocomún de memoria y asignar una porción detrabajo a cada uno de ellos y de esta formaresolver con un pequeño aumento en la velocidadproblemas con grandes dimensiones.La otra solución y la que utilizamos en esteartículo viene planteado desde el punto de vistadel intercambio de mensajes entre procesos paracompartir los datos, realizar los cómputosnecesarios y unir los resultados de nuevamente enun proceso padre o maestro. Para tal efecto hemosutilizado la Interfaz de Paso de Mensajes (MPI)

que es una de las más utilizadas hoy en día para elintercambio de mensajes a la hora de implementarun algoritmo paralelo.En el algoritmo propuesto se tiene en cuenta lacantidad de procesos a distribuir los datos de lasmatrices, para que estos calculen su partecorrespondiente y finalmente se unan en elproceso padre o maestro en la matriz resultante.Lo interesante de este algoritmo para el cálculo demultiplicación de matrices, es que de acuerdo a lacantidad de procesos que se requiera, estos seejecutan en las distintas maquinas del clústerconfigurado, tratando de balancear la ejecuciónentre los distintos procesadores disponibles.Además, como las salidas son extensas se decidióguardar en archivos separados a cada matriz.Todos los datos obtenidos fueron analizados, y seencuentran reflejados en el presente documento.

8 ANALISIS DE RESULTADOS

Cuando los procesos culminan su tiempo deprocesamiento, envían su resultado local alproceso cero mediante un mensaje no bloqueante.El proceso cero recoge dichos resultados locales,los guarda en una matriz resultante e imprime elresultado global en archivo de texto. Una vezrealizado esto el programa termina.Al analizar los distintos tiempos obtenidos comolo muestra en la Tabla 2, nos percatamos que seencuentra una mejora en el tiempo de ejecución,cuando los valores del tamaño de las matricesempiezan a ser mayores, en el caso de una solamaquina los valores de rendimiento tienden aalejarse cada vez más significativamente, con loque el costo computacional en un entorno de unasola maquina se vuelve inapropiado.Otra observación con respecto al tiempo deejecución es que la versión que se ejecutó encluster en un principio tarda más como se muestraen la Fig. 2 y por lo tanto el coste computacionalasociado también. Cuantos más nodos intervienenen la ejecución menor es el tiempo de ejecución.

Sin embargo el coste aumenta gradualmente, porlo tanto deberíamos emplear más o menos nodosesclavos dependiendo de la necesidad quetengamos de acelerar el procesamiento y de losrecursos que podamos utilizar, intentando llegar aun compromiso entre rendimiento y coste que seaóptimo para nuestras necesidades.

Tabla 2. Tiempos de ejecución en milisegundos –Multiplicación de matrices.

Tiempos de ejecución enmilisegundos (Ms)

Dimensiónde matrices(NxN) Cluster Maquina 1

100 65.437 11.576

200 216.238 117.490

300 660.619 591.061

400 1175.836 873.057

500 2832.324 1767.430

600 3340.276 2605.753

700 5635.443 4991.344

800 7060.987 6838.067

900 11293.440 11129.352

1000 13489.475 13150.818

1100 19382.907 25248.289

1200 20827.049 30278.202

1300 31591.461 33392.365

1400 34233.110 36040.208

1500 46169.254 48574.480

1600 57988.904 68176.690

1700 68686.980 82679.934

1800 70906.676 98964.491

1900 94716.344 120971.949

2000 95382.402 130809.741

2100 128816.283 173628.497

2200 133977.829 204738.963

2300 182178.878 248056.754

2400 301571.432 384512.850

2500 324535.481 391710.398

Figura 2. Tiempos de ejecución de la aplicación de multiplicación de matrices en la maquina 1 y cluster.

9 CONCLUSIONES

En este trabajo en donde se realizó unadistribución de datos y división de cómputo paralograr la paralelización, se concluyó que eltiempo de ejecución de una aplicación paralelaejecutada en un cluster, no siempre es menor al deuna aplicación ejecutada en una sola máquina,además esta depende de la complejidad delproblema de la aplicación.Por lo cual concluimos que una aplicaciónparalela no siempre es eficiente, ya quedependería del número de procesos en que seejecuta y también de las dimensiones que tenganlas matrices. Mientras mayor sea el número deprocesos existentes, y menor sea la cantidad deprocesadores, puede tardar más tiempo laejecución de una aplicación paralela.En cuanto al algoritmo utilizado para realizar lamultiplicación de matrices, puede verse deacuerdo a los resultados obtenidos en la Tabla 2,que no existe una diferencia demasiada marcadaentre la aplicación ejecutada en el cluster y en unasola máquina, hasta antes de la dimensión 1600de cálculo de las matrices. A partir de dichadimensión, la aplicación ejecutada en el cluster,empieza a presentar un mejor desempeño estable,teniendo en cuenta el tiempo de ejecución, a partirde este punto en donde se comienza a ver elrendimiento del cluster.También, podemos decir que la paralelizaciónparece ser la tendencia cuando se habla decálculos muy complejos a nivel computacional,los cuales llevarían un gran tiempo si no sehicieran en un cluster, es por ello importanteidentificar aquellas tareas que son independientesunas de otras, y poder de esta forma obtener ungran incremento en el rendimiento, lo cual esfácilmente observable en los resultados obtenidosen este trabajo.Como un futuro trabajo, se podría realizarpruebas en un mayor número de máquinas parapoder obtener resultados aún más significativos.También sería muy interesante obtener resultados,utilizando diversas maquinas distribuidas a lolargo de una Wan, es decir, pruebas utilizandonodos que se encuentran en Internet.Por último, la realización de un clúster fue unagran experiencia, en donde se obtuvo nuevosconocimientos, despertando en nosotros uninterés en el campo de la investigación

10 REFERENCIAS

Configuración de un cluster y ejecución deaplicaciones paralelas,https://docs.google.com/file/d/0B-mQXi4VGfRdZjY3NTA0YWMtOTMwZS00MmNmLWI1MTItNzAxNzZiZDVjODFj/edit?hl=en_US&pli=1, 19/07/12.

Multiprocesamiento,http://www.slideshare.net/rfsolano/programacin-paralela, 04/07/12.

Puerta V. F., Procesamiento Paralelo en RedesLinux Utilizando MPI, página 47, 2004.

Tinetti F. G., Cómputo Paralelo en Redes Localesde Computadoras, Universidad Autónoma deBarcelona, página 18, 2003.