Existe algoritmo para classificar a matriz de cordas para GPU?

Question

Array para classificar tem aproximadamente um milhão de strings, onde cada string pode ter comprimento de até um milhão de caracteres.

Eu estou procurando qualquer implementação de algoritmo de classificação para GPU.

Eu tenho um bloco de dados com tamanho de aproximadamente 1MB e eu preciso construir sufixo array .Agora você pode ver como é possível ter um milhão de strings dentro da quantidade realmente pequena de memória.

Answer 1

O estado da arte na classificação do GPU não é particularmente encorajador.

Para classificar inteiros de 32 bits, o seguinte papel de 2009 (com 2 autores que são pesquisadores da NVIDIA) apenas reivindica o aumento de 23% para o melhor tipo de CUDA no GTX280 em comparação com o melhor tipo de CPU. .

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

Isso usou uma classificação de radix na GPU e mesclar o tipo na CPU. Você precisaria de um tipo baseado em comparação para construir uma matriz de sufixo, então em vez de GPU Radix classificar o melhor daqueles no papel seria o tipo de mesclagem GPU, que alcançou cerca de metade da velocidade do tipo GPU Radix (com 1 milhão chaves) - ou seja, cerca de 40% mais lento do que o tipo de mesclagem da CPU.

Adicionando chaves de comprimento variável parece provável que faça com que os encadeamentos em uma Warp saísse de sincronia em uma GPU, assim reduziriam o desempenho na GPU mais do que a CPU.

No geral, se a sua finalidade é construir um sistema eficiente, eu recomendo que você use uma implementação da CPU para esse problema, porque será mais rápido e fácil de escrever.

Mas, se o seu propósito é experimentar ou apenas aprender sobre GPU, você pode encontrar a implementação do CUDA de Mesclar Classificar do papel no CUDA SDK:

http://developer.download.nvidia .com / compute / cuda / sdk / site / data-parallel_algorithms.html