Aplicación de métodos avanzados de sincronización en GPUs para la resolución de sistemas triangulares dispersos

Abstract

La resolución de sistemas de ecuaciones dispersas lineales triangulares (SpTrSv) es, en muchos casos, el cuello de botella de distintos métodos numéricos. En GPUs mayoritariamente se utilizan tres enfoques. Las estrategias Level-set utilizan un costoso preprocesamiento para determinar dependencias entre filas de la matriz y generar un cronograma estático de ejecución en paralelo para la etapa de resolución. Por otro lado, los métodos synchronization-free van generando el cronograma de manera dinámica a medida que las dependencias se van completando y evitando la etapa de análisis. Finalmente, se puede utilizar un enfoque híbrido que utilice la etapa de análisis para acelerar una etapa de resolución que utilice una estrategia synchronization-free. En este trabajo presentamos una rutina eficiente en GPU para la etapa de análisis y luego aplicamos algunas de estas ideas para la etapa de resolución. La comparación con otras rutinas disponibles de manera pública muestran una mejora en tiempo de ejecución para la resolución de sistemas triangulares generados por muchas matrices pertenecientes a la biblioteca SuiteSparse.