劉項洋，許勇

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

?

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

劉項洋，許勇

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

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

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

1　引言

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

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

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

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

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

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

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

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

2.1直接FCT計算

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

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

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

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

2.2修剪FCT

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

然后式(1)就改寫為

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

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

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

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

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

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

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

證明根據(jù)圖2(a)，階段s +1的蝴蝶運算單元需要結(jié)合權(quán)重因子計算，而，根據(jù)三角函數(shù)屬性: cos2A = cos2A—sin2A，權(quán)重因子2cos(2mπ/ 2N)可改寫成2(cos(mπ/2N))2-2［sin(mπ/2N)］2，第一項而第二項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)的兩個權(quán)重因子推導(dǎo)出，所以只需加載這兩個權(quán)重因子便可以一起計算這4個蝴蝶運算單元.

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

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

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

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

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

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

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

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

5　結(jié)論

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

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

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

表3　存儲權(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］.計算機工程與應(yīng)用，2010，46(2): 181 -183.

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

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

［7］許亞軍，韓雪松，韓應(yīng)征.AVS二維DCT變換的FPGA實現(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.

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

E-mail: 33736326@ qq.com

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

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

作者簡介

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

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

中圖分類號：TN911.23

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

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