cuda - mathematica - fft python example

CUDA fft-cooley tukey, ¿cómo se explota el paralelismo?

Question

Sé cómo funciona la implementación de FFT ( algoritmo Cooley-Tuckey ) y sé que hay una biblioteca CUFFT CUDA para calcular la FFT 1D o 2D rápidamente, pero me gustaría saber cómo se aprovecha el paralelismo de CUDA en el proceso.

¿Está relacionado con el cálculo de las mariposas? (algo así como cada subproceso carga parte de los datos en la memoria compartida y luego cada subproceso calcula un término par o un término impar?)

Answer 1

No creo que utilicen el algoritmo Cooley-Tuckey porque su fase de permutación de índice hace que no sea muy conveniente para las arquitecturas de memoria compartida. Además, este algoritmo funciona con pasos de memoria de potencia de dos, lo que tampoco es bueno para la fusión de la memoria. Lo más probable es que usen alguna formulación de FFT de auto clasificación de Stockham: por ejemplo, el algoritmo de Bailey .

Con respecto a la implementación, tiene razón, generalmente uno divide una FFT grande en varias más pequeñas que se ajustan perfectamente a un bloque de hilos. En mi trabajo , utilicé FFT de 512 ó 1024 puntos (completamente desenrollado por supuesto) por bloque de hilos con 128 hilos. Normalmente, no se trabaja con un algoritmo clásico radix-2 en la GPU debido a la gran cantidad de transferencias de datos requeridas. En cambio, uno elige el algoritmo radix-8 o incluso radix-16 para que cada hilo realice una "mariposa" grande a la vez. Por ejemplo, implementaciones, también puede visitar la página de Vasily Volkov o consultar este documento "clásico".