Departamento de Computación

La diagonalización de matrices es uno de los problemas de Algebra Lineal que mayor aplicación tiene en áreas como la Física y Química Cuántica. Especialmente cuando se trata de diagonalizar matrices de alta dimensionalidad. Lo que generalmente se busca en este tipo de problemas es encontrar los valores y vectores propios de una matriz, ya que presentan información sobre cantidades observables que tienen interpretaciones físicas como energía, velocidad o momento, por mencionar algunas. Existen 2 métodos principales para la diagonalización, usando un método iterativo o usando un método directo. En esta tesis nos enfocaremos en el método iterativo. Este método tiene una alta complejidad respecto al uso de CPU y de memoria, debido a que se debe de calcular la factorización QR. La factorización QR representa un procedimiento pesado para una computadora, además se debe realizar muchas veces. Para resolver este problema se han generado diversos algoritmos paralelos. Estos algoritmos paralelos se ejecutan correctamente con tamaños de matrices que se adapten a las capacidades de la máquina donde se ejecute. Esto ha originado que en matrices de alta dimensionalidad, se presenten problemas como el espacio en memoria, la correctitud del algoritmo y los tiempos de ejecución aumentan. Para matrices de alta dimensionalidad es necesario adaptar estos algoritmos para funcionar en clusters de computadoras. También se pueden ocupar un conjunto de bibliotecas especializadas en explotar los recursos de los clusters como son MKL, ACML o IMSL. En los últimos años el uso de las tarjetas gráficas ha crecido, esto debido a que en comparación con el CPU, estas ofrecen mayor computación por segundo (Flops) a un costo energético menor (Flops/watt). Por lo que las GPUs se han empezado a integrar como una infraestructura común en clusters. Sin embargo, no existen muchos algoritmos que utilicen las ventajas de los clusters de GPUs. En esta tesis se propone implementar un algoritmo paralelo heterogéneo de diagonalización utilizando el método de Givens para la factorización QR. Nuestro algoritmo se implementó utilizando una arquitectura multi-CPU/GPU con el fin de obtener las ventajas energéticas que ofrecen los GPUs. Nuestra implementación utiliza todas las ventajas de un cluster con muchas tarjetas de GPUs y maneja la memoria con el fin de evitar cuellos de botella.

Abstract

It can be said, in the case of high-dimensional matrices, that the diagonalization is one of the most useful problems within Linear Algebra due to its applicability into fields as Physics and Chemistry. Here, the main task is to find the eigenvalues and eigenvectors of a matrix, since they represent measures, which can lead to quantities that have physical interpretations, for instance, energy, speed, time, etcetera. There exist two different methods to compute the diagonalization of a matrix: (i) the direct method and (ii) the iterative method. In this work we mainly focus in the iterative method. Such a method has a high complexity regarding the use of CPU and memory, since one has to compute the QR-factorization. The QR-factorization represents a heavy procedure for the computer and it has to be done several times. In order to overcome this problem, the parallel algorithms have been developed. Parallel algorithms works properly to solve matrices whose size is adapted to the computer features where they are executed. Nevertheless, when one wants to manage high dimensional matrices, several problems arise, i.e. the lack of space to store the data, the correctness of the algorithm and the execution time increases. As a possible solution to treat a high dimensional matrix is to adapt these algorithms in order to work on clusters. Another way to exploit the resources of a cluster is to use libraries such as MKL, ACML or ISML. Nowadays, the use of graphical cards has grown. This growth is due to the fact that GPUs can offer higher computation power per second (Flops) with a lower energetic cost (Flops/watts) than CPUs. The GPUs now have been integrated into clusters. However, still missing algorithms that take advantage of these GPUs. In this work, we propose a heterogeneous parallel diagonalization algorithm using Givens method to perform the QR factorization. Our algorithm is implemented on a multi-CPU/GPU architecture in order to obtain the energetic advantages offered by GPUs. The proposed method takes advantage of having many GPU card and manages the memory in order to avoid bottlenecks.