Aplicación de estrategias Synchornization Free a la resolución de operaciones de Algebra Lineal Dispersa.

Abstract

El Álgebra Lineal Numérica dispersa es fundamental en muchas áreas de la computación científica, desde la simulación numérica hasta el aprendizaje automático. Sin embargo, su implementación eficiente en hardware paralelo enfrenta desafíos debido a la baja intensidad computacional y la irregularidad en el acceso a memoria. En el contexto de los métodos iterativos para la resolución de sistemas lineales de gran tamaño, la resolución de sistemas triangulares dispersos (SpTRSV) y la factorización LU incompleta (ILU) representan gran parte del costo computacional. Esta tesis explora el uso de estrategias synchronization-free para optimizar la ejecución de SpTRSV e ILU en GPUs. En SpTRSV, se estudian las limitaciones del enfoque tradicional basado en la generación de una estructura de niveles y se optimizan implementaciones que siguen el paradigma synchronization-free. Se propone una nueva estrategia para el ordenamiento del cómputo de las filas, así como un formato de almacenamiento diseñado específicamente para acelerar esta rutina. De manera similar, se desarrollan diversas implementaciones de ILU bajo el paradigma synchronization-free, empleando distintas estrategias para la etapa de actualización, el ordenamiento de filas y la distribución de la carga de trabajo entre los hilos. Los métodos desarrollados son evaluados experimentalmente y comparados con soluciones del estado del arte en diferentes conjuntos de matrices dispersas. Los resultados muestran que las estrategias propuestas logran una reducción significativa en el tiempo de ejecución en SpTRSV y ofrecen resultados competitivos en la ILU. En resumen, las técnicas synchronization-free demuestran ser una alternativa viable para optimizar el rendimiento en operaciones de álgebra dispersa que tienen dependencias de cómputo, evitando las penalizaciones asociadas a la sincronización explícita y al sobrecosto de lanzamiento de kernels.