基于嵌入式移動GPU的離散傅里葉變換并行優化※

曾寶國，楊斌

(1.成都工業職業技術學院，成都 610213； 2.西南交通大學)

?

基于嵌入式移動GPU的離散傅里葉變換并行優化※

曾寶國1，楊斌2

(1.成都工業職業技術學院，成都 610213； 2.西南交通大學)

摘要:GPGPU能夠針對計算密集型的計算問題進行大規模的并行加速，為DFT在嵌入式平臺上的高效實現提供了一種新的方式。基于Mali-T604嵌入式GPU實現了針對DFT和FFT的并行加速方案，并進行了實際測試。實驗結果證明，所設計的并行方案能夠在ARM嵌入式平臺上有效加速DFT和FFT，可大大提升移動設備進行數字信號處理的實時性。

關鍵詞:DFT；FFT；GPGPU；Mali-T604 GPU；數字信號處理；ARM嵌入式系統

引言

GPGPU(General purpose GPU)技術近年來在嵌入式領域廣泛應用，移動GPU對于輸入量龐大的計算密集型、數據可并行化的通用計算問題有顯著的加速能力[1]。DFT以及FFT的運算復雜度極高，嵌入式平臺上計算能力有限的CPU難以對其進行快速處理。

在實時信號分析場景下，需要高效的計算方案，DFT和FFT的數學模型適合使用GPU對其進行并行加速。本文基于Mali-T604 GPU對DFT和FFT的并行計算方案進行設計，提供了實現方法和實際測試結果，為使用GPGPU技術在嵌入式平臺上進行數字信號處理的研究人員提供了參考和借鑒。

1離散傅里葉變換并行化解析

離散傅里葉變換在頻譜分析、數字通信、圖像處理、遙感遙測等領域有著廣泛的應用，有多種算法以不同的時間復雜度對其進行實現，常規的DFT方式和Cooley-Tukey快速變換方式是最常見的兩種離散傅里葉變換實現方式。

1.1常規DFT數學模型分析

數字信號處理中應用的離散傅里葉變換通常用于將時域采樣信號轉換至頻域進行分析，其輸入數據通常是實數，對于長度為N的實數輸入信號序列x[0DK∶N-1]，其一維DFT變換公式為：

(1)

從式(1)可以看出，從實數序列x[0∶N-1]到復數序列X[0∶N-1]的變換過程實際上可轉換為矩陣乘法的形式：

(2)

(3)

可見對于輸出序列X[0∶N-1]的每個元素而言，其變換過程是相互獨立的，其中涉及的是大量的一維向量內積計算，對于數字信號而言，輸入序列x[0∶N-1]為實數浮點序列，式(2)和式(3)涵蓋的是多次浮點乘法和三角函數計算，嵌入式的CPU(如ARM處理器)對于這樣的計算,速度是比較慢的，如果每個元素的變換過程能夠獨立分解到不同的任務中并行執行,且浮點運算能夠快速完成，則常規的DFT就能夠快速完成，而MaliGPU正好就是符合這樣計算特征的協處理器。

Cooley-Tukey在1965年提出了快速傅里葉變換算法，該算法高效簡單，在數字信號處理領域經久不衰，該算法利用了離散傅里葉變換的疊加性質、移位性質和延展性質,簡化了DFT變換的運算量，能夠得出和常規DFT變換相同的運算結果。

Cooley-TukeyFFT算法可處理長度為2次冪的任意序列的變換，其核心思想是歸并，不斷利用短序列的變換結果歸并產生長序列的變換結果。在計算變換結果X[0∶N-1]的時候，首先分別計算子序列x[0∶N/2-1]和x[N/2,N-1]的變換結果X[0∶N/2-1]和X[N/2∶N-1]，再歸并產生X[0∶N-1]。根據原始序列x[0∶N-1]構建序列x1[0∶N-1]={x(0),0,x(1),0,…,x(N/2-1), 0}和序列x2[0∶N-1]= {0,x(N/2),0,x(N/2+1),…,0,x(N-1)}，根據DFT的延展性質和移位性質，有下式成立：

(4)

(5)

(6)

根據DFT變換的疊加性質，有下式成立：

(7)

4個元素的 FFT相對簡單，算法從4個元素的變換開始，將原始序列的每4個元素分解為一組，每組元素首先用蝶形運算進行DFT變換，然后利用式(4)～(7)的算法不斷歸并，得到更大長度的FFT變換結果，直至歸并長度等于原始序列長度N為止。

Cooley-Tukey FFT算法的時間復雜度為O(N×log2(N))，相對常規的DFT算法的O(N2)復雜度而言，運算量有所下降，FFT算法中涉及的4元素分組的蝶形運算可以獨立進行，互不干擾，后期每個子段的歸并過程也是互不依賴的，涉及的也多為浮點乘法運算，適合使用Mali GPU進行性能優化。

2Mali GPU并行計算模型簡介

Mali-T600系列的GPU可以支持OpenCL 1.1 Full Profile標準，OpenCL是真正意義上的跨平臺異構并行框架，能夠真正挖掘出Mali GPU的并行計算特性。在OpenCL框架下，設計者可將預定數目的計算任務下載至Mali GPU端，以多線程形式實現全局的任務并行，其運行過程略——編者注。

OpenCL通過主程序來定義上下文，并管理內核程序在GPU設備的執行[2]，應用程序通過host 提交命令, 驅動設備上的PE 執行內核程序[3]。GPU可以同時處理成百上千的線程，大量晶體管用于ALU[4]，每個Mali-T604 GPU的著色器核心最多可以同時容納256個線程[5]。在單個線程內部，可以利用Mali GPU內置的128位寄存器和ALU實現向量數據的SIMD(Single Instruction Multiple Data)局部并行加速，Mali-T604 GPU的4個著色器核心以及其中的2條向量運算流水線和1條向量讀寫流水線能夠高效完成128位向量的讀寫和運算。

3并行DFT以及并行FFT變換實現

傳統的DFT以及Cooley-Tukey FFT算法均適合使用Mali GPU進行并行優化，下文分別針對這兩種算法介紹并行化的方法。

3.1常規DFT算法并行化實現

常規的DFT算法中，變換結果X[0∶N-1]中的每個元素都是由一維向量的內積得到的，因此每一個元素的計算過程可以分解到單個線程中完成，對于實數序列的DFT變換而言，X(0)和X(N/2)的虛數部分始終為0，對于其他的元素而言，X[k]和X[N-k]具有共軛復數關系，所以真正的計算中只需要計算X[0∶N/2]。因此GPU端總共分配N/2+1個線程，每個元素完成一次長度為N的一維向量的內積，得出X[0∶N/2]中的一個標量計算結果，圖1顯示了單個線程的運行流程。

圖1　并行DFT變換運算核流程圖

OpenCL實現的并行DFT內核源碼如下所示：

__kernel void dft(__global float *dft_src,

//變換之前的原始數據緩存，長度為N

__global float *dft_dst, //變換結果的緩存，長度為N

const int N //dft變換的長度){

……

thread_id = get_global_id(0); two_pai_kN = 2.0f*PI*thread_id/N;

sum_real = sum_imag = 0.0f;

for(i=0; i<(N>>2); i++){

src_vec = vload4(i, dft_src); //讀取輸入向量

angle = (float4)(two_pai_kN) * (float4)( (i<<2)+0, (i<<2)+1, (i<<2)+2, (i<<2)+3);

real = cos(angle); imag = sin(angle);

sum_real += dot(real, src_vec); sum_imag -= dot(imag, src_vec);

}

……

}

3.2Cooley-Tukey FFT算法并行優化實現

Cooley-Tukey FFT算法分為前后兩部分，前半部分每4個元素一組,利用蝶形運算進行FFT變換，4個元素進行蝶形運算的方式如圖2所示。

圖2　4個元素的FFT蝶形運算

在FFT算法中，一開始每4個元素的FFT變換是相互獨立的，因此分配N/4個線程對每一組數據進行圖2所示的蝶形運算，圖2中的X(0)～X(3)需要從原始數據緩存中讀取，其讀取位置和分組的組號相關，設線程i(i=0,1,2,…,N/4-1)處理第i組數據中的4個元素，則線程i讀取的4個元素的下標應該分別是4i、4i+1、4i+2、4i+3四個數字進行位翻轉之后的結果。設log2(N)=b，則下標index位翻轉的結果應該是其二進制第(b-1)位和第0位交換、第(b-2)位和第1位交換……直至較高數位和較低數位全部交換一遍之后的結果，能夠用Mali GPU進行位運算在每個線程中并行執行，這樣能夠保證最終歸并后的結果是順序排列的。圖2中蝶形運算的輸入量都是實數，其計算過程可以拆分成實數部分和虛數部分分別進行，并且都能夠用Mali GPU中的4通道浮點向量高效完成，代碼如下：

__kernel void fft4(__global float *fft_src,

//變換之前的原始數據緩存，長度是N

__global float *fft_dst_real,

//變換結果的緩存，長度為N(保存實部)

__global float *fft_dst_imag,

//變換結果的緩存，長度為N(保存虛部)

const int bits

//bits=log2(N),用于位翻轉計算

){

int id = get_global_id(0);

……//位翻轉部分省略

X_real = (float4)(x0);X_real += (float4)(x1, 0-x1, x1, 0-x1);

X_real += (float4)(x2, 0, 0-x2, 0);X_real += (float4)(x3, 0, 0-x3, 0);

X_imag = (float4)(0.0f, x3-x2, 0.0f, x2-x3);

vstore4(X_real, id, fft_dst_real);vstore4(X_imag, id, fft_dst_imag); //回存結果

}

Cooley-Tukey FFT算法的后半部分需要對前半部分的計算結果進行歸并，對于長度為N(N為2的冪)的FFT變換，在進行了4元素分組的FFT蝶形運算后，還需進行log2N-2次歸并，第i次(i從1開始)歸并過程的歸并長度為2i+2，即將相鄰的兩個長度為2i+1的FFT變換序列歸并為長度為2i+2的序列。對式(4)～(7)進行分析可知，雖然每次歸并的長度翻倍后歸并的分組會減少，但總計算量是不變的，因此，將長度為N的浮點復數序列每4個相鄰元素分成一組，則不論在第幾次歸并過程中，必然能夠讓每組數據兩兩配對，且分別屬于歸并運算的兩個輸入子段，這樣每個線程可分別讀取這兩個長度為4的子段，進行式(4)～(7)的歸并計算，并可將實部和虛部的計算拆開，4個浮點數剛好可以湊齊128位,用Mali GPU的向量運算進行處理，綜上所述，每一次歸并過程可以分配N/8個線程，每個線程進行長度為4的子段的歸并計算。

設Mali GPU端編號為i(i=0,1,2,…,N/8)的線程在參與歸并長度為merge_len的歸并過程中，上一次歸并的結果為X_old[0DK∶N-1]，則線程i應首先讀取X_old中的第一個長度為4的子段vec0，其偏移地址為：

offset0=(i/(merge_len>>3))×merge_len

(8)

后一個子段vec1和vec0間的地址間隔是由歸并長度決定的：

(9)

根據前文分析，由vec0和vec1兩個向量可以計算出新序列X_new[0DK∶N-1]中的兩個長度為4的新子段X_new[offset0∶offset0+3]和X_new[of]fset1∶offset1+3]，下面是OpenCL歸并內核的核心代碼略——編者注。

由于Cooley-Tukey FFT算法中每次歸并都依賴于上一次歸并的結果，因此在ARM CPU主機端需要將歸并內核順序log2N次加入Mali GPU在OpenCL框架下的命令隊列中，并且每次傳入的歸并長度參數merge_len翻倍。

4優化效果測試

筆者在Arndale Board開發板(核心為ARM Cortex-A15雙核CPU+Mali-T604 GPU的Exynos5250 SoC)上和嵌入式Linux操作系統上，對所述的并行DFT和并行FFT優化方案進行了測試，對比ARM Cortex-A15 CPU進行的串行方案和Mali GPU進行的并行方案，以不同長度的隨機浮點實數序列進行離散傅里葉變換效率測試，得到的測試數據如表1所列。

表1　離散傅里葉變換并行優化效果對比

從表1的測試數據可以看出，在離散傅里葉變換的變換長度較短的時候，Mali GPU端的運算線程數量不足，其并行運算能力未能發揮出來，故并行方案的計算效率不及串行方案。隨著變換長度的增加，Mali GPU端的并發線程數量上升，并行方案的計算效率迅速上升，不論是常規DFT算法還是Cooley-Tukey FFT算法的并行方案,效率都遠超串行方案，加速比達到了百倍以上，證明所設計的并行方案的加速效果穩定而有效。對比并行的DFT方案和并行的FFT方案，在變換長度較低的時候，DFT方案的效率更高，雖然FFT方案的總計算量低于常規的DFT算法，但是在歸并過程需要多次將歸并內核入隊，帶來了內核運行之間的同步開銷。在并發線程不足的情況下，并行化帶來的收益未能彌補同步開銷，所以并行FFT方案的性能提升不高，在變換長度較大的場景下，Mali GPU端的運算并行度增加，同步開銷成為影響效率的次要因素，FFT算法的低運算量特征體現出其優勢，使得后期并行FFT方案的效率遠超并行DFT方案。在實際工程中，應針對不同的嵌入式GPU硬件結構和變換長度，綜合選取兩者中效率更高的方案投入具體的應用場景中。

結語

本文基于Mali-T604 GPU設計了針對常規DFT算法和Cooley-Tukey FFT算法的并行優化方案，并在嵌入式Linux操作系統和OpenCL框架下進行了實現。實際測試效果表明，該優化方案效果明顯，嵌入式GPU的新興GPGPU技術在數字信號處理領域有著廣闊的應用前景。

參考文獻

[1] 龔若皓,楊斌.基于移動多核GPU的并行二維DCT變換實現方法[J] .成都信息工程學院學報,2015,30(1):22-26.

[2] 向陽霞,張惠民,王自強.面向OpenCL模型的DCT并行化[J] .電腦知識與技術,2013,9(26):6007-6011.

[3] 陳鋼,吳百鋒.面向OpenCL模型的GPU性能優化[J] .計算機輔助設計與圖形學學報,2011,23(4):571-580.

[4] Owens J D,Houston M,Luebke D,et al.GPUComputing[J] .Proceedings of the IEEE,2008,96(5):879-899.

[5] ARM Company.ARM Mali-T600 Series GPU OpenCL Developer Guide Version 2.0，2012.

曾寶國(副教授)，主要研究方向為嵌入式應用開發；楊斌(教授)，主要研究方向為嵌入式系統應用及異構并行計算。

(責任編輯：薛士然收修改稿日期：2015-08-27)

Parallelization of DFT Based on Embedded Mobile GPU※

Zeng Baoguo1,Yang Bin2

(1.College of Chengdu Industrial Vocational Technical,Chengdu 610213;2.Southwest Jiaotong University)

Abstract：GPGPU can provide efficient parallel computing solution for the complex compute-intensive computing problem,which is a new way of the efficient implementation of DFT in the embedded platform.In the paper,the parallelization solution of DFT and FFT based on Mali-T604 GPU is proposed.The results of experiment show that the parallel scheme can effectively accelerate DFT and FFT on ARM embedded platform,which can greatly improve the real-time performance of digital signal processing.

Key words:DFT;FFT;GPGPU;Mali-T604 GPU;digital signal processing;ARM Embedded System

中圖分類號:TP311

文獻標識碼:A