Parallélisation des algorithmes de multiplication rapide de matrices sur machines à mémoire distribuée
Institution:
Paris 8Disciplines:
Directors:
Abstract EN:
Fast matrix multiplication (FMM) algorithms to multiply two n x n matrices reduce the asymptotic operation count from O (n³) of the traditional method to O (n². Xx), thus the parallelization of FMM algorithms always gives remarkable results in comparison to the parallel matrix multiplication algorithms based on traditional method. Within this parallelization, the application of FMM algorithms at the inter-processor level requires us to solve more difficult problems in designing but it forms the most effective algorithms. To use FMM algorithms at the inter-processor level, the most significant point is to determine the submatrices after having recursively executed r times the FMM formulas and then to find the result matrix from the products of these sub matrices. With a definite value of r, we can manually solve this problem like in the previous works with r=1,2, but the solution for the general case has not been found. In this PhD work, by combining our general solution for this problem with a good storage map of submatrices to processor, and with the parallel matrix multiplication algorithms based on traditional method (1D-systolic, 2D-systolic, Fox (BMR), Cannon, PUMMA, BiMMeR, SUMMA, DIMMA. . . ) we have a general scalable parallelization of FMM algorithms on distributed memory computers. Complexity analyses show that our algorithms should be faster than the parallel algorithms based on traditional method when the matrix size is large and our work is relevant to exploit better algorithms when the recursion level is large enough. Experimental results on Fujitsu Siemens Computers/hpcLine confirm the theoretical result by showing that our algorithms perform better than Cannon's Algorithm from 1. 2 to 2. 4 times for matrices of size 8196 x 8196.
Abstract FR:
Les algorithmes de la multiplication rapide de matrices (FMM) pour multiplier deux matrices n x n réduisent le nombre asymptotique d'opérations de O (n³) de la méthode traditionnelle à O (n²,xx), donc la parallélisation des algorithmes de FMM donne des résultats remarquables par rapport aux algorithmes parallèles de multiplication matricielle basés sur la méthode traditionnelle. Dans cette parallélisation, l'application des algorithmes de FMM au niveau inter-processeur nécessite une conception plus fine de celle-ci mais conduit à des algorithmes plus efficaces. Pour utiliser des algorithmes de FMM au niveau inter-processeur, le point le plus important est de déterminer les sous-matrices après avoir appliqué r fois les formules de FMM et puis de trouver la matrice résultat à partir des produits de ces sous-matrices. Avec une valeur définie de r, nous pouvons manuellement résoudre ce problème comme dans les travaux précédents avec r=1,2, mais la solution pour le cas général n'est pas encore trouvée. Dans cette thèse, en combinant notre solution générale pour ce problème avec un bon modèle de stockage des sous-matrices, et avec les algorithmes parallèles de multiplication matricielle basés sur la méthode traditionnelle (1D-systolic, 2D-systolic, Fox (BMR), Cannon, PUMMA, BiMMeR, SUMMA, DIMMA. . . ) nous avons une voie générale de parallélisation adaptative des algorithmes de FMM sur machines à mémoire distribuée. L'analyse de complexité prouve que nos algorithmes sont plus rapides que les algorithmes parallèles basés sur la méthode traditionnelle quand la taille de matrice est grande et notre travail est pertinent pour exploiter de meilleurs algorithmes quand le niveau de récursivité est assez grand. Les résultats expérimentaux sur Fujitsu Siemens Computers/hpcLine confirment le résultat théorique en montrant que nos algorithmes sont plus rapides que l'algorithme de Cannon de 1,2 à 2,4 fois pour les matrices de taille 8196 x 8196.