CUDA - Implementación de dispositivo Hash Map?

Question

¿Alguien tiene alguna experiencia implementando un mapa hash en un dispositivo CUDA? Específicamente, me pregunto cómo se podría asignar memoria al dispositivo y copiar el resultado al host, o si hay bibliotecas útiles que puedan facilitar esta tarea.

Parece que necesitaría saber el tamaño máximo del mapa hash a priori para asignar la memoria del dispositivo. Todos mis intentos anteriores de CUDA han utilizado matrices y memcpys y, por lo tanto, han sido bastante sencillos.

Cualquier apreciación de este problema es apreciada. Gracias.

Answer 1

Hay una implementación de GPU Hash Table presentada en "CUDA por ejemplo", de Jason Sanders y Edward Kandrot.

Afortunadamente, se puede obtener información sobre este libro y descargar el código fuente ejemplos libremente en esta página:
http://developer.nvidia.com/object/cuda-by-example.html

En esta implementación, la mesa está preasignado a cada CPU y el acceso multiproceso seguro es garantizado por una función de bloqueo basada en la función atómica atomicCAS (Compare And Swap).

Además, la generación de hardware más nueva (de 2.0) combinada con CUDA> = 4.0 se supone que pueden usar directamente operadores nuevos/eliminar en la GPU (http://developer.nvidia.com/object/cuda_4_0_RC_downloads.html?utm_source=http://forums.nvidia.com&utm_medium=http://forums.nvidia.com&utm_term=Developers&utm_content=Developers&utm_campaign=CUDA4), que podrían servir para su implementación. Todavía no he probado estas características.

Answer 2

Recuerdo que alguien desarrolló una implementación directa del mapa hash en la parte superior de thrust. Hay un código para él here, aunque no sé si funciona con versiones de empuje actuales. Al menos podría darle algunas ideas.

Answer 3

AFAIK, la tabla hash dada en "Cuda por ejemplo" no funciona muy bien. Actualmente, creo, la tabla hash más rápida en CUDA se da en Dan Alcantara's PhD dissertation. Consulte el capítulo 6.