Y a-t-il des algorithmes pour tri des chaînes de GPU?

Question

Tableau pour trier compte environ un million de chaînes, où chaque chaîne peut avoir une longueur pouvant atteindre un million de caractères.

Je cherche toute mise en œuvre de l'algorithme de tri pour GPU.

J'ai un bloc de données avec la 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 grande quantité de mémoire.

Answer 1

L'état de la technique dans le tri du GPU n'est pas particulièrement encourageant.

Pour trier les entiers 32 bits Le document suivant de 2009 (avec 2 auteurs qui sont des chercheurs de Nvidia) ne prévoit que 23% d'augmentation pour la meilleure sorte de CUDA sur GTX280 par rapport au meilleur tri de la CPU sur un 4 noyau York.

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

Ceci a utilisé un triadix sur le GPU et la fusion de la CPU. Vous auriez besoin d'un type basé sur la comparaison afin de construire un ensemble de suffixe, alors au lieu de GPU Radix Trier le meilleur de ceux de l'article serait un type de fusion GPU, qui a obtenu environ la moitié de la vitesse du type RADIX GPU (avec 1 million clés) - c'est-à-dire environ 40% plus lentement que le type de fusion de la CPU.

L'ajout de touches de longueur variable semble susceptible de provoquer des fils dans une chaîne Servera de synchronisation sur un GPU, de manière à réduire la performance sur le GPU plus que la CPU.

Global Si votre objectif est de créer un système efficace, je vous recommande d'utiliser une implémentation de la CPU pour ce problème car elle sera plus rapide et plus facile à écrire.

Mais, si votre but est d'expérimenter ou d'apprendre simplement à en apprendre davantage sur le GPU, vous pouvez trouver la mise en œuvre de CUDA de la fusion de la fusion du papier dans le CUDA SDK:

http://developer.download.nvidia .Com / Compute / CUDA / SDK / Site Web / Data-parallel_algorithms.html