Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos.

Abstract

La notoria evolución de disciplinas como la ciencia de datos y el aprendizaje automático en los últimos años ha despertado un gran interés en operaciones del álgebra lineal dispersa tales como la multiplicación de matrices dispersas generales (SpGeMM). Esta operación anteriormente no gozaban de la misma atención dedicada como por ejemplo a la multiplicación de matriz dispersavector (SpMV) por parte de la comunidad científica. Consecuentemente, hoy día son comunes los esfuerzos de investigación volcados al desarrollo eficiente de ambas rutinas en plataformas paralelas. La mayoría de las operaciones sobre matrices dispersas son caracterizadas por implicar una cantidad baja de cómputo en relación a los accesos a memoria, algo que dificulta explotar la gran capacidad de cómputo que tienen dispositivos masivamente paralelos como las GPUs. Estos accesos, además, son altamente irregulares, dado que dependen de la distribución de los valores no nulos y, en el caso de SpGeMM, dependen también de como se vinculen los elementos no nulos de las dos matrices de entrada. Para mitigar esta irregularidad, una posibilidad es el uso de formatos a bloques para el almacenamiento de las matrices dispersas. En este trabajo se explora el uso de formatos de almacenamiento a bloques para las operaciones SpGeMM y SpMV. En este sentido, se profundiza en el formato bmSparse, que permite potenciales ahorros importantes tanto en espacio de almacenamiento como en accesos a memoria. En primera instancia, se busca atacar distintos cuellos de botella de una implementación base de la operación SpGeMM a través de distintas propuestas, que incluyen cambios en la representación del formato, mejoras en el paso de ordenamiento y el uso de Tensor Cores para la multiplicación de bloques.

Por otro lado, se implementa una rutina para la operación SpMV con el fin de explorar el potencial del formato más allá del producto de matrices dispersas. Los resultados obtenidos al evaluar estas dos implementaciones en matrices de distintos tamaños de la Suite Sparse Matrix Collection muestran importantes mejoras del tiempo de ejecución para varias matrices. En el caso de SpGeMM, la implementación propuesta obtiene resultados considerablemente mejores que las variantes para CSR presentes en bibliotecas conocidas como cuSPARSE de NVIDIA y MKL de Intel, y es competitiva con la implementación para BCSR de esta última. En el caso de SpMV, se alcanzan speedups de más de 4× en algunas matrices en comparación con la implementación de cuSPARSE para CSR, lo que sugiere que el formato es una alternativa interesante para distintas aplicaciones que involucran el uso de matrices dispersas.