¿Hay algoritmo para clasificar la matriz de cuerdas para la GPU?
https://stackoverflow.com/questions/3255569
-
16-09-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
La matriz para ordenar tiene aproximadamente un millón de cadenas, donde cada cadena puede tener una longitud de hasta un millón de caracteres.
Estoy buscando cualquier implementación de algoritmo de clasificación para GPU.
Tengo un bloque de datos con el tamaño de aproximadamente 1 MB y necesito construir matriz de sufijo .Ahora puede ver cómo es posible tener un millón de cuerdas dentro de una cantidad realmente pequeña de memoria.
Solución
El estado de la técnica en la clasificación de la GPU no es particularmente alentadora.
Para clasificar enteros de 32 bits el siguiente documento de 2009 (con 2 autores que son investigadores en NVIDIA), solo reclaman un aumento del 23% del 23% para la mejor clasificación de CUDA en GTX280 en comparación con la mejor clasificación de CPU en un SoachField de 4 Core.
http://www.mgarland.org/files/papers/gpusort -IPDPS09.PDF
Esto usó un ordenador de radix en la GPU, y fusionó la clasificación de la CPU. Necesitaría un tipo basado en comparación para construir una matriz de sufijo, por lo que en lugar de GPU Radix Ordenar lo mejor de los que están en el documento sería una especie de combinación de GPU, lo que logró aproximadamente la mitad de la velocidad de la GPU Radix Sort (con 1 millón llaves) - es decir, aproximadamente un 40% más lento que el tipo de combinación de la CPU.
La adición de teclas de longitud variable parece probable que cause hilos en una deformación se saldrá de la sincronización en una GPU, por lo que reduciría el rendimiento en la GPU más que la CPU.
En general, si su propósito es construir un sistema eficiente, le recomendaría que utilice una implementación de CPU para este problema porque será más rápido y más fácil de escribir.
Pero, si su propósito es experimentar o simplemente para aprender sobre la GPU, entonces puede encontrar la implementación de CUDA de la ordenación de combustión del papel en el CUDA SDK:
