PACO: FFT Paralel yang Sepenuhnya Cache-Oblivious dengan Satu Redistribusi Global

Menyelaraskan komputasi lokal cache-oblivious dengan satu permutasi global untuk FFT paralel

Shina Guo; Weiguo Gao; Yuan Tang· 2026· DOI 10.48550/arXiv.2609.06449

Masalah inti

Fast Fourier transform (FFT) paralel menghadapi dua biaya perpindahan data yang berbeda: transfer lokal prosesor melalui hierarki memori dan redistribusi global antarprosesor. Organisasi FFT empat langkah mengurangi komunikasi global menjadi satu pertukaran mirip transpos dengan mengganti dimensi transformasi yang aktif, tetapi tidak menjamin komputasi lokal yang efisien terhadap cache. FFT cache-oblivious mencapai lalu lintas memori lokal yang optimal secara asimtotik melalui transformasi tata letak rekursif, namun mewujudkan tata letak tersebut dapat menimbulkan lintasan penataan ulang data tambahan dan pertukaran global tambahan. PACO mengatasi ketegangan ini dengan menggabungkan tahap lokal cache-oblivious dengan satu permutasi global yang digabungkan. Kerangka ini menargetkan komputasi DFT N-titik secara eksak di bawah model hybrid ideal-cache/BSP dengan dekomposisi slab basis-b yang eksak.

Di bawah dekomposisi slab basis-b yang eksak dalam model hybrid ideal-cache/BSP, PACO menghitung DFT N-titik secara eksak dengan kerja maksimum per prosesor Θ ((N / p) lo g N) dan kompleksitas cache maksimum per prosesor Θ ((N / (pB)) (1 + lo g_{M} N)), menggunakan tepat satu putaran redistribusi global. Di sini p adalah jumlah prosesor, B adalah ukuran cache line, dan M adalah ukuran cache. Volume komunikasi dari redistribusi tunggal ini optimal untuk permutasi gabungan dan distribusi slab sumber-target yang ditetapkan. Algoritma ini mengembalikan koefisien DFT logis kanonis di bawah kepemilikan slab target yang ditukar faktornya, sehingga menjamin kebenaran urutan keluaran.

Fast Fourier transform (FFT) paralel menghadapi dua biaya perpindahan data yang berbeda: transfer lokal prosesor melalui hierarki memori dan redistribusi global antarprosesor. Organisasi FFT empat langkah mengurangi komunikasi global menjadi satu pertukaran mirip transpos dengan mengganti dimensi transformasi yang aktif, tetapi tidak menjamin komputasi lokal yang efisien terhadap cache. FFT cache-oblivious mencapai lalu lintas memori lokal yang optimal secara asimtotik melalui transformasi tata letak rekursif, namun mewujudkan tata letak tersebut dapat menimbulkan lintasan penataan ulang data tambahan dan pertukaran global tambahan. PACO mengatasi ketegangan ini dengan menggabungkan tahap lokal cache-oblivious dengan satu permutasi global yang digabungkan. Kerangka ini menargetkan komputasi DFT N-titik secara eksak di bawah model hybrid ideal-cache/BSP dengan dekomposisi slab basis-b yang eksak.

PACO menjalankan tiga tahap: LocalFFT \to OneGlobalPermutation \to LocalFFT. Tahap lokal secara rekursif mempartisi dimensi transformasi dan batch tanpa pengetahuan tentang parameter cache. Alih-alih mewujudkan tata letak mirip transpos yang diinduksi oleh rekursi ini, PACO menundanya dan menunjukkan bahwa tata letak tersebut menyusun menjadi permutasi pembalikan digit basis-b. Permutasi ini digabungkan dengan redistribusi yang sudah diperlukan untuk mengubah dimensi transformasi lokal. Tahap tengah yang dihasilkan adalah permutasi pembalikan digit cache-oblivious paralel yang sepenuhnya seimbang di mana setiap pasangan prosesor sumber-tujuan menukar tepat N / p^{2} elemen. Kerangka ini mengasumsikan dekomposisi slab basis-b yang eksak dan model hybrid ideal-cache/BSP. Redistribusi tunggal ini diperlukan di bawah model kepemilikan tanpa replikasi yang dinyatakan, dan volume komunikasinya optimal untuk permutasi gabungan yang ditetapkan serta distribusi slab sumber-target. PACO mengembalikan koefisien DFT logis kanonis di bawah kepemilikan slab target yang ditukar faktornya.

PACO menyelaraskan dua tujuan yang sebelumnya bersaing: komputasi lokal cache-oblivious dan komunikasi global yang minimal. Dengan menunda transformasi tata letak rekursif dan menggabungkannya menjadi satu permutasi pembalikan digit, PACO menghindari lintasan penataan ulang data tambahan dan pertukaran global yang jika tidak akan muncul dari mewujudkan tata letak cache-oblivious. Redistribusi global tunggal ini terbukti diperlukan di bawah model kepemilikan tanpa replikasi, dan volumenya optimal untuk permutasi gabungan yang ditetapkan. Batas kerja dan kompleksitas cache sesuai dengan hasil asimtotik terbaik yang diketahui untuk FFT paralel sekaligus mencapai satu putaran komunikasi. Hal ini membuat PACO sangat cocok untuk mesin paralel berskala besar di mana komunikasi global merupakan biaya yang dominan. Penelitian selanjutnya dapat mengeksplorasi perluasan ke dekomposisi non-slab atau model kepemilikan yang direplikasi.

Praktisi dan peneliti ilmu komputer

Membuka konten member…