Revisiting Matrix Product on Master-Worker Platforms
Résumé
This paper is aimed at designing efficient parallel matrix-product algorithms for heterogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm and ScaLAPACK outer product algorithm), there are three key hypotheses that render our work original and innovative: - Centralized data. We assume that all matrix files originate from, and must be returned to, the master. The master distributes both data and computations to the workers (while in ScaLAPACK, input and output matrices are initially distributed among participating resources). Typically, our approach is useful in the context of speeding up MATLAB or SCILAB clients running on a server (which acts as the master and initial repository of files). - Heterogeneous star-shaped platforms. We target fully heterogeneous platforms, where computational resources have different computing powers. Also, the workers are connected to the master by links of different capacities. This framework is realistic when deploying the application from the server, which is responsible for enrolling authorized resources. - Limited memory. Because we investigate the parallelization of large problems, we cannot assume that full matrix panels can be stored in the worker memories and re-used for subsequent updates (as in ScaLAPACK). The amount of memory available in each worker is expressed as a given number m_i of buffers, where a buffer can store a square block of matrix elements. The size q of these square blocks is chosen so as to harness the power of Level 3 BLAS routines: q=80 or 100 on most platforms. We have devised efficient algorithms for resource selection (deciding which workers to enroll) and communication ordering (both for input and result messages), and we report a set of numerical experiments on various platforms at École Normale Supérieure de Lyon and the University of Tennessee. However, we point out that in this first version of the report, experiments are limited to homogeneous platforms.
Ce papier a pour objectif la définition d'algorithmes efficaces pour le produit de matrices en parallèle sur plate-formes maître-esclaves hétérogènes. Bien que le produit de matrices soit bien compris pour des grilles bi-dimensionnelles de processeurs homogènes (cf. l'algorithme de Cannon et le produit externe de ScaLAPACK), trois hypothèses rendent notre travail original :- Données centralisées. Nous supposons que toutes les matrices résident originellement sur le maître, et doivent y être renvoyées. Le maître distribue données et calculs aux esclaves (alors que dans ScaLAPACK, les matrices initiales et résultats sont initialement distribuées aux processeurs participant). Typiquement, notre approche est justifiée dans le contexte de l'accélération de clients MATLAB ou SCILAB s'exécutant sur un serveur (qui se comporte comme le maître et détient initialement les données).- Plates-formes hétérogènes en étoile. Nous nous intéressons à des plateformes complètement hétérogènes dont les ressources de calculs ont des puissances de calcul différentes et dont les esclaves sont reliés au maître par des liens de capacités différentes. Ce cadre de travail est réaliste quand l'application est déployée à partir du serveur qui est responsable de l'enrôlement des ressources nécessaires.- Mémoire bornée. Comme nous nous intéressons à la parallélisation de gros problèmes, nous ne pouvons pas supposer que toutes les sous-matrices peuvent être stockées dans la mémoire de chaque esclave pour être éventuellement très utilisée ultérieurement (comme c'est le cas dans ScaLAPACK). La quantité de mémoire disponible sur un esclave donné est exprimé comme un nombre mi de tampons, où un tampon peut exactement contenir un bloc carré d'éléments de matrice. La taille q de ces blocs carrés est choisie afin de pouvoir tirer parti de la puissance des routines BLAS de niveau 3 : q = 80 ou 100 sur la plupart des plates-formes.Nous avons défini des algorithmes efficaces pour la sélection de ressources (pour décider quel(s) esclave(s) utiliser) et l'ordonnancement des communications (envoi de données et récupérations de résultats), et nous rapportons un ensemble d'expériences sur des plates-formes à l’École normale supérieure de Lyon et à l'Université du Tennessee. Nous faisons cependant remarquer que dans la première version de ce rapport les expériences ne concernent que des plateformes homogènes.
Fichier principal
RR-6053.pdf (391.84 Ko)
Télécharger le fichier
LIP-RR2006-39.pdf (405.42 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...