Producto de matrices Sparse en un entorno MPI

Abstract

Proyecto de Fin de Grado de Ingeniería Informática en la especialidad de Ingeniería de Computadores. El objetivo principal de este proyecto es: Partiendo del artículo Parallel Sparse Matrix-Matrix Multiplication: A Scalable Solution 1-D Algorithm [1], proponer un algoritmo eficiente para la multiplicación de matrices sparse de grandes dimensiones, del orden de 106*106 y una probabilidad de que un elemento sea no cero de 75E-06. Nos hemos autoimpuesto la restricción de que un nodo del clúster realice como máximo el producto de matrices del orden de 105 x 105 por motivos de la memoria necesaria. Esto implica que, si queremos resolver el caso de matrices 106 x 106, se deba complementar con una solución 2D, producto de submatrices. La memoria ocupada en este caso por las estructuras necesarias en la solución propuesta es del orden de 500MB. El algoritmo usa la descomposición de matrices en bloques basada en el número de procesadores. Las matrices con las que se trabajan no tienen estructura, repartiéndose los elementos no nulos de forma aleatoria. Se ha mejorado el algoritmo inicial propuesto y se ha estudiado la posibilidad y las consecuencias de aplicar otros algoritmos, como el algoritmo de Cannon y se han propuesto mejoras y soluciones a los problemas detectados. Para lograr el objetivo se ha estudiado la escalabilidad y el paralelismo de los algoritmos propuestos en dos clústeres de la facultad, uno de 1Gb con 64 nodos de 4 cores cada nodo y otro de 10Gb con 16 nodos de 4 cores cada uno. Como resumen de los resultados obtenidos se puede destacar lo siguiente. Para los clústeres con los que hemos trabajado la solución óptima es de 4 procesos en un nodo, cada proceso en un core del procesador del nodo. Para el clúster de 1Gb la opción -map by node es la mejor. Para el clúster de 10Gb se puede realizar el reparto de los procesos a procesadores por nodo o por core, ya que no hay diferencias significativas. Los tiempos totales del producto matricial de 106 x 106 son comparables a los del artículo de referencia. La comparación solo puede ser grosera debido a las diferencias entre los recursos computacionales que ellos y nosotros usamos, pero los tiempos avalan nuestra solución. Pensamos que la solución propuesta puede adaptarse fácilmente a clústeres que se diferencien en el ancho de banda de la red de la comunicación, procesadores con distinto número de cores y diferente jerarquía de memoria. Queda como posible estudio el análisis teórico de la necesidad de memoria asociada a una matriz en función de su dimensión y la probabilidad de que un elemento de la matriz sea no cero. Por último, es importante analizar las entradas/salidas a disco para almacenar matrices de semejante tamaño. El hecho de paralelizar las entradas/salidas parece más que razonable.