Quel algorithme de tri parallèle a la meilleure performance moyenne ?

Question

Le tri prend O(n log n) dans le cas de la série. Si nous disposons de O(n) processeurs, nous pouvons espérer une accélération linéaire. Des algorithmes parallèles O(log n) existent mais ils ont une constante très élevée. Ils ne sont pas non plus applicables sur le matériel de base qui ne dispose pas de O(n) processeurs. Avec p processeurs, des algorithmes raisonnables devraient prendre O(n/p log n) temps.

Dans le cas du traitement en série, le tri rapide présente en moyenne la meilleure complexité d'exécution. Un algorithme de tri rapide parallèle est facile à implémenter (voir aquí y aquí ). Cependant, il n'est pas très performant car la toute première étape consiste à partitionner l'ensemble de la collection sur un seul cœur. J'ai trouvé des informations sur de nombreux algorithmes de tri parallèle, mais jusqu'à présent, je n'ai rien vu qui indique un vainqueur clair.

Je cherche à trier des listes de 1 à 100 millions d'éléments dans un langage JVM fonctionnant sur 8 à 32 cœurs.

Answer 1

L'article suivant (téléchargement PDF) est une étude comparative des algorithmes de tri parallèle sur différentes architectures :

Algorithmes de tri parallèles sur diverses architectures

Selon l'article, tri des échantillons semble être le meilleur sur de nombreux types d'architecture parallèle.

Mise à jour pour répondre à la préoccupation de Mark concernant l'âge :

Voici des articles plus récents présentant quelque chose de plus nouveau (de 2007, qui, d'ailleurs, sont toujours comparés à des échantillons) :

Amélioration du tri des échantillons
AA-Sort

Le dernier cri (vers 2010, certains datant de quelques mois seulement) :

Modèle de tri parallèle
Tri parallèle basé sur un GPU à plusieurs cœurs
Tri parallèle hybride CPU/GPU
Algorithme de tri parallèle aléatoire avec une étude expérimentale
Tri parallèle hautement évolutif
Tri de N-éléments par ordre naturel : Une nouvelle approche de tri adaptatif

Mise à jour pour 2013 : Voici l'état des lieux en janvier 2013. (Note : Quelques-uns des liens renvoient à des articles sur Citeseer et nécessitent une inscription gratuite) :

Conférences universitaires :
Partitionnement parallèle pour la sélection et le triage
Cours sur les algorithmes de tri parallèles
Algorithmes de triage parallèles Lecture 2
Algorithmes de tri parallèles Lecture 3

Autres sources et documents :
Un nouvel algorithme de tri pour les architectures à plusieurs cœurs basé sur le tri bitonique adaptatif.
Triage parallèle hautement évolutif 2
Fusion parallèle
Fusion parallèle 2
Système parallèle de tri automatique d'objets
Comparaison des performances des algorithmes de tri rapide séquentiel et de tri rapide parallèle
Mémoire partagée, passage de messages et tri hybride par fusion pour les SMP autonomes et en grappe
Divers algorithmes parallèles (tri et autres), y compris des implémentations

Sources et articles sur les GPU et les hybrides CPU/GPU :
Une méthode OpenCL d'algorithmes de tri parallèle pour l'architecture GPU
Tri des données à l'aide d'unités de traitement graphique
Algorithmes efficaces de tri sur les GPU
Conception d'algorithmes de tri efficaces pour les GPU multi-coeurs
Tri d'échantillons déterministe pour les GPU
Triage rapide en place avec CUDA basé sur le triage bitonique
Triage parallèle rapide sur GPU à l'aide d'un algorithme hybride
Algorithmes de tri rapides et parallèles sur les GPU
Tri rapide sur les CPU et les GPU : un cas pour le tri SIMD sans tenir compte de la bande passante
Exemple de tri GPU
GPU-ABiSort : Triage parallèle optimal sur les architectures à flux.
GPUTeraSort : tri par coprocesseur graphique haute performance pour la gestion de grandes bases de données
Algorithme de tri basé sur la comparaison très performant sur les GPU à plusieurs cœurs.
Tri externe parallèle pour les GPU compatibles avec CUDA avec équilibrage de la charge et faible surcharge de transfert.
Triage sur les GPU pour les ensembles de données à grande échelle : Une comparaison approfondie

Mise à jour pour 2021 : Je n'ai pas oublié cette réponse et comme tout ce qui concerne l'informatique, elle n'a pas bien vieilli. Je ferai de mon mieux pour la mettre à jour et la rafraîchir en fonction des tendances actuelles et de l'état de l'art, avant la fin de cette année (2021).

Answer 2

J'ai travaillé à la fois avec un algorithme de tri rapide parallèle et un algorithme PSRS qui combine essentiellement le tri rapide en parallèle avec la fusion.

Avec l'algorithme Parallel Quicksort, j'ai démontré une accélération quasi linéaire avec jusqu'à 4 cœurs (double cœur avec hyper-threading), ce qui est attendu étant donné les limitations de l'algorithme. Un Quicksort parallèle pur repose sur une ressource de pile partagée, ce qui entraîne des conflits entre les threads, réduisant ainsi tout gain de performance. L'avantage de cet algorithme est qu'il trie "sur place", ce qui réduit la quantité de mémoire nécessaire. Vous pouvez envisager cette solution lorsque vous triez plus de 100 millions d'éléments, comme vous l'avez indiqué.

Je vois que vous cherchez à trier sur un système avec 8-32 cœurs. L'algorithme PSRS évite la contention de la ressource partagée, ce qui permet d'accélérer le nombre de processus. J'ai démontré l'algorithme avec un maximum de 4 cœurs comme ci-dessus, mais les résultats expérimentaux d'autres personnes rapportent une accélération quasi linéaire avec un nombre de cœurs beaucoup plus important, 32 et plus. L'inconvénient de l'algorithme PSRS est qu'il n'est pas in-place et nécessite beaucoup plus de mémoire.

Si vous êtes intéressé, vous pouvez utiliser ou consulter mon code Java pour chacun de ces algorithmes. Vous pouvez le trouver sur github : https://github.com/broadbear/sort . Ce code est conçu comme un remplacement direct de Java Collections.sort(). Si vous recherchez la possibilité d'effectuer un tri parallèle dans une JVM comme vous l'indiquez ci-dessus, le code dans mon repo peut vous aider. L'API est entièrement générique pour les éléments implémentant Comparable ou implémentant votre propre Comparateur.

Puis-je vous demander ce que vous cherchez à trier avec autant d'éléments ? Je suis intéressé de connaître les applications potentielles de mon paquet de tri.

Answer 3

Jetez un coup d'œil à ce document : Un algorithme de tri parallèle évolutif utilisant le fractionnement exact. . Il concerne bien plus que 32 cœurs. Cependant, il décrit en détail un algorithme dont la complexité en temps d'exécution est de O(n/p * log(n) + p * log(n)**2) et qui est applicable à des comparateurs arbitraires.

Answer 4

Le document "Comparaison d'algorithmes de triage parallèles sur différentes architectures " peut être un bon point de départ pour vous.