En informatique , l' opérateur de réduction est un type d' opérateur couramment utilisé en programmation parallèle pour réduire les éléments d'un tableau à un seul résultat. Les...
Worldlex WikiFrancaisLecture gratuite
En informatique , l' opérateur de réduction est un type d' opérateur couramment utilisé en programmation parallèle pour réduire les éléments d'un tableau à un seul résultat. Les opérateurs de réduction sont associatifs et souvent (mais pas nécessairement) commutatifs . La réduction d'ensembles d'éléments est une composante essentielle de modèles de programmation tels que MapReduce , où un opérateur de réduction est appliqué ( mappé ) à tous les éléments avant leur réduction. D'autres algorithmes parallèles utilisent les opérateurs de réduction comme opérations principales pour résoudre des problèmes plus complexes. De nombreux opérateurs de réduction peuvent être utilisés pour la diffusion afin de distribuer des données à tous les processeurs.
Théorie
Un opérateur de réduction permet de décomposer une tâche en plusieurs sous-tâches en calculant des résultats partiels qui servent à obtenir un résultat final. Il permet d'exécuter certaines opérations séquentielles en parallèle et de réduire le nombre d'étapes nécessaires à ces opérations. L'opérateur de réduction stocke le résultat des sous-tâches dans une copie privée de la variable. Ces copies privées sont ensuite fusionnées en une copie partagée à la fin.
Un opérateur est un opérateur de réduction si :
Il peut réduire un tableau à une seule valeur scalaire.
Le résultat final devrait pouvoir être obtenu à partir des résultats des tâches partielles qui ont été créées.
Ces deux conditions sont satisfaites pour les opérateurs commutatifs et associatifs appliqués à tous les éléments du tableau.
Parmi les opérateurs qui satisfont à ces exigences, on peut citer l'addition, la multiplication et certains opérateurs logiques (et, ou, etc.).
Un opérateur de réduction
Exemple
Supposons que nous ayons un tableau
La norme IEEE 754-2019 définit quatre types de réductions de sommes et trois types de réductions de produits mis à l'échelle. Comme il s'agit d'opérateurs de réduction, la norme précise que « les implémentations peuvent être associées dans n'importe quel ordre ou évaluées dans n'importe quel format plus large ».
Contre-exemple
La multiplication matricielle n'est pas un opérateur de réduction car elle n'est pas commutative. Si les processus pouvaient renvoyer leurs résultats de multiplication matricielle dans n'importe quel ordre au processus maître, le résultat final calculé par ce dernier serait probablement incorrect si les résultats arrivaient dans le désordre. Cependant, la multiplication matricielle étant associative, le résultat serait correct à condition de respecter l'ordre des opérations, comme dans la technique de réduction par arbre binaire.
Algorithmes
Algorithmes d'arbres binomiaux
Concernant les algorithmes parallèles, il existe deux principaux modèles de calcul parallèle : la machine à accès aléatoire parallèle (PRAM), extension de la RAM avec mémoire partagée entre les unités de traitement, et l’ ordinateur parallèle synchrone (BSPC) , qui prend en compte la communication et la synchronisation . Ces deux modèles ont des implications différentes sur la complexité temporelle ; par conséquent, deux algorithmes seront présentés.
Algorithme PRAM
Cet algorithme représente une méthode largement répandue pour traiter les entrées où
Visualisation de l'algorithme avec p = 8, m = 1 et l'addition comme opérateur de réduction
pour
L'opérateur binaire pour les vecteurs est défini élément par élément de telle sorte que
L'algorithme suppose en outre qu'au début
Seulement
Analyse d'exécution
La boucle principale est exécutée.
Algorithme de mémoire distribuée
Contrairement à l'algorithme PRAM, dans le modèle de mémoire distribuée , la mémoire n'est pas partagée entre les unités de traitement et les données doivent être échangées explicitement entre elles. Par conséquent, les données doivent être échangées explicitement entre les unités, comme on peut le constater dans l'algorithme suivant.
pour
La seule différence entre l' algorithme distribué et la version PRAM réside dans l'inclusion de primitives de communication explicites ; le principe de fonctionnement reste le même.
Analyse d'exécution
La communication entre les unités engendre une certaine surcharge. Une analyse simple de l'algorithme utilise le modèle BSP et intègre le temps.
algorithme de pipeline
Visualisation de l'algorithme de pipeline avec p = 5, m = 4 et l'addition comme opérateur de réduction.
Pour les modèles de mémoire distribuée, l'utilisation d'une communication pipelinée peut s'avérer judicieuse. C'est notamment le cas lorsque
pour
Il est important de noter que les opérations d'envoi et de réception doivent être exécutées simultanément pour que l'algorithme fonctionne. Le vecteur de résultat est stocké à l'adresse suivante :
Analyse d'exécution
Le nombre d'étapes dans l'exécution parallèle est
Bien que
Applications
La réduction est l'une des principales opérations collectives implémentées dans l' interface de passage de messages (MPI) , où les performances de l'algorithme utilisé sont importantes et constamment évaluées pour différents cas d'utilisation. Les opérateurs peuvent être utilisés comme paramètres pour MPI_Reduceet MPI_Allreduce, à la différence que le résultat est disponible sur une seule unité de traitement (racine) ou sur toutes.
OpenMP propose une clause de réduction pour décrire comment les résultats des opérations parallèles sont collectés.
MapReduce s'appuie fortement sur des algorithmes de réduction efficaces pour traiter de grands ensembles de données, même sur d'énormes clusters.
Certains algorithmes de tri parallèle utilisent des réductions pour pouvoir traiter de très grands ensembles de données.
Worldlex Wiki 
