Évolutivité de la transformation de Fourier rapide (FFT)

Pour utiliser la transformée de Fourier rapide (FFT) sur des données échantillonnées uniformément, par exemple en relation avec des solveurs PDE, il est bien connu que la FFT est un algorithme ). Dans quelle mesure l'échelle FFT est-elle traitée en parallèle pour n → ∞ (c'est-à-dire très grande)?$\mathcal{O}(n\log(n)$$n\to\infty$

Il s'agit de preuves plus anecdotiques que de preuves démontrées, mais il semble que les implémentations existantes pour les FFT, telles que FFTW , ont une limite à leur capacité de mise à l'échelle.

${\bf k}$$O(10^7)$

Mais le message à retenir ici est que la FFT devrait s'intensifier; cependant, il existe parfois des limitations et des interactions inattendues qui entrent en jeu lorsque l'on passe de la considération théorique des performances d'un algorithme à sa mise en œuvre pratique sur une plate-forme HPC réelle.

$O(n)$

$n$$d$$d$

La recherche de «FFT parallèle» ou «évolutivité pseudospectrale» sur Google Scholar fournit une mine d'informations que je ne suis pas qualifié pour évaluer. Mais cela semble être un bel exemple récent de ce qui peut être accompli dans la pratique:

Un schéma hybride MPI-OpenMP pour des calculs pseudospectraux parallèles évolutifs pour la turbulence des fluides

Abstrait:

Un schéma hybride qui utilise MPI pour le parallélisme de mémoire distribuée et OpenMP pour le parallélisme de mémoire partagée est présenté. Le travail est motivé par le désir d'atteindre des nombres de Reynolds exceptionnellement élevés dans les calculs pseudospectraux de turbulence des fluides sur des systèmes de traitement pétascale émergents, à nombre de cœurs élevé et massivement parallèles. L'implémentation hybride dérive et augmente un code pseudospectral évolutif parallélisé MPI bien testé. Le paradigme hybride conduit à une nouvelle image de la décomposition de domaine des grilles pseudospectrales, qui est utile pour comprendre, entre autres, la transposition 3D des données globales qui est nécessaire pour les transformées de Fourier rapides parallèles qui sont la composante centrale de la discrétisations numériques. Les détails de la mise en œuvre hybride sont fournis, et les tests de performances illustrent l'utilité de la méthode. Il est démontré que le schéma hybride atteint une évolutivité presque idéale jusqu'à ~ 20000 cœurs de calcul avec une efficacité moyenne maximale de 83%. Des données sont présentées qui montrent comment choisir le nombre optimal de processus MPI et de threads OpenMP afin d'optimiser les performances du code sur deux plates-formes différentes.

$O(n)$

$O(\log n)$

$O(n)$