Um die schnelle Fourier-Transformation (FFT) für gleichmäßig abgetastete Daten zu verwenden, z. B. in Verbindung mit PDE-Solvern, ist es bekannt, dass die FFT ein ) -Algorithmus ist. Wie gut ist die FFT-Skalierung bei paralleler Verarbeitung für n → ∞ (dh sehr groß)?
pde
fftw
fourier-analysis
Allan P. Engsig-Karup
quelle
quelle
Antworten:
Dies ist eher ein anekdotischer Beweis als ein nachgewiesener Beweis, aber es scheint, dass vorhandene Implementierungen für FFTs , wie z. B. FFTW , ihre Skalierbarkeit einschränken.
Als wir damit begannen, LAMMPSs Raum-Löser in sehr großen Systemen ( O ( 10 7 ) Atome) einzusetzen , stellten wir fest, dass die Skalierung fortgesetzt wurde, solange wir die Anzahl der Prozessoren so klein halten konnten, dass sie auf ein Rack passen . Sobald wir versuchten, weiter zu expandieren (über 4K-Prozessoren, je nach Maschine), brach die Skalierung zusammen - anscheinend, weil die Kommunikationskosten für das Verschieben von Daten zwischen den Prozessoren zu hoch wurden, um die Skalierung aufrechtzuerhalten. [Um dieses Problem zu umgehen, wurde kürzlich die Möglichkeit eingeführt, der FFT-Berechnung eine bestimmte Partition der Prozessorzuordnung zuzuweisen.]k Ö ( 107)
Aber die Botschaft zum Mitnehmen ist hier, dass FFT skaliert werden sollte; Manchmal treten jedoch unerwartete Einschränkungen und Interaktionen auf, wenn man von der theoretischen Betrachtung der Leistung eines Algorithmus zu seiner praktischen Implementierung auf einer tatsächlichen HPC-Plattform übergeht.
quelle
quelle
Die Suche nach "paralleler FFT" oder "pseudospektraler Skalierbarkeit" in Google Scholar liefert eine Fülle von Informationen, die ich nicht beurteilen kann. Dies scheint jedoch ein schönes aktuelles Beispiel dafür zu sein, was in der Praxis erreicht werden kann:
Ein hybrides MPI-OpenMP-Schema für skalierbare parallele pseudospektrale Berechnungen für Fluidturbulenzen
Abstrakt:
quelle
Wenn Sie eine unendliche Anzahl von Prozessoren haben, kann die DFT in bestimmt werdenO ( n ) Zeit.
Im naiven Algorithmus können Sie jeden Ausgabepunkt auf einen separaten Knoten legen und diesen Fourier-transformierten Punkt in berechnenO ( logn ) Zeit. Jeder schnelle Algorithmus sollte in der Lage sein, diese Skalierung zumindest zu erreichen.
Sie müssen jedoch auch alle fouriertransformierten Punkte in einem Array sammeln, was dauertO ( n ) Zeit.
quelle