FFTW
Wprowadzenie¶
FFTW (Fastest Fourier Transform in the West) to zoptymalizowana biblioteka pozwalającą na wykonywanie operacji z dziedziny FFT czyli szybkiej transformacji Fouriera (Fast Fourier Transform). Jest to wydajna implementacja umożliwiająca obliczenia zrównoleglone – zarówno wielowątkowe jak i rozproszone. Przewidziana do obliczeń na CPU.
Dostępność¶
Biblioteka jest napisana w języku ANSI C. Posiada interfejs dla języka C, naturalnie można z niej korzystać w C++. Udostępnia również (od wersji 3.3) interfejs dla języka Fortran. Poprzez dodatkowe wrappery możliwe jest udostępniane jej API w innych językach. Przykładowo moduł pyFFTW udostępnia możliwości tej biblioteki dla języka Python.
Szczegóły¶
FFTW to jedna z najbardziej efektywnych bibliotek numerycznych używanych do operacji związanych z szybką transformatą Fouriera FFT. Dokładniej mówiąc, biblioteka umożliwia wyznaczanie jedno- lub wielowymiarowej dyskretnej transformaty Fouriera (DFT). Wspiera różne architektury procesorów (x86, x86_64, ARM). Wielowątkowość w FFTW może być oparta o pthreads (wątki POSIX) lub OpenMP. Obliczenia rozproszone są oparte o MPI.
FFTW często jest używana jako punkt odniesienia dla innych bibliotek z dziedziny FFT (patrz Implementacje ). Z uwagi na jej dostępność, popularność oraz wydajność można uznać ją za bibliotekę referencyjną w tej dziedzinie. Jej najważniejsze cechy to:
- szybkość – obsługuje rozszerzenia AVX oraz ARM Neon,
- transformacje o dowolnym rozmiarze,
- efektywna obsługa wielu transformacji krokowych,
- transformacje równoległe,
- przenośność – dostępna dla każdej platformy obsługującej kompilator języka C.
Informacje o wydaniu¶
Najnowsze wydanie biblioteki to 3.3.10, które zostało opublikowane we wrześniu 2021. Dostępna jest również wersja 2.1.5 z roku 1999, która jest ostatnim wydaniem biblioteki w wersji 2.x, niekompatybilnej z nowszymi wydaniami.
Przykładowy sposób linkowania dla kompilatora GNU GCC
Linkowanie FFTW odbywa się w zależności od rodzaju linkowanej biblioteki:
- Wersja szeregowa:
gcc -o start start.c -lfftw3 - Wersja z obsługą pamięci współdzielonej poprzez wątki POSIX:
gcc -o start start.c -lfftw3 -lfftw3_threads - Wersja z obsługą pamięci współdzielonej poprzez interfejs OpenMP, może zapewnić lepszą wydajność niż wątki POSIX:
gcc -o start start.c -lfftw3 -lfftw3_omp - Wersja z obsługą pamięci rozproszonej ze wsparciem MPI:
mpicc -o start start.c -lfftw3 -lfftw3_mpi
Implementacje¶
Poszczególni dostawcy jednostek obliczeniowych dostarczają swoje własne implementacje bibliotek obsługujące algorytmy z dziedziny FFT. Zwykle bazują one na kodzie FFTW lub udostępniają zbliżony interfejs. Implementacje producentów są zoptymalizowane pod kątem własnego sprzętu, dlatego warto porównać wydajność osiąganą przez FFTW z tymi zoptymalizowanymi wersjami.
-
Intel oneMKL – Wersja zoptymalizowana pod procesory Intel
- posiada swoje własne API (patrz funkcje FFT w oneMKL),
- umożliwia korzystanie z interfejsu FFTW (patrz interfejs FFTW dla oneMKL).
-
AMD AOCL-FFTW – Wersja zoptymalizowana pod procesory AMD.
Dostępne są również implementacje korzystające z akceleratorów GPU.
- cuFFT – Wersja dla GPU firmy NVIDIA, korzystająca z modelu CUDA.
- rocFFT – Wersja dla GPU firmy AMD, napisana w modelu HIP. Dostępna jest również wersja hipFFT, będąca interfejsem zarówno do cuFFT jak i rocFFT.
Linki¶
- strona FFTW
- dokumentacja
- repozytorium – zawiera wyłącznie generator kodu, nie sam kompilowalny kod