Existe-t-il un algorithme pour trier les tableaux de chaînes pour le GPU?

Question

Le tableau à trier contient environ un million de chaînes, chaque chaîne pouvant contenir jusqu'à un million de caractères.

Je suis à la recherche de toute implémentation d'algorithme de tri pour GPU.

J'ai un bloc de données avec une taille d'environ 1 Mo et j'ai besoin de construire suffix array. Maintenant, vous pouvez voir comment il est possible d'avoir un million de chaînes à l'intérieur d'une très petite quantité de mémoire.

Answer 1

L'état de l'art dans le tri des GPU n'est pas particulièrement encourageant. Pour le tri des entiers 32 bits, le document suivant de 2009 (avec 2 auteurs qui sont des chercheurs chez Nvidia) ne réclame que 23% d'augmentation pour le meilleur tri CUDA sur GTX280 par rapport au meilleur tri CPU sur un Yorkfield 4 cœurs.

http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf

Cette utilisé une sorte de base sur le GPU, et le tri par fusion sur le processeur. Vous auriez besoin d'un tri basé sur la comparaison pour construire un tableau de suffixes, donc au lieu de trier la base GPU, le meilleur de ceux dans le papier serait le tri par fusion GPU, qui a atteint environ la moitié de la vitesse du type GPU. clés) - c'est-à-dire environ 40% plus lent que le tri par fusion du processeur. L'ajout de clés de longueur variable risque d'entraîner une désynchronisation des threads dans un GPU, ce qui réduirait davantage les performances du GPU que du CPU.

Dans l'ensemble, si votre but est de construire un système efficace, je vous recommande d'utiliser une implémentation de CPU pour ce problème car il sera plus rapide et plus facile à écrire.

Mais, si votre but est d'expérimenter ou tout simplement pour en apprendre davantage sur GPU, alors vous pouvez trouver l'application CUDA de tri fusion du papier dans le kit de développement CUDA:

http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html