Leveraging index compression techniques to optimize the use of co-processors

Abstract

The significant presence that many-core devices like GPUs have these days, and their enormous computational power, motivates the study of sparse matrix operations in this hardware. The essential sparse kernels in scientific computing, such as the sparse matrix-vector multiplication (SpMV), usually have many different high-performance GPU implementations. Sparse matrix problems typically imply memory-bound operations, and this characteristic is particularly limiting in massively parallel processors. This work revisits the main ideas about reducing the volume of data required by sparse storage formats and advances in understanding some compression techniques. In particular, we study the use of index compression combined with sparse matrix reordering techniques in CSR and explore other approaches using a blocked format. The systematic experimental evaluation on a large set of real-world matrices confirms that this approach achieves meaningful data storage reductions. Additionally, we find promising results of the impact of the storage reduction on the execution time when using accelerators to perform the mathematical kernels.

La importante presencia que tienen hoy en día los dispositivos multinúcleos como las GPU, y su enorme poder computacional, motivan el estudio de las operaciones matriciales dispersas en dicho hardware. Las rutinas matemáticas esenciales para la computación científica en álgebra dispersa, como la multiplicación matriz dispera vector (SpMV), suelen tener muchas implementaciones de alto rendimiento diferentes en GPUs. Los problemas de matrices dispersas normalmente ünplican operaciones acotadas por la memoria, y esta característica es particularmente limitante en procesadores masivamente paralelos. Este trabajo revisa las ideas principales sobre cómo reducir el volumen de datos requerido por los formatos de almacenamiento dispersos y avanza en la comprensión de algunas técnicas de compresión. En particular, estudiamos el uso de compresión de índices combinada con técnicas de reordenamiento de matrices dispersas en CSR y exploramos otros enfoques utilizando un formato a bloques. La evaluación experimental sistemática en un gran conjunto de matrices del mundo real confirma que este enfoque logra reducciones significativas en el almacenamiento de datos. Además, encontramos resultados prometedores del impacto de la reducción del almacenamiento en el tiempo de ejecución cuando se utilizan aceleradores para realizar las operaciones matemáticas.