Merge sort (Français)

Merge sort se parallélise bien grâce à l’utilisation de la méthode divide-and-conquer. Plusieurs variantes parallèles de l’algorithme ont été développées au fil des ans. Certains algorithmes de tri de fusion parallèle sont fortement liés à l’algorithme de fusion séquentielle de haut en bas, tandis que d’autres ont une structure générale différente et utilisent la méthode de fusion K-way.

Merge sort with parallel recursionEdit

la procédure de merge sort séquentielle peut être décrite en deux phases, la phase de division et la phase de fusion., Le premier consiste en de nombreux appels récursifs qui effectuent à plusieurs reprises le même processus de division jusqu’à ce que les sous-séquences soient trivialement triées (contenant un ou aucun élément). Une approche intuitive est la parallélisation de ces appels récursifs. Le pseudocode suivant décrit le tri de fusion avec récursivité parallèle en utilisant les mots-clés fork and join:

cet algorithme est la modification triviale de la version séquentielle et ne se parallélise pas bien. Par conséquent, son accélération n’est pas très impressionnant., Il a une durée de Θ ( n ) {\displaystyle \Theta (n)} , qui n’est qu’une amélioration de Θ ( log ⁡ n ) {\displaystyle \Theta (\log n)} par rapport à la version séquentielle (voir Introduction aux Algorithmes). Cela est principalement dû à la méthode de fusion séquentielle, car c’est le goulot d’étranglement des exécutions parallèles.

Fusionner les trier en parallèle mergingEdit

un Meilleur parallélisme peut être obtenue en utilisant un parallèle algorithme de fusion. Cormen et coll. présenter une variante binaire qui fusionne deux sous-séquences triées en une séquence de sortie triée.,

Dans l’une des séquences (la plus longue, si l’inégalité de longueur), l’élément de l’indice moyen est sélectionné. Sa position dans l’autre séquence est déterminée de telle sorte que cette séquence resterait triée si cet élément était inséré à cette position. Ainsi, on sait combien d’autres éléments des deux séquences sont plus petits et la position de l’élément sélectionné dans la séquence de sortie peut être calculée. Pour les séquences partielles des éléments plus petits et plus grands créés de cette manière, l’algorithme de fusion est à nouveau exécuté en parallèle jusqu’à ce que le cas de base de la récursivité soit atteint.,

le pseudocode suivant montre la méthode de tri par fusion parallèle modifiée à l’aide de l’algorithme de fusion parallèle (adopté par Cormen et al.).

pour analyser une relation de récurrence dans le pire des cas, les appels récursifs de parallelMergesort ne doivent être incorporés qu’une seule fois en raison de leur exécution parallèle, en obtenant

pour des informations détaillées sur la complexité de la procédure de fusion parallèle, voir algorithme de fusion.,

La solution de cette récurrence est donnée par

T ∞ tri = Θ ( log ⁡ ( n ) 3 ) {\textstyle T_{\infty }^{\text{tri}}=\Theta \left(\log(n)^{3}\right)} .

Parallel multiway merge sortEdit

Il semble arbitraire de restreindre les algorithmes de tri de fusion à une méthode de fusion binaire, car il y a généralement p> 2 processeurs disponibles. Une meilleure approche peut être d’utiliser une méthode de fusion K-way, une généralisation de la fusion binaire, dans laquelle k {\displaystyle k} séquences triées sont fusionnées ensemble., Cette variante de fusion est bien adaptée pour décrire un algorithme de tri sur un landau.

de Base IdeaEdit

Multisequence selectionEdit

PseudocodeEdit

ci-dessous, le pseudocode complet de l’algorithme de tri par fusion à plusieurs voies parallèles est donné., Nous supposons qu’il existe une synchronisation de barrière avant et après la sélection multiséquence de sorte que chaque processeur puisse déterminer correctement les éléments de division et la partition de séquence.

Analysemodifier

adaptation et application Pratiquemodifier

l’algorithme de tri par fusion multiway est très évolutif grâce à sa capacité de parallélisation élevée, ce qui permet l’utilisation de nombreux processeurs. Cela fait de l’algorithme un candidat viable pour trier de grandes quantités de données, telles que celles traitées dans des clusters informatiques., De plus, comme dans de tels systèmes la mémoire n’est généralement pas une ressource limitative, l’inconvénient de la complexité spatiale du tri par fusion est négligeable. Cependant, d’autres facteurs deviennent importants dans de tels systèmes, qui ne sont pas pris en compte lors de la modélisation sur un landau. Ici, les aspects suivants doivent être pris en compte: la hiérarchie de la mémoire, lorsque les données ne rentrent pas dans le cache des processeurs, ou la surcharge de communication de l’échange de données entre processeurs, qui pourrait devenir un goulot d’étranglement lorsque les données ne sont plus accessibles via la mémoire partagée.

Sanders et coll., ont présenté dans leur article un algorithme parallèle synchrone en vrac pour multilevel multiway mergesort, qui divise p {\displaystyle P} Processeurs en r {\displaystyle r} groupes de taille p ‘{\displaystyle p’}. Tous les processeurs trient localement en premier. Contrairement aux mergesort multiway à un seul niveau, ces séquences sont ensuite partitionnées en parties r {\displaystyle R} et affectées aux groupes de processeurs appropriés. Ces étapes sont répétées récursivement dans ces groupes. Cela réduit la communication et évite surtout les problèmes avec de nombreux petits messages., La structure hiérarchique du réseau réel sous-jacent peut être utilisée pour définir les groupes de processeurs (par exemple racks, clusters,…).

autres VariantsEdit

Le Tri par Fusion a été l’un des premiers algorithmes de tri où une vitesse optimale a été atteinte, Richard Cole utilisant un algorithme de sous-échantillonnage intelligent pour assurer la fusion O(1). D’autres algorithmes de tri parallèle sophistiqués peuvent atteindre des limites de temps identiques ou Meilleures avec une constante inférieure., Par exemple, en 1991, David Powers a décrit un quicksort parallélisé (et un tri Radix connexe) qui peut fonctionner en O(log n) temps sur une machine à accès aléatoire parallèle CRCW (PRAM) avec n Processeurs en effectuant le partitionnement implicitement. Powers montre en outre qu’une version pipelinée du Mergesort Bitonique de Batcher à L’heure O((log n)2) sur un réseau de tri papillon est en pratique plus rapide que ses tries O(log n) sur un landau, et il fournit une discussion détaillée des frais généraux cachés en comparaison, radix et tri parallèle.