C'è algoritmo per l'ordinamento della serie di stringhe per GPU?

Question

Array per ordinare ha circa un milione di stringhe, dove ogni stringa può avere una lunghezza fino a 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 Array suffisso .Ora puoi vedere come è possibile avere un milione di stringhe all'interno di una quantità davvero piccola di memoria.

Answer 1

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

Per l'ordinamento di numeri interi a 32 bit, il seguente documento dal 2009 (con 2 autori che sono ricercatori di Nvidia) rivendica solo il 23% di aumento del 23% per il miglior tipo CUDA su GTX280 rispetto al miglior tipo CPU su un campo da 4 core. .

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

Questo ha utilizzato un radix ordinabile sulla GPU e unire ordinamento su CPU. Avresti bisogno di un ordinamento basato sul confronto per costruire un array suffisso, quindi invece del radix GPU ordina il meglio di quelli nella carta sarebbe un ottimo tipo GPU, che ha raggiunto circa la metà della velocità del radix GPU (con 1 milione Chiavi) - cioè circa il 40% più lento rispetto alla CPU Merge Ordina.

Aggiunta di tasti di lunghezza variabile Sembra probabile che causi fili in un ordito si sincronizzano di sincronizzazione su una GPU, quindi ridurrebbe le prestazioni sulla GPU più della CPU.

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

Ma, se il tuo scopo è quello di sperimentare o semplicemente per conoscere la GPU, puoi trovare l'implementazione CUDA di unione ordinata dalla carta nell'SDK CUDA:

http://developer.download.nvidia .com / calcolo / cuda / sdk / sito web / dati-parallel_algorithms.html