劉項(xiàng)洋，許勇

(安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院，安徽蕪湖241000)

?

快速DCT修剪在DSP上的內(nèi)存訪問優(yōu)化方法

劉項(xiàng)洋，許勇

(安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院，安徽蕪湖241000)

摘要：在本論文中，我們提出一個(gè)新的內(nèi)存訪問優(yōu)化方法以減少由權(quán)重因子(在DCT的快速修剪計(jì)算圖中的余弦系數(shù))和輸入點(diǎn)而產(chǎn)生的內(nèi)存訪問量，實(shí)現(xiàn)在DSP上的快速DCT修剪.該方法通過兩個(gè)步驟來減少內(nèi)存訪問量: 1.減少權(quán)重因子的個(gè)數(shù); 2.將快速DCT修剪的計(jì)算流程圖中兩個(gè)階段中的蝴蝶運(yùn)算單元合并到一個(gè)階段中，從而形成一個(gè)高效的蝴蝶運(yùn)算單元.我們?cè)赥I TMSC320C64x DSP上應(yīng)用該方法來實(shí)現(xiàn)修剪FCT.實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的實(shí)現(xiàn)方法相比，修剪FCT方法在DSP上可以平均減少40%的內(nèi)存訪問量，平均減少48.6%的時(shí)鐘周期和平均節(jié)約32.6%的由存儲(chǔ)加權(quán)因子導(dǎo)致的內(nèi)存訪問.

關(guān)鍵詞：數(shù)字信號(hào)處理器(DSP);離散余弦變換(DCT);內(nèi)存訪問

1　引言

離散余弦變換(Discrete Cosine Transform，DCT)從1974年被文獻(xiàn)［1］定義以來，在許多圖像、語(yǔ)音編碼應(yīng)用程序中發(fā)揮了非常重要的作用，而其中最常用的是二型DCT(DCT-II).文獻(xiàn)［2］給出了二型DCT的具體定義:

直接用硬件或軟件來實(shí)現(xiàn)這個(gè)公式是非常低效的.為解決這個(gè)問題，文獻(xiàn)［2］中也提出了各種直接或間接的計(jì)算的方法.此后，DCT算法的研究進(jìn)展包括了radix -2nDCT［3］，量化二維DCT［4］、多維矢量DCT正交矩陣變換［5］以及FPGA實(shí)現(xiàn)DCT［6，7］等，均是直接計(jì)算DCT.

通常這些算法都假定DCT系數(shù)的輸入與輸出數(shù)量相同.然而在大多數(shù)圖像處理應(yīng)用程序中只有低頻DCT系數(shù)部分才保存最有用的信號(hào)信息，所以實(shí)際上中只需要計(jì)算這部分DCT系數(shù)就可以了.這種只計(jì)算部分DCT系數(shù)的方法通常被稱為DCT修剪或修剪DCT［10］.由于只計(jì)算一部分而不是完整的DCT系數(shù)，DCT修剪可以減少一些CPU的運(yùn)算操作和一定數(shù)量的內(nèi)存訪問.因此DCT修剪一般比傳統(tǒng)DCT速度更快，效率更高.目前也有許多算法已用于計(jì)算DCT修剪［8，9］等.Wang［10］在這些論文中首先提出有效的快速DCT修剪算法(Fast DCT Prunning).后來又有學(xué)者提出修剪FCT(Prunning FCT)［11］，并且通過與前者比較計(jì)算復(fù)雜度而證明文獻(xiàn)［10］更快.

盡管DCT修剪比傳統(tǒng)DCT和許多已經(jīng)出現(xiàn)在文獻(xiàn)上的算法快，但是到目前為止，大多數(shù)快速DCT修剪算法并沒有具體的軟件實(shí)現(xiàn)，而且僅有的一些軟件實(shí)現(xiàn)也都是基于通用處理器的.基于通用處理器的軟件實(shí)現(xiàn)通常遠(yuǎn)比基于DSP的實(shí)現(xiàn)速度慢.DSP是一類特殊的經(jīng)過優(yōu)化以用來處理各種信號(hào)處理應(yīng)用程序的處理器，如FIR濾波器、傅里葉變換FFT、DCT以及他們各自的修剪算法.在工業(yè)上，DSP作為各種信號(hào)處理應(yīng)用程序的平臺(tái)，發(fā)揮著重要的作用.德州儀器(TI)，模擬設(shè)備公司(ADI)和飛思卡爾等DSP制造商已經(jīng)提供了很多不同的DSP芯片及其評(píng)估板材和仿真工具，供大學(xué)研究和工業(yè)使用.由于其性能的優(yōu)異性、靈活性以及合適的成本，基于DSP的軟件實(shí)現(xiàn)已經(jīng)成為優(yōu)良的商業(yè)產(chǎn)品解決方案.

然而在實(shí)際當(dāng)中，基于DSP的快速而有效的FCT修剪實(shí)現(xiàn)仍然很困難.眾所周知，DSP系統(tǒng)的內(nèi)存訪問會(huì)導(dǎo)致較長(zhǎng)的時(shí)鐘延遲和大量的功耗，因此運(yùn)算成本非常高.如在TI TMS320C64x DSP中，執(zhí)行一個(gè)內(nèi)存裝載指令會(huì)花費(fèi)四個(gè)時(shí)鐘周期.因此頻繁內(nèi)存訪問會(huì)大幅增加時(shí)鐘周期數(shù).盡管DCT修剪與快速DCT算法相比能減少一定數(shù)量的內(nèi)存訪問，但卻沒有根本解決問題.諸如修剪FCT［11］中還是存在大量由輸入點(diǎn)和權(quán)重因子(余弦系數(shù))而導(dǎo)致的內(nèi)存訪問數(shù)量，這也在很大程度上影響了速度的提高.

本文提出了一個(gè)新的減少內(nèi)存訪問的修剪FCT算法.首先利用修剪FCT中權(quán)重因子的性質(zhì)來減少運(yùn)算所需的權(quán)重因子數(shù).然后將運(yùn)算流程圖內(nèi)兩個(gè)階段中的蝴蝶計(jì)算結(jié)構(gòu)合并到一個(gè)階段，從而形成一個(gè)高效的蝴蝶計(jì)算結(jié)構(gòu)來進(jìn)行計(jì)算.實(shí)驗(yàn)結(jié)果表明，該方法可以節(jié)約用于保存權(quán)重因子的內(nèi)存空間，并且也能顯著減少運(yùn)算所需的內(nèi)存訪問以及時(shí)鐘周期的數(shù)量.

2　快速離散余弦變換的修剪算法

修剪FCT回顧:本節(jié)首先簡(jiǎn)要介紹FCT(快速離散余弦變換)的基本思想.然后簡(jiǎn)要介紹基于FCT的修剪FCT.

2.1直接FCT計(jì)算

式(1)給出了最常用的離散余弦變換: II-型DCT.

為簡(jiǎn)便起見，我們將公式右邊的比例系數(shù)一起整合到X［m］中，并應(yīng)用于文獻(xiàn)［12］中提到的輸入映射:

接著通過使用三角函數(shù)的性質(zhì)(4)以及將式(3)中的輸出序列X［M］分解為奇數(shù)與偶數(shù)索引部分.

于是便有了兩個(gè)N/2點(diǎn)DCT［12］.然后進(jìn)一步分解直到一系列兩點(diǎn)輸入DCT，便得到了按頻率分解的FCT［11］.圖1列出了FCT運(yùn)算流程圖.(注:目前在流程圖中虛線和實(shí)線是相同作用的).它由兩部分組成:蝴蝶計(jì)算部分和后序操作部分.在蝴蝶計(jì)算部分除了輸入點(diǎn)和系數(shù)(2c)不同以外，算法流程與FFT類似.如圖所示，蝴蝶計(jì)算部分與后序操作部分相比，產(chǎn)生了大部分內(nèi)存訪問和CPU計(jì)算.本文的內(nèi)容將專注于蝴蝶計(jì)算部分.

2.2修剪FCT

DCT在具備快速算法的一類轉(zhuǎn)換運(yùn)算中具備非常優(yōu)越的能量壓縮屬性.正是這種可以僅僅計(jì)算部分系數(shù)的屬性，使得DCT在各種圖形信號(hào)處理應(yīng)用程序中最適合處理有損數(shù)據(jù)壓縮轉(zhuǎn)換.通常，25%的DCT系數(shù)已經(jīng)能夠很好的壓縮和恢復(fù)圖像，而不會(huì)造成視覺上的差異［2］.如在圖1的N個(gè)DCT系數(shù)中，如僅計(jì)算前N0個(gè)低頻組件(其中N0= 3，N = 16，N0不一定是2的整數(shù)冪)，那么就不用處理圖中虛線對(duì)應(yīng)的所有運(yùn)算，因此修剪FCT相比一般FCT能節(jié)省一些操作(包括CPU運(yùn)算和內(nèi)存訪問操作).不過實(shí)際運(yùn)算中，它還是存在很多由權(quán)重因子和輸入點(diǎn)X［］而導(dǎo)致的內(nèi)存訪問.

然后式(1)就改寫為

3　修剪FCT的內(nèi)存訪問優(yōu)化方法

為了解決上述提到的問題，我們提出了內(nèi)存訪問優(yōu)化方法，該方法通過兩個(gè)步驟來應(yīng)用于修剪FCT.

步驟1:利用權(quán)重因子的余弦函數(shù)屬性(5)，將實(shí)現(xiàn)N點(diǎn)修剪FCT的權(quán)重因子數(shù)量由N - 1減少到「(2N -1)/3」.

例如在圖1中的階段3和4中的蝴蝶運(yùn)算單元需要分別與權(quán)重因子:結(jié)合計(jì)算.其中可用取代，推導(dǎo)過程如下:

步驟2:在運(yùn)用上述特性后，將相鄰兩個(gè)階段中的全部蝴蝶運(yùn)算單元合并到一個(gè)階段中進(jìn)行運(yùn)算.

在修剪FCT計(jì)算流程圖中蝴蝶計(jì)算部分的階段s中有N/2s個(gè)不同的權(quán)重因子，它們按照如下方式進(jìn)行排列:階段s(s =0，1，2，……，log2N - 1)的第一個(gè)權(quán)重因子是:= cos(kπ/2N));階段s的第二個(gè)權(quán)重因子由第一個(gè)權(quán)重因子中的k加上N得到，即第三和第四個(gè)權(quán)重因子是由前兩個(gè)因子分別在他們的參數(shù)k上加N/2得到.在同一階段的其余權(quán)重因子都是通過這個(gè)遞歸過程而產(chǎn)生.因?yàn)樵谶\(yùn)行修剪FCT算法前對(duì)輸入點(diǎn)進(jìn)行了重排序［12］，所以在每個(gè)階段里的所有的蝴蝶運(yùn)算單元都可以按照自然數(shù)輸入序列的常規(guī)方式來從上向下逐一進(jìn)行計(jì)算.圖2(a)描繪出一般情況下在階段s和s + 1中相鄰的4個(gè)蝴蝶運(yùn)算單元之間的計(jì)算關(guān)系.

定理如圖2(a)所示，修剪FCT的蝴蝶計(jì)算部分階段s和s +1(s≤log2N -1)中的四個(gè)蝴蝶運(yùn)算單元只需通過加載如圖2(b)所示的兩個(gè)權(quán)重因子和來計(jì)算.

證明根據(jù)圖2(a)，階段s +1的蝴蝶運(yùn)算單元需要結(jié)合權(quán)重因子計(jì)算，而，根據(jù)三角函數(shù)屬性: cos2A = cos2A—sin2A，權(quán)重因子2cos(2mπ/ 2N)可改寫成2(cos(mπ/2N))2-2［sin(mπ/2N)］2，第一項(xiàng)而第二項(xiàng)2［sin(mπ/2N)］2可變?yōu)?2 { cos［(π/2)-(mπ/2N)］}2= 2{ cos［(π/2)+(mπ/2N)］}2= 2 { cos［(m +N)π/2N)］}2這樣就可以得到階段s + 1的權(quán)重因子:

因此，階段s + 1內(nèi)的權(quán)重因子可以由階段s內(nèi)的兩個(gè)權(quán)重因子推導(dǎo)出，所以只需加載這兩個(gè)權(quán)重因子便可以一起計(jì)算這4個(gè)蝴蝶運(yùn)算單元.

在減少權(quán)重因子后，我們將每?jī)呻A段中的蝴蝶運(yùn)算單元合并在一個(gè)階段中以形成一個(gè)如圖2(b)所示的高效蝴蝶運(yùn)算單元，所以當(dāng)log2N是奇數(shù)時(shí)，該方法要將階段1到階段log2N -1內(nèi)的所有蝴蝶運(yùn)算單元合并到(log2N -1)/2個(gè)階段內(nèi)來計(jì)算，而在階段log2N最后奇數(shù)階段)中的所有蝴蝶運(yùn)算單元還需用傳統(tǒng)的修剪FCT方法來計(jì)算.

利用完該方法后，圖1中的蝴蝶計(jì)算部分便可重新被畫為圖3所示.假設(shè)圖1和3均需要計(jì)算16個(gè)DCT系數(shù)，即圖中的實(shí)線和虛線沒有區(qū)別，那么圖3需要加載10個(gè)權(quán)重因子，而圖1的傳統(tǒng)修剪FCT卻需加載15個(gè)權(quán)重因子.此外在圖3中由輸入點(diǎn)X［］產(chǎn)生的內(nèi)存訪問只發(fā)生在圖中黑色和白色圓圈，而圖1里的由輸入點(diǎn)導(dǎo)致的內(nèi)存訪問卻發(fā)生在所有蝴蝶運(yùn)算單元兩邊所有圓圈內(nèi).

如果僅需計(jì)算部分DCT系數(shù)，則可以省略兩圖中的虛線部分，也就省去了相應(yīng)的運(yùn)算操作，并減少了圖中由黑圈所標(biāo)識(shí)的內(nèi)存訪問量.如圖1所示，在16點(diǎn)修剪FCT中，當(dāng)N0= 3，也即只計(jì)算3個(gè)DCT系數(shù)時(shí)，蝴蝶計(jì)算部分中因輸入點(diǎn)產(chǎn)生的內(nèi)存訪問量為87，而當(dāng)N0=16時(shí)它增加為128，相比之下在圖3中，當(dāng)N0= 3，因輸入點(diǎn)產(chǎn)生的內(nèi)存訪問量為僅為43，而當(dāng)N0= 16時(shí)它增加為64.

4　內(nèi)存訪問優(yōu)化方法的性能評(píng)價(jià)

假設(shè)N點(diǎn)輸入中計(jì)算N0個(gè)DCT系數(shù)，同時(shí)查看N0是2的整數(shù)冪的特殊情況，在傳統(tǒng)修剪FCT的蝴蝶計(jì)算部分中，由輸入點(diǎn)產(chǎn)生的內(nèi)存訪問量為(2log2N0+3)N -3N0，采用本文的方法后，內(nèi)存訪問量減少到如下表達(dá)式:

并且該方法可以使N點(diǎn)修剪FCT中由權(quán)重因子產(chǎn)生的內(nèi)存訪問量從N -1它減少到「(2N -1)/3」.

為了能方便全面推廣，我們選取了一款比較通用的處理器: TI TMSC320C64x DSP為測(cè)試平臺(tái).實(shí)驗(yàn)中編寫了兩段C代碼來對(duì)比:代碼C1用傳統(tǒng)算法實(shí)現(xiàn)修剪FCT，代碼C2則基于內(nèi)存訪問優(yōu)化方法實(shí)現(xiàn)修剪FCT.兩段代碼都包括一段相同的基于［11］的后序操作部分.測(cè)試環(huán)境采用德州儀器設(shè)計(jì)的軟件開發(fā)工具Code Composer Studio(CCS).由于篇幅限制，我們只能用如下三個(gè)表來報(bào)告當(dāng)修剪值N0為2的整數(shù)冪時(shí)的對(duì)比數(shù)據(jù):表1列出時(shí)鐘周期數(shù);表2列出由權(quán)重因子和輸入點(diǎn)產(chǎn)生的內(nèi)存訪問量;表3列出存儲(chǔ)權(quán)重因子所需內(nèi)存量.

結(jié)果表明，應(yīng)用該方法的修剪FCT相比于傳統(tǒng)方式能減少平均40%的由權(quán)重因子和輸入點(diǎn)產(chǎn)生的內(nèi)存訪問量，減少平均48.6%的時(shí)鐘周期數(shù)和節(jié)約平均32.6%的內(nèi)存空間.目前公認(rèn)25%的DCT系數(shù)就能很好地重建圖像［2］，而當(dāng)修剪值N0為N的25%時(shí)，該方法可以減少平均44%的內(nèi)存訪問數(shù)量，以及減少平均51.3%的時(shí)鐘周期數(shù).

5　結(jié)論

本文提出了實(shí)現(xiàn)修剪FCT算法的內(nèi)存訪問優(yōu)化方法.它先利用權(quán)重因子的余弦函數(shù)屬性來減少計(jì)算過程中所需加載的權(quán)重因子數(shù)，然后將計(jì)算流程圖中兩個(gè)階段中的蝴蝶運(yùn)算單元合并到一個(gè)階段以形成一個(gè)高效蝴蝶單元結(jié)構(gòu).實(shí)驗(yàn)結(jié)果表明:相比于傳統(tǒng)實(shí)現(xiàn)算法，該方法可以減少平均40%的內(nèi)存訪問數(shù)量，減少平均48.6%的時(shí)鐘周期數(shù)和減少平均32.6%的用于存儲(chǔ)權(quán)重因子的內(nèi)存空間.

表1　時(shí)鐘周期數(shù)的比較

表2　內(nèi)存訪問量的比較

表3　存儲(chǔ)權(quán)重因子所需內(nèi)存空間(Byte)的比較

參考文獻(xiàn)

［1］N AHMED，T NATARAJAN，K R RAO.Discrete Cosine transform［J］.IEEE Transactions on Computers，1974，C -23: 90 -93.

［2］K R Rao，P Yip.Discrete Cosine Transform: Algorithms，Ad-vantages，Applications［M］.New York: Academic.1990.

［3］M Wezelenburg.General radix - 2n DCT and DST algori thms［A］.Proceedings of the International Conference on ECCTD’97［C］.Budapest，Hungary，1997.789 -794.

［4］李永亭，齊詠生，肖志云.基于量化的二維DCT優(yōu)化算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(2): 181 -183.

［5］沈鵬.基于多維矢量DCT正交矩陣變換及熵編碼算法的研究［D］.吉林:吉林大學(xué)，2011.

［6］劉斌，何劍鋒，孫玲玲.基于FPGA的H.264 DCT算法的硬件實(shí)現(xiàn)［J］.現(xiàn)代電子技術(shù)，2012，35(10): 90 -92.

［7］許亞軍，韓雪松，韓應(yīng)征.AVS二維DCT變換的FPGA實(shí)現(xiàn)［J］.電視技術(shù)，2013，37(11): 18 -21.

［8］R Stasiliski.On pruning the discrete Cosine and Sine transforms［A］.IEEE MELECON 2004［C］.IEEE，2004.269 -271.

［9］Mohamed El-Sharkawy，Waleed Eshmawy.A fast recursive pruned DCT for image compression applications［A］.Proceed-ings of the 37th Midwest Symposium on Circuits and Systems［C］.Los Angeles，USA: IEEE，1994.887 -891.

［10］Z Wang.Pruning the fast discrete Cosine transform［J］.IEEE Trans Communications，1991，39(5): 640 -643.

［11］Athanassios N Skodras.Fast discrete Cosine transform pruning［J］.IEEE Transactions on Signal Processing，1994，42(7): 1833 -1837.

［12］A N Skodras，A G Constantinides.Efficient input-reordering algorithms for fast DCT［J］.Electronics Letters，1991，27(21): 1973 -1975.

劉項(xiàng)洋男，1979年6月生于安徽省蕪湖市，博士，現(xiàn)為安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院講師，主要研究方向?yàn)閿?shù)字信號(hào)處理算法、嵌入式計(jì)算.

E-mail: 33736326@ qq.com

許勇男，1966年12月生于安徽省六安市.博士，安徽師范大學(xué)數(shù)學(xué)計(jì)算機(jī)科學(xué)學(xué)院教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和嵌入式計(jì)算.

E-mail: yxull@ mail.ahnu.edu.cn

Memory Access Optimization Method for the Implementation of Fast DCT Pruning on DSP

LIU Xiang-yang，XU Yong
(School of Math and Computer Science，Anhui Normal University，Wuhu，Anhui 241000，China)

Abstract:In this paper，we propose a memory access optimization method to minimize the memory accesses due to weighting factors(cosine coefficients in the computation diagram of fast DCT pruning)and input points for implementing fast DCT pruning on DSP.The proposed method reduces the number of memory accesses in two steps: 1.Reduce the number of weighting factors; 2.Combine butterflies at two stages in fast DCT pruning diagram to form an efficient butterfly structure in one stage and calculate them.The proposed method is applied to implement Pruning FCT on TI TMSC320C64x DSP.Experimental results show that the proposed method can achieve an average of 40%memory access reduction，48.6%clock cycle reduction and 32.6%of memory space saving for weighting factors to compute Pruning FCT on DSP comparing with the conventional implementation.

Key words:digital signal processor(DSP); discrete Cosine transform(DCT); memory access

作者簡(jiǎn)介

收稿日期:2014-05-19;修回日期: 2015-07-06;責(zé)任編輯:李勇鋒

DOI:電子學(xué)報(bào)URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.034

中圖分類號(hào)：TN911.23

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112(2016)01-0227-06