# Peut-on exprimer un produit de matrices distribué haute performance avec un modèle Map-Reduce ?

Hugo Dodelin

► To cite this version:

Hugo Dodelin. Peut-on exprimer un produit de matrices distribué haute performance avec un modèle Map-Reduce?. Conférence francophone d'informatique en Parallélisme, Architecture et Système (COMPAS 2025), Jun 2025, Bordeaux, France. hal-05063477

HAL Id: hal-05063477

https://hal.science/hal-05063477v1

Submitted on 12 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Peut-on exprimer un produit de matrices distribué haute performance avec un modèle Map-Reduce ?

Hugo Dodelin *

INRIA - Équipe Concace,
Centre Inria de l'Université de Bordeaux - 200 avenue de la Vieille Tour
33405 Talence - France
hugo.dodelin@inria.fr

## Résumé

Le modèle de programmation fonctionnelle MapReduce a permis d'écrire de manière compacte, élégante et performante de nombreux algorithmes parallèles pour le traitement de données massives sur des architectures distribuées. En revanche, il n'est sans doute pas exagéré de penser que son utilisation effective pour la mise au point d'algorithmes de calcul haute performance (HPC) sur des supercalculateurs puisse être considérée comme ésotérique en 2025. Dans cette note, nous considérons un algorithme HPC étendard, à savoir le produit de matrices $C \leftarrow \alpha \cdot A \times B + \beta \cdot C$ (GEMM) et étudions si les schémas complexes de sa parallélisation posés dans la littérature peuvent être exprimés dans ce paradigme. Nous montrons qu'en enrichissant le modèle pour exprimer sur quels processus placer les données et effectuer les calculs, il est effectivement possible d'exprimer les schémas de parallélisation de la littérature du produit $C \leftarrow \alpha \cdot A \times B$. Nous montrons que cette expression ne permet cependant pas d'exprimer toute la localité d'accès aux données au sein d'un processus requise pour une performance optimale. Nous proposons finalement en enrichissant encore le modèle avec une troisième fonction combined_mapreduce (en sus de map et reduce), d'exprimer également cette localité et de supporter le cas plus général $C \leftarrow \alpha \cdot A \times B + \beta \cdot C$. Un prototype de ce modèle MapReduce HPC a été implémenté au-dessus du moteur d'exécution StarPU.

**Mots-clés** : MapReduce, HPC, Produit de matrices, GEMM, Mémoire distribuée

## 1. Introduction

Par souci de performance, les codes HPC mettent souvent beaucoup d'emphase sur les optimisations bas niveau. Mais l'écosystème du calcul haute peformance comportant des architectures de plus en plus complexes et hétérogènes et des algorithmes de plus en plus sophistiqués, les abstractions de haut niveau présentent un intérêt dans la mesure où elles peuvent permettre de mieux tirer parti des architectures modernes. Une telle abstraction pourrait par exemple éviter d'écrire plusieurs versions d'algorithmes sémantiquement peu différents pour gérer les diverses architectures, la distribution des données, des matrices aussi bien denses que creuses, des matrices hiérarchiques, etc.

À la genèse du modèle MapReduce se trouvait également l'observation que des préoccupations non sémantiques complexes freinaient systématiquement l'implémentation de traitements pour-

<footnote>*. Remerciements à Emmanuel Agullo et Olivier Coulaud pour leurs relectures et corrections</footnote>
tant simples conceptuellement [4]. Ainsi, nous nous demandons si une abstraction analogue
serait suffisamment expressive pour nous permettre de redécouvrir toutes les opérations d'al-
gèbre linéaire.

Le modèle MapReduce a déjà été considéré pour le calcul haute-performance [12, 13, 7, 9, 18]. De même, plusieurs travaux ont exprimé un produit de matrices via un modèle MapReduce [17, 16, 14, 11]. En revanche, peu ont interrogé ce modèle pour faire de la généreration de schémas de communication présents dans les algorithmes numériques de l'état de l'art une partie intégrante d'un modèle MapReduce. C'est l'objet de ce travail. Nous considérons ici le produit de matrices distribué, car, en plus d'être omniprésent au sein des algorithmes numériques, il requiert la mise en oeuvre de schémas de communication avancés.

## 2. Briques de base

### 2.1. Modèle de programmation à base de tâches

Un modèle de programmation à base de tâches considère qu'un programme est une série d'opé-
rations simples (les tâches) comportant des dépendances d'ordre d'exécution. On peut alors le
décrire comme le parcours d'un graphe orienté acyclique où l'on exécute un code séquentiel
pour chaque noeud et une communication pour chaque arête.

Ce modèle est supporté par de nombreux moteurs d'exécutions tels que OmpSS [6], StarPU [2] et OpenMP [3] (depuis sa version 4.0 et l'introduction de la clause "depend" pour contraindre l'exécution des tâches).

Il a été récemment montré qu'un produit de matrices distribué $C \leftarrow \alpha \cdot A \times B + \beta \cdot C$ (GEMM) peut être exprimé dans un modèle à base de tâches et atteindre les performances de l'état de l'art [1]. Un tel modèle permet une expression haut-niveau des schémas de parallélisation en exprimant simplement la distribution des données (*datamap*) et celle des calculs (*taskmap*). Les communications peuvent alors être inférées automatiquement à partir des *datamap* et *taskmap*. Les communications collectives sont également inférées dynamiquement [5].

### 2.2. Modèle de programmation Application-Réduction (MapReduce)

Le modèle MapReduce est une abstraction proposée par Google en 2004 [4] pour réaliser des
traitements parallèles en masse sur de gros volumes de données distribuées sur des clusters en
automatisant la parallélisation et la résilience.

Détaillons les 5 grandes étapes d'un programme MapReduce à travers le problème du compte de mots ou WordCount qui consiste à recenser le nombre d'apparitions de chaque mot présent dans un ensemble de documents (voir Figure 1) :

1. **Lecture (Read)** : On exprime notre entrée comme une collection de couples clé/valeur `(k_map, v_map)`. Typiquement, cette étape est une simple requête en base de données. Pour WordCount, on considère par exemple le nom et le contenu du document : `(Doc1.txt, "Bonjour Compas")`.

2. **Application (Map)** : On cherche à extraire les données utiles au problème qu'on veut résoudre. Pour ce faire, on applique à chaque couple une fonction `map : ⟨k_map, v_map⟩ → list(⟨k_reduce, v_reduce⟩)`. Pour WordCount, cette fonction va parcourir le document et pour chaque mot ajouter à la liste qu'elle renverra un couple de la forme `⟨"Bonjour", 1⟩`.

3. **Distribution (Shuffle)** : On rassemble les couples ayant des $k_{reduce}$ identiques sur un nombre arbitraire de noeuds de calcul identiques.
<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Exemple de l'exécution de WordCount sur un modèle MapReduce.</figcaption></figure>

4. **Réduction (Reduce)** : On peut maintenant résoudre notre problème à proprement parler. Soit une fonction reduce : `<k<reduce, list<i<reduce,i>> → list<j<reduce, v<out,j>>>)`, on l'applique à tous les éléments deux à deux jusqu'à n'avoir plus qu'une valeur associée à chaque clé. Pour WordCount, cette fonction va être une somme et transformer un objet de la forme `("Bonjour", [1, 1, 1, 1])` en `("Bonjour", 4)`.

5. **Écriture (Write)** : On reconstitue notre sortie à partir des couples clé/valeur obtenus en sortie de l'étape précédente et on les écrit en mémoire. Pour WordCount on écrira typiquement dans une base de données les comptes de mots qu'on a obtenus.

Les étapes 1, 3 et 5 ne dépendent pas de l'algorithme appliqué, ainsi, l'essence du paradigme MapReduce est l'expression d'algorithmes parallèles sous la forme d'un couple de fonctions (*map*, *reduce*).

Nous sommes surtout intéressés par MapReduce pour son potentiel en termes de séparation des préoccupations, et en particulier dans le cadre de l'algèbre linéaire, ce paradigme pourrait être une abstraction utile pour écrire des algorithmes à la fois simples, composites et efficaces. Nous avons choisi d'écrire un modèle d'exécution qui va, à partir d'une fonction *map* et *reduce*, s'appuyer sur un runtime à base de tâches pour superviser l'exécution des calculs.

## 2.3. Problème

Le problème WordCount présenté en exemple dans notre présentation du modèle MapReduce ne ressemble pas à GEMM. Toutefois, Karloff et al. [15] montrent que la classe des problèmes solubles de manière déterministe par une succession de MapReduce, notée *DMRC*, est un sur-
ensemble de celle à laquelle appartiennent les problèmes fortement parallèles notée $\mathcal{NC}$ dont
GEMM fait partie. L'expression d'un produit de matrices avec MapReduce est donc possible.

En plus d'être capable d'exprimer avec MapReduce un produit de matrices distribué, nous
voulons être capables d'exprimer les différents schémas de communication de la littérature,
leur impact sur les performances étant conséquent. Par exemple, dans le cas d'une matrice A
grande par rapport à B et C on veut déplacer les blocs de B vers A (on parle de produit A-
stationnaire). Cela implique un contrôle sur la distribution des données et des tâches absent du
modèle MapReduce présenté en section 2.2 qui est agnostique de la localité des données. La
première étape de notre contribution a donc été d'armer MapReduce d'un moyen d'exprimer
la distribution des données et des tâches.

### 3. Expression d'un produit de matrices distribué dans un modèle MapReduce

Dans cette section, nous considérons le produit de matrice $C \leftarrow A \times B$. La Figure 2 illustre
les schémas de communication pour un produit A-stationnaire et la Figure 3 leur transcrip-
tion dans notre Modèle MapReduce étendu. En considérant les matrices découpées en blocs,
on a $C_{i,j} \leftarrow \sum_k A_{i,k} \times B_{k,j}$ par définition du produit matriciel. Comme [1], nous faisons l'hy-
pothèse que les blocs de matrices A et B sont distribuées sur les processus selon des *datamap*
(contrairement aux expressions MapReduce de produits de matrice de l'état de l'art qui sont
agnostiques de la distribution des données). Il s'agit des données d'entrée (colonne de gauche
de la Figure 3) de notre MapReduce.

L'étape *map* (du MapReduce) correspond aux calculs des produits intermédiaires $A_{i,k} \times B_{k,j}$ à partir des données $A_{i,k}$ et $B_{k,j}$ et peut formellement s'écrire : $map : \langle (i, j, k), (A_{i,k}, B_{k,j}) \rangle \rightarrow \langle (i, j), A_{i,k} \times B_{k,j} \rangle$. Cette étape conduit à la génération de données intermédiaires calculées sur le processus selon la *taskmap* (colonne centrale de la Figure 3). De même que les *datamap*, la *taskmap* est fournie par l'utilisateur qui peut ainsi décider précisément du schéma de communication qui sera inféré, ces communications correspondent à une stratégie de distribution – dont la définition était transparente à l'utilisateur dans le modèle original – utilisée lors de l'étape *shuffle* du MapReduce. Par exemple, en indiquant que la tâche $A_{1,1} \times B_{1,1}$ doit être calculée sur le processus P1 (là où était déjà $A_{1,1}$), la donnée $B_{1,1}$ y est transférée (selon le même protocole que [1]). Cet exemple correspond à un schéma A-stationnaire : on ne déplace pas les données de A pour les calculs intermédiaires (ce schéma permet de minimiser le volume de communication lorsque A est la plus grosse des matrices).

L'étape *reduce* (du MapReduce) correspond à sommer ces produits intermédiaires et peut s'écrire formellement reduce : $\langle (i, j), \text{list}_k(C_{i,j,k}) \rangle \rightarrow \langle (i, j), \sum_k C_{i,j,k} \rangle$. La *datamap* de C permet de décider où les données intermédiaires doivent être envoyées pour réaliser ces sommes (colonne de droite de la Figure 3).

## 4. Limitations

### 4.1. Localité

Le modèle proposé nous permet ainsi d'exprimer les schémas de communication avancés de
la littérature sur le produit de matrice distribué. Toutefois, au sein d'un processus, il ne permet
pas une localité temporelle optimale. Par exemple, en considérant le produit de matrice de la
Figure 4, on peut constater que pour une exécution sur un processus unique, notre modèle
insérerait deux tâches via *map* ($C_{1,1,1} \leftarrow A_{1,1} \times B_{1,1}$ et $C_{1,1,2} \leftarrow A_{1,2} \times B_{2,1}$) puis une tâche via
<figure><img src="image_3.png" /><figcaption>FIGURE 2 – Produit A-stationnaire de matrices C ← A · B distribuées avec datamap.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>FIGURE 3 – Exécution avec taskmap A-stationnaire du produit de matrices de la figure 2 dans notre modèle MapReduce étendu.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>FIGURE 4 – Exemple exécuté sur un seul processus (P0).</figcaption></figure>

*reduce* (C ← C<sub>1,1,1</sub> + C<sub>1,1,2</sub>). Or il est possible d'effectuer le même calcul avec seulement deux GEMM (C ← A<sub>1,1</sub> × B<sub>1,1</sub> suivi de C ← C + A<sub>1,2</sub> × B<sub>2,1</sub>).

**4.2. Effets de bord**

De la même manière que la philosophie des langages fonctionnels implique l'utilisation de fonctions sans effets de bord, ce modèle reposant sur les fonctions d'ordre supérieur *map* et *reduce* se retrouve assez naturellement incapable d'exécuter sans produire de valeurs intermédiaires une instruction de type C ← α · A × B + β · C.

# 5. Extension du modèle MapReduce

La seconde étape de notre contribution a été de proposer une extension supplémentaire au modèle MapReduce pour répondre à ces limitations.

**5.1. Localité**

Tout d'abord, nous introduisons une fonction *combined_mapreduce* ayant pour objet d'effectuer la composée de *map* et *reduce*. Sa définition est pour GEMM la suivante : *combined_mapreduce* : ⟨⟨i, j, k⟩, (A<sub>i,k</sub>, B<sub>k,j</sub>)⟩ → ⟨⟨i, j⟩, α · A<sub>i,k</sub> × B<sub>k,j</sub> + C<sub>i,j,k</sub>⟩. C<sub>i,j,k</sub> est le bloc temporaire initialisé à 0 qui reçoit les contributions locales. Il est ainsi possible d'exécuter le produit de matrice de la Figure 4 avec deux GEMM comme envisagé en section 4.1.

**5.2. Effets de bord**

On souhaite maintenant pouvoir généraliser à C ← α · A × B + β · C. Le fait qu'on accumulerait plusieurs multiplications par β en l'incluant dans la définition de *reduce* n'est pas le principal problème car un mécanisme pour n'appliquer la multiplication qu'une seule fois (pour k = 1 par exemple) pourrait fonctionner. En revanche, ce facteur nous ferait perdre — lorsqu'il est différent de 1 — la propriété d'associativité qui définit une réduction et permet de commuter les tâches insérées.

Nous avons donc choisi d'introduire d'une fonction *prepare* de pré-traitement pour être à même d'effectuer des calculs nécessitant d'appliquer au préalable des effets de bord sur chaque bloc de notre matrice de sortie. Pour GEMM elle est définie ainsi : *prepare* : ⟨⟨i, j⟩, C<sub>i,j</sub>⟩ → ⟨⟨i, j⟩, β · C<sub>i,j</sub>⟩. On remarque qu'utiliser *map* est équivalent à utiliser *combined_mapreduce* en remplaçant C<sub>i,j,k</sub> par C<sub>i,j</sub> quand celui-ci est sur la même localité. Le modèle final peut donc s'affranchir de la définition de *map*.
## 6. Résultats préliminaires et travaux futurs

Nous avons implémenté un prototype d'une version C++ MapReduce au-dessus du moteur d'exécution StarPU [2], ainsi qu'un produit de matrices pour le valider. À l'heure actuelle, le code est fonctionnel. Nous l'avons testé pour jusqu'à 8 noeuds de calcul. Les performances sont prometteuses bien qu'encore en-deçà des codes de l'état de l'art.

Au-delà de la consolidation de l'étude de performance, qui est l'étape suivante de ce travail, nous envisageons de paralléliser des produits de matrices accélérés (type FMM [8] et H-matrices [10]) ainsi que de considérer l'écriture de factorisation de matrices (telle que la factorisation LU) comme une succession de MapReduce.

La séparation des préoccupations restant l'une des motivations principales de ce travail, nous prévoyons également de découpler notre modèle de StarPU pour pouvoir l'interfacer avec d'autres runtimes comme OpenMP ou OmpSS.

## Bibliographie

1. Agullo (E.), Buttari (A.), Guermouche (A.), Herrmann (J.) et Jego (A.). – Task-based parallel programming for scalable matrix product algorithms. *ACM Transactions on Mathematical Software*, vol. 49, n2, 2023, pp. 1–23.

2. Augonnet (C.), Thibault (S.), Namyst (R.) et Wacrenier (P.-A.). – StarPU : a unified platform for task scheduling on heterogeneous multicore architectures. – In *Euro-Par 2009 Parallel Processing : 15th International Euro-Par Conference, Delft, the Netherlands, August 25-28, 2009. Proceedings* 15, pp. 863–874. Springer, 2009.

3. Dagum (L.) et Menon (R.). – OpenMP : an industry standard API for shared-memory programming. *IEEE computational science and engineering*, vol. 5, n1, 1998, pp. 46–55.

4. Dean (J.), Ghemawat (S.) et al. – MapReduce : simplified data processing on large clusters. – In *6th Symposium on Operating System Design and Implementation*. USA, 2004.

5. Denis (A.), Jeannot (E.), Swartvagher (P.) et Thibault (S.). – Using dynamic broadcasts to improve task-based runtime performances. – In *Euro-Par 2020 : Parallel Processing : 26th International Conference on Parallel and Distributed Computing, Warsaw, Poland, August 24–28, 2020, Proceedings* 26, pp. 443–457. Springer, 2020.

6. Duran (A.), Ayguadé (E.), Badia (R. M.), Labarta (J.), Martinell (L.), Martorell (X.) et Planas (J.). – OmpSS : a proposal for programming heterogeneous multi-core architectures. *Parallel processing letters*, vol. 21, n02, 2011, pp. 173–193.

7. Fadika (Z.), Dede (E.), Govindaraju (M.) et Ramakrishnan (L.). – Mariane : MapReduce implementation adapted for HPC environments. – In *2011 IEEE/ACM 12th International Conference on Grid Computing*, pp. 82–89. IEEE, 2011.

8. Greengard (L.) et Rokhlin (V.). – A fast algorithm for particle simulations. *Journal of computational physics*, vol. 73, n2, 1987, pp. 325–348.

9. Guo (Y.), Bland (W.), Balaji (P.) et Zhou (X.). – Fault tolerant MapReduce-MPI for HPC clusters. – In *proceedings of the international conference for high performance computing, networking, storage and analysis*, pp. 1–12, 2015.

10. Hackbusch (W.). – A sparse matrix arithmetic based on H-matrices. Part I : Introduction to H-matrices. *Computing*, vol. 62, n2, 1999, pp. 89–108.

11. Hajiaghayi (M.), Lattanzi (S.), Seddighin (S.) et Stein (C.). – MapReduce meets fine-grained complexity : MapReduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond. *arXiv preprint arXiv:1905.01748*, 2019.

12. He (B.), Fang (W.), Luo (Q.), Govindaraju (N. K.) et Wang (T.). – Mars : a MapReduce
framework on graphics processors. – In *Proceedings of the 17th international conference on Parallel architectures and compilation techniques*, pp. 260–269, 2008.

13. Hoefler (T.), Lumsdaine (A.) et Dongarra (J. J.). – Towards efficient MapReduce using MPI. – In *European Parallel Virtual Machine/Message Passing Interface Users' Group Meeting*, pp. 240–249. Springer, 2009.

14. Kadhum (M.), Qasem (M. H.), Sleit (A.) et Sharieh (A.). – Efficient MapReduce matrix multiplication with optimized mapper set. – In *Cybernetics and Mathematics Applications in Intelligent Systems : Proceedings of the 6th Computer Science On-line Conference 2017 (CSOC2017)*, Vol 2 6, pp. 186–196. Springer, 2017.

15. Karloff (H.), Suri (S.) et Vassilvitskii (S.). – A model of computation for MapReduce. – In *Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms*, pp. 938–948. SIAM, 2010.

16. Seo (S.), Yoon (E. J.), Kim (J.), Jin (S.), Kim (J.-S.) et Maeng (S.). – HAMA : An efficient matrix computation with the MapReduce framework. – In *2010 IEEE Second International Conference on Cloud Computing Technology and Science*, pp. 721–726. IEEE, 2010.

17. Sun (Z.), Li (T.) et Rishe (N.). – Large-scale matrix factorization using MapReduce. – In *2010 IEEE International Conference on Data Mining Workshops*, pp. 1242–1248. IEEE, 2010.

18. Wasi-ur Rahman (M.), Lu (X.), Islam (N. S.), Rajachandrasekar (R.) et Panda (D. K.). – High-performance design of YARN MapReduce on modern HPC clusters with Lustre and RDMA. – In *2015 IEEE International Parallel and Distributed Processing Symposium*, pp. 291–300. IEEE, 2015.