Skalowalność szybkiej transformaty Fouriera (FFT)

Aby użyć szybkiej transformacji Fouriera (FFT) na danych o jednakowym próbkowaniu, np. W połączeniu z rozwiązaniami PDE, dobrze wiadomo, że FFT jest algorytmem ). Jak dobrze skala FFT jest przetwarzana równolegle dla n → ∞ (tj. Bardzo duża)?$\mathcal{O}(n\log(n)$$n\to\infty$

Jest to bardziej niepotwierdzony dowód niż udowodniony dowód, ale wydaje się, że istniejące implementacje dla FFT, takie jak FFTW , mają ograniczoną zdolność skalowania.

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

Ale przesłanie „do domu” jest takie, że FFT powinno się zwiększyć; jednak czasami pojawiają się nieoczekiwane ograniczenia i interakcje, które przechodzą od teoretycznego rozważenia wydajności algorytmu do jego praktycznej implementacji na rzeczywistej platformie HPC.

$O(n)$

$n$$d$$d$

Poszukiwanie „równoległego FFT” lub „skalowalności pseudospektralnej” w Google Scholar dostarcza wielu informacji, których nie mam kwalifikacji do oceny. Ale wydaje się, że jest to ładny niedawny przykład tego, co można osiągnąć w praktyce:

Hybrydowy schemat MPI-OpenMP dla skalowalnych równoległych obliczeń pseudospektralnych dla turbulencji płynów

Abstrakcyjny:

Przedstawiono schemat hybrydowy, który wykorzystuje MPI do równoległości pamięci rozproszonej i OpenMP do równoległości pamięci współużytkowanej. Praca jest motywowana chęcią osiągnięcia wyjątkowo wysokich liczb Reynoldsa w pseudospektralnych obliczeniach turbulencji płynów na powstających systemach petaskali, o dużej liczbie rdzeni, masywnie równoległych. Implementacja hybrydowa wywodzi się z dobrze przetestowanego, skalowalnego, równoległego do MPI kodu pseudospektralnego. Hybrydowy paradygmat prowadzi do nowego obrazu dekompozycji domen siatek pseudospektralnych, który pomaga między innymi zrozumieć trójwymiarową transpozycję globalnych danych, niezbędną do równoległych szybkich transformacji Fouriera, które są centralnym składnikiem dyskretyzacje numeryczne. Podane są szczegóły implementacji hybrydowej, a testy wydajności ilustrują użyteczność metody. Pokazano, że schemat hybrydowy osiąga niemal idealną skalowalność do ~ 20000 rdzeni obliczeniowych z maksymalną średnią wydajnością 83%. Prezentowane dane pokazują, jak wybrać optymalną liczbę procesów MPI i wątków OpenMP, aby zoptymalizować wydajność kodu na dwóch różnych platformach.

$O(n)$

$O(\log n)$

$O(n)$