FFTW - Fastest Fourier Transform in the West

De Wiki de Calcul Québec
Aller à : Navigation, rechercher
Cette page est une traduction de la page FFTW - Fastest Fourier Transform in the West et la traduction est complétée à 100 % et à jour.

Autres langues :anglais 100% • ‎français 100%

Sommaire

Fourier Transforms

The Fourier transform is a mathematical operation that allows you to decompose a function into oscillatory functions. It is used to transform a signal into its characteristic frequencies. Fast algorithms for discrete Fourier transforms are essential for high performance computing. Although the most trivial algorithm to calculate a Fourier transform requires O(N2) operations, the fast Fourier transform does it in O(N log N) operations. For larger numbers, this difference becomes enormous.

FFTW

The FFTW library (for Fastest Fourier Transform in the West), allows the realization of these operations. It supports serial computations, threaded computations, and MPI. Two major versions of FFTW are available: FFTW2 and FFTW3. These two versions are incompatible and their interfaces are different. FFTW2 is now considered obsolete and has not been updated since 1999.

To get to know the versions that are installed on the server that you are using, run this command:

[name@server $] module avail 2>&1 | grep -i fftw


MKL

Intel's MKL library included its own version of FFTW which is optimized for Intel processors.

Performance Comparison

A performance test was done on Colosse to compare the performance of different FFTW versions. The tested versions are:

  • FFTW, version 3.2.2 - an open source library (available for Intel and GCC compilers);
  • FFTW, version 2.1.5 - the previous version of FFTW, for compatibility with applications that have not been changed to use FFTW 3.x (available for Intel and GCC compilers);
  • MKL - Math Kernel Library offers a highly optimized implementation of discrete Fourier transforms.


Here is an observation of the performance of the various libraries for a Fourier transform in one dimension. This is the first test of the test suite BenchFFT, done on Colosse in the form on serial jobs.

Bfftw-fr.png

Source code for an example

The following file contains an example of a Fourier transform computation into cosine functions for a real function. The code is written in Fortran 90:

File : ex_fftwR2d.f90
! This program compute the Fourier transform in two dimensions of a product of cosines. The transform used here is real (not complex).
!
      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
!
! Creating plans for the Fourier transform
!
      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)
!
! Initializing the data
!
      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
!
!  Calling functions that do the transform
!
      call dfftw_execute(plan1)
      call dfftw_execute(plan2)
!
!  Normalizing the transforms
!
      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
!
! Redo the transformation to show that we obtain the initial function
!
      call dfftw_execute(plan1)
      call dfftw_execute(plan2)
!
! Destroy the plans
!
      call dfftw_destroy_plan(plan1)
      call dfftw_destroy_plan(plan2)
!
! Output
!
      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