Algorytmy obliczania FFT równolegle


12

Próbuję zrównoleglić obliczenia FFT na plikach sygnałowych wielkości terabajta. W tej chwili taka FFT przy użyciu biblioteki open source zajmuje wiele godzin, nawet przez CUDA na najszybszym GPU, jaki mam. Framework, który próbuję dostosować do tego procesu, to Hadoop. Mówiąc bardzo prosto, Hadoop rozdziela problem na dowolną liczbę węzłów serwera w następujący sposób:

• Dzielisz plik wejściowy na pary (klucz, wartość).
• Pary te są wprowadzane do algorytmu „Mapa”, który przekształca pary (klucz, wartość) w inne pary (klucz, wartość) na podstawie tego, co umieścisz w Mapie.
• Framework gromadzi następnie wszystkie dane wyjściowe (klucz, wartość) z map i sortuje je według klucza, a także agreguje wartości z tym samym kluczem do pojedynczej pary, więc otrzymujesz (klucz, lista (wartość1, wartość2, ..)) pary
• Pary te są następnie wprowadzane do algorytmu „Zmniejsz”, który z kolei generuje więcej par (klucz, wartość) jako wynik końcowy (zapisywany do pliku).

Istnieje wiele aplikacji dla tego modelu w praktycznych rzeczach, takich jak przetwarzanie dzienników serwera, ale mam trudności z zastosowaniem frameworka do dzielenia FFT na „mapowanie” i „redukowanie” zadań, zwłaszcza, że ​​tak naprawdę nie jestem zaznajomiony z DSP.

Nie będę ci przeszkadzać w programowaniu mumbo jumbo, ponieważ jest to pytanie dotyczące DSP. Jestem jednak zdezorientowany, jakie algorytmy istnieją do równoległego obliczania FFT; Zadania mapowania i ograniczania nie mogą (technicznie) ze sobą rozmawiać, dlatego FFT musi zostać podzielone na niezależne problemy, z których wyniki można w jakiś sposób połączyć na końcu.

Zaprogramowałem prostą implementację Dole Cooley-Tukey Radix 2, która działa na małych przykładach, ale użycie jej do rekurencyjnego obliczania indeksów DFT nieparzystych / parzystych dla miliarda bajtów nie będzie działać. Spędziłem kilka tygodni na czytaniu wielu artykułów, w tym jednego na temat algorytmu MapReduce FFT (napisanego przez Tsz-Wo Sze w ramach jego pracy na temat mnożenia SSA, nie mogę połączyć więcej niż 2 hiperłączy) i „czterostopniowego FFT” ( tu i tutaj), które wydają się podobne do siebie i do tego, co próbuję osiągnąć. Jestem jednak beznadziejnie zła w matematyce, a zastosowanie którejkolwiek z tych metod ręcznie do prostego zestawu czegoś takiego jak {1,2, 3, 4, 5, 6, 7, 8} (przy wszystkich wyimaginowanych elementach równych 0) daje mi bardzo niepoprawne wyniki. Czy ktoś może mi wyjaśnić skuteczny równoległy algorytm FFT prostym językiem angielskim (tym, który podłączyłem lub dowolnym innym), abym mógł spróbować go zaprogramować?

Edycja: Jim Clay i wszyscy inni, którzy mogą być zdezorientowani moim wyjaśnieniem, próbuję zrobić jedną FFT pliku terabajta. Ale chcę to zrobić jednocześnie na wielu serwerach, aby przyspieszyć ten proces.


1
Co dokładnie próbujesz osiągnąć? Czy chcesz zrobić jedną FFT pliku sygnału terabajtowego, czy wiele mniejszych FFT każdego pliku?
Jim Clay

Odpowiedzi:


13

ej2πkNN=240

Będziesz także gromadzić wiele błędów zaokrąglania i obcinania, ponieważ sama liczba operacji, które przechodzą w jedną liczbę wyjściową, jest również bardzo duża. Ze względu na naturę FFT „każde wyjście zależy od każdego wejścia”, propagacja błędów jest powszechna.

Nie wiem, jak łatwo to obejść. Twoja prośba jest nietypowa. Większość aplikacji, które wykonują analizę spektralną dużych zestawów danych, wykonuje bieżącą analizę, w której nie ma tego problemu. Być może, jeśli potrafisz opisać swoją aplikację, a jest to jeszcze więcej ograniczeń, możemy wskazać Ci bardziej odpowiednie rozwiązanie.


Całkiem słuszna uwaga. Będę musiał więcej o tym pomyśleć. Może w końcu skorzystam z „bieżącej analizy”, jak pan powiedział.
Philipp

Wiem, że jestem naprawdę spóźniony, ale czy przypadkiem masz źródło, jak to zrobić, skoro wspomniałeś, że można to zrobić?
Claudio Brasser

4

Zamiast próbować ponownie napisać FFT, możesz spróbować użyć istniejącej implementacji FFT (takiej jak na przykład FFTW ) i zastosować ją powtarzalnie wzdłuż długości twojego sygnału (bez względu na to, jak duży jest) poprzez albo overlap-add lub overlap- zapisz metody. Jest to możliwe, wyrażając FFT jako splot .

Te krótsze FFT nie muszą się ze sobą komunikować, a cały schemat odpowiada krokom zmniejszania mapy.

Ogólnie rzecz biorąc, Twoim celem byłoby podzielenie sygnału X na mniejsze segmenty, które również mogą się nakładać (na przykład X [0:10], X [5:15], X [10:20] ... .). Wykonaj FFT na tych małych segmentach i połącz je na końcu, aby uzyskać końcowy. To bardzo dobrze pasuje do operatorów zmniejszających mapę.

Podczas „mapy” można wygenerować pary (klucz, wartość), gdzie „klucz” jest jakimś kolejnym identyfikatorem każdego segmentu (0,1,2,3,4,5, ....), a „wartość” jest INDEKS (lub pozycja pliku) pierwszej wartości segmentu w pliku twojego sygnału. Na przykład, jeśli twój plik jest pełen INT32, wówczas indeks drugiego segmentu (powyżej) ma 5 * sizeof (INT32). (Lub jeśli jest w innym formacie, możesz mieć dla niego bibliotekę lib)

Teraz każdy pracownik otrzymuje (klucz, wartość) otwiera plik, szuka właściwego punktu, odczytuje z niego M próbek (gdzie M wynosi 10 powyżej), wykonuje FFT i zapisuje go w pliku o pewnej nazwie, na przykład „ RES_ [INKEY] .dat ”i zwraca parę (klucz, wartość). W tym przypadku „kluczem” byłby INDEKS („wartość” przychodzącej krotki (klucz, wartość)), a „wartość” byłaby nazwą pliku zawierającego wyniki FFT. (wrócimy do tego)

W ramach „zmniejszania” możesz teraz wdrożyć dodawanie nakładania lub zapisywanie nakładania poprzez akceptację (klucza, wartości) z kroku „mapy”, otwieranie tego pliku, ładowanie wyników FFT, wykonywanie operacji OA lub OS, a następnie zapisywanie ich w właściwy INDEKS w pliku wyjściowym. (Patrz pseudokod w tym (lub tym ), krok „mapa” obsługuje równolegle „yt = ...”, a krok „zmniejsz” obsługuje część „y (i, k) = ...”).

W tym przypadku może być potrzebne żonglerka plików w celu zmniejszenia ruchu w sieci lub obciążenia serwera, który może zawierać rzeczywisty plik danych.


1
Nie jestem pewien co do ważności nakładania-dodawania i nakładania-zapisywania w celu łączenia mniejszych porcji w celu odzyskania większego rozmiaru FFT - o ile wiem, że do tego jest konieczne drugie przejście FFT (DFT o rozmiarze N = AB można podzielić na A DFT wielkości B, zastosowanie współczynnika zmienności, a następnie B DFT wielkości A). Może to zadziałać, jeśli chcemy uzyskać wyjście o niższej rozdzielczości ...
piknety

Witam licencje, dziękuję za to, co miałem na myśli to ( engineeringproductivitytools.com/stuff/T0001/PT11.HTM ), które uwzględnię w odpowiedzi.
A_A

2

2N

2N/2N/22N/2

Mówiąc dokładniej, nie ma potrzeby używania MR podczas całej rekurencji, będzie to rzeczywiście dość nieefektywne. Twój problem można podzielić na milion wewnętrznych i zewnętrznych FFT o wielkości megabajtów, a te FFT w megabajtach można idealnie obliczyć za pomocą FFTW lub podobnego. MR będzie po prostu odpowiedzialny za nadzorowanie tasowania i rekombinacji danych, a nie rzeczywiste obliczenia FFT ...

Mój pierwszy pomysł byłby następujący, ale podejrzewam, że można to zrobić w jednym MR z bardziej inteligentną reprezentacją danych.

sR=2N/2

Pierwszy MR: wewnętrzny FFT

Mapa: wykonaj decymację w czasie, grupuj próbki w bloki dla wewnętrznego FFT

(k,v)k0..2N1vs[k]

(k%R,(k/R,v))

Zmniejsz: oblicz wewnętrzny FFT

(k,vs)kvs(i,v)

inRin[i]=v

RinoutR

i0..R1(k,(i,out[i]))

Drugi MR: zewnętrzny FFT

Mapa: grupuj próbki dla zewnętrznego fft i zastosuj współczynniki drgań

(k,(i,v))k(i,v)

(i,(k,v×exp2πjik2N))

Zmniejsz: wykonaj zewnętrzną FFT

(k,vs)kvs(i,v)

inRin[i]=v

RinoutR

i0..R1(i×R+k,out[i]))

Dowód koncepcji kodu Pythona tutaj.

Jak widać, Mapperzy zmieniają tylko kolejność danych, więc przy następujących założeniach:

  • dziesiątkowanie w czasie (program mapujący 1) można wykonać w poprzednim kroku (na przykład przez program, który konwertuje dane do odpowiedniego formatu wejściowego).
  • Twój szkielet MR obsługuje Redukcje zapisujące do klucza innego niż ich klucz wejściowy (w implementacji Google reduktory mogą wysyłać dane tylko do tego samego klucza, w którym je otrzymały, myślę, że jest to spowodowane tym, że SSTable jest używany jako format wyjściowy).

Wszystko to można zrobić w jednym MR, wewnętrznym FFT w module odwzorowującym, zewnętrznym FFT w reduktorze. Dowód koncepcji tutaj .


Twoja implementacja wydaje się obiecująca i właśnie ją przechodzę, ale w wewnętrznej reduktorze FFT piszesz „wykonaj FFT o rozmiarze 2 ^ R, aby uzyskać wektor o rozmiarze 2 ^ R”. Jeśli R wynosi 2 ^ (N / 2), to czy ta FFT nie będzie miała rozmiaru 2 ^ (2 ^ N / 2), a zatem jest nieprawidłowa? Czy chodziło Ci o FFT o rozmiarze R?
Philipp

R2Rexp2πjik2N

0

Jeśli twój sygnał jest wielowymiarowy, to równoległe FFT można osiągnąć dość łatwo; zachowaj ciągłość jednego wymiaru w procesie MPI, wykonaj FFT i transponuj (alttoall), aby pracować nad następnym wymiarem. FFTW to robi.

Jeśli dane to 1D, problem jest znacznie trudniejszy. Na przykład FFTW nie napisał 1D FFT przy użyciu MPI. Jeśli używa się algorytmu dziesiętnego w częstotliwości Radix-2, wówczas kilka pierwszych etapów można wykonać jako naiwny DFT, co pozwala na użycie 2 lub 4 węzłów bez utraty precyzji (dzieje się tak dlatego, że korzenie jedności dla pierwsze etapy to -1 lub i, które są fajne do pracy).

Nawiasem mówiąc, co planujesz zrobić z danymi po ich przekształceniu? Można to zrobić, jeśli wiadomo, co dzieje się z wyjściem (np. Splot, filtr dolnoprzepustowy itp.).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.