基于CUDA的FFT并行計算研究.pdf

1、離散傅立葉變換是數(shù)字信號處理系統(tǒng)中常用的重要數(shù)學(xué)變換，算法的可行性、復(fù)雜度和運(yùn)行效率等都是影響計算結(jié)果的重要因素。近年來，GPU正在以大大超過摩爾定律的速度高速發(fā)展，主流GPU的單精度浮點(diǎn)處理能力和外部存儲器帶寬相對于同時期的CPU都有明顯的優(yōu)勢，基于圖形硬件GPU的通用計算正成為并行領(lǐng)域的研究熱點(diǎn)。特別是NVIDIA公司于2007年推出的CUDA統(tǒng)一計算設(shè)備架構(gòu)，在編程、優(yōu)化等方面都得到了顯著的提升，極大地增強(qiáng)了GPU的通用計算能力。

2、CUDA不需要借助于圖形API，采用類C語言進(jìn)行開發(fā)，使開發(fā)人員比較容易的從CPU編程模式過渡到GPU編程模式。隨著GPU可編程能力、并行處理能力以及應(yīng)用范圍的不斷提升和擴(kuò)展，GPU已發(fā)展成為一種高度并行化、多線程、多核的處理器。利用GPU的并行處理能力，以CPU+GPU混合加速為特征的異構(gòu)并行計算系統(tǒng)將會成為未來高性能計算的主流。
　　 本文首先分析了CUDA硬件架構(gòu)和編程模型，在分析GPU通用計算現(xiàn)狀的基礎(chǔ)上，提出CUDA程

3、序設(shè)計的方法。然后深入探討了快速傅立葉變換的基本原理，詳細(xì)介紹了時域抽取基2-FFT算法的實現(xiàn)過程及相關(guān)性質(zhì)，根據(jù)快速傅立葉算法高度并行分治的特征，結(jié)合CUDA編程模型及實現(xiàn)機(jī)制，用CUDA的類C語言設(shè)計了快速傅立葉變換的并行算法。改進(jìn)算法采用CPU+GPU異構(gòu)模型方式，將GPU引入到計算中來，讓GPU承擔(dān)程序中的大規(guī)模計算-復(fù)數(shù)的加法與算數(shù)的乘法。傳統(tǒng)串行算法實現(xiàn)N點(diǎn)序列的快速傅立葉變換需要三層循環(huán)，時間復(fù)雜度為O(Nlog2N)。改

4、進(jìn)后的算法采用線程層次組織結(jié)構(gòu)，將同一級中相互獨(dú)立的N/2個蝶形運(yùn)算實現(xiàn)并行操作，原有的三層循環(huán)可以用兩層循環(huán)來完成，時間復(fù)雜度變?yōu)镈(N)，從而實現(xiàn)對快速傅立葉變換的加速與優(yōu)化。文章最后搭建CUDA實驗運(yùn)行環(huán)境，實現(xiàn)傳統(tǒng)快速傅立葉算法在CPU上的運(yùn)行，以及改進(jìn)后的算法在GPU上的運(yùn)行，同時還調(diào)用了FFTW函數(shù)庫的程序代碼和CUFFT函數(shù)庫的程序代碼，并將以上結(jié)果進(jìn)行比較，通過對實驗數(shù)據(jù)的分析證明了運(yùn)用CUDA架構(gòu)實現(xiàn)快速傅立葉算法的優(yōu)