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.