Algoritme Fast Fourier Transform (FFT) dan Implementasinya pada Parallel Virtual Machine (PVM)

Abstract

Algoritme Fast Fourier Transform (FFT) merupakan algoritme yang efisien untuk menghitung Discrete Fourier Transform (DFT), tetapi untuk data yang besar masih diperlukan waktu eksekusi yang cukup besar. Salah satu cara mengurangi waktu eksekusi adalah dengan mengimplementasikan algoritme FFT itu pada komputer yang berkinerja lebih baik. Diantara versi-versi algoritme FFT yang populer, algoritme FFT Split Radix mempunyai cacah perkalian dan penjumlahan terkecil. Penelitian ini membahas implementasi yang efisien dari algoritme FFT Split Radix pada Parallel Virtual Machine (PVM), setelah algoritme FTT Split Radix itu dipararelkan dengan metode Alternating Sequential-Parallel (ASP). Implementasi dilakukan dengan memanfaatkan jaringan komputer lokal yang terdiri dari SUN Spare Station 1+ di PAU Ilmu Komputer Universitas Indonesia. Speed-up terbaik sebesar 1,67 diperoleh dari 2 prosesor dengan jumlah data 40%.