Skalabilitas Fast Fourier Transform (FFT)

Untuk menggunakan Fast Fourier Transform (FFT) pada data sampel yang seragam, misalnya dalam kaitannya dengan pemecah PDE, diketahui bahwa FFT adalah algoritma ). Seberapa baik skala FFT saat diproses secara paralel untuk n → ∞ (yaitu sangat besar)?$\mathcal{O}(n\log(n)$$n\to\infty$

Ini lebih merupakan bukti anekdotal daripada bukti yang diperlihatkan, tetapi tampaknya implementasi yang ada untuk FFT, seperti FFTW , memiliki batas untuk kemampuan penskalaan mereka.

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

Tetapi pesan yang bisa dibawa pulang di sini adalah bahwa FFT harus ditingkatkan; namun, kadang-kadang ada batasan dan interaksi tak terduga yang berperan ketika seseorang bergerak dari pertimbangan teoretis kinerja algoritma ke implementasi praktisnya pada platform HPC yang sebenarnya.

$O(n)$

$n$$d$$d$

Mencari "parallel FFT" atau "skalabilitas pseudospectral" di Google Cendekia menghasilkan banyak informasi yang saya tidak memenuhi syarat untuk menilai. Tapi ini sepertinya contoh baru yang bagus dari apa yang bisa dicapai dalam praktik:

Skema MPI-OpenMP hybrid untuk komputasi pseudospectral paralel yang dapat diskalakan untuk turbulensi fluida

Abstrak:

Skema hybrid yang memanfaatkan MPI untuk paralelisme memori terdistribusi dan OpenMP untuk paralelisme memori bersama disajikan. Pekerjaan ini dimotivasi oleh keinginan untuk mencapai angka Reynolds yang sangat tinggi dalam perhitungan pseudospectral turbulensi fluida pada sistem pemrosesan petrosale, hitung inti, dan paralel besar yang muncul secara masal. Implementasi hybrid berasal dari dan menambah kode pseudospectral paralel-terukur MPI yang teruji dengan baik. Paradigma hibrida mengarah ke gambar baru untuk dekomposisi domain dari pseudospectral grids, yang membantu dalam memahami, antara lain, transpos 3D dari data global yang diperlukan untuk transformasi cepat Fourier paralel yang merupakan komponen utama dari diskritisasi numerik. Rincian implementasi hibrida disediakan, dan tes kinerja menggambarkan kegunaan metode ini. Terlihat bahwa skema hybrid mencapai skalabilitas mendekati ideal hingga ~ 20000 core komputasi dengan efisiensi rata-rata maksimum 83%. Data disajikan yang menunjukkan cara memilih jumlah optimal proses MPI dan utas OpenMP untuk mengoptimalkan kinerja kode pada dua platform yang berbeda.

$O(n)$

$O(\log n)$

$O(n)$