¿Hay algún algoritmo para ordenar una matriz de cadenas para la GPU?

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.¿Hay algún algoritmo para ordenar una matriz de cadenas para la GPU?

Estoy buscando cualquier implementación de algoritmo de clasificación para GPU.

Tengo un bloque de datos con un tamaño de aproximadamente 1MB y necesito construir suffix array. Ahora puede ver cómo es posible tener un millón de cadenas dentro de una cantidad realmente pequeña de memoria.

Fuente

2010-07-15 Kentzo

'1M' caracteres por string (avg '.5M'?),' 1M' strings, 2 bytes/char (más común) produce: '.5 * 1 * 2 = 1TB' memory. Necesita algo especial para esto (¿tal vez una base de datos?), Ya que existen muy pocas máquinas con ese tipo de memoria, y mucho menos con la memoria GPU. http://blogs.technet.com/b/markrussinovich/archive/2008/07/21/3092070.aspx – Abel

La longitud máxima de la cadena no dice nada sobre el promedio. Supongo que las cadenas ya están en la memoria y se ordenan, pero el póster no está satisfecho con el rendimiento de la CPU en la tarea. –

Puede ser relevante/útil escuchar cómo se estructuran los datos. ¿Es un grupo de cadenas contiguas separadas por '\ 0'? ¿Las cadenas van precedidas de un encabezado que contiene un recuento de bytes? ¿O hay una serie de indicadores en un montón? ¿Estamos hablando de cadenas ASCII o Unicode? –

El estado del arte en la clasificación de GPU no es particularmente alentador.

Para clasificar enteros de 32 bits el siguiente artículo de 2009 (con 2 autores que son investigadores de Nvidia) solo afirma un aumento del 23% para el mejor tipo de CUDA en GTX280 en comparación con la mejor ordenación de CPU en un Yorkfield de 4 núcleos.

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

Esta utilizaron una especie radix en la GPU, y ordenamiento por mezcla en la CPU. Necesitaría una ordenación basada en comparación para construir una matriz de sufijos, por lo que en lugar del ordenamiento de GPU radix, el mejor de los del documento sería la fusión de GPU, que logró aproximadamente la mitad de la velocidad del ordenamiento de la GPU (con 1 millón teclas), es decir, aproximadamente un 40% más lento que la ordenación por fusión de CPU.

La adición de claves de longitud variable parece causar que los hilos en una urdimbre se desincronicen en una GPU, por lo que reduciría el rendimiento en la GPU más que en 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, ya que será más rápido y fácil de escribir.

Pero, si su propósito es experimentar o simplemente para aprender acerca de la GPU, a continuación, puede encontrar la aplicación CUDA de fusión tipo del papel en el SDK de CUDA:

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

Fuente

2010-07-17 05:37:21 RD1

¿No es el objetivo de CUDA utilizar un procesador que esté inactivo de todos modos? Incluso si no obtuvieras ninguna mejora de velocidad en una GPU sobre una CPU, aún tendrías una mejora 2 veces mayor que tener una CPU solamente, siempre que puedas utilizar el paralelismo adicional de manera efectiva. –

@Robert Harvey: la mayoría de los usos de CUDA no mantienen la CPU ocupada al mismo tiempo. Sin embargo recientemente esto se ha vuelto más común, y generalmente se llama GPU/CPU híbrida. Sin embargo, la necesidad de copiar entre la CPU y las memorias de la GPU hace que sea bastante complicado obtener un buen rendimiento. En este caso, esperaría que en el mejor de los casos alcanzara el 150% de la velocidad de la CPU, y sería mejor que invirtiera en un sistema con dos CPU. – RD1

Gracias por su respuesta. Estoy de acuerdo con todas sus notas sobre la clasificación de cadenas en una GPU, pensé de la misma manera, pero esperaba que hubiera un algoritmo que me había perdido. – Kentzo

¿Hay algún algoritmo para ordenar una matriz de cadenas para la GPU?

Respuesta

Cuestiones relacionadas