72-347-1-PB

Implementación Paralela del Algoritmo de Jubete

María del Carmen Galeano Medina Universidad Nacional del Este - Facultad Politécnica

[email protected] Resumen. Este trabajo se halla enmarcado dentro de la teoría del procesamiento distribuido y la programación paralela, conjuntamente con técnicas basadas en los conceptos de dual, polar u ortogonal, que se asocian a inecuaciones lineales y pertenecen a las teorías de polaridad. En este trabajo se define cómo pueden ser aplicados los conjuntos ortogonales para resolver problemas matriciales, estos problemas son abordados desde una perspectiva puramente algebraica sin considerar los aspectos relativos al análisis numérico como la estabilidad, la aplicabilidad a matrices dispersas, la elección numérica de pivotes, etc. Palabras claves: procesamiento distribuido, conjuntos ortogonales, pivote. Abstract. This work is framed within the distributed processing theory and the parallel programming, jointly with techniques based in the dual, polar and orthogonal concepts that are related to lineal inequations and belongs to the polarity theory. In this work is defined how the orthogonal sets can be applied to resolve matrices problems, which are boarded from a purely algebraic perspective not considering the Numerical Analysis related aspects like stability, the dispersed matrices applicability, the numeric choice of pivots, etc. Keywords: distributed processing, orthogonal sets, pivots. 1. Introducción

La inversión de matrices, el cálculo de determinantes, la resolución de sistemas lineales de ecuaciones, y los problemas de programación lineal son algunos de los problemas matemáticos que surgen frecuentemente en la vida práctica. Por ello, existen muchos procedimientos y programas de ordenador para resolverlos. Sin embargo, muchos de estos programas no están preparados para lidiar con otros problemas también de aparición frecuente, tales como: • Calcular la inversa de una matriz tras

modificarla, suprimiendo y/o añadiendo filas o columnas, a partir de la inversa de la matriz inicial.

• Calcular la inversa de una matriz simbólica.

• Resolver sistemas de ecuaciones lineales con algunas variables.

• Obtener la solución de un sistema de ecuaciones lineales cuando se han eliminado o añadido algunas ecuaciones y/o variables, sin empezar desde el principio, es decir, utilizando la solución del sistema inicial.

• Analizar la compatibilidad de los sistemas lineales de ecuaciones e inecuaciones con variables restringidas.

• Resolver sistemas de inecuaciones lineales.

El Algoritmo de Ortogonalización de Jubete, ofrece un método computacionalmente eficiente para hallar la inversa, el determinante y el rango de una matriz. Además, el método permite actualizaciones dinámicas de inversas y determinantes, cuando se cambian las filas de la matriz inicial, y son especialmente convenientes para cálculos simbólicos [6]. El Algoritmo de Jubete tiene la operativa análoga a la empleada en los métodos de programación lineal; sin embargo, esta nueva concepción basada en los conjuntos ortogonales y de mayor profundidad, permite acceder a su generalización en el caso de matrices simbólicas y particionadas [7]. En el presente trabajo se utiliza el Algoritmo de Ortogonalización de Jubete para hallar la inversa de matrices no singulares.

50

ARTÍCULOS CIENTÍFICOS – INFORMÁTICA – Nº 4 – AÑO 20 08

2. Inversa de una matriz

Para calcular la inversa de la matriz A= (a1; … ; an)

T Se aplica el Algoritmo 2.1 a las filas de A, usando una matriz inicial no singular V0, se obtienen las matrices Vj para j = 1,…n, mediante las transformaciones.

V j+1= Vj M i

-1 (2.1) donde j= 0,.., n-1, Donde Mi es definida como Mi = (e1,…,ei-1, ti, ei+1,…,en)

T Entonces se satisface que: aj

T Vn = ajT V j M i

-1 M i+ 1-1….. Mn

-1

= tjT M j

-1 M j+1-1…. Mn

-1

= ejT M j

-1 M j+1-1…. Mn

-1 = ejT (2.2)

Esto prueba que A-1 = Vn, es decir, la inversa de A es la matriz cuyas columnas están en la tabla final, obtenida utilizando el Algoritmo 2.1. El proceso anterior también permite obtener la descomposición ortogonal del subespacio con

respecto a cualquier fila de A. Sean {v1,…., vn} las columnas de Vn,

entonces:

(2.3)

es la descomposición ortogonal de con respecto a ai. De esta manera, se tiene que: ai x vj = δij (2.4) Siendo δij las deltas de Kronecker [15]. Algoritmo 2.1 – Algoritmo de Ortogonalización

de Jubete

Entrada: Dos subespacios vectoriales

Salida: El subespacio vectorial ortogonal

Paso 1: Hacer W= V0 (la matriz con vj , j= 1,….,s como columnas). Paso 2: Hacer i= 1 y l=0 Paso 3: Calcular los productos escalares tl

j = ui

x wj, j = 1,…., s Paso 4: Desde j= l donde s localizar la columna pivote rl como la primera columna no ortogonal a ui es decir, tlrl ≠ 0. Si no existe tal

columna ir al Paso 7. En caso contrario, continuar con el Paso 5. Paso 5: Incrementar l en una unidad, dividir la columna rl-ésima por tlrl, y si rl ≠ l intercambiar las columnas l y rl, y los productos escalares asociados tl

rl y tll. Paso 6: Desde j=1 hasta s y j ≠ rl hacer lo siguiente: Si tlj ≠ 0 hacer wkj = wkj – tlj wki para k=1,…,n. Paso 7: Si i = m ir al Paso 8. En caso contrario, incrementar i en una unidad e ir al Paso3.

Paso 8: como el subespacio ortogonal :

como su complemento. 2.1. Complejidad En esta sección se obtiene la complejidad del Algoritmo de Ortogonalización de Jubete y se compara con el procedimiento de eliminación de Gauss. En la Tabla 2.1 se da el número de productos y sumas requeridos en las iteraciones. Así, se tiene: Número total de productos = n3 y Número total de sumas = n3- 2n2+n Similarmente, en la Tabla 2.2 se muestra el número de productos y sumas requeridas en las iteraciones del método de eliminación de Gauss para invertir una matriz.

Productos o divisiones

Fase Iter. 1 Iter.2 … Iter. n Total

Nor

mali

zació

n

n n … n n2

Pivot

aje n( n - 1) n( n - 1) … n( n - 1) n2( n - 1)

Sumas

Pivot

aje ( n - 1)2 ( n - 1)2 … (n -1)2 (n3-2n2+n)


51

así, se tiene:

Número total de productos = n3 y Número total de sumas = n3-2n2+n Lo que demuestra que las complejidades de los dos algoritmos son exactamente las mismas. 3. Procesamiento Paralelo

En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos clásicos o algoritmos secuenciales, puede ejecutarse por partes en el mismo instante de tiempo por varias unidades de procesamiento, para que finalmente se agrupen todas las partes y se obtenga el resultado correcto.

Algunos algoritmos se dividen fácilmente en partes; como por ejemplo, un algoritmo que obtenga todos los números primos entre 1 y 100, donde se podría dividir los números originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los números originales, al final, se unirían todos los resultados y se tendría la solución final del algoritmo.

Por el contrario, a veces los problemas no se paralelizan fácilmente, de ahí que estos problemas se conocen como problemas inherentemente secuenciales [4]. Como ejemplo de estos métodos se tienen los métodos numéricos iterativos, como el método de Newton o el problema de los tres cuerpos.

Los algoritmos paralelos son importantes, porque se tratan grandes tareas de computación más rápidamente mediante la paralelización, que a través de técnicas secuenciales. Ésta es la forma como se trabaja en el desarrollo de los procesadores modernos, ya que es más difícil incrementar la capacidad de procesamiento con un único procesador, que aumentar su capacidad de cómputo mediante la inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de instrucciones dentro del procesador.

Pero se debe mantener cautela con la excesiva paralelización de algoritmos, ya que existe siempre una parte secuencial en cada algoritmo paralelo, y debido a esto, se puede llegar a un punto de saturación [3]. Por tanto, a partir de cierto nivel de paralelismo, en caso de que se adicionen más unidades de procesamiento, solo se obtiene el incremento de coste y la disipación de calor.

El coste o complejidad de los algoritmos secuenciales se estima en términos de espacio (memoria) y tiempo (ciclos de procesador) que requiera. Los algoritmos paralelos también necesitan optimizar la comunicación entre diferentes unidades de procesamiento. Esto se consigue mediante la aplicación de dos paradigmas de programación y diseño de procesadores distintos: memoria compartida o paso de mensajes.

La técnica de memoria compartida requiere de seguridad en los datos para impedir que se modifiquen simultáneamente por dos procesadores, lo que produce un coste extra en ciclos de CPU y ciclos de bus. También obliga a serializar alguna parte del algoritmo.

La técnica paso de mensajes utiliza canales y mensajes, pero esta comunicación añade un coste de bus, memoria adicional para las colas y los mensajes, y latencia en los mensajes. Los diseñadores de procesadores paralelos implementan buses especiales para que el coste de la comunicación sea pequeño, pero es el algoritmo paralelo el que decide el volumen del tráfico. Finalmente, una subclase de los algoritmos paralelos, los algoritmos

Productos o divisiones

Fase Iter.

1 Iter.2 … Iter. n Total

Prod.

Escala

res

0 n … n( n - 1) (n3 - n2)/2

Norm

alizaci

ón

1 2 … n (n2 + n)/2

Pivota

je n - 1 2 (n - 1) … n( n - 1) (n3 - n)/2

Sumas

Fase Iter. 1 Iter.2 … Iter. n Total

Prod.

Escala

res

0 n - 1 … (n -1)2 (n3-

2n2+n)/2

Pivota

je 0 n - 1 … (n -1)2

(n3-

2n2+n)/2


52

distribuidos, son algoritmos que trabajan en entornos tipo cluster y de computación distribuida, donde se utilizan otras técnicas, fuera del alcance de los algoritmos paralelos clásicos.

La idea básica detrás del procesamiento paralelo es que varios dispositivos (procesadores), ejecuten simultánea y coordinadamente las tareas, para que puedan rendir más que un único dispositivo. El problema fundamental son las innovaciones tecnológicas que se requieren para obtener ese rendimiento mejorado.

Si bien el procesamiento paralelo ofrece una ventaja definitiva en cuanto a costos, su principal beneficio, la escalabilidad (capacidad de crecimiento), puede ser difícil de alcanzar. Esto se debe a que conforme se adicionen procesadores, las disputas por los recursos compartidos se intensifican. [5].

3.1. Modelos de Programas Distribuidos

Existen diversos modelos de programas distribuidos, entre ellos se destacan [12]: • Maestro/Esclavo: Procesos hijos ejecutan

partes menores de una tarea, devolviéndose los resultados al proceso padre.

• Pipeline (línea de producción): Procesos cooperan intercambiando información en un flujo continuo. Un proceso, al completar su tarea, pasa el resultado al proceso siguiente, quedando libre para recibir nuevas tareas del procesador anterior.

3.2. Herramienta de la Programación Paralela:

Paso de Mensajes

El paradigma de paso de mensajes es utilizado en sistemas débilmente acoplados, representados por la arquitectura basada en memoria distribuida (clusters), en donde cada procesador tiene acceso solamente a su memoria local y, por consiguiente, la comunicación necesariamente se lleva a cabo por medio de una red de interconexión [12].

Conceptualmente, la idea de paso de mensajes, es totalmente independiente del hardware, sistema operativo, lenguaje de programación, y bibliotecas. Durante el desarrollo de un

programa paralelo por paso de mensajes, los datos se deben distribuir explícitamente entre los procesadores. El espacio de direccionamiento de los procesos, que componen el programa paralelo, es distinto, por eso se concibió la abstracción de usar mensajes que pueden ser enviados de un proceso a otro por un canal de comunicación. Tal concepto es denotado en el programa, a través de las primitivas send y receive, las cuales suponen que un proceso pretende enviar (send) un mensaje a otro proceso, el cual espera recibirlo (receive). Entre los procesos existe un canal de comunicación.

En la práctica, los programadores disponen de bibliotecas de comunicación con primitivas semejantes a send y receive. Las bibliotecas de comunicación que obtuvieron mayor aceptación fueron: MPI y PVM, ambas con soporte a lenguaje C y Fortran [11].

En este trabajo se usará la biblioteca MPI para la implementación paralela del Algoritmo de Jubete; a continuación se exponen los conceptos básicos de dicha biblioteca.

3.3 MPI

El MPI es una biblioteca de Message Passing o Paso de Mensajes desarrollada para ambientes de memoria distribuida, máquinas paralelas, y redes heterogéneas. Define un conjunto de rutinas para facilitar la comunicación (intercambio de datos y sincronización) entre procesos paralelos. Posee aproximadamente 125 funciones para la programación [10].

Al diseñarse MPI, se tomaron en cuenta las características más atractivas de los sistemas existentes para el paso de mensajes, en vez de seleccionar solo uno de ellos y adoptarlo como el estándar. Resultaron así una fuerte influencia para MPI los trabajos hechos por IBM, INTEL, NX/2, Express, nCUBE’s Vernex, p4 y PARMACS. Otras contribuciones importantes provienen de Zipcode, Chimp, PVM, Chameleon y PICL [12].

El esfuerzo para estandarizar MPI involucró a cerca de 60 personas de 40 organizaciones diferentes, principalmente de U.S.A y Europa. La mayoría de los vendedores de computadoras concurrentes estaban involucrados con MPI, así como los investigadores de diferentes universidades, laboratorios del gobierno e


53

industrias. El proceso de estandarización comenzó en el taller de estándares para el paso de mensajes en un ambiente de memoria distribuida, patrocinado por el Centro de Investigación en Computación Paralela en Williamsbur, Virginia. Se llegó a una propuesta preliminar conocida como MPI1 , enfocada principalmente en comunicaciones punto a punto sin incluir rutinas para comunicación colectiva y no presentaba tareas seguras. El estándar final para el MPI fue presentado en la conferencia de Supercomputación en Noviembre de 1993, y se constituyó así el foro para el MPI [10,12].

Las implementaciones en MPI consisten en un conjunto de bibliotecas de rutinas que pueden ser utilizadas en programas escritos en los lenguajes de programación C, C++, Fortran y Ada, Java etc. [12].

Las arquitecturas de computación paralela pueden verse como una extensión de las arquitecturas convencionales que permiten la cooperación y comunicación entre elementos de procesos.

Actualmente existen 2 paradigmas en las arquitecturas de computación paralela.

Respecto al modelo de programación, actualmente 3 paradigmas principales

4. Implementación

El objetivo del presente trabajo es emplear las propiedades del pilotaje para hallar la inversa de matrices no singulares de grandes dimensiones e implementarlas en un ambiente paralelo. Para llegar al objetivo propuesto se utilizó como base el MPI en su versión para C/C++ y el sistema Operativo Linux. El mismo fue instalado en una red de computadoras compuesto por PCs (computadoras personales) interconectadas en red. La idea básica es comparar el tiempo de

ejecución del Algoritmo Secuencial con el Algoritmo en Paralelo y demostrar las ventajas que ofrece la computación paralela, en la gestión de datos en grandes cantidades. El algoritmo de Jubete resuelve un gran número de problemas del álgebra lineal, de forma muy eficiente. El problema seleccionado para probar la eficiencia del Algoritmo de Ortogonalización de Jubete fue hallar la inversa de matrices no singulares. Para tal efecto, se ha implementado el Algoritmo en forma secuencial (en un solo procesador) y paralela (en varios procesadores), y luego se han comparado los tiempos de ejecución entre ambas implementaciones, y se obtuvo el speedUp a partir de estos datos, para concluir los resultados finales. El primer paso para la implementación paralela del Algoritmo de ortogonalización de Jubete fue el estudio detallado y detenido del código, para hallar la manera más efectiva de paralelizarlo. Seguidamente fue codificado y probado en una PC con sistema operativo Linux y MPI. Luego de verificarse la corrección de los resultados, se procedió a realizar las pruebas en un cluster de 10 PCs con sistema operativo Linux y MPI. Se utilizaron matrices de datos diversos y de tamaño variable. Luego se verificó el tiempo de procesamiento de acuerdo con el tamaño de las matrices y el número de procesadores empleados. Seguidamente se extrajeron y se analizaron los resultados para obtener las conclusiones finales.

4.1 Implementación Secuencial

Como mencionado en la sección anterior, luego del estudio de las propiedades y bondades del Algoritmo de Ortogonalización de Jubete, se procedió a la implementación del mismo en código secuencial, utilizando como herramienta el Dev-C++. Como plataforma se ha utilizado una PC de Sum corporation con procesador AMD Opteron de 2.8 GHz con 1 GB de memoria RAM, en donde fue instalado el Sistema Operativo Linux, distribución Fedora y MPI para Linux. Para ejecutar la implementación secuencial del Algoritmo se realizan los siguientes pasos:

Algoritmo 4.1. Algoritmo de Jubete en secuencial.

Incluir la biblioteca “jubete.h”

//programa principal Main


54

{ Leer matriz A generada desde el archivo mat.dat Cargar la matriz identidad C Mientras el nro. de columnas sea menor al contador{

Colocar la primera fila de A en el vector B Hallar los productos escalares y colocar los resultados en el vector TIJ Hallar el pivote y la columna pivote Dividir los elementos de la columna pivote por el pivote Multiplicar la columna pivote por el producto escalar correspondiente a la columna y restar del valor actual de C en dicha columna

}Fin del mientras Cargar la matriz resultado en el archivo mat.dat }Fin

4.2. Implementación Paralela

Antes de realizar la codificación paralela del Algoritmo de Ortogonalización de Jubete, se ha analizado el código cuidadosamente con el fin de obtener el mejor desempeño posible en la implementación paralela. Se ha utilizado una red de 10 computadoras personales de idénticas características de la utilizada para la solución secuencial, las mismas fueron conectadas a través de una red Ethernet, donde una de ellas hace el papel de administrador y las demás de esclavos, todas con Sistema Operativo Linux, distribución Fedora y MPI para Linux. En la Figura 4.1 se puede ver la disposición topológica del Cluster. Para la implementación paralela se tomó el esquema algorítmico básico de la programación paralela, llamado Maestro-Esclavo. En este esquema se tienen algunos procesos que funcionan como maestro y otros como esclavos donde la comunicación solo se realiza entre el maestro y los esclavos.

Maestro.- Este se encarga de la descomposición en subproblemas, de la distribución del trabajo, de la recolección y combinación.

Este esquema se puede apreciar en la figura 4.2 Esclavo.- Este se encarga de la captación del subproblema, del procesamiento que le fue asignado por el maestro y del envío de resultados al maestro

Figura4.2: Esquema maestro - esclavo A continuación se muestran los algoritmos utilizados Algoritmo 4.2. Algoritmo de Jubete en paralelo (Administrador). Incluir la biblioteca “jubete.h”

Nodo Maestro

Nodos Esclavos

Nodos Esclavos

Figura 4. Topología del Cluster

55


//programa principal Main{ Definir variales tipo double t_inicial_par, t_final_par; Asignar valor a mpierr; Para mpierr<0 { Imprimir error de inicialización } Caso Contrario { Leer matriz A generada desde el archivo mat.dat Cargar la matriz identidad C Mientras contador<iteraciones {

Colocar la primera fila de A en el vector B Hallar los productos escalares y colocar los resultados en el vector TIJ Hallar el pivote y la columna pivote Dividir los elementos de la columna pivote por el pivote Multiplicar la columna pivote por el producto escalar correspondiente a la columna y restar del valor actual de C en dicha columna Construir el vector CP

Construir la matriz PLL Enviar el vector PLL a cada proceso i Enviar el vector CP a cada proceso i Enviar PTIJ Enviar el tamaño de la matriz t Enviar el número de iteraciones i Esperar que los procesadores devuelvan los resultados parciales Si todas las multiplicaciones parciales fueron recibidas, cargar los vectores resultados en la matriz C. } Fin Mientras

Almacenar el resultado final en mat.dat } Fin Para } Fin Algoritmo 4.3. Algoritmo de Jubete en paralelo (Esclavo). Incluir la biblioteca “jubete.h” //programa principal Main { Definir variales tipo double t_inicial_par, t_final_par; Asignar valor a mpierr; Para mpierr<0 { Imprimir error de inicialización } Caso Contrario { Mientras contador<iteraciones { Identifica el proceso Identifica la cantidad de procesos Esperar el vector PLL Esperar el vector CP Esperar PTIJ Esperar el tamaño de la matriz t Esperar el número de iteraciones i Calcular PLL[c]=PLL[c]-(PTIJ*CP[c]); Enviar el resultado PLL al administrador Esperar PLL, CPL, PTIJ, i, t del administrador } Fin mientras } Fin Para } Fin

5. Resultados de la implementación

Secuencial

A continuación se exhiben los resultados respecto al tiempo de ejecución y tamaño de la matriz (Gráfico 5.1), de la implementación

secuencial del Algoritmo de Ortogonalización de Jubete.

Tiempo de Ejecucion Algoritmo Secuencial

0

100

200

300

400

500

600

10 15 50 70 100 150 180

Tamaño de Matriz

Tie

mpo

de

Eje

cuci

on

Gráfico 5.1. Tiempo de Ejecución del Algoritmo Secuencial.


56

Como se pudo observar, al aumentar el tamaño de la matriz de entrada, el tiempo de ejecución del Algoritmo de Ortogonalización de Jubete aumenta, llegando a un punto en que este tiempo se vuelve excesivamente largo. Esta limitación, imposibilitó que las pruebas del Algoritmo sean realizadas con matrices de mayor tamaño 6. Resultados de la implementación paralela

En los algoritmos paralelos, además del tiempo utilizado en la computación efectiva del problema, es necesario estimar el tiempo generado por la comunicación entre los procesos. En sistemas de paso de mensajes, el tiempo utilizado con el envío de mensajes debe ser considerado como el tiempo total de ejecución de un problema. Por lo tanto, el tiempo de ejecución está dado por la suma del tiempo utilizado en la parte computacional y el tiempo de comunicación [12]. En una red de wordstations, debido a la heterogeneidad de las máquinas, resulta difícil hacer un análisis matemático del tiempo de computación [14]. De esta forma, usualmente, se considera que todos los procesadores son homogéneos y que operan a la misma velocidad. De manera análoga, el cálculo del tiempo de comunicación depende de varios factores: estructura de la red, latencia, ancho de banda y tamaño del mensaje a ser transferido. De esta forma, se puede usar la siguiente aproximación:

tcom= tstartup + n. tdata

donde: tstartup = Tiempo utilizado para empaquetar el mensaje en el origen y desempaquetarlo en el destino. tdata = Tiempo utilizado para transmitir un dato del origen hasta el destino. Tales tiempos son tomados como constantes en este trabajo. En el siguiente apartado se muestran los tiempos de procesamiento, el SpeedUp y la eficiencia en las pruebas del Algoritmo de Jubete utilizando 1, 2, 4, 8 y 10 procesadores. Las pruebas se

realizaron con tamaños de matrices variables, como se puede observar en las tablas a continuación. 6.1 Tiempo de procesamiento paralelo del

Algoritmo de Jubete

Se puede observar los tiempos de procesamiento encontrados en las pruebas. Las pruebas fueron realizadas variando el número de procesadores y el tamaño de la matriz.

Como se pudo percibir en lo expuesto, el tiempo de procesamiento paralelo del Algoritmo de Ortogonalización de Jubete va disminuyendo a medida que aumenta el número de procesadores. 6.2 SpeedUp logrado con el procesamiento

paralelo del Algoritmo de Jubete

La medición del rendimiento en ambientes paralelos es más compleja por nuestro propósito de conocer cuánto más rápido ejecuta una aplicación en un computador paralelo. Es decir, nos interesa conocer cuál es el beneficio obtenido cuando utilizamos el paralelismo y cuál es la aceleración resultante. El SpeedUp [12] es la “Aceleración” obtenida al resolver el problema en cuestión utilizando una implementación paralela y está dada por la razón del tiempo gastado por la solución en forma secuencial entre el tiempo gastado por la solución en forma paralela, de acuerdo con la expresión (5.2)

A continuación se exhibe el SpeedUp alcanzado por el Algoritmo de Jubete.

(5.1) Sp =

t_sec

t_par

Grafico 5.2. Tiempo Ejecución del Algoritmo Paralelo


57

De lo expuesto, se puede decir que el SpeedUp en el Algoritmo de Jubete va aumentando a medida que es incrementado el número de procesadores utilizado, alcanzando así mayor rapidez en la obtención del resultado final. Como se pudo observar, la implementación paralela del Algoritmo de Ortogonalización de Jubete es ventajosa, porque es posible llegar al resultado final hasta tres veces más rápidamente que implementando el algoritmo secuencialmente. Esta ventaja es bastante significativa a la hora de hallar la inversa de matrices de gran tamaño, situación encontrada con frecuencia en problemas de ingeniería. 7. Conclusiones

El objetivo de este trabajo consistió en la implementación, tanto secuencial como paralela, del Algoritmo de Ortogonalización de Jubete, para hallar la inversa de matrices no singulares, y como resultado final se obtuvo un tiempo aceptable, comparado al obtenido al aplicarlo en su forma secuencial. Estos objetivos fueron logrados, pues como se pudo verificar, la versión paralela del Algoritmo de Ortogonalización de Jubete, logró obtener el resultado hasta 3 veces más rápidamente que implementándolo en su forma secuencial. Estos resultados demuestran la efectividad de la implementación paralela del algoritmo, cuando lo que se desea es utilizar matrices de grandes dimensiones. De lo expuesto se puede afirmar que el excesivo costo computacional en la obtención de matrices inversas no singulares, de grandes dimensiones, irá en disminución, gracias a la paralelización

del Algoritmo de Ortogonalización de Jubete, al contar con un ambiente de programación de bajo costo que permite la resolución del problema en tiempos de procesamiento aceptables. 8. Propuestas para trabajos futuros

Como se expuso en los capítulos anteriores, el Algoritmo de Ortogonalización de Jubete, soluciona varios problemas del álgebra lineal, como por ejemplo: resolver sistemas de ecuaciones lineales; obtener la solución de un sistema de ecuaciones lineales cuando se han eliminado o añadido algunas ecuaciones y/o variables, sin empezar desde el principio; analizar la compatibilidad de los sistemas lineales de ecuaciones e inecuaciones con variables restringidas; resolver sistemas de inecuaciones lineales, hallar el determinante y rango de una matriz, etc. Sería interesante la implementación de uno de estos problemas en un ambiente paralelo, en donde sea posible llegar al resultado final en un tiempo aceptable, cuando es manipulada una gran cantidad de información. 9. Referencias [1] Castillo, E. et al. Orthogonal Sets and Polar Methods in Linear Algebra , J. Mason ( Editor), Plenum Press, New York, 1999. [2] Castillo, E. et al. Updating Inverses in Matriz Análisis of Structures. International Journal of Numerical Methods in Engineering, 43, 1479 – 1504, 1998. [3] Wikipedia. Ley de Amdahl. [marzo-2008]. http://es.wikipedia.org/wiki/Ley_de_Amdahl [4] Wikipedia. Algoritmos Paralelos[marzo-2008]. http://es.wikipedia.org/wiki/Algoritmo_paralelo [5] Romo M, Procesamiento Paralelo. Universidad Internacional del Ecuador, Facultad de Informática y Multimedia. Boletín 5. [6] Castillo E. Conjuntos Ortogonales. CIS, Santander, España, 2001. [7] Castillo, E. et al. Conjuntos Ortogonales y Métodos Polares en Algebra Lineal.Aplicaciones a Cálculo Matricial, Sistema de Ecuaciones, Inecuaciones y

Grafico 5.3. SpeedUp alcanzado por el Algoritmo de Jubete


58

Programación Lineal.Academia de Ingeniería, Madrid, España.

[8] Wikipedia. Distributed Computing. [marzo-2008]. http://en.wikipedia.org/ wiki/ Distributed _ computing [9] Pires A, Ferreira C, Souza M. Computação distribuída de baixo custo aplicada à resolução de problemas matemáticos no ambiente ms-windows. [marzo-2008]. http://www.geocities.com/amaurycarvalho/mpi.html

[10] Wikipedia. MPI. [enero-2008]. http://en.wikipedia.org/wiki/Message_Passing_Interface

[11] Wikipedia. Parallel Computing [enero-2008]. http://en.wikipedia.org /wiki/ Parallel_computing

[12] Guia de Inovaçâo Tecnológica em Cluster e Grid. Ministerio do Planejamento, Orçamento e Gestâo. [marzo-2008]. http://guialivre.governoeletronico. gov.br/guiaonline/guiacluster/ [13] Plaza, E. Cluster Heterogéneo de Computadoras. [junio- 2006].

http://es.tldp.org/Manuales- LuCAS/doc-cluster-computadoras/doc-cluster computadoras-html/manual.html

[14] Macera G. Guía de Aulas. [marzo-2008]. http://www.ucb.br/ prg/professores/giovanni /disciplinas/20052/pc/Avaliando%20Programas%20Paralelos.html [15] Maple User Group Answers. Kronecker Delta [marzo-2008]. http://www.math.rwthaachen.de/mapleAnswers/html/66.html [16] Tanenbaum, A. Sistemas Operativos Modernos, Ed. Guanabara Koogan,1995


59

Documents

72-347-1-PB