A parallel implementation of fast fourier transform algorithm

Abstract

Bu çalışmada hızlı Fourier dönüşüm (HFD) yönteminin çoklu işletim birimine sahip bilgisayarlardaki paralel uygulanışı araştırılmış ve eşzamanlı programlama ile benzetimi yapılmıştır. Bu uygulamalardan iki tanesi, VAXcluster denilen, iki VAX 11/780 bilgisayarın karşılıklı bağlanmasından oluşan sistemde, benzetim yapmak için ele alınmıştır. Bunlardan biri Bergland'm paralel HFD yönteminin, paralel eleman işletim bütünü, denilen bilgisayardaki uygulanışı ve diğer ide zamanda-parçalama taban-2 HFD yönteminin, bir gevşek bağlantılı çoklu işletim birimi, sistemindeki uygulanışıdır. Her iki uygulama şekli için, VAX FORTRAN dilinde benzetim programları geliştirilmiştir. Ayrıca, her benzetim çeşitli dalga şekilleri için test edilmiş ve sonuçlar karmaşıklık, çalışma zamanı ve verim yönünden tartışılmıştır. Anahtar kelimeler: HFD yöntemi, paralel uygulanış, benzetim, eşzamanlı programlama, çalışma zamanı, v

Parallel implementations of the fast Fourier transform algorithms (FFT) on multiprocessor systems are investigated and simulated with concurrent programming. Two parallel FFT implementations are considered for simulation on a VAXcluster system which consists of two interconnected VAX 11/780 computers. These are the Bergland's parallel FFT algorithm on a parallel element processing ensemble, and the decimation-in-time radix-2 FFT algorithm on a loosely coupled multiprocessor system. A set of simulation programs is developed for each implementation, in VAX FORTRAN language. Furthermore, each simulation is tested for a set of time domain waveforms and results are discussed in terms of complexity, execution time, and efficiency. Key words: FFT algorithm, parallel implementation, simulation, concurrent programming, execution time.IV