Algoritma untuk menghitung FFT secara paralel

12

Saya mencoba memparalelkan perhitungan FFT pada file sinyal berukuran terabyte. Saat ini FFT seperti menggunakan perpustakaan open-source membutuhkan waktu berjam-jam, bahkan berjalan melalui CUDA pada GPU tercepat yang saya miliki. Kerangka kerja saya mencoba untuk beradaptasi dengan proses ini adalah Hadoop. Dalam istilah yang sangat mendasar, Hadoop mendistribusikan masalah pada sejumlah node server dengan cara berikut:

• Anda membagi file input Anda menjadi pasangan (kunci, nilai).
• Pasangan ini dimasukkan ke dalam algoritma "Peta", yang mengubah pasangan (kunci, nilai) Anda menjadi pasangan (kunci, nilai) lainnya berdasarkan apa yang Anda masukkan ke dalam Peta.
• Kerangka kerja kemudian mengumpulkan semua output (kunci, nilai) dari Peta dan mengurutkannya berdasarkan kunci, serta mengumpulkan nilai dengan kunci yang sama untuk satu pasangan, sehingga Anda berakhir dengan (kunci, daftar (nilai1, nilai2, ..)) pasangan
• Pasangan ini kemudian dimasukkan ke dalam algoritma "Reduce", yang pada gilirannya menghasilkan lebih banyak (kunci, nilai) pasangan sebagai hasil akhir Anda (ditulis ke file).

Ada banyak aplikasi untuk model ini dalam hal-hal praktis seperti pemrosesan log server, tetapi saya mengalami kesulitan menerapkan kerangka kerja untuk memotong FFT menjadi tugas-tugas "peta" dan "mengurangi", terutama karena saya tidak terlalu mengenal DSP.

Saya tidak akan mengganggu Anda dengan pemrograman omong kosong, karena ini adalah Tanya Jawab DSP. Namun, saya bingung tentang algoritma apa yang ada untuk menghitung FFT secara paralel; Tugas-tugas Map dan Reduce tidak dapat (secara teknis) berbicara satu sama lain, sehingga FFT harus dipecah menjadi masalah-masalah independen yang hasilnya dapat digabungkan kembali pada akhirnya.

Saya telah memprogram implementasi sederhana dari Cooley-Tukey Radix 2 DIT yang bekerja pada contoh-contoh kecil, tetapi menggunakannya untuk menghitung DFT indeks ganjil / genap secara berulang untuk satu miliar byte tidak akan berfungsi. Saya telah menghabiskan beberapa minggu untuk membaca banyak makalah, termasuk satu di algoritma FFT MapReduce (ditulis oleh Tsz-Wo Sze sebagai bagian dari makalahnya tentang perkalian SSA, saya tidak dapat menghubungkan lebih dari 2 hyperlink) dan "FFT empat langkah" (di sini dan di sini), yang tampak mirip satu sama lain dan dengan apa yang saya coba capai. Namun, saya sangat buruk dalam matematika, dan menerapkan salah satu dari metode-metode itu dengan tangan ke perangkat sederhana seperti {1,2, 3, 4, 5, 6, 7, 8} (dengan semua komponen imajiner menjadi 0) memberikan saya hasil yang sangat salah. Adakah yang bisa menjelaskan algoritma FFT paralel yang efisien kepada saya dalam bahasa Inggris biasa (yang saya tautkan atau lainnya) sehingga saya dapat mencoba dan memprogramnya?

Sunting: Jim Clay dan siapa pun yang mungkin bingung dengan penjelasan saya, saya mencoba melakukan FFT tunggal dari file terabyte. Tetapi saya ingin dapat melakukannya bersamaan pada beberapa server untuk mempercepat proses.

fft Philipp
sumber

1

Apa yang sebenarnya ingin Anda capai? Apakah Anda ingin melakukan FFT tunggal dari file sinyal terabyte, atau beberapa FFT lebih kecil dari setiap file?

Jim Clay

13

Saya pikir masalah utama Anda bukan bagaimana memparalelkan algoritme (yang sebenarnya bisa dilakukan) tetapi ini adalah ketepatan angka. FFT dengan ukuran yang besar secara numerik cukup rumit. Koefisien FFT adalah dalam bentuk dan jika N sangat besar maka perhitungan koefisiennya menjadi berisik. Katakanlah Anda memiliki dan Anda menggunakan aritmatika presisi ganda 64 bit. 1000 koefisien pertama memiliki bagian nyata yang persis bersatu (meskipun seharusnya tidak seperti itu) sehingga Anda akan membutuhkan matematika presisi yang lebih tinggi, yang sangat tidak efisien dan rumit untuk digunakan. $e^{-j\cdot 2\cdot \pi \cdot \frac{k }{N}}$ $N = 2^{40}$

Anda juga akan mengumpulkan banyak kesalahan pembulatan dan pemotongan karena banyaknya operasi yang masuk ke nomor output tunggal juga sangat besar. Karena sifat "setiap output tergantung pada setiap input" FFT, propagasi kesalahan merajalela.

Saya tidak menyadari cara mudah untuk mengatasinya. Permintaan Anda tidak biasa. Sebagian besar aplikasi yang melakukan analisis spektral dari kumpulan data besar melakukan analisis berjalan di mana Anda tidak memiliki masalah itu. Mungkin jika Anda dapat mendeskripsikan aplikasi Anda dan kendala yang ada tetapi lebih, kami dapat mengarahkan Anda ke solusi yang lebih cocok.

Hilmar
sumber

Poin yang cukup valid .. Saya harus berpikir lebih banyak tentang yang ini. Mungkin saya akan menggunakan "analisis berjalan" pada akhirnya, seperti yang Anda katakan.

Philipp

Saya tahu saya benar-benar terlambat, tetapi apakah Anda, secara kebetulan, memiliki sumber tentang bagaimana hal itu dapat dilakukan, karena Anda menyebutkan bahwa hal itu dapat dilakukan?

Claudio Brasser

4

Alih-alih mencoba menulis ulang FFT Anda bisa mencoba menggunakan implementasi FFT yang ada (seperti FFTW misalnya) dan menerapkannya secara berulang sepanjang sinyal Anda (tidak peduli seberapa besar itu) baik melalui tumpang tindih tambah atau tumpang tindih- simpan metode. Ini dimungkinkan dengan menyatakan FFT sebagai konvolusi .

FFT dengan panjang lebih pendek ini tidak perlu saling berkomunikasi dan keseluruhan skema cocok dengan langkah-langkah pengurangan peta.

Secara umum, yang ingin Anda lakukan adalah membuat sinyal X Anda dipecah menjadi segmen yang lebih kecil yang juga bisa tumpang tindih (misalnya X [0:10], X [5:15], X [10:20] ... .). Lakukan FFT pada segmen kecil ini dan gabungkan kembali pada akhirnya untuk menghasilkan yang terakhir. Ini sangat cocok dengan operator pengurang peta.

Selama "peta" Anda dapat menghasilkan pasangan (kunci, nilai) dengan "kunci" menjadi beberapa ID berurutan dari setiap segmen (0,1,2,3,4,5, ....) dan "nilai" menjadi INDEX (atau posisi file) dari nilai pertama segmen dalam file sinyal Anda. Jadi, misalnya, jika file Anda penuh dengan INT32s maka indeks segmen kedua (di atas) adalah 5 * sizeof (INT32). (Atau jika itu dalam format lain, Anda mungkin memiliki lib untuk itu)

Sekarang, setiap pekerja menerima (kunci, nilai) membuka file, mencari ke titik yang tepat, membaca sampel M dari itu (di mana M adalah 10 di atas), melakukan FFT dan menyimpannya ke file dengan beberapa nama, misalnya " RES_ [INKEY] .dat "dan mengembalikan pasangan (kunci, nilai). Dalam hal ini, "kunci" akan menjadi INDEX ("nilai" dari tuple masuk (kunci, nilai)) dan "nilai" akan menjadi nama file yang berisi hasil FFT. (kami akan kembali ke ini)

Dalam "kurangi" Anda sekarang dapat menerapkan tumpang tindih-tambah atau tumpang tindih-simpan dengan menerima (kunci, nilai) dari langkah "peta", membuka file itu, memuat hasil FFT, melakukan oa atau os kemudian menyimpannya ke INDEX tepat di file output Anda. (Lihat pseudocode dalam hal ini (atau ini ), langkah "peta" menangani "yt = ..." secara paralel dan langkah "mengurangi" menangani bagian "y (i, k) = ...".)

Beberapa juggling file mungkin diperlukan di sini untuk mengurangi lalu lintas di jaringan atau memuat server yang mungkin berisi file data aktual Anda.

A A
sumber

1

Saya tidak yakin tentang validitas tumpang tindih-tambahkan dan tumpang tindih-simpan untuk menggabungkan bongkahan yang lebih kecil untuk mengambil FFT ukuran yang lebih besar - sejauh yang saya tahu ada lintasan kedua FFT yang diperlukan untuk melakukan itu (DFT berukuran N = AB dapat dipecah menjadi A DFT ukuran B, aplikasi faktor dua arah, kemudian B DFT ukuran A). Ini mungkin bekerja jika kita menginginkan output resolusi yang lebih rendah ...

pichenettes

Halo picenettes, terima kasih untuk ini, yang ada dalam pikiran saya adalah ini ( engineeringproductivitytools.com/stuff/T0001/PT11.HTM ) yang akan saya sertakan dalam jawabannya.

A_A

2

Mari kita berasumsi bahwa ukuran data Anda . Pad dengan nol sebaliknya. Dalam kasus Anda, karena Anda menyebutkan ukuran "skala Terabyte", kami akan mengambil N = 40. $2^N$

Karena adalah besar - tetapi benar-benar masuk akal untuk satu mesin - ukuran FFT, saya sarankan Anda untuk melakukan satu saja pengulangan Cooley-Tukey dari radix , dan kemudian biarkan perpustakaan FFT yang tepat (seperti FFTW) melakukan pekerjaan pada setiap mesin untuk ukuran yang lebih kecil . $2^{N / 2}$ $N / 2$ $2 ^{N / 2}$

Untuk lebih eksplisit, tidak perlu menggunakan MR sepanjang rekursi keseluruhan, ini memang akan sangat tidak efisien. Masalah Anda dapat dipecah menjadi jutaan FFT dalam dan luar ukuran megabyte, dan FFT megabyte tersebut dapat dengan sempurna dihitung menggunakan FFTW atau sejenisnya. MR hanya akan bertanggung jawab untuk mengawasi pengacakan dan rekombinasi data, bukan perhitungan FFT yang sebenarnya ...

Gagasan pertama saya adalah sebagai berikut, tetapi saya menduga ini dapat dilakukan dalam satu MR tunggal dengan representasi data yang lebih cerdas.

Biarkan menjadi Anda sinyal input, $s$ $R = 2^{N / 2}$

MR pertama: inner FFT

Peta: melakukan penipisan dalam waktu, kelompokkan sampel dalam blok untuk FFT dalam

input: mana adalah indeks sampel dalam ; nilai yang diambil oleh $(k, v)$ $k$ $0 .. 2^N - 1$ $v$ $s[k]$

emit: - di mana% merupakan divisi modulo dan / integer. $(k \% R, (k / R, v))$

Kurangi: hitung FFT dalam

masukan: di mana adalah indeks blok; dan adalah daftar pasangan $(k, vs)$ $k$ $vs$ $(i, v)$

mengisi vektor ukuran sedemikian rupa sehingga untuk semua nilai dalam daftar. $in$ $R$ $in[i] = v$

melakukan ukuran FFT di untuk mendapatkan vektor dari ukuran $R$ $in$ $out$ $R$

untuk in , emit $i$ $0 .. R - 1$ $(k, (i, out[i]))$

MR kedua: FFT luar

Peta: kelompokkan sampel untuk fft luar dan terapkan faktor dua arah

input: mana adalah indeks blok, sampel FFT dalam untuk blok ini. $(k, (i, v))$ $k$ $(i, v)$

memancarkan $(i, (k, v \times \exp \frac{-2 \pi j i k}{2 ^ N}))$

Kurangi: lakukan FFT luar

masukan: di mana adalah indeks blok; dan adalah daftar pasangan $(k, vs)$ $k$ $vs$ $(i, v)$

mengisi vektor ukuran sedemikian rupa sehingga untuk semua nilai dalam daftar. $in$ $R$ $in[i] = v$

melakukan ukuran FFT di untuk mendapatkan vektor dari ukuran $R$ $in$ $out$ $R$

untuk dalam , lepaskan $i$ $0 .. R - 1$ $(i \times R + k, out[i]))$

Bukti konsep kode python di sini.

Seperti yang Anda lihat, Pemetaan hanya mengacak urutan data, jadi berdasarkan asumsi berikut:

penipisan dalam waktu (Mapper 1) dapat dilakukan pada langkah sebelumnya (misalnya oleh program yang mengubah data menjadi format input yang benar).
Kerangka kerja MR Anda mendukung Reducers menulis ke kunci yang berbeda dari kunci input mereka (Dalam implementasi Google reduksi hanya dapat menampilkan data ke kunci yang sama dengan yang mereka terima, saya pikir itu karena SSTable digunakan sebagai format output).

Semua ini dapat dilakukan dalam satu MR tunggal, FFT dalam di mapper, FFT luar di peredam. Bukti konsep di sini .

pichenettes
sumber

Implementasi Anda tampaknya menjanjikan dan saya akan melewatinya sekarang, tetapi di bagian dalam FFT reducer, Anda menulis "lakukan ukuran 2 ^ R FFT dalam untuk mendapatkan vektor dari ukuran 2 ^ R". Jika R adalah 2 ^ (N / 2), bukankah FFT ini berukuran 2 ^ (2 ^ N / 2), dan karenanya salah? Apakah maksud Anda FFT ukuran R?

Philipp

Ya, sepertinya saya mencampur dan di beberapa tempat ... diedit. Perhatikan bahwa komentar Hilmar berlaku untuk pendekatan saya - Anda harus menggunakan presisi yang lebih tinggi daripada dua kali lipat jika tidak, beberapa faktor twiddle ( ) akan memiliki bagian nyata 1 sementara mereka seharusnya tidak - mengarah ke ketidakakuratan numerik.

R

$R$

2^{R}

$2^R$

\exp \frac{- 2 π j i k}{2^{N}}

$\exp \frac{-2 \pi j i k}{2^N}$

pichenettes

0

Jika sinyal Anda multi-dimensi, maka memparalelkan FFT dapat dilakukan dengan cukup mudah; pertahankan satu dimensi secara berdampingan dalam proses MPI, lakukan FFT, dan transpos (altoall) untuk bekerja pada dimensi berikutnya. FFTW melakukan ini.

Jika datanya 1D, masalahnya jauh lebih sulit. FFTW, misalnya, tidak menulis FFT 1D menggunakan MPI. Jika seseorang menggunakan algoritma frekuensi-dalam-frekuensi radix-2, maka beberapa tahap pertama dapat dilakukan sebagai DFT naif, memungkinkan seseorang untuk menggunakan 2 atau 4 node tanpa kehilangan presisi (ini karena akar persatuan untuk tahap pertama adalah -1 atau i, yang bagus untuk digunakan).

Secara kebetulan, apa yang Anda rencanakan dengan data begitu Anda mengubahnya? Mungkin melakukan sesuatu jika orang tahu apa yang terjadi pada output (yaitu konvolusi, filter low-pass, dll).

Malcolm
sumber

Algoritma untuk menghitung FFT secara paralel

Jawaban:

MR pertama: inner FFT

MR kedua: FFT luar