FFTW - Fastest Fourier Transform in the West

De Wiki de Calcul Québec
(Redirigé depuis FFTW)
Aller à : Navigation, rechercher
Autres langues :anglais 100% • ‎français 100%

Sommaire

Transformée de Fourier

La transformée de Fourier est une opération mathématique permettant de décomposer une fonction en fonctions oscillatoires. On l’utilise pour transformer un signal en ses fréquences constitutives. Les algorithmes de transformées de Fourier discrètes rapides sont essentielles pour le calcul de haute performance. Alors que l'algorithme trivial pour calculer une transformée de Fourier requiert O(N2) opérations, la transformée de Fourier rapide la réalise en O(N log N) opérations. Pour des grand nombres, cette différence devient colossale.

FFTW

La bibliothèque FFTW (pour Fastest Fourier Transform in the West), permet de réaliser ces opérations. Elle supporte les calculs séquentiels, à plusieurs fils d'exécution (threads) et MPI. Deux versions majeures de FFTW sont disponibles : FFTW2 et FFTW3. Ces deux versions sont incompatibles et leur interface est différente. La version FFTW2 est considérée comme obsolète et n'a pas été mise à jour depuis 1999.

Pour connaître les versions installées sur le serveur que vous utilisez, exécutez la commande

[nom@serveur $] module avail 2>&1 | grep -i fftw


MKL

La bibliothèque MKL d'Intel inclut sa propre version de FFTW optimisée pour les processeurs Intel.

Comparaison de performances

Un test de performance a été réalisé sur Colosse pour comparer la performance des différentes versions de FFTW. Les versions testées sont :

  • FFTW, version 3.2.2 - une bibliothèque en code source ouvert (disponible pour les compilateurs Intel et GCC);
  • FFTW, version 2.1.5 - la version précédente de FFTW pour la compatibilité avec les applications qui n’ont pas été modifiées pour utiliser FFTW 3.x (disponible pour les compilateurs Intel et GCC);
  • MKL - Math Kernel Library offre une implémentation hautement optimisée des transformées de Fourier discrètes.


Voici un aperçu des performances des diverses bibliothèques pour une transformée de Fourier à une dimension. Il s’agit du premier test du banc d’essai BenchFFT, réalisé sur Colosse en tâches séquentielles :

Bfftw-fr.png

Code source d'un exemple

Le fichier suivant contient un exemple de calcul d'une transformée de Fourier en cosinus pour une fonction réelle. Le code est en Fortran 90 :

Fichier : ex_fftwR2d.f90
! Ce programme calcule la transformée de Fourier en deux dimensions d'un produit de cosinus. Il s'agit de la transformée réelle
!
      Program test
      implicit none
      integer,parameter             :: fftw_cs =3, fftw_es =64, L=8
      real*8,parameter              :: div = 2*3.1415926535/L
      integer                       :: i, j
      integer*8                     :: plan1, plan2
      real*8,dimension(L/2+1,L/2+1) :: data1, data2
!
! Création des plans pour la transformée de Fourier
!
      call dfftw_plan_r2r_2d(plan1,L/2+1,L/2+1,data1,data1,fftw_cs,fftw_cs,fftw_es)
      call dfftw_plan_r2r_2d(plan2,L/2+1,L/2+1,data2,data2,fftw_cs,fftw_cs,fftw_es)
!
! Initialisation des données
!
      do i = 1, L/2+1
         do j = 1, L/2+1
            data1(j,i)=cos((i-1)*div)
            data2(j,i)=cos(3*(i-1)*div)
         end do
      end do
!
!  Appel des fonctions de transformation
!
      call dfftw_execute(plan1)
      call dfftw_execute(plan2)
!
!  Normalisation des transformées
!
      do i = 1, L/2+1
         do j = 1, L/2+1
            data1(j,i) = data1(j,i)/L/L
            data2(j,i) = data1(j,i)*data2(j,i)
         end do
      end do
!
! Refait la transformation pour montrer que l'on obtient la fonction initiale
!
      call dfftw_execute(plan1)
      call dfftw_execute(plan2)
!
! Destruction des plans
!
      call dfftw_destroy_plan(plan1)
      call dfftw_destroy_plan(plan2)
!
! Sorties
!
      open(unit=30,file='output.dat')
      write(30,fmt=100) ((data1(j,i), j=1,L/2+1),i= 1, L/2+1)
      write(30,fmt=100) ((data2(j,i), j=1,L/2+1),i= 1, L/2+1)
      close(30)
  100 format( 5( 5(e11.3,2x)/) )
      end


Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Ressources de Calcul Québec
Outils
Partager