El poder de cálculo incorporado en las unidades de procesamiento gráfico (GPU's) de las nuevas tarjetas de video Nvidia ha permitido aplicar el procesamiento en paralelo a la solución de problemas que requieren de una gran cantidad de cálculoS y que no están ligados al ambiente gráfico,  para el cual fueron originalmente creadas.  En este proyecto se pretende aplicar esta tecnología a la solución de sistemas lineales mediante métodos interativos.

Objetivo general

Diseñar e implementar un método en paralelo para la solución de sistemas de ecuaciones lineales.  

Objetivos específicos

a) Investigar sobre la existencias de métodos iterativos para la solución de sistemas lineales.  

b) Analizar cuál de los métodos iterativos analizados es susceptible de ser paralelizado. 

c) Diseñar un algoritmo paralelo para dicho método iterativo.  

d) Implementar usando programación paralela dicho algoritmo.  

e) Probar y depurar el algoritmo desarrollado sobre algunos sistemas lineales. 

Conclusiones

Las principales conclusiones a las que hemos llegado después de realizar esta investigación son:  

El paradigma de programación CUDA es una tecnología que resulta muy eficiente al resolver problemas en los cuales se requieren realizar muchas tareas independientes sobre una gran cantidad de datos. En general los métodos iterativos son eficientes para resolver sistemas de ecuaciones lineales de gran tamaño. Para los métodos estudiados se diseñaron e implementaron versiones en paralelo usando los paradigmas CUDA y OpenMP con éxito. Aunque CUDA es una herramienta muy poderosa no es aplicable de forma eficiente a cualquier tipo de problema, esta especialmente diseñada para ejecutar muchas tareas independientes sobre grandes cantidades de datos. 

En los casos en que el método de Gauss-Seidel convergía más rápido que el método del gradiente conjugado, el método del gradiente conjugado convergía aun así con bastante rapidez. La eficiencia de CUDA se ve mermada cuando se hacen accesos a la memoria global, pareciera que esto se presenta sobre todo cuando se realiza una operación de escritura. Esto es un punto muy importante al diseñar algoritmos para esta arquitectura. De las pruebas realizadas con OpenMP (cuadro 4.3) el tiempo de ejecución no mejora significativamente después de que se utilizan más de 5 procesadores. El desempeño de OpenMP mejora significativamente conforme el tamaño de la matriz aumenta (cuadro 4.4). Esto se debe a que el tiempo que se pierde en el proceso de dividir el trabajo se recupera por la mayor cantidad del mismo. De las pruebas realizadas pareciera que OpenMP es más eficiente que CUDA en matrices “grandes”, creemos que la razón de esto es una combinación de lo que se acotaba en el ítem anterior y de que muchos accesos (escritura) a memoria global reducen el desempeño de CUDA. En algunos casos sobre todo para matrices muy grandes por encima de los sesenta millones de entradas creemos que se puede mejorar la convergencia aplicando alguna técnica de precondicionamiento, incluso en aquellos casos en los que no se logro la convergencia, por ejemplo con el método de GaussSeidel (cuadro 4.4 y 4.5), una técnica de estas podría ayudar.