陣列處理器上一種基于DFGSP的分像素插值算法實(shí)現(xiàn)

胡傳瞻 蔣 林 朱 筠 謝曉燕 王 萍 楊 坤

1(西安郵電大學(xué)計(jì)算機(jī)學(xué)院 陜西 西安 710121) 2(西安科技大學(xué)集成電路實(shí)驗(yàn)室 陜西 西安 710054) 3(西安郵電大學(xué)電子工程學(xué)院 陜西 西安 710121)

0 引 言

視頻編解碼應(yīng)用具有數(shù)據(jù)量大、算法各異、標(biāo)準(zhǔn)眾多的特點(diǎn)。H.264/AVC、H.265/HEVC是當(dāng)前應(yīng)用最為廣泛的視頻編解碼標(biāo)準(zhǔn)，其中分?jǐn)?shù)運(yùn)動(dòng)估計(jì)(Fractional Motion Estimation，F(xiàn)ME)是視頻編解碼器中計(jì)算密集度最高的任務(wù)之一，而亞像素精度運(yùn)動(dòng)估計(jì)是其中最復(fù)雜的部分。國(guó)內(nèi)外學(xué)者已有很多針對(duì)各種分辨率下的FME軟、硬件實(shí)現(xiàn)方案。文獻(xiàn)[1]提出了兩個(gè)近似的HEVC分?jǐn)?shù)插值濾波器，通過(guò)修改插值濾波器系數(shù)來(lái)進(jìn)行分?jǐn)?shù)濾波，能耗降低了67.1%，但是以損耗峰值信噪比(Peak Signal to Noise Ratio，PSNR)和增加比特率為代價(jià)。文獻(xiàn)[2]提出了一種可配置的濾波器的電路結(jié)構(gòu)，雖然提高了硬件資源利用率，但卻增加了計(jì)算的復(fù)雜度。

目前現(xiàn)有的方法可以減少較多的數(shù)據(jù)計(jì)算量，但是分?jǐn)?shù)像素插值計(jì)算的硬件實(shí)現(xiàn)難度較大，資源消耗過(guò)多，采用超大規(guī)模集成電路進(jìn)行視頻編碼時(shí)缺少靈活性，難以滿足視頻編碼質(zhì)量多標(biāo)準(zhǔn)的要求?？芍貥?gòu)陣列處理器在視頻方面應(yīng)用十分廣泛，在進(jìn)行復(fù)雜計(jì)算時(shí)，會(huì)將復(fù)雜的計(jì)算拆分成若干的子任務(wù)，將若干子任務(wù)合理地映射到可重構(gòu)陣列處理器中是十分重要的。文獻(xiàn)[3]提出了臨時(shí)數(shù)據(jù)的寄存器存儲(chǔ)和無(wú)寄存器存儲(chǔ)相結(jié)合的可重構(gòu)算術(shù)邏輯單元簇(Reconfigurable ALU Cluster，RAC)間通信方式，設(shè)計(jì)了計(jì)算模型松弛映射調(diào)度算法，該方法達(dá)到了復(fù)雜計(jì)算內(nèi)核運(yùn)行時(shí)間的最大化，缺點(diǎn)是RAC的配置成本較大。文獻(xiàn)[4]提出了一種并行度最大化的貪婪算法，雖然獲得了較大并行度，但此算法并沒(méi)有考慮實(shí)際存在的硬件碎片問(wèn)題。文獻(xiàn)[5-6]提出了細(xì)粒度的劃分方法，但并未和粗粒度可重構(gòu)體系結(jié)構(gòu)(Coarse Grained Reconfigurable Architecture，CGRA)映射技術(shù)相結(jié)合。

合理的并行映射方案可以解決資源分配不合理、計(jì)算復(fù)雜等問(wèn)題，從而提高可重構(gòu)陣列處理器的計(jì)算效率。文獻(xiàn)[7]提出了一個(gè)雙輸入神經(jīng)網(wǎng)絡(luò)，捕獲應(yīng)用程序中數(shù)據(jù)流圖(Data Flow Graph，DFG)的元素和CGRA元素陣列中特征的過(guò)程，建立了自動(dòng)培訓(xùn)和測(cè)試的數(shù)據(jù)集，實(shí)現(xiàn)了基于整個(gè)映射流程的卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network，CNN)預(yù)測(cè)，減少了編譯時(shí)間。文獻(xiàn)[8]為了獲得用于CGRA應(yīng)用程序映射的更好的數(shù)據(jù)傳輸路徑，提出了一種用于路由資源共享優(yōu)化的兩步蟻群算法，將傳統(tǒng)蟻群算法的搜索過(guò)程分為兩步，執(zhí)行時(shí)間比傳統(tǒng)蟻群算法少32%，且數(shù)據(jù)傳輸路徑也減少4%～6%。由此可看出，任務(wù)劃分對(duì)可重構(gòu)處理器提高整體執(zhí)行性能、降低能耗具有重要作用。

因此本文采用了一種基于DFGSP算法[9]，針對(duì)亞像素精度運(yùn)動(dòng)估計(jì)中的計(jì)算部分，按深度優(yōu)先搜索方式，對(duì)該算法的DFG圖進(jìn)行合理任務(wù)劃分，設(shè)計(jì)并行映射方案，在視頻陣列處理器上加速實(shí)現(xiàn)。使其兼具軟件可編程靈活性和硬件實(shí)現(xiàn)的高效性。達(dá)到提高計(jì)算速度和節(jié)約大量硬件資源的目的。

1 分像素插值的DFG

HEVC沿用了H.264中1/2、1/4像素精度運(yùn)動(dòng)估計(jì)，但使用了更多鄰近像素點(diǎn)進(jìn)行亞像素精度插值，其重點(diǎn)是對(duì)亮度分量進(jìn)行插值計(jì)算。1/2像素模板和1/4像素模板如圖1所示。亮度分量的1/2像素位置值由離散余弦變化的8抽頭濾波器生成，亮度分量1/4、3/4像素位置的值由離散余弦變化的7抽頭濾波器生成，抽頭系數(shù)如表1所示。

表1 亮度差值濾波器抽頭系數(shù)表

分像素插值的計(jì)算過(guò)程分為兩步：

(1) 以1/2像素點(diǎn)公式為例進(jìn)行變換，將像素點(diǎn)A0,-3、A0,-2、A0,-1、A0,0、A0,1、A0,2、A0,3、A0,4分別記作a、b、c、d、e、f、g、h，得到式(1)。

h0，0=(-a+4b-11c+40d+40e-11f+4g-h)>>6=

[-(a+h)+4(b+g)-8(c+f)-4(c+f)+(c+f)+

32(d+e)+8(d+e)]>>6=

[(b+g)>>2-(a+h)-((c+f)>>3+(c+f)>>2))+

(d+e)>>5+(d+e)>>3]>>6

(1)

對(duì)式(1)進(jìn)行分析，根據(jù)其數(shù)據(jù)流向畫出圖2所示的1/2像素點(diǎn)DFG。其中:“+”表示對(duì)輸入數(shù)值進(jìn)行加法運(yùn)算；“-1”表示對(duì)輸入數(shù)值取相反數(shù)；“<>n”表示對(duì)輸入數(shù)值進(jìn)行右移位操作，即對(duì)輸入數(shù)值除以2的n次冪。

(2) 以1/4像素點(diǎn)公式進(jìn)行變換，將A-3,0、A-2,0、A-1,0、A0,0、A1,0、A2,0、A3,0分別記作t、u、v、w、x、y、z, 得到以下分像素點(diǎn)：

a0,0=(-t+4u-10v+58w+17x-5y+z)>>6=

[10(w-v)-5y+4u+(48w+16x)+x+z-t]>>6=

[8(w-v)-4y+4u+2(w-v)-y+16(3w+x)+x+z-t]>>6=

{[2(w-v)-y+u]>>2+(w-v)>>1-y+[(w>>1+w)+

x]>>4+x+z-t}>>6

(2)

由于3/4像素插值計(jì)算與1/4像素插值計(jì)算是對(duì)稱的，故可用相同DFG通過(guò)反轉(zhuǎn)輸入?yún)⒖枷袼氐捻樞騺?lái)實(shí)現(xiàn)，因此不再展開(kāi)描述。

2 基于深度優(yōu)先貪婪算法的分像素插值任務(wù)劃分

本文使用一種基于DFGSP劃分方法，基于待劃分的插值計(jì)算DFG(其中每個(gè)節(jié)點(diǎn)表示為一個(gè)操作符)，分別從各就緒節(jié)點(diǎn)出發(fā)，沿DFG中的數(shù)據(jù)流向向下進(jìn)行搜索。具體實(shí)現(xiàn)為：先從待調(diào)度的就緒隊(duì)列中取出隊(duì)首任務(wù)，在給定的硬件面積的約束下，按深度優(yōu)先搜索方式掃描DFG，逐個(gè)劃入同時(shí)滿足下述兩個(gè)條件的節(jié)點(diǎn)。

(1) 本節(jié)點(diǎn)的輸入數(shù)據(jù)已經(jīng)由其他節(jié)點(diǎn)處理完并送至該節(jié)點(diǎn)輸入端口。

(2) 新節(jié)點(diǎn)加入后，劃分塊的輸出邊數(shù)不在原劃分塊輸出邊數(shù)的基礎(chǔ)上增加。

若有其中之一條件不符合時(shí)，跳過(guò)該計(jì)算流程，并將之前跳過(guò)流程后的后驅(qū)節(jié)點(diǎn)劃為就緒節(jié)點(diǎn)，繼續(xù)搜索其他就緒節(jié)點(diǎn)，直至沒(méi)有新的節(jié)點(diǎn)加入則搜索結(jié)束。

圖2中a、b、c、d、e、f、g、h八個(gè)像素點(diǎn)作為原始輸入直接從數(shù)據(jù)輸入存儲(chǔ)(Data Input Memory，DIM)中讀取。將所有節(jié)點(diǎn)分別劃分為v1-v16，初始就緒節(jié)點(diǎn)為第一層中的v1、v2、v3、v4節(jié)點(diǎn)，具體劃分步驟如下：

(1) 第一層的v1節(jié)點(diǎn)按深度優(yōu)先流向第二層的v5節(jié)點(diǎn)。數(shù)據(jù)流到第三層的v9節(jié)點(diǎn)時(shí)，需等待第二層v5、v6的計(jì)算結(jié)果。

(2) 由于v9節(jié)點(diǎn)加入后的塊間邊數(shù)小于當(dāng)前塊的邊數(shù)，滿足DFGSP算法條件，故將v9節(jié)點(diǎn)加入v2→v6流程中。因此v1→v5為任務(wù)p1，v2→v6→v9為任務(wù)p2。

按照算法規(guī)則將其他節(jié)點(diǎn)加入任務(wù)，則圖2的DFG劃分為如圖3中的任務(wù)p1、p2、p3、p4、p5。按照相同的劃分原則，可將圖4所示的1/4像素點(diǎn)的DFG進(jìn)行劃分,如圖5所示。

3 基于陣列處理器的分像素插值算法的并行映射

本文所用的視頻陣列處理器(DPR-CODEC)[10]是由項(xiàng)目組自主研發(fā)的一種可重構(gòu)視頻陣列處理器，支持H.264/AVC、MVC、H.265/HEVC等多種視頻編解碼標(biāo)準(zhǔn)，邏輯上把陣列結(jié)構(gòu)劃分成處理元簇(Process Element Group，PEG)，每個(gè)簇由4×4處理元(Process Element，PE)以陣列形式組成。由于視頻算法中的數(shù)據(jù)處理大部分以N×N矩形塊進(jìn)行，因此這種專用體系結(jié)構(gòu)相比其他結(jié)構(gòu)更能滿足視頻算法的需求，能更有效地對(duì)視頻算法進(jìn)行并行化設(shè)計(jì)。在可重構(gòu)計(jì)算的任務(wù)編譯過(guò)程中，由核心計(jì)算轉(zhuǎn)換來(lái)的DFG如何被映射到可重構(gòu)處理單元是實(shí)現(xiàn)可重構(gòu)系統(tǒng)高性能的關(guān)鍵所在[11]。

前期研究的亞像素精度運(yùn)動(dòng)估計(jì)采用兩步搜索完成分?jǐn)?shù)像素運(yùn)動(dòng)估計(jì)，結(jié)合不同分?jǐn)?shù)像素點(diǎn)的位置分布以及所需插值濾波器類型，使用8個(gè)PEG進(jìn)行分像素運(yùn)動(dòng)估計(jì)算法的映射，將周圍搜索候選點(diǎn)分別記為1/2像素候選點(diǎn)0-8(整像素點(diǎn)為4)。將8×8像素塊分解為4個(gè)4×4像素塊進(jìn)行率失真計(jì)算并累加得到8×8像素塊的率失真值。

本文經(jīng)過(guò)對(duì)亞像素精度運(yùn)動(dòng)估計(jì)算法的分析，在劃分時(shí)充分考慮1/2和1/4像素點(diǎn)中可復(fù)用的數(shù)據(jù)，以8×8大小的塊為例，僅需分別算出225個(gè)1/2像素點(diǎn)和225個(gè)1/4像素點(diǎn)，數(shù)據(jù)復(fù)用可以達(dá)到44%。如圖6所示，只需用2個(gè)PEG即可將1/2、1/4和3/4像素的DFG圖采用任務(wù)并行的方式映射在DPR-CODEC上。PEG00中，任務(wù)p1在PE00、PE10、PE30上分別實(shí)現(xiàn)加法和“-1”操作；任務(wù)p2、p3、p4、p5與p1類似。PE23用于計(jì)算比較得到最優(yōu)1/2像素點(diǎn)，通過(guò)鄰接互聯(lián)寄存器輸出給PEG01中的PE00、PE10、PE30。PEG01中采用相似處理方式實(shí)現(xiàn)1/4、3/4像素點(diǎn)的插值計(jì)算。選擇數(shù)據(jù)流水線方式并行執(zhí)行完8×8的整數(shù)點(diǎn)，算出所有的1/2像素點(diǎn)。

4 實(shí)驗(yàn)結(jié)果分析

4.1 測(cè)試方法及結(jié)果

為了驗(yàn)證基于DFGSP的分像素插值算法方案的可行性，在DPR-CODEC上進(jìn)行驗(yàn)證。將測(cè)試數(shù)據(jù)存入陣列處理器的數(shù)據(jù)存儲(chǔ)中，將并行方案的指令初始化到指令存儲(chǔ)器，用Modelsim仿真軟件分別對(duì)陣列結(jié)構(gòu)上實(shí)現(xiàn)兩步搜索方案和DFGSP進(jìn)行仿真驗(yàn)證。并在SMIC 90 nm工藝庫(kù)下進(jìn)行綜合。

圖7統(tǒng)計(jì)了高清測(cè)試序列highway_qcif.yuv(1 920×1 080)選擇兩種不同算法且不同大小編碼塊完成一幀圖像的運(yùn)行時(shí)間。結(jié)果顯示本方案完成一幀所用的時(shí)間都遠(yuǎn)低于兩步搜索方案的執(zhí)行時(shí)間。32×32塊大小所花費(fèi)時(shí)間最長(zhǎng)，采用DFGSP方案需要16.5×10-3s，幀率可達(dá)60幀/s，滿足1 920×1 080@30幀/s視頻序列的實(shí)時(shí)編碼需求。

在多核系統(tǒng)中，衡量程序性能的一個(gè)重要指標(biāo)就是加速比，加速比定義如下：

(3)

式中：T1是單處理器最優(yōu)串行算法計(jì)算時(shí)間；Tn是使用n個(gè)處理器并行計(jì)算時(shí)間；Sn是加速比。相比兩步搜索方案，針對(duì)8×8塊大小，本方案執(zhí)行加速比可達(dá)4.27；針對(duì)32×32塊大小加速比可達(dá)7.7。需要處理的編碼塊越大，DFGSP執(zhí)行速度越快，加速比越高。

4.2 性能分析

本文統(tǒng)計(jì)了高清測(cè)試序列highway_qcif.yuv(1 920×1 080)以8×8編碼塊為大小完成一幀所用的時(shí)鐘周期數(shù)為162 000，平均每個(gè)時(shí)鐘周期可以處理12.8個(gè)像素。表2為執(zhí)行時(shí)間對(duì)比，文獻(xiàn)[12]在15個(gè)時(shí)鐘周期可處理8×15個(gè)像素值，平均每個(gè)時(shí)鐘周期可處理8個(gè)像素，本文方案在1個(gè)時(shí)鐘周期內(nèi)可多處理4.8個(gè)像素值。對(duì)比文獻(xiàn)[13]，本文方案1個(gè)時(shí)鐘周期可多處理3.8個(gè)像素，減少了算法執(zhí)行的時(shí)間。

表2 執(zhí)行時(shí)間對(duì)比

表3為SMIC 90 nm工藝庫(kù)下，各方案執(zhí)行分像素插值算法的性能對(duì)比。本文算法將每個(gè)子任務(wù)流圖劃分到陣列處理器上進(jìn)行映射，在每個(gè)子任務(wù)進(jìn)行完后即可開(kāi)始下一個(gè)編碼塊的計(jì)算，16個(gè)PE規(guī)模的陣列結(jié)構(gòu)可同時(shí)處理16個(gè)子任務(wù)，故并行度為16。硬件實(shí)現(xiàn)時(shí)最大工作頻率可達(dá)357 MHz，與文獻(xiàn)[14]中的原始HEVC方法相比硬件資源使用減少了72%。與文獻(xiàn)[14]相比，硬件資源使用減少了60.1%；與文獻(xiàn)[15]所提出的插值濾波器VLSI架構(gòu)相比，硬件資源使用減少了30.78%。因此，在保證運(yùn)動(dòng)矢量精度的同時(shí)，本文方案可以快速完成分像素插值算法且節(jié)約了大量硬件資源消耗。

表3 性能對(duì)比(90 nm工藝庫(kù)下)

5 結(jié) 語(yǔ)

本文提出一種基于DFGSP的分像素插值任務(wù)劃分映射方法，該方法結(jié)合了視頻陣列處理器天然并行的特點(diǎn)，采用數(shù)據(jù)和任務(wù)并行的方法，將分像素插值的DFG中的子任務(wù)合理映射在視頻陣列處理器加速實(shí)現(xiàn)。實(shí)驗(yàn)表明，本文方案可滿足實(shí)時(shí)實(shí)現(xiàn)分像素插值算法的需求，執(zhí)行時(shí)間遠(yuǎn)低于兩步搜索方案。與專用插值濾波器相比，有效降低了資源消耗，提高了資源利用率和并行度。因此，將HEVC算法使用任務(wù)劃分的方式在陣列處理器上實(shí)現(xiàn)是降低計(jì)算復(fù)雜度和提高資源利用率問(wèn)題的一種有效方法。