El producto matricial distribuido en entornos computacionales de alto rendimiento

Abstract

[ES] La multiplicación de matrices es una operación fundamental para la resolución de innumerables problemas matemáticos que tienen a esta operación en su base. El coste de esta operación, incluso el algoritmo utilizado, es diferente según la forma particular que tengan las matrices (densas, diagonales, dispersas, ...). En el caso de matrices densas sin estructura conocida a priori, es decir, de matrices generales, esta operación tiene un coste computacional elevado O(n^3). Es por este motivo por el que existen desde hace tiempo algoritmos paralelos diversos según el entorno de computación particular en el que se ejecutan. Entre estos algoritmos tiene especial relevancia el algoritmo SUMMA, diseñado para entornos de memoria distribuida. En este documento, en primer lugar, se lleva a cabo una implementación del algoritmo SUMMA para clusters de ordenadores utilizando la conocida librería MPI, teniendo en cuenta y aprovechando la capacidad multicore de los nodos. En segundo lugar, y aprovechando la experiencia anterior, se implementa el mismo algoritmo para un entorno de computación de alto rendimiento, objetivo real de este trabajo, formado por 4 GPUs interconectadas mediante una red de alta capacidad (NVLink) y utilizando, para ello, la librería NCCL de NVIDIA. Finalmente, el trabajo construye una envoltura C++ que permite una utilización accesible de la librería desarrollada. Además, se ofrece una interfaz Matlab que proporciona la habilidad de utilizar el software desarrollado eficientemente a usuarios no programadores. Se demuestra la eficacia de la solución propuesta mediante un ejemplo real: el cálculo de funciones de matrices basado en la evaluación de polinomios matriciales.

[EN] Matrix multiplication is a fundamental operation for solving uncountable mathematical problems that have this operation at their base. The cost of this operation, including the algorithm used, is different depending on the particular structure of the matrices (dense, diagonal, sparse, ...). In the case of dense matrices, with no known structure, that is, of general matrices, this operation has a high computational cost (O(n3)). It is for this reason that parallel algorithms have existed for a long time, being different according to the particular computing environment in which they are executed. Among these algorithms it is specially relevant the SUMMA algorithm, designed for distributed memory environments. In this document, firstly, we build an implementation of the SUMMA algorithm for computer clusters using the MPI library, taking into account and exploiting the multicore capacity of the nodes. Secondly, using the previous experience, we implement a version of the same algorithm for another high-performance computing environment, which is the real objective of this work, featuring 4 GPUs interconnected by a high-speednetwork (NVLink) and using, for this, the NVIDIA NCCL library. Finally, the work builds a C++ wrapper that allows a handy use of the developed library. In addition, it offers a Matlab interface that provides the ability to use the developed software ef¿ciently for non-programmer users. We demonstrate the effectiveness of the proposed solution on a real example: the computation of matrix functions based on the evaluation of matrix polynomials.

[CA] La multiplicació de matrius és una operació fonamental per a la resolució d’innombrables problemes matemàtics que tenen a aquesta operació en la seua base. El cost d’aquesta operació, fins i tot l’algorisme utilitzat, és diferent segons la forma particular que tinguen les matrius (denses, diagonals, disperses, . . . ). En el cas de matrius denses sense estructura coneguda a priori, és a dir, de matrius generals, aquesta operació té un cost computacional elevat (O(n 3 )). És per aquest motiu pel qual existeixen des de fa temps algorismes paral·lels diversos segons l’entorn de computació particular en el qual s’executen. Entre aquests algorismes té especial rellevància l’algorisme SUMMA, dissenyat per a entorns de memòria distribuïda. En aquest document, en primer lloc, es porta a terme una implementació de l’algorisme SUMMA per a clústers d’ordinadors utilitzant la coneguda llibreria MPI, tenint en compte i aprofitant la capacitat multicore dels nodes. En segon lloc, i aprofitant l’experiència anterior, s’implementa el mateix algorisme per a un entorn de computació d’alt rendiment, objectiu real del treball, format per 4 GPUs interconnectades mitjançant una xarxa d’alta capacitat (NVLink) i utilitzant, per a això, la llibreria NCCL de NVIDIA. Finalment, el treball construeix un embolcall C++ que permet una utilització accessible de la llibreria desenvolupada. A més, s’ofereix una interfície Matlab que proporciona l’habilitat d’utilitzar el programari desenvolupat eficientment a usuaris no programadors. Es demostra l’eficàcia de la solució proposada mitjançant un exemple real: el càlcul de funcions de matrius basat en l’avaluació de polinomis matricials.