Skalowalność szybkiej transformaty Fouriera (FFT)

12

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)?O(nlog(n)n

Allan P. Engsig-Karup
źródło
1
Jestem trochę zmieszany. Czy mówisz o tym, jak czas wykonania skaluje się dla określonej liczby procesorów wraz ze wzrostem liczby punktów danych, jak czas wykonania skaluje się dla stałej liczby punktów danych wraz ze wzrostem liczby lub procesorów, lub jak skaluje się czas wykonania dla stały stosunek liczby punktów danych na procesor wraz ze wzrostem liczby punktów danych?
Geoff Oxberry
Zarówno słabe, jak i silne skalowanie.
Allan P. Engsig-Karup

Odpowiedzi:

8

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.

kO(107)

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.

eeismail
źródło
6

O(n)

Jed Brown
źródło
5

ndd

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.

David Ketcheson
źródło
1

O(n)

O(logn)

O(n)

Dan
źródło
1
W FFT istnieje znaczna ilość komunikacji, ale z pewnością nie jest konieczne (lub pożądane) zebranie wyniku w jednym węźle. Bardzo powszechnym zastosowaniem FFT jest bezpośrednia symulacja numeryczna turbulencji, w której stosuje się go do zastosowania nieliniowego terminu konwekcji w przestrzeni rzeczywistej, podczas gdy reszta symulacji jest wykonywana w przestrzeni Fouriera. To zdecydowanie nie wymaga serializacji wyniku. Ogólnie przy obliczeniach równoległych „duże” dane powinny zawsze być przechowywane i analizowane w formie rozproszonej.
Jed Brown