一種高速實(shí)時(shí)視頻檢測(cè)系統(tǒng)的優(yōu)化選擇

一種高速實(shí)時(shí)視頻檢測(cè)系統(tǒng)的優(yōu)化選擇

0基于fpga的快速fft算法fft是雷達(dá)信號(hào)分析和處理中的一個(gè)常見轉(zhuǎn)換。實(shí)際應(yīng)用中,普遍使用基2或基4FFT算法,該算法的程序代碼不因變換點(diǎn)數(shù)變化而變化,旋轉(zhuǎn)因子規(guī)律性強(qiáng),程序緊湊,速度快。但它所能提供的FFT變換點(diǎn)數(shù)必須是2的整數(shù)冪2h(對(duì)基4FFT算法應(yīng)為4h,其中h為正整數(shù)),可是在信號(hào)處理中,處理的數(shù)據(jù)個(gè)數(shù)往往不能滿足該條件,需要進(jìn)行補(bǔ)零處理,對(duì)小于且接近于2h的點(diǎn)數(shù),補(bǔ)很少的零就可以進(jìn)行運(yùn)算,對(duì)其運(yùn)算效率不會(huì)有太大影響,但對(duì)于大于2h且和2h+1相差很大的點(diǎn)數(shù),補(bǔ)的零就會(huì)很多,這樣,運(yùn)算量增大,需要的硬件設(shè)備量增大,效率降低。Kolba和Parks提出了PFA(素因子FFT)算法,其適用于長(zhǎng)度可分解為一些互質(zhì)因子相乘的DFT,能提供一些特定點(diǎn)數(shù)的DFT快速算法,但該算法對(duì)數(shù)據(jù)重排計(jì)算復(fù)雜,同址運(yùn)算不易實(shí)現(xiàn),在DSP上實(shí)現(xiàn)時(shí)點(diǎn)數(shù)越多程序越復(fù)雜。本文針對(duì)所計(jì)算FFT點(diǎn)數(shù)的特點(diǎn),提出了結(jié)合基2或基4FFT算法的一種快速FFT算法。該算法能靈活地改變FFT點(diǎn)數(shù),程序容量略高于基2或基4FFT算法,速度與基2或基4FFT算法相近。1維陣列n點(diǎn)dft的計(jì)算長(zhǎng)度為N的有限長(zhǎng)序列x(n)的DFT為X(k)=Ν-1Σn=0x(n)WknΝ,k=0,1,?,Ν-1(1)X(k)=Σn=0N?1x(n)WknN,k=0,1,?,N?1(1)式中:WknΝknN=exp{-j2πkn/N}為旋轉(zhuǎn)因子。令N=N1N2,將x(n)分解為N2個(gè)長(zhǎng)度為N1的序列,將這些序列用如下的陣列x′表示x′=[x(0)x(Ν2)?x(Ν2(Ν1-1))x(1)x(Ν2+1)?x(Ν2(Ν1-1)+1)????x(Ν2-1)x(2Ν2-1)?x(Ν2Ν1-1)](2)x′=???????x(0)x(1)?x(N2?1)x(N2)x(N2+1)?x(2N2?1)????x(N2(N1?1))x(N2(N1?1)+1)?x(N2N1?1)???????(2)令n和k的序號(hào)映射定義如下n=Ν2n1+n2{0≤n1≤Ν1-10≤n2≤Ν2-1(3)k=k1+Ν1k2{0≤k1≤Ν1-10≤k2≤Ν2-1(4)則N點(diǎn)DFT可表示為X(k)=X(k1+Ν1k2)=Ν2-1Σn2=0Ν1-1Σn1=0x(Ν2n1+n2)×W(Ν2k1n1)ΝWk1n2ΝWΝ1k2n2ΝWΝ1Ν2k2n1Ν=Ν2-1Σn2=0{[Ν1-1Σn1=0x(Ν2n1+n2)Wn1k1Ν1]Wk1n2Ν}Wn2k2Ν2(5)令G(n2,k1)=Ν1-1Σn1=0x(Ν2n1+n2)Wn1k1Ν1,則G(n2,k1)為序列x(N2n1+n2)的N1點(diǎn)DFT,即式(2)中二維陣列N2行元素的DFT。計(jì)算陣列x′每一行N1的點(diǎn)DFT就得到另一個(gè)陣列GG=[G(0,0)G(0,1)?G(0,(Ν1-1))G(1,0)G(1,1)?G(1,(Ν1-1))????G(Ν2-1,0)G(Ν2-1,1)?G(Ν2-1,(Ν1-1))](6)矩陣的元素為復(fù)數(shù)G(n2,k1)。因n2行的數(shù)據(jù)在計(jì)算完x(N2n1+n2)的N1點(diǎn)DFT后不再需要,G(n2,k1)可以存儲(chǔ)在同一行(原址運(yùn)算)。要計(jì)算式(5)中的X(k),應(yīng)乘以旋轉(zhuǎn)因子Wk1n2Ν形成新的陣列?G(n2,k1)=Wn1k1ΝG(n2,k1)。最后計(jì)算陣列?G(n2,k1)的每一列的N2點(diǎn)DFT:X(k1+Ν1k2)=Ν2-1Σn2=0?G(n2,k1)Wk2n2Ν1。DFT變換結(jié)果可由二維陣列讀出:X(k)=X(k1+N1k2)。以上的某個(gè)因子若可能被繼續(xù)分解,如N=N1N2N3,則可以先作N2N3個(gè)N1點(diǎn)DFT變換,再作N1N3個(gè)N2點(diǎn)變換,最后作N1N2個(gè)N3點(diǎn)變換。對(duì)N點(diǎn)DFT進(jìn)行分解時(shí),應(yīng)考慮N的特點(diǎn),如果N接近或等于2h或4h,則作補(bǔ)零處理,直接應(yīng)用基2或基4FFT算法運(yùn)算;如果N與2h或4h相差很大,但與N1·mr(其中m為2或4,r為正整數(shù))接近,則仍作補(bǔ)零處理,將N′(補(bǔ)零后長(zhǎng)度)分解為N1·mr,先做mr個(gè)N1點(diǎn)DFT(可用快速循環(huán)卷積實(shí)現(xiàn)),再應(yīng)用基2或基4FFT算法作N1個(gè)mr點(diǎn)FFT,其中N1的選取應(yīng)盡量采用較小的素?cái)?shù),這樣程序更緊湊,所用的旋轉(zhuǎn)因子也會(huì)更少;如果N與N1N2·mr接近,則仍作補(bǔ)零處理,將N′分解為N1N2·mr,再作變換。以此類推,可將N′分解成N1N2·mr。2ts113算法的實(shí)現(xiàn)在實(shí)時(shí)處理中,即使運(yùn)算點(diǎn)數(shù)相同,采用不同的代碼和數(shù)據(jù)存儲(chǔ)形式、不同的程序設(shè)置,也會(huì)得到不同的FFT運(yùn)算速度,下面將以N=2800點(diǎn)FFT為例講述該算法在TS101上的實(shí)現(xiàn)。2.1基于l鞣碼/s處理器TS101處理器是一種新型高速浮點(diǎn)DSP(DigitalSignalProcessor)。該處理器內(nèi)核時(shí)鐘可達(dá)300MHz,其峰值運(yùn)算能力達(dá)到18億次/s。一個(gè)周期內(nèi),可同時(shí)進(jìn)行三次128位的存儲(chǔ)器訪問,完成存儲(chǔ)、讀取和乘累加等操作。內(nèi)部的兩個(gè)運(yùn)算核支持SIMD模式。2.2ts113片內(nèi)數(shù)據(jù)存儲(chǔ)對(duì)于相同的源代碼和數(shù)據(jù),將其定位到不同的存儲(chǔ)器空間,代碼的執(zhí)行速度會(huì)有明顯差別。為了得到最優(yōu)或接近最優(yōu)的處理性能,應(yīng)遵從以下規(guī)則:盡量將代碼、數(shù)據(jù)放在片內(nèi),這要比放在片外的執(zhí)行速度高得多;TS101片內(nèi)有三個(gè)存儲(chǔ)器塊,將其中一塊存代碼,一塊存放原始數(shù)據(jù)和輸出結(jié)果,另一塊存放旋轉(zhuǎn)因子,這樣,程序控制器、兩個(gè)計(jì)算塊就可以同時(shí)利用三套片內(nèi)總線訪問這三個(gè)存儲(chǔ)塊;盡可能將代碼、數(shù)據(jù)排放在四字邊界上,便于利用廣播讀、合并讀、合并寫等方式。2.3空間誤差處理在某應(yīng)用中,需要用頻域方法完成脈壓,FFT點(diǎn)數(shù)為2800點(diǎn)復(fù)數(shù),按上述方法,數(shù)據(jù)補(bǔ)零作3072點(diǎn)FFT。其處理過程是:先作1024個(gè)3點(diǎn)DFT,再應(yīng)用基2FFT算法作3個(gè)1024點(diǎn)FFT。FFT變換必須對(duì)輸出數(shù)據(jù)進(jìn)行整序處理。TS101支持位反序?qū)ぶ?但位反序?qū)ぶ返臄?shù)據(jù)量(緩沖區(qū)的長(zhǎng)度)必須是2的整數(shù)冪(例如,緩沖區(qū)的長(zhǎng)度=2n,n為正整數(shù)),且所尋址的數(shù)據(jù)緩沖區(qū)的起始地址必須與緩沖區(qū)長(zhǎng)度的整數(shù)倍地址對(duì)齊。3072點(diǎn)不是2的整數(shù)冪,不能直接使用位反序?qū)ぶ贰Ｒ虼宋环葱驅(qū)ぶ凡僮魇窃?024點(diǎn)FFT過程完成的。2.4fft的算法描述本例中的1024點(diǎn)FFT算法是關(guān)鍵。以圖1a給出的16點(diǎn)基2DIT-FFT運(yùn)算流圖來(lái)說(shuō)明。此蝶形流圖的旋轉(zhuǎn)因子遵循如下規(guī)律:先將所有旋轉(zhuǎn)因子進(jìn)行位反序,將需要的旋轉(zhuǎn)因子排放在存儲(chǔ)器中,在每一級(jí)的每一組中依次提取一個(gè),省去了其他蝶形流圖編程時(shí)連續(xù)改變旋轉(zhuǎn)因子的時(shí)間。下面將詳細(xì)講述1024點(diǎn)FFT的循環(huán)設(shè)置。圖中“0”表示W(wǎng)0Ν,“2”表示W(wǎng)2Ν。在FFT匯編程序中,蝶形運(yùn)算可采用三個(gè)嵌套循環(huán)來(lái)完成,即,級(jí)循環(huán)、組循環(huán)、蝶形循環(huán)(見圖1a)。按照各級(jí)蝶形運(yùn)算中組循環(huán)和蝶形循環(huán)迭代次數(shù)的不同,將算法分為三部分。令FFT的中間級(jí)為MIDSTAGE=[M/2]+1(這一級(jí)組循環(huán)和蝶形循環(huán)迭代次數(shù)相同或相近)。如圖1a所示,算法的前兩級(jí)沒有乘法,故采用一級(jí)基4FFT算法來(lái)完成,流圖形式如圖1b所示,這樣的效率比基2FFT算法的效率更高,不但省去了一級(jí)數(shù)據(jù)的存取操作,也避免了基4FFT算法旋轉(zhuǎn)因子多的問題。在第三級(jí)到中間級(jí)的程序設(shè)置上令蝶形循環(huán)置于組循環(huán)內(nèi),組循環(huán)置于級(jí)循環(huán)內(nèi),這樣,內(nèi)部(蝶形)循環(huán)的迭代次數(shù)大于外部(組)循環(huán),效率更高,使系統(tǒng)的總消耗達(dá)到最小。同理,在中間級(jí)到M級(jí)的程序設(shè)置上令組循環(huán)置于蝶形循環(huán)內(nèi),但此時(shí)每次蝶形運(yùn)算都要取旋轉(zhuǎn)因子,需要多次訪問數(shù)據(jù),但TS101芯片的內(nèi)部總線帶寬克服了這一影響。蝶形計(jì)算采用SIMD運(yùn)算模式,巧妙地將兩個(gè)蝶形的計(jì)算用并行指令相互穿插在一起,同時(shí)還將前一次循環(huán)和后一次循環(huán)所計(jì)算的蝶形的一些操作通過并行指令安排在本次循環(huán)計(jì)算的蝶形當(dāng)中,從而最大限度地運(yùn)用并行指令。2.5執(zhí)行指令的選擇TS101的匯編指令為四字指令方式,程序優(yōu)化潛力很大,但復(fù)雜度也很高。一次計(jì)算或一次存儲(chǔ)器的訪問往往有多種實(shí)現(xiàn)方式及相應(yīng)的指令,應(yīng)選擇最有效的指令。但幾條最有效的指令放在一起并不一定能得到最快的執(zhí)行速度,甚至得不到正確的結(jié)果。這涉及到指令間的資源沖突、流水線引起的數(shù)據(jù)相關(guān)性問題等,可參閱參考文獻(xiàn)。2.6表1:表1在TS101上,不同點(diǎn)數(shù)執(zhí)行時(shí)間及運(yùn)算周期的比較如表1所示。由表可見,在TS101上實(shí)現(xiàn)這種FFT算法效率很高,3072點(diǎn)FFT的運(yùn)算速度達(dá)到9.50億次/s,相當(dāng)于TS101峰值運(yùn)算速度的52.78%。2.7ts113相關(guān)應(yīng)用如上所述,TS101進(jìn)行FFT的速度是很快的,但其存在運(yùn)算與I/O的不平衡問題。以連續(xù)進(jìn)行多個(gè)1024點(diǎn)復(fù)數(shù)FFT為例,要得到最高的處理效率,TS101必須在33μs時(shí)間內(nèi)將2048個(gè)數(shù)據(jù)輸入、輸出,若用32位總線實(shí)現(xiàn)I/O,則總線傳輸速度必須達(dá)到128MHz,即512MB/s,這是很難的。即使采用同步SDRAM總線接口的速度也只有100MHz,因此I/O限制了TS101連續(xù)進(jìn)行FFT的能力?？刹捎萌缦?種解決方法:一種是采用64位總線接口,這需要較多的存儲(chǔ)器件和連線;另一種是利用TS101的鏈路口,將總線上的一部分I/O負(fù)荷轉(zhuǎn)移到TS101的鏈路上。下面給出一個(gè)采用第二種方法的應(yīng)用實(shí)例,它是用1片TS101完成FFT,將結(jié)果轉(zhuǎn)至另一片輸出,每批FFT點(diǎn)數(shù)2800,為提高傳數(shù)可靠性,I/O數(shù)據(jù)率為50MHz。3072點(diǎn)FFT需要的運(yùn)算時(shí)間為122μs,輸入數(shù)據(jù)以實(shí)部、虛部交替方式用DMA送入第一片TS101,需要112μs,第一片TS101做完FFT,把結(jié)果通過鏈路口送向第二片TS101,鏈路口傳送速度設(shè)定為100MB/s,用兩條鏈路口傳3072個(gè)復(fù)數(shù)需要122μs,這樣,此片的輸入、運(yùn)算、輸出可以最高速度并發(fā)進(jìn)行。第二片TS1