【摘要】：離散傅立葉變換是數(shù)字信號(hào)處理系統(tǒng)中常用的重要數(shù)學(xué)變換，算法的可行性、復(fù)雜度和運(yùn)行效率等都是影響計(jì)算結(jié)果的重要因素。近年來(lái)，GPU正在以大大超過(guò)摩爾定律的速度高速發(fā)展，主流GPU的單精度浮點(diǎn)處理能力和外部存儲(chǔ)器帶寬相對(duì)于同時(shí)期的CPU都有明顯的優(yōu)勢(shì)，基于圖形硬件GPU的通用計(jì)算正成為并行領(lǐng)域的研究熱點(diǎn)。特別是NVIDIA公司于2007年推出的CUDA統(tǒng)一計(jì)算設(shè)備架構(gòu)，在編程、優(yōu)化等方面都得到了顯著的提升，極大地增強(qiáng)了GPU的通用計(jì)算能力。CUDA不需要借助于圖形API，采用類(lèi)C語(yǔ)言進(jìn)行開(kāi)發(fā)，使開(kāi)發(fā)人員比較容易的從CPU編程模式過(guò)渡到GPU編程模式。隨著GPU可編程能力、并行處理能力以及應(yīng)用范圍的不斷提升和擴(kuò)展，GPU已發(fā)展成為一種高度并行化、多線(xiàn)程、多核的處理器。利用GPU的并行處理能力，以CPU+GPU混合加速為特征的異構(gòu)并行計(jì)算系統(tǒng)將會(huì)成為未來(lái)高性能計(jì)算的主流。 本文首先分析了CUDA硬件架構(gòu)和編程模型，在分析GPU通用計(jì)算現(xiàn)狀的基礎(chǔ)上，提出CUDA程序設(shè)計(jì)的方法。然后深入探討了快速傅立葉變換的基本原理，詳細(xì)介紹了時(shí)域抽取基2-FFT算法的實(shí)現(xiàn)過(guò)程及相關(guān)性質(zhì)，根據(jù)快速傅立葉算法高度并行分治的特征，結(jié)合CUDA編程模型及實(shí)現(xiàn)機(jī)制，用CUDA的類(lèi)C語(yǔ)言設(shè)計(jì)了快速傅立葉變換的并行算法。改進(jìn)算法采用CPU+GPU異構(gòu)模型方式，將GPU引入到計(jì)算中來(lái)，讓GPU承擔(dān)程序中的大規(guī)模計(jì)算——復(fù)數(shù)的加法與算數(shù)的乘法。傳統(tǒng)串行算法實(shí)現(xiàn)N點(diǎn)序列的快速傅立葉變換需要三層循環(huán)，時(shí)間復(fù)雜度為O (Nlog2N)。改進(jìn)后的算法采用線(xiàn)程層次組織結(jié)構(gòu)，將同一級(jí)中相互獨(dú)立的N/2個(gè)蝶形運(yùn)算實(shí)現(xiàn)并行操作，原有的三層循環(huán)可以用兩層循環(huán)來(lái)完成，，時(shí)間復(fù)雜度變?yōu)镺 (N)，從而實(shí)現(xiàn)對(duì)快速傅立葉變換的加速與優(yōu)化。文章最后搭建CUDA實(shí)驗(yàn)運(yùn)行環(huán)境，實(shí)現(xiàn)傳統(tǒng)快速傅立葉算法在CPU上的運(yùn)行，以及改進(jìn)后的算法在GPU上的運(yùn)行，同時(shí)還調(diào)用了FFTW函數(shù)庫(kù)的程序代碼和CUFFT函數(shù)庫(kù)的程序代碼，并將以上結(jié)果進(jìn)行比較，通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)的分析證明了運(yùn)用CUDA架構(gòu)實(shí)現(xiàn)快速傅立葉算法的優(yōu)越性，也驗(yàn)證了GPU在處理大量數(shù)據(jù)計(jì)算時(shí)所占的優(yōu)勢(shì)。
[Abstract]:Discrete Fourier transform (DFT) is an important mathematical transformation commonly used in digital signal processing system. The feasibility, complexity and efficiency of the algorithm are the important factors that affect the calculation results. In recent years, GPU is developing at a speed that greatly exceeds Moore's Law. The single precision floating-point processing capability and external memory bandwidth of mainstream GPUs are obviously superior to those of CPU in the same period. General computing based on graphics hardware GPU is becoming a research hotspot in parallel field. In particular, NVIDIA introduced the CUDA unified computing equipment architecture in 2007, which has been greatly improved in programming, optimization and so on, greatly enhanced the GPU's general computing capability .CUDA does not need to use graphics API, using C language to develop. Make it easier for developers to transition from CPU programming mode to GPU programming mode. With the development of GPU's programmable ability, parallel processing ability and application scope, GPU has developed into a highly parallel, multithreaded, multi-core processor. Using the parallel processing capability of GPU, heterogeneous parallel computing systems characterized by CPU-GPU hybrid acceleration will become the mainstream of high-performance computing in the future. In this paper, the hardware architecture and programming model of CUDA are analyzed. Based on the analysis of the current situation of GPU general computing, the method of CUDA programming is put forward. Then the basic principle of Fast Fourier transform (FFT) is discussed in depth, and the implementation process and related properties of 2-FFT algorithm in time domain are introduced in detail. According to the characteristics of high parallel division and control of FFT algorithm, combined with CUDA programming model and implementation mechanism, The parallel algorithm of fast Fourier transform is designed with C-like language of CUDA. The improved algorithm adopts the CPU GPU heterogeneous model, and introduces GPU into the calculation, which allows GPU to undertake the addition and multiplication of the complex number and the large scale computation in the program. The traditional serial algorithm for the fast Fourier transform of N-point sequence needs three-layer cycle, and the time complexity is O (Nlog2N). The improved algorithm uses thread-level organization structure to realize parallel operation of independent N / 2 butterfly operations in the same level, and the original three-layer loop can be completed by two-layer loop. The time complexity becomes O (N), which can accelerate and optimize the fast Fourier transform (FFT). Finally, the paper builds up the CUDA experimental running environment, realizes the traditional fast Fourier algorithm running on CPU, and the improved algorithm running on GPU. At the same time, the program code of FFTW function library and CUFFT function library are also called. Through the analysis of experimental data, the superiority of fast Fourier algorithm using CUDA architecture is proved, and the advantage of GPU in dealing with a large amount of data is verified.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類(lèi)號(hào)】：TP338.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 李偉;孫進(jìn)平;王俊;李少洪;;一種基于FPGA的超高速32k點(diǎn)FFT處理器[J];北京航空航天大學(xué)學(xué)報(bào);2007年12期

2 韓博;周秉鋒;;GPGPU性能模型及應(yīng)用實(shí)例分析[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2009年09期

3 趙麗麗;張盛兵;張萌;姚濤;;基于CUDA的高速FFT計(jì)算[J];計(jì)算機(jī)應(yīng)用研究;2011年04期

4 王芳;張學(xué)鋒;程增會(huì);;快速傅立葉變換中的一種倒位序生成法[J];計(jì)算機(jī)應(yīng)用與軟件;2011年02期

5 林一松;楊學(xué)軍;唐滔;王桂彬;徐新海;;一種基于并行度分析模型的GPU功耗優(yōu)化技術(shù)[J];計(jì)算機(jī)學(xué)報(bào);2011年04期

6 朱林;王志凌;黃天戍;;基于DSP并行系統(tǒng)的FFT算法實(shí)現(xiàn)[J];武漢理工大學(xué)學(xué)報(bào);2009年20期

7 董惠;衛(wèi)銘斐;江麗;曾俊;;基于FPGA的FFT處理器的設(shè)計(jì)與仿真[J];微電子學(xué)與計(jì)算機(jī);2008年11期

8 王潤(rùn)澤;王穎;楊棟毅;;大規(guī)模FFT并行計(jì)算中二維SRAM的設(shè)計(jì)[J];中國(guó)科學(xué)院研究生院學(xué)報(bào);2008年01期

本文編號(hào)：2137456