Paralelizacion semi-automatica de aplicaciones con matrices dispersas

Abstract

Con este trabajo se pretende dar un paso más hacia la paralelización automática de aplicaciones irregulares, completando los resultados obtenidos en trabajos anteriores. Se han analizado diferentes aspectos que caracterizan a las aplicaciones con matrices dispersas, y que pueden influir de una forma notable a la hora de obtener un código paralelo eficiente: La extensión de las distribuciones de datos tradicionales para adaptarlas a estructuras de datos complejas, la generación de esquemas de enumeración local eficientes útiles para los bucles que contengan referencias dispersas, la caracterización de la modificación en tiempo de ejecución de una distribución de datos pseudo-regular para estructuras de datos comprimidas, y el desarrollo de un esquema de compilación basado en las relaciones semánticas entre los diferentes vectores que componen un estructura de datos de alto nivel y que sea aplicable a los algoritmos que consulten o modifiquen la información. Como principal aportación se especifica la descomposición de las iteraciones de los bucles entre los diferentes procesadores en función de la información dispersa que cada uno de ellos almacena, reemplazando la típica regla de computación del propietario. Por otro lado, también se requiere un análisis semántico de cada uno de los bucles con el fin de paralelizarlos en función de la información dispersa a la que se acceda. Al mismo tiempo, se han propuesto diversas estrategias para el cálculo de coordenadas y el almacenamiento temporal de la información involucrada en una comunicación dispersa, las cuales son útiles por su sencillez, ocupación de memoria y clasificación de la información en orden a evitar costosas etapas de reconstrucción de la estructura de datos local en cada procesador.