Escalabilidad de la transformación rápida de Fourier (FFT)

12

Para utilizar la Transformada rápida de Fourier (FFT) en datos muestreados de manera uniforme, por ejemplo, en relación con los solucionadores de PDE, es bien sabido que el FFT es un algoritmo ). ¿Qué tan bien se escala la FFT cuando se procesa en paralelo para n (es decir, muy grande)?O(nlog(n)n

Allan P. Engsig-Karup
fuente
1
Estoy un poco confundido. ¿Está hablando de cómo se escala el tiempo de ejecución para un número fijo de procesadores a medida que aumenta el número de puntos de datos, cómo se escala el tiempo de ejecución para un número fijo de puntos de datos a medida que aumenta el número o los procesadores, o cómo se escala el tiempo de ejecución para un ¿Relación fija de puntos de datos por procesador a medida que aumenta el número de puntos de datos?
Geoff Oxberry
Escala débil y fuerte.
Allan P. Engsig-Karup

Respuestas:

8

Esta es una evidencia más anecdótica que una prueba demostrada, pero parece que las implementaciones existentes para FFT, como FFTW , tienen un límite en su capacidad de escalado.

kO(107)

Pero el mensaje para llevar a casa aquí es que FFT debería escalar; sin embargo, a veces hay limitaciones e interacciones inesperadas que entran en juego cuando uno pasa de la consideración teórica del rendimiento de un algoritmo a su implementación práctica en una plataforma HPC real.

aeismail
fuente
6

O(n)

Jed Brown
fuente
5

ndd

La búsqueda de "FFT paralela" o "escalabilidad pseudoespectral" en Google Académico arroja una gran cantidad de información que no estoy calificado para evaluar. Pero esto parece un buen ejemplo reciente de lo que se puede lograr en la práctica:

Un esquema híbrido MPI-OpenMP para cálculos pseudopectrales paralelos escalables para turbulencia de fluidos

Resumen:

Se presenta un esquema híbrido que utiliza MPI para el paralelismo de memoria distribuida y OpenMP para el paralelismo de memoria compartida. El trabajo está motivado por el deseo de lograr números de Reynolds excepcionalmente altos en cálculos pseudopectrales de turbulencia de fluidos en sistemas emergentes de procesamiento de petascala, alto conteo de núcleos y paralelos masivos. La implementación híbrida deriva y aumenta un código pseudo espectral paralelo escalable de MPI bien probado. El paradigma híbrido conduce a una nueva imagen para la descomposición del dominio de las cuadrículas pseudoespectrales, que es útil para comprender, entre otras cosas, la transposición 3D de los datos globales que son necesarios para las transformadas rápidas paralelas de Fourier que son el componente central de la discretizaciones numéricas Se proporcionan detalles de la implementación híbrida, y las pruebas de rendimiento ilustran la utilidad del método. Se muestra que el esquema híbrido logra una escalabilidad casi ideal de hasta ~ 20000 núcleos de cómputo con una eficiencia media máxima del 83%. Se presentan datos que demuestran cómo elegir la cantidad óptima de procesos MPI y subprocesos OpenMP para optimizar el rendimiento del código en dos plataformas diferentes.

David Ketcheson
fuente
1

O(n)

O(logn)

O(n)

Dan
fuente
1
Hay una cantidad significativa de comunicación en FFT, pero ciertamente no es necesario (o deseable) reunir el resultado en un solo nodo. Un uso muy común de FFT es en la simulación numérica directa de la turbulencia, donde se usa para aplicar el término de convección no lineal en el espacio real, mientras que el resto de la simulación se realiza en el espacio de Fourier. Esto enfáticamente no requiere serializar el resultado. En general con la computación paralela, los datos "grandes" siempre deben almacenarse y analizarse en forma distribuida.
Jed Brown