整型2D－IDCT算法的優(yōu)化與實(shí)現(xiàn)

胡小濤，梁利平

(中國科學(xué)院微電子研究所，北京 100029)

自從Ahmed和Rao于1974年給出離散余弦變換(DCT)定義以來，這類變換被廣泛應(yīng)用，對于這類變換的快速算法的研究發(fā)展也十分重要，特別是對特定條件下的快速算法的研究對于整個系統(tǒng)的性能提高有很大幫助。

在IDCT計算中，對于一個8×8大小的圖像塊而言，如果要直接計算，將需要4096次乘法和4032次加法。而IDCT的3種經(jīng)典快速算法為B.G.Lee算法、AAN算法和LLM算法，都是基于如何減少運(yùn)算次數(shù)而設(shè)計。而對于整數(shù)2D-IDCT變換而言，如何保證計算精度滿足IEEE Standard 1180—1990與離散余弦變換標(biāo)準(zhǔn)也是一大挑戰(zhàn)。

本文基于自身的DSP平臺，通過不同算法之間的比較與分析，設(shè)計出滿足標(biāo)準(zhǔn)前提下的解決方案，設(shè)計并確保計算精度，在此算法基礎(chǔ)上進(jìn)行匯編優(yōu)化，盡可能地減少消耗，得到滿足預(yù)期的實(shí)現(xiàn)結(jié)果。

1 整型2D-IDCT算法設(shè)計

1.1 算法描述

為了下一步的算法設(shè)計，本文首先對公式進(jìn)行簡單變換

把公式轉(zhuǎn)換為矩陣并經(jīng)過余弦函數(shù)化解得到

于是可采取常用的蝶形運(yùn)算方法(Loeffler，Chen W等IDCT快速算法)，過程如下

計算后的y［0］～y［7］作為輸入再次運(yùn)算便可得到2D-IDCT 結(jié)果［1-3］。

1.2 算法設(shè)計

進(jìn)行整數(shù)IDCT變換［4-6］，需將上述公式中矩陣C(泛指)中的浮點(diǎn)運(yùn)算定點(diǎn)化，因此如何最大限度保證數(shù)據(jù)精確性成為這一步的首要工作。在已有的蝶形運(yùn)算優(yōu)化的基礎(chǔ)上，本文根據(jù)精度標(biāo)準(zhǔn)需求，提出保證精度的解決方案，在保證數(shù)據(jù)精確性的前提下實(shí)現(xiàn)優(yōu)化。

由于擴(kuò)展時會進(jìn)行一次舍入，因此第一次運(yùn)算的擴(kuò)展位數(shù)應(yīng)該達(dá)到最大限度。而轉(zhuǎn)換成2次1D-IDCT運(yùn)算后，第一次運(yùn)算結(jié)果為32位，進(jìn)入第二次計算時需要縮小到16位參與運(yùn)算，必須舍棄低位數(shù)據(jù)來參與第二次運(yùn)算。

本文暫且遵循這樣一個原則:盡量保留第二次運(yùn)算前輸入數(shù)據(jù)位數(shù)。本文在后面會對比矩陣C與保留位數(shù)之間的優(yōu)劣。

第一次IDCT運(yùn)算的輸入是16位數(shù)據(jù)，實(shí)際有效位數(shù)為12位整數(shù)(-2048～2047)。運(yùn)算中共有8個數(shù)據(jù)參與加減，須空余3位緩沖區(qū)域，故而最大可用于矩陣C位數(shù)為17位。而根據(jù)上面得到的第二次運(yùn)算輸入數(shù)據(jù)保留最多的原則。第二次矩陣運(yùn)算時輸入數(shù)據(jù)要保留16位。同樣會進(jìn)行8個數(shù)據(jù)加減占用3位，因此第二次的運(yùn)算中矩陣C的可設(shè)定位數(shù)為13位，參考圖1。

圖1 矩陣C參考

于是有兩種方案選擇:

1)方案1，固定選取矩陣C為13位，參與2次矩陣運(yùn)算。

2)方案2，第一次選擇17位矩陣C，第二次選擇13位，分別運(yùn)算。

如果2次選擇的矩陣相同，后面實(shí)現(xiàn)起來將會更加簡潔;但如果精度不能滿足要求，則需要采取方案2。但經(jīng)過考慮認(rèn)為，每次二維IDCT計算都要使用2個矩陣來進(jìn)行，損耗太大。特別是在匯編實(shí)現(xiàn)時，每次IDCT運(yùn)算的第一次計算結(jié)果緩存之后，還需要更新一次矩陣C，不僅會導(dǎo)致寄存器緊張，而且耗時較多。

實(shí)際操作中發(fā)現(xiàn)每一步蝶形運(yùn)算中y［0］=a0+b0=(x［0］× C4+x［2］× C2+x［4］× C4+x［6］× C6)+(x［1］×C1+x［3］×C3+x［5］×C5+x［7］×C7)，未能飽和利用數(shù)據(jù)位。cos(n×π/16)是0.195～0.98之間的。這樣就算是輸入比特流x［0］到x［7］都為12位數(shù)(比如2000以上的數(shù)據(jù))，相加之后的 y［0］只有4.577×2000，而預(yù)留的3位總共能達(dá)到8×2000大小的數(shù)據(jù)。于是在矩陣C中乘，因?yàn)?4.577×≈6.47，沒有超過8。同樣的2個矩陣C相乘之后相當(dāng)于=2，這樣在之后的右移移位還原中多移一位即可，不用再做額外的變換。

于是，提出方案3:選取固定的13位矩陣再乘作為矩陣C參與運(yùn)算。

3種方案實(shí)驗(yàn)結(jié)果對比參見表1，顏色加深處表示結(jié)果未達(dá)標(biāo)。

IEEE Standard 1180—1990標(biāo)準(zhǔn)主要要求有:

1)經(jīng)過浮點(diǎn)運(yùn)算得到參考結(jié)果f’(x，y)與整數(shù)IDCT運(yùn)算結(jié)果f(x，y)誤差值不大于1。

表1 3種方案實(shí)驗(yàn)結(jié)果對比

2)下面4個誤差不越界:

本文選擇方案3進(jìn)行測試。精度遠(yuǎn)遠(yuǎn)超過IEEE Standard 1180—1990標(biāo)準(zhǔn)的要求。與參考文獻(xiàn)［7］中針對精度提升的離散余弦變換的測試精度相仿，其中在體現(xiàn)整體性能的Pme(點(diǎn)平均誤差)參數(shù)上本文精度要優(yōu)于文獻(xiàn)［7］。

在大幅度滿足精度要求的基礎(chǔ)上，繼續(xù)進(jìn)行標(biāo)準(zhǔn)離散余弦變換要求測試，在［-5，5］，［-256，255］，［-384，383］這3個區(qū)間段之間隨機(jī)抽取1×104和1×106兩組數(shù)據(jù)參與測試，結(jié)果參照表2，陰影部分為文獻(xiàn)［7］中經(jīng)過精度優(yōu)化后的整體性能參數(shù)對比。

表2 標(biāo)準(zhǔn)離散余弦變換測試結(jié)果

由于本文之前遵循一個原則:盡量保留第二次運(yùn)算前輸入數(shù)據(jù)位數(shù)。實(shí)際上如果減小第二次運(yùn)算的保留位數(shù)，可以得到更精確的矩陣C。本文將保留位數(shù)與矩陣C大小的不同設(shè)定得到一個誤差對比，參數(shù)去除了相同的分母，保留分子誤差數(shù)據(jù)，結(jié)果見表3。

表3 矩陣C大小不同設(shè)定的誤差對比

由測試數(shù)據(jù)可以得知，選擇更大的矩陣C將使得Omse測試參數(shù)更小，選擇保留更多位數(shù)將使Ome測試參數(shù)更小。這是因?yàn)閮煞N選擇方式降低失真度的重點(diǎn)不同，實(shí)現(xiàn)者可以通過實(shí)際操作的需要有所取舍。在本次實(shí)現(xiàn)中兩者均能達(dá)到測試標(biāo)準(zhǔn)，最后本文采取優(yōu)先保留位數(shù)的方法。

1.3 匯編設(shè)計

本文在自主設(shè)計的指令集環(huán)境下完成上述IDCT運(yùn)算模塊，有包括MIPS 32個寄存器在內(nèi)一共64個32位寄存器可供支配。由于IDCT運(yùn)算中間結(jié)果為64個，在要求高并行度計算的前提下，無法提供足夠寄存器空間存儲中間數(shù)據(jù)，第一次IDCT計算結(jié)果將會回存并在第二次計算時再取出。實(shí)現(xiàn)流程如圖2所示。

圖2 匯編實(shí)現(xiàn)流程

由上述流程圖可知，2次8×8運(yùn)算、轉(zhuǎn)置、數(shù)據(jù)搬運(yùn)、邊界截取組成了一次IDCT計算的消耗主體，同時也是優(yōu)化重點(diǎn)。

指令環(huán)境對于每次轉(zhuǎn)置運(yùn)算，針對的是4×8的數(shù)據(jù)塊，轉(zhuǎn)置之后的數(shù)據(jù)參與第二次運(yùn)算后要存在寄存器中然后順序存回內(nèi)存。在匯編中轉(zhuǎn)置消耗較多，開銷主要在轉(zhuǎn)置后的數(shù)據(jù)調(diào)整和第二次運(yùn)算后為后面邊界截取進(jìn)行數(shù)據(jù)準(zhǔn)備，本文經(jīng)過分析轉(zhuǎn)置消耗，采取手動配置初始寄存器位置的方式將最終轉(zhuǎn)置控制消耗降低為2個周期。配置如圖3所示。

圖3 轉(zhuǎn)置運(yùn)算寄存器分配

在每個4×8計算塊的數(shù)據(jù)并行性保證上，采用多指針電梯式掃描方式存取，將數(shù)據(jù)的轉(zhuǎn)移搬運(yùn)冗余操作降低到最低限度。經(jīng)過每次電梯式掃描方式存取之后，4×8數(shù)據(jù)塊運(yùn)算完畢，進(jìn)入下一個模塊計算時橫向移動即可，這樣既保證了數(shù)據(jù)的流水線操作，大大降低了損耗，同時也化簡了兩次運(yùn)算中數(shù)據(jù)搬運(yùn)的冗余操作。操作如圖4所示。

圖4 電梯掃描方式操作

在流程圖中可知，每次IDCT運(yùn)算需要循環(huán)8次，而在上述的匯編優(yōu)化中可知，為實(shí)現(xiàn)并行運(yùn)算和優(yōu)化方法，需要將每次運(yùn)算的循環(huán)數(shù)減小，增加循環(huán)體內(nèi)部計算。為找到最佳循環(huán)次數(shù)，本文在操作中將循環(huán)次數(shù)逐漸減小，并對每個循環(huán)次數(shù)下的結(jié)構(gòu)進(jìn)行盡可能的優(yōu)化仿真，得到對比數(shù)據(jù)見表4，陰影處表示選擇此方法。

表4 循環(huán)次數(shù)選擇與周期損耗關(guān)系

從上面對比圖可以得知，隨著循環(huán)次數(shù)減小，行運(yùn)算和列運(yùn)算中每次循環(huán)的開銷變大，但綜合來說循環(huán)2次時總周期最小，最終優(yōu)化結(jié)果需要(6×136+8)個周期(在6 blocks的情況下)。完全去除循環(huán)時，雖然減少了循環(huán)消耗，但增加了寄存器分配操作，且流水線利用率也已達(dá)到飽和，最終效率不及前者。于是采用2次循環(huán)方法。

2次循環(huán)方法最大限度地利用了之前的轉(zhuǎn)置控制寄存器分配和邊界截取時的并行處理能力，最大限度地發(fā)揮了流水線作用，使得最終的消耗在140以內(nèi)。

2 實(shí)驗(yàn)對比

純MIPS指令實(shí)現(xiàn)的計算如果不加優(yōu)化，對于每次IDCT計算會進(jìn)行4096次乘法和4032次加法，在仿真器下做一次計算，周期數(shù)接近20000。而采用快速算法優(yōu)化之后用MIPS指令自動實(shí)現(xiàn)匯編進(jìn)行一次IDCT計算周期數(shù)在1000左右，作為本文性能指標(biāo)的縱向比較。

同時，本文參考了TI產(chǎn)品指標(biāo)中的IDCT模塊消耗作為參照標(biāo)準(zhǔn)，這些數(shù)據(jù)是在TI平臺上優(yōu)化之后得到的，采用的指令系統(tǒng)、算法和優(yōu)化方法與本文不同，作為性能的橫向比較(見表5)。

表5 IDCT模塊性能對比表

在運(yùn)行多個block下，各個不同產(chǎn)品性能指標(biāo)有一定變化，DSP在6 blocks下周期數(shù)可到137，參照視圖見圖5。

圖5 IDCT模塊性能對比圖

經(jīng)過分析，本文基于的DSP平臺下的IDCT計算效果好于TMS320C62X，差于TMS320C64X+系列。TMS320C64X+解第1個block的周期為135 cycles，在解到6 blocks之后速度會提升到103 cycle。這也是需要學(xué)習(xí)和改進(jìn)的地方。

3 結(jié)束語

本文依據(jù)離散余弦變換和IEEE Standard 1180—1990標(biāo)準(zhǔn)分析并選擇符合要求的算法來實(shí)現(xiàn)2D-IDCT功能，所進(jìn)行的驗(yàn)證試驗(yàn)符合預(yù)期。在匯編優(yōu)化上針對本文所基于的DSP指令設(shè)計符合需要的相應(yīng)代碼并使用并行流水線結(jié)構(gòu)優(yōu)化，實(shí)現(xiàn)了IDCT運(yùn)算并達(dá)到計算優(yōu)化度預(yù)期。在與同類IDCT運(yùn)算方法進(jìn)行結(jié)果比較之后也找到了一些不足，這也是下一步需要優(yōu)化的方向。

［1］CHEN W H.A fast computational algorithm for the discrete cosine transform［J］.IEEE Trans.Communication，1977，25(9):1004-1009.

［2］FEIG E，WINOGRAD S.On the multiplicative complexity of discretecosine transform［J］.IEEE Trans.Inform.Theory，1992，38(6):1387-1391.

［3］LOEFFLER C，LIGHTENBERG A，MOSCHYTZ G S.Practical fast 1-DDCT algorithms with 11-Multiplications［EB/OL］.［2013-01-20］.http://ieeexplore.ieee.org/xpl/articleDetails.jsp reload=true&arnumber=266596.

［4］SLAWECKI D，LI W.DCT/IDCT processor design for high data rate image coding［J］.IEEE Trans.Circuits System Video Technology，1992，2(2):135-145.

［5］EI M，BELKOUCH S.An efficient pipelined fast and multiplier-less 2-D IDCT for image/video decoding［EB/OL］.［2013-01-20］.http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5945687.

［6］KIHO C，KIHOON L.Zero coefficient-aware fast IQ-IDCT algorithm［EB/OL］.［2013-01-20］.http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5657972&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5657972.

［7］唐永亮.高速高精度離散余弦變換的設(shè)計與實(shí)現(xiàn)［D］.天津:天津大學(xué)，2008.