¿CUDA es compatible con la recursión?

Question

¿CUDA es compatible con la recursividad?

Answer 1

Lo hace en hardware NVIDIA apoyar la capacidad de cómputo 2.0 y CUDA 3.1:

nuevas características del lenguaje añadido a CUDA C /C++ incluye:

Ayuda para la función punteros y recursión facilite para portar muchos algoritmos existentes a GPU de Fermi

http://developer.nvidia.com/object/cuda_3_1_downloads.html

punteros de función: http://developer.download.nvidia.com/compute/cuda/sdk/website/CUDA_Advanced_Topics.html#FunctionPointers

Recursión: no puedo encontrar un ejemplo de código en el sitio web de NVIDIA, pero en el forum alguien publicar esto:

__device__ int fact(int f) 
{ 
    if (f == 0) 
    return 1; 
    else 
    return f * fact(f - 1); 
} 

Answer 2

Cualquier algoritmo recursivo se puede implementar con una pila y un bucle. Es mucho más doloroso, pero si realmente necesitas recursividad, esto puede funcionar.

Answer 3

Sí, ver la NVIDIA CUDA Programming Guide: solamente

dispositivo funciones recursión apoyo en código de dispositivo compilado para dispositivos de la capacidad de cálculo 2.0.

Necesita una tarjeta Fermi para usarlos.

Answer 4

CUDA 3.1 admite la recursión

Answer 5

Aunque solo admite recursividad para chips específicos, a veces puede salirse con la recursión "emulada": see how I used compile-time recursion for my CUDA raytracer.

Answer 6

Intenté recién ahora en mi pc con una GPU NVIDIA con capacidad de cálculo de 1.1. Dice que la recurrencia aún no es compatible. Así que no tiene nada que ver con el tiempo de ejecución sino con el hardware

Answer 7

En la versión CUDA 4.1, CUDA admite la recursión solo para la función __device__ pero no para la función __global__.

Answer 8

Claro que sí, pero requiere la arquitectura de Kepler para hacerlo. Echa un vistazo a su último ejemplo en la clasificación rápida clásica.

http://blogs.nvidia.com/2012/09/how-tesla-k20-speeds-up-quicksort-a-familiar-comp-sci-code/

Por lo que yo sé, sólo el último Kepler GK110 soporta paralelismo dinámico, que permite este tipo de llamada recursiva y desove de nuevos temas dentro del kernel. Antes de Kepler GK110, no fue posible. Y tenga en cuenta que no toda la arquitectura Kepler es compatible con esto, solo GK110 lo hace.

Si necesita recursión, probablemente necesite el Tesla K20. No estoy seguro de si Fermi lo admite, nunca lo lea.: \ Pero Kepler seguro sí. =)

Answer 9

Si su algoritmo incluye muchas recurrencias, soporte o no, no está diseñado para GPU, rediseñe sus algorthims o consiga una mejor CPU, de cualquier forma será mejor (apuesto en muchos casos, maginitudes mejor) luego hacer repeticiones en GPU.

Answer 10

Sólo después de 2.0 capacidad de cómputo en dispositivos compatibles

Answer 11

Sí, se apoya en la versión actual. Pero a pesar de que es posible ejecutar funciones recursivas, debe tener en cuenta que la asignación de memoria de la pila de ejecución no se puede predecir (la función recursiva se debe ejecutar para conocer la profundidad real de la recursión), por lo que su pila podría resultar insuficiente para sus propósitos y podría necesitar un incremento manual del tamaño de pila predeterminado