Departamento de Computación

La descomposición en valores singulares en matrices densas es usado en técnicas de aprendizaje de máquina, en sistemas de recomendación, entre otras aplicaciones. El amplio número de usuarios de esta descomposición se observa en la implementación en la biblioteca LAPACK y SCALAPACK que son ampliamente usadas. Sin embargo, el cálculo de esta descomposición tiene un alto costo computacional que ralentiza su ejecución en matrices de gran tamaño y densas. Además, las implementaciones actuales no están diseñadas para los nuevos clusters que cuentan con nodos con multiples CPUs y GPUs que no solo aceleran cálculos matemáticos sino que tienen una mejor eficiencia que un cluster tradicional, es decir, tienen un mayor número de operaciones flotantes por Watt usado que su contra parte tradicional. Por esta razón se realizó una implementación paralela híbrida heterogénea del método de Jacobi por un lado usando las herramientas (marcos de trabajo, API, especificaciones) CUDA, OpenMP y MPI; para aprovechar los recursos de estos nuevos tipos de clusters. Además se realizaron otras implementaciones del mismo método numérico pero para diferentes modelos de programación: paralela, paralela heterogénea, paralela híbrida. Se encontró que nuestra implementación paralela para memoria compartida con OpenMP tuvo un menor tiempo de ejecución que la implementación de LAPACK. El resultado más importante de este texto fue que nuestra implementación paralela heterogénea es el menor en tiempo de ejecución comparado con LAPACK y nuestras otras implementaciones y fue el menor en error absoluto comparado con nuestras otras implementaciones. En general, se observó una aceleración de casi hasta 5 veces comparado con nuestra implementación paralela para memoria compartida.

Abstract

Singular value decomposition (SVD) in dense matrices is used in machine learning techniques, recommendation systems, among other applications. The widespread use of this decomposition is in the implementation in the LAPACK and SCALAPACK libraries, which are widely used. However, the computation of this decomposition has a high computational cost that slows down its execution in large and dense matrices. Furthermore, current implementations are not designed for new clusters that have nodes with multiple CPUs and GPUs, which not only accelerate mathematical calculations but also have better efficiency than a traditional cluster, meaning they have a higher number of floating point operations per Watt used than their traditional counterpart. For this reason, a parallel hybrid heterogeneous implementation of the Jacobi method was carried out using tools (frameworks, APIs, specifications) such as CUDA, OpenMP, and MPI to take advantage of the resources of these new types of clusters. Additionally, other implementations of the same numerical method were performed for different programming models: parallel, heterogeneous parallel, hybrid parallel. It was found that our parallel implementation for shared memory using OpenMP had a shorter execution time than the LAPACK implementation. The most important result of this thesis was that our heterogeneous parallel implementation had the shortest execution time compared to LAPACK and our other parallel implementations and had the lowest absolute error compared to our other implementations. Overall, an acceleration of almost up to 5 times was observed compared to our parallel shared memory implementation.