Esiste un algoritmo per ordinare l'array di stringhe per la GPU?

Question

La matrice per ordinare ha circa un milione di stringhe, in cui ogni stringa può avere una lunghezza massima di un milione di caratteri.

Sto cercando qualsiasi implementazione dell'algoritmo di ordinamento per GPU.

Ho un blocco di dati con dimensioni di circa 1 MB e ho bisogno di costruire suffix array. Ora puoi vedere come è possibile avere un milione di stringhe all'interno di una quantità veramente piccola di memoria.

Answer 1

Lo stato dell'arte nell'ordinamento GPU non è particolarmente incoraggiante.

Per classificare 32 bit interi seguente carta dal 2009 (con 2 autori che sono ricercatori Nvidia) sostiene solo aumento del 23% per la migliore CUDA ordinamento su GTX280 rispetto ai migliori ordinamento CPU su un nucleo 4 Yorkfield.

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

Questo usato un ordinamento di radice sulla GPU e unire ordinamento CPU. Avresti bisogno di un ordinamento basato su confronto per costruire un suffisso array, quindi al posto di GPX radix sort il meglio di quelli nella carta sarebbe l'ordinamento di merge GPU, che ha ottenuto circa la metà della velocità di GPX radix sort (con 1 milione chiavi) - cioè circa il 40% più lento rispetto all'ordinamento di fusione della CPU.

L'aggiunta di chiavi di lunghezza variabile sembra probabile che i thread in una curvatura non saranno sincronizzati su una GPU, quindi ridurrebbe le prestazioni sulla GPU più della CPU.

In generale se il tuo scopo è quello di costruire un sistema efficiente, ti consiglio di utilizzare un'implementazione della CPU per questo problema perché sarà più veloce e più facile da scrivere.

Ma, se il vostro scopo è quello di sperimentare o semplicemente per conoscere GPU, allora si può trovare l'attuazione CUDA di merge sort dalla carta nel CUDA SDK:

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