Tri rapide sur CPU et GPU

Le tri est un noyau fondamental utilisé dans de nombreuses opérations de base de données. Les tris en mémoire sont désormais réalisables ; la performance du tri est limitée par les flops de calcul et la bande passante de la mémoire principale plutôt que par l'I/O. Dans cet article, nous présentons une analyse compétitive des algorithmes de tri basés sur la comparaison et non comparatifs sur deux architectures modernes - les dernières architectures CPU et GPU. Nous proposons de nouvelles implémentations de tri radicé pour CPU et de tri par fusion pour GPU qui sont 2 fois plus rapides que les résultats précédemment publiés. Nous effectuons une comparaison équitable des algorithmes en utilisant ces implémentations les plus performantes sur les deux architectures. Bien que le tri radicé soit plus rapide sur les architectures actuelles, l'écart se réduit des architectures CPU aux architectures GPU. Le tri par fusion fonctionne mieux que le tri radicé pour trier des clés de grande taille - de telles clés seront nécessaires pour accueillir la cardinalité croissante des bases de données futures. Nous présentons des modèles analytiques pour analyser la performance de nos implémentations en termes de caractéristiques architecturales telles que le nombre de cœurs, SIMD et bande passante. Nos résultats de performance obtenus sont prédites avec succès par nos modèles. Notre analyse montre que le tri par fusion l'emporte sur le tri radicé sur les futures architectures en raison de son utilisation efficace de SIMD et de sa faible utilisation de bande passante. Nous simulons une plateforme à 64 cœurs avec des largeurs SIMD variables sous des contraintes de bande passante constante par cœur, et montrons que pour de grandes tailles de données de 240 (un trillion d'enregistrements), la performance du tri par fusion sur de grandes tailles de clés est jusqu'à 3 fois meilleure que celle du tri radicé pour de grandes largeurs SIMD sur les futures architectures. Par conséquent, le tri par fusion devrait être la méthode de tri de choix pour les bases de données futures.