Parallelisation & Map-Reduce

1. Introduction
Cette partie du cours introduit des schémas d’applications multi-tâches, visant à exploiter en
parallèle plusieurs cœurs d’une même machine ou plusieurs machines. Il se focalise sur
deux schémas de parallélisation classiques et de haut niveau : le schéma SPMD apparu
dans le HPC, et le schéma Mapreduce associé au Big Data.

2. Problématique
La plupart des applications sont développées pour une exécution des instructions du
programme résultant en série sur un processeur. voir figure 1.

L'exécution parallèle vise à diviser/répartir l'exécution des instructions pour la résolution

d’une problème entre plusieurs unités de calculs comme sur le figure 2.

La réalisation de programme parallèle demande de mettre en place des outils de

synchronisation entre la partie principale et les sous-parties qui s'exécutent en parallèle,
dans le cas où les sous parties aient besoin de se partager des informations/données. La
section XXX liste les principaux outils de synchronisation qui ont été proposés.

Il faut noter aussi que plusieurs architectures et/ou modèles de programmation parallèles ont
été proposées. La section XXX, fourni des types d’architectures.

2.1. Outil de synchronisation

● Verrous :
● Sémaphores :
● Variables conditionnelles :
● Barrières sur fin de tâches :
● Barrières génériques :

source [1]

3. Les approches des parallélismes

Plusieurs architectures de programmation parallèle ont été proposées. Elles vont se
distingués par la façon dont :
● Les processus maîtres et les processus esclaves vont s’exécuter sur les processeurs
● Les processus vont communiquer et se synchroniser entre eux.
● les processus vont accéder aux données et accès aux différentes mémoires
● etc.

Source [1] Mémoire partagée (Gauche) - Communication MPI (Droite)

Figure XXX - Architecture Mixte - Source [1]

3.1. Quelques exemples d’architecture

Voir [1] pour la liste complète et le détail :
● Shared Memory (without threads)
● Threads
● Distributed Memory / Message Passing
● Data Parallel
● Hybrid
● Single Program Multiple Data (SPMD)
● Multiple Program Multiple Data (MPMD)

● Shared Memory on Distributed machines : Machine memory was physically

distributed across networked machines, but appeared to the user as a single shared
memory global address space.

● Distributed Memory Model on a shared memory machine : where every task has
direct access to global address space spread across all machines. However, the
ability to send and receive messages using Message Passing Interface (MPI), as is
commonly done over a network of distributed memory machines, was implemented
and commonly used.

3.2. Single Program Multiple Data (SPMD)

3.2.1. Présentation
● SPMD is actually a "high level" programming model that can be built upon any
combination of the previously mentioned parallel programming models.
● SINGLE PROGRAM: All tasks execute their copy of the same program
simultaneously. This program can be threads, message passing, data parallel or
hybrid.
● MULTIPLE DATA: All tasks may use different data
● SPMD programs usually have the necessary logic programmed into them to allow
different tasks to branch or conditionally execute only those parts of the program they
are designed to execute. That is, tasks do not necessarily have to execute the entire
program - perhaps only a portion of it.
 ● The SPMD model, using message passing or hybrid programming, is probably the
most commonly used parallel programming model for multi-node clusters.

Une programmation SMPD signifie que l’on déploie un ensemble de tâches et qu’elles
exécutent toutes le même programme, avec de temps en temps des points de
synchronisation. Mais tout en exécutant le même programme, deux tâches peuvent
exécuter des instructions parfois différentes car certaines divergences sont tolérées (If …
then … Else … EndIf).

Figure XXX - Approche SPMD avec synchronisation avec des barrières - Source [2]

3.2.2. Cas particulier de SPMD

Les problèmes embarrassingly parallel, ou happily parallel, sont souvent des schémas
SPMD extrêmes. Il s’agit de cas où on lance N tâches en concurrence totale (voir figure
XXX), sans communication ni synchronisation, souvent pour exécuter le même
programme sur des données différentes (eg. correction de N images indépendantes) ou
sur les mêmes données avec des jeux de paramètres différents (eg. investigation
multi-paramètres) pour identifier ensuite le jeu de paramètres ayant mené à la meilleure
solution. Ces problèmes ont en général une simple barrière à la fin pour qu’une tâche mère
sache que tout est terminé.

Figure XXX - SPDM - Embarrassingly parallel, ou happily parallel - Source[2]

3.3. Multiple Program Multiple Data (MPMD)
● like SPMD, MPMD is actually a "high level" programming model that can be built
upon any combination of the previously mentioned parallel programming models.
● MULTIPLE PROGRAM: Tasks may execute different programs simultaneously. The
programs can be threads, message passing, data parallel or hybrid.
● MULTIPLE DATA: All tasks may use different data
● MPMD applications are not as common as SPMD applications, but may be better
suited for certain types of problems, particularly those that lend themselves better to
functional decomposition than domain decomposition (discussed later under
Partitioning).

4. Map-Reduce en détails

4.1. Présentation
Map-Reduce est une approche de programmation parallèle. Elle a été inventée par google
pour répondre à des problématiques embarrassing parallel. Map-Reduce est inventé pour
les problèmes très simples à paralléliser.

Map-Reduce représente un changement mental quant à la façon dont on écrit un algorithme.

MR est un paradigme.

Le schéma de pensées de Map-Reduce consiste à découper la résolution du problème en

deux (ou 3) grandes étapes :
● une étape de Map qui suit a priori un schéma SPMD embarrassingly parallel,
● puis une étape de Reduce qui semble suivre un schéma similaire.
● Ces deux étapes sont reliées par une redistribution des données (le Shuffle &
Sort) qui route les paires clé-valeur de sortie de l’étape Map vers l’entrée de l’étape
Reduce.
L’étape de redistribution est complexe mais quasiment figée, et les deux étapes de Map et
de Reduce sont pipelinées, ce qui rend le fonctionnement du Map-Reduce à la fois plus
efficace et plus générique.
 Source [2]

Remarque
Les étapes Map et Reduce sont inspirées de la programmation fonctionnelle. Ce sont des
opérateurs génériques et leur combinaison permet donc de modéliser énormément de
problèmes.
● Map :
○ map(f)[x0, ..., xn] = [f(x0, ...,f(xn)]
○ map(*4)[2, 3, 6] = [8, 12, 24]
● Reduce:
○ reduce(f)[x0, ..., xn] = f(x0, f(x1, f(x2, ...)))
○ reduce(+)[2, 3, 6] = (2 + (3 + 6)) = 11

4.2. Principes de la chaîne de traitement Map-Reduce

La figure illustre le principe de traitement Map-Reduce.

● La collecte et le filtrage des données vise à lire les fichiers de données et réaliser
de nombreuses lectures de fichiers. Chaque fichier est lu (sous-étape 1.1) et analysé
(1.2), et seules les données satisfaisant les processus Map seront conservées.
 ● Le regroupement des données en ensembles cohérents: chaque processus Map
envoie ses données à des processus Reduce (voir ci-après), mais au final toutes les
données avec la même clé doivent être envoyées vers le même processus Reduce.
Il s’agit à la fois d’une étape de routage et d’une étape de redistribution des données
filtrées, appelé shuffle & sort.
● Le calcul de caractéristiques de groupes: chaque processus Reduce regroupe
dans une même liste toutes les valeurs reçues avec une même clé (3.1), puis
applique une fonction de calcul sur cette liste des valeurs associées à une même clé
(3.2).

4.3. Exécution parallèle de la chaîne Map-Reduce

Les différents processus Map de notre exemple peuvent s’exécuter en concurrence totale,
ce sont des traitements indépendants. Il en est de même pour les processus Reduce, et
pour les redistributions de données de la phase 2. Chaque phase de notre chaîne de
traitement est fortement parallèle en interne, mais chaque étape dépend de la précédente
pour ses entrées. D’autre part, ce type de traitement est appliqué sur de gros volumes de
données, et il est souvent impossible de stocker en mémoire toutes les données d’entrée
avant de les filtrer, ou même de garder en mémoire toutes les données retenues après
filtrage.

Chaque tâche Map lit une partie des données, les filtre, et évacue rapidement les données
retenues directement vers une tâche Reduce à travers le réseau d’interconnexion ou bien
vers des fichiers temporaires.

Un raisonnement similaire s’applique aux tâches Reduce. Il peut toutefois être nécessaire
qu’une tâche Reduce stocke en mémoire toutes les valeurs associées à une même clé
avant de pouvoir réaliser ses calculs sur cette liste de valeurs. Si l’algorithme et le code de
la tâche Reduce exigent un stockage fort en mémoire, cela peut limiter la taille des données
traitées. Une solution consiste à implanter un algorithme out-of-core, qui travaille par
morceaux puis stocke ses résultats intermédiaires sur disque avant de les relire pour
terminer ses calculs. Mais ce genre d’algorithme peut être lent.

Il est donc préférable de déployer des tâches Reduce sur plusieurs machines, afin de
disposer de toute la mémoire d’une machine pour chaque tâche Reduce et de charger
chaque tâche Reduce de travailler sur moins de clés, donc sur moins de groupes de
données, pour mieux répartir et accélérer les calculs.

4.4. Pipelining de la chaîne Map-Reduce

Une implantation efficace de la chaîne de traitement de Map-Reduce à deux principaux
objectifs :
● Réaliser les traitements en limitant l’espace mémoire requis (pour ne pas limiter les
volumes de données traitables), et
● Réduire au maximum les temps d’exécution.
Une solution consiste donc à pipeliner les différentes étapes :
● traiter les données par morceaux et
● faire travailler chaque étape de la chaîne en parallèle sur des données successives.

Chaque tâche Map lit une partie de ses données sur disque, pendant qu’elle filtre la partie
lue précédemment et qu’elle transmet les données retenues à la tâche de redistribution.
Cette dernière évacuera alors ces données dès que possible vers les tâches Reduce pour
libérer la mémoire occupée par la tâche Map. Chaque tâche Reduce regroupera les
données reçues possédant la même clé en les ordonnant au fur et à mesure qu’elle les
recevra, pour constituer des paires clé-liste de valeurs. En revanche, chaque tâche Reduce
ne traitera ces nouvelles paires que lorsqu’elles seront complètes, c’est-à-dire lorsque toutes
paires clé-valeur de sortie des tâches Map auront été produites et routées. Evidemment,
chaque étape ou sous-étape ne durera pas autant que les autres, contrairement au
chronogramme quasi-idéal de la Figure XXX. Mais une exécution en pipeline est quand
même plus efficace qu’une exécution séquentielle des tâches Map, suivie de la redistribution
des données, suivie d’une exécution séquentielle des tâches Reduce.

4.5. Impact sur la volumétrie

Le traitement de grosses volumétries de données impose d’exploiter plusieurs nœuds de
stockage, éventuellement localisés sur plusieurs sites de production ou de stockage de
données. Dès lors, certains choix ont été fait pour obtenir des traitements de données
efficaces:
● Amener les traitements aux données. Les processeurs étant capables de traiter
des données beaucoup plus vite que les réseaux ne peuvent les transporter, et les
données brutes (avant filtrage) étant souvent très volumineuses, il est préférable
d’amener des codes de filtrage et de lancer des tâches Map sur les nœuds de
données plutôt que de déplacer les données brutes vers des nœuds de calcul.
On transforme donc des nœuds de stockage en nœuds de calcul le temps de filtrer
les données brutes, et on doit gérer le déploiement d’une application distribuée sur
un ensemble de nœuds de stockage/calcul.

● Organiser des traitements par blocs. Traiter de grosses volumétries de données

signifie souvent manipuler des données plus volumineuses que la mémoire d’une
machine, et même que la somme des mémoires de tous les nœuds de stockage
utilisés. Il est donc nécessaire de concevoir le plus possible des traitements par
 morceaux qui évacuent régulièrement leurs résultats vers des fichiers
temporaires ou directement vers d’autres nœuds de traitement. C’est ce que
font les mécanismes internes d’Hadoop dans l’exécution des tâches Map sur des
blocs de données d’entrée.

● Paralléliser efficacement les traitements. Afin de traiter de gros volumes de

données en temps raisonnable, il est nécessaire de paralléliser et de distribuer
les traitements sur un grand nombre de machines. Mais les machines étant des
nœuds de données à base de PC standards reliés par un réseau standard, pas des
nœuds de calculs interconnectés par des réseaux très performants, il est préférable
d’adopter un schéma de parallélisation maximisant les traitements locaux, et
recouvrant les calculs et les communications.

● Pipeliner les traitements et les communications. Pour des raisons de

performances il est souhaitable de recouvrir les communications avec les
calculs des tâches amont et aval, quand cela est possible, afin de masquer les
coûts de communication. Le mécanisme de Map-Reduce de Hadoop le fait en
pipelinant une partie des traitements et les communications.

● Rendre simples les développements applicatifs. Au final, l’architecture logicielle

distribuée obtenue (chaîne de Map-Reduce) est complexe, mais doit être exploitée
par des data scientists et non pas par des spécialistes du calcul parallèle.

4.6. Exemple 1 de traitement Map-Reduce

4.6.1. Etape Map

La figure précédente illustre le fonctionnement d’une opération Map-Reduce
indépendamment de son implantation exacte. Un ensemble de paires clé1-valeur1 (numéro
de contrat, nom du vendeur) est lu et traité par l’étage Map qui applique indépendamment
sur chaque paire une fonction f_map. Celle-ci teste la clé de la paire et ne retient que les
clés inférieure à 17000, pour lesquelles elle génère une nouvelle paire clé2-valeur2 (nom du
vendeur, 1), avec 1 = un contrat vendu. La clé de la deuxième paire est donc la valeur de la
paire initiale, et sa valeur est imposée à 1.
4.6.2. Etape : Shuffle & Sort
La phase shuffle & sort regroupe tout d’abord toutes les paires de même clé, et crée une
nouvelle paire clé2 - liste de valeur2. Deux paires de clé Martin et de valeur 1 vont donc
donner naissance à une paire (Martin, (1,1)).

4.6.3. Etape Reduce

Puis on applique une fonction g_reduce à chaque paire clé2 - liste de valeur2, qui calcule la
somme des valeur2 de la liste, c'est-à-dire le nombre de contrats vendu par un même
vendeur. La fonction g_reduce génère alors une nouvelle paire clé3-valeur3, avec toujours le
nom du vendeur comme clé, et le nombre de contrats vendus par ce vendeur comme valeur.

4.7. Exemple 2 : Wordcount

4.8. Exercices de Map-Reduce

cf. fiche de TD

5. Références
● [1] [Link]
● [2] [Link]
● [3][Link]
r-des-donnees-massives/4308631-parcourez-les-principaux-algorithmes-mapreduce
● [4][Link]
r-des-donnees-massives/4308626-divisez-et-distribuez-pour-regner
●