多層次細(xì)粒度并行HEVC幀內(nèi)模式選擇算法

張　峻　代　鋒　馬宜科　張勇東

1(中國科學(xué)院智能信息處理重點(diǎn)實(shí)驗(yàn)室 (中國科學(xué)院計(jì)算技術(shù)研究所)　北京　100190)2(中國科學(xué)院大學(xué)　北京　100049) (zhangjun01@ict.ac.cn)

多層次細(xì)粒度并行HEVC幀內(nèi)模式選擇算法

張峻1,2代鋒1馬宜科1張勇東1

1(中國科學(xué)院智能信息處理重點(diǎn)實(shí)驗(yàn)室 (中國科學(xué)院計(jì)算技術(shù)研究所)北京100190)2(中國科學(xué)院大學(xué)北京100049) (zhangjun01@ict.ac.cn)

摘要在眾核平臺上并行加速是解決高效視頻編碼(high efficiency video coding, HEVC)標(biāo)準(zhǔn)編碼復(fù)雜度高的有效方法.傳統(tǒng)的粗粒度并行方案如Tiles和WPP未能在并行度和編碼質(zhì)量之間取得較好的平衡，對編碼質(zhì)量影響較大或者并行度不高.充分挖掘HEVC幀內(nèi)模式選擇中的并行性，提出了一種在CTU內(nèi)使用的多層次細(xì)粒度的幀內(nèi)模式選擇算法.具體說來，對幀內(nèi)模式選擇過程進(jìn)行了子任務(wù)劃分，分析并消除了相鄰編碼塊之間多種阻礙并行計(jì)算的數(shù)據(jù)依賴關(guān)系，包括幀內(nèi)預(yù)測參考像素依賴、預(yù)測模式依賴和熵編碼依賴等，實(shí)現(xiàn)了同一個CTU內(nèi)所有層次的細(xì)粒度編碼塊的代價計(jì)算和模式選擇并行進(jìn)行.將算法在Tile-Gx36平臺上實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果表明此并行算法與HEVC參考代碼HM相比能獲得18倍的整體編碼加速比而且編碼質(zhì)量損失較小(碼率上升3%).

關(guān)鍵詞高效視頻編碼；幀內(nèi)預(yù)測；眾核；并行模式選擇；細(xì)粒度

高效視頻編碼(highefficiencyvideocoding,HEVC)[1-2]標(biāo)準(zhǔn)的壓縮效率超越以往所有標(biāo)準(zhǔn)，比目前最流行的H.264AVC提高1倍.雖然HEVC仍然屬于基于塊的混合編碼框架，但是其各個編碼階段都有了增強(qiáng)和改進(jìn)，其中最重要的變化就是采用了更加靈活的編碼結(jié)構(gòu)和高級的編碼工具，這也導(dǎo)致HEVC的編碼模式搜索空間非常大.為了保證編碼質(zhì)量，編碼器要進(jìn)行大量的計(jì)算以尋找率失真代價較小的編碼模式，即模式選擇(modedecision,MD)，編碼復(fù)雜度非常高.隨著多核和眾核處理器的發(fā)展[3]，在并行計(jì)算平臺上并行化HEVC編碼將是滿足其計(jì)算能力需求實(shí)現(xiàn)實(shí)時編碼的有效手段[4-12].與以往所有標(biāo)準(zhǔn)不同，HEVC標(biāo)準(zhǔn)本身就采納了多種便于并行編解碼的工具，如WPP(wavefrontparallelprocessing)[9]，Tiles[10]，MER(motionestimationregion)[11]，可見并行計(jì)算對于HEVC及今后視頻編碼領(lǐng)域的重要性.

目前HEVC并行相關(guān)的研究工作主要集中于計(jì)算量較大的幀間MD尤其是運(yùn)動估計(jì)(motionestimation,ME)模塊[7-8,11]，對幀內(nèi)MD并行的研究則相對較少.隨著幀間MD的并行化，幀內(nèi)MD逐漸成為了速度瓶頸.在文獻(xiàn)[13]中，在幀間MD被加速了近15倍之后，I幀的平均編碼時間大大超過了PB幀的平均編碼時間，是其4～5倍，限制了編碼器的整體效率，因此對幀內(nèi)MD的并行加速同樣重要.

現(xiàn)有的對HEVC幀內(nèi)MD并行的研究較少，而且算法的并行度不夠高[14-16]，HEVC標(biāo)準(zhǔn)支持的Tiles和WPP也未能在并行度和編碼質(zhì)量取得較好的平衡.針對這些問題，本文提出了一種在編碼樹單元(codingtreeunit,CTU)內(nèi)使用的并行幀內(nèi)MD算法：本文對幀內(nèi)MD過程進(jìn)行了子任務(wù)劃分，深入分析并解除了各個子任務(wù)在相鄰編碼塊之間存在的數(shù)據(jù)依賴性，包括幀內(nèi)預(yù)測參考像素依賴、PU預(yù)測模式依賴、熵編碼概率模型依賴和概率建模依賴，實(shí)現(xiàn)了每個子任務(wù)對整個CTU里面多層次細(xì)粒度的編碼塊并行處理，最終實(shí)現(xiàn)了CTU內(nèi)并行幀內(nèi)MD.

1背景及研究現(xiàn)狀

本節(jié)介紹與本文工作相關(guān)的一些背景.首先介紹HEVC幀內(nèi)模式選擇基本概念，然后對已有的一些并行幀內(nèi)模式選擇算法進(jìn)行了介紹和分析.

1.1HEVC幀內(nèi)模式選擇

在HEVC編碼標(biāo)準(zhǔn)中，一幀視頻圖像被均勻地劃分成CTU，CTU的大小可以為64×64,32×32或16×16，典型且不失一般性，本文以下默認(rèn)CTU大小為64×64.如圖1所示，每一個CTU四叉樹遞歸地劃分為4個相同大小的子單元，該四叉樹的每一個葉子節(jié)點(diǎn)叫作一個編碼單元(codingunit,CU)；每個CU也會采用四叉樹遞歸劃分，每一個葉子節(jié)點(diǎn)叫作變換單元(transformunit,TU).此外，從圖1可見，每個CU有多種預(yù)測單元(predictionunit,PU)劃分模式，能更靈活地進(jìn)行預(yù)測編碼.HEVC的幀內(nèi)預(yù)測模式也比H.264復(fù)雜很多，共35種模式.CTU,CU,PU,TU包含的單一亮度或色度分量信息分別記為CTB(codingtreeblock),CB(codingblock),PB(predictionblock),TB(transformblock).

Fig. 1　Flexible coding structures in HEVC.圖1　HEVC標(biāo)準(zhǔn)中靈活的編碼結(jié)構(gòu)

在HEVC幀內(nèi)MD過程中，對于一個CTU來說，它可以采用四叉樹遞歸劃分的方式劃分出更小的CU，最小為8×8.對于8×8CU有2N×2N和N×N兩種PU劃分方式，其他CU只有2N×2N的PU劃分.N×N劃分情況下包含4個亮度PB和1個色度PB，2N×2N劃分時包含1個亮度PB和1個色度PB，每個PB有一個預(yù)測模式.對一個幀內(nèi)編碼CU來說，色度PB和亮度PB的預(yù)測模式可以是不同的，TU劃分模式對亮度和色度是相同的，因此一個幀內(nèi)編碼CU的模式可由亮度PB預(yù)測模式、色度PB預(yù)測模式和TU劃分模式來表征，如式(1)所示.幀內(nèi)MD即對CTU里面的每個CU從式(1)所表示的模式空間中尋找率失真代價最小的模式組合，并且據(jù)此決策出整個CTU的最佳CU四叉樹劃分方式.在HEVC的參考軟件HM中,一個CTU里面CU的MD計(jì)算是按深度優(yōu)先遍歷順序進(jìn)行的，如圖2所示，為簡便起見只畫了3層，每個節(jié)點(diǎn)表示一個CU.

CU模式(亮度PB預(yù)測模式,色度PB預(yù)測模式,

(1)

Fig. 2　Depth-first serial processing order of CUs in a CTU of HM.圖2　HM中一個CTU里CU的深度優(yōu)先串行處理順序

1.2相關(guān)研究工作

由于采用了靈活的編碼結(jié)構(gòu)和復(fù)雜的預(yù)測模式，幀內(nèi)MD計(jì)算量非常大.為了加快幀內(nèi)MD，許多研究工作[17-19]提出了快速算法.快速算法能在一定程度上減小計(jì)算復(fù)雜度，但是獲得的加速比有限，距離實(shí)時編碼仍然有很大的差距.

并行計(jì)算是提高HEVC編碼速度的有效手段，標(biāo)準(zhǔn)本身采納了幾種粗粒度的并行化工具.Tiles將一幀圖像縱橫劃分成若干可以獨(dú)立進(jìn)行編碼的子圖像，子圖像之間無依賴關(guān)系，所以可以并行處理.Tiles劃分對并行編碼比較容易實(shí)現(xiàn)且并行度比較靈活，缺點(diǎn)是對編碼效率影響較大，經(jīng)測試[20]，將1080p的視頻均勻劃分成6×3的Tiles用于幀內(nèi)MD,在intra_main配置下實(shí)際平均加速比為12，BDBR[21]達(dá)到5%左右.HEVC采用的另一種并行方案為WPP，由于其盡可能地保持了數(shù)據(jù)依賴關(guān)系，所以對編碼質(zhì)量影響較小，但是并行度卻不高.對一個寬度為W個CTU、高度為H個CTU的視頻幀來說，如果滿足條件2(H-α-1)

(2)

對于720p和1080p的視頻序列滿足α=2，所以1080p的視頻TPD只能到8[22].

在另外一些并行幀內(nèi)MD的研究中，文獻(xiàn)[14-15]都使用前向無環(huán)圖描述CTU之間的依賴關(guān)系，實(shí)現(xiàn)了CTU之間的并行處理，但本質(zhì)仍屬于WPP，文獻(xiàn)[14]平均獲得了5倍的加速比，文獻(xiàn)[15]則使用分類器決策出最佳CTU的大小，通過較小的CTU大小能獲得較高的加速比，平均達(dá)到10倍.在文獻(xiàn)[16]中，該文作者提出了一種在TU四叉樹劃分時4個子節(jié)點(diǎn)并行幀內(nèi)預(yù)測的算法，但是由于幀內(nèi)預(yù)測仍依賴于重構(gòu)像素，理論并行度只能達(dá)到4.

從以上內(nèi)容可以看出，現(xiàn)有的幀內(nèi)MD并行算法主要是粗粒度并行(Tiles,WPP)，文獻(xiàn)[16]屬于細(xì)粒度并行但是并行度不高.針對它們存在的問題，本文提出了一種在CTU內(nèi)使用的多層次細(xì)粒度的并行幀內(nèi)MD算法，在保證編碼質(zhì)量的前提下獲得了更高的并行度.多層次體現(xiàn)在不同深度的CU，PU，TU可以并行處理，細(xì)粒度則體現(xiàn)在最小計(jì)算單元為一個TB.

2多層次細(xì)粒度并行幀內(nèi)模式選擇

本節(jié)提出了一種在CTU內(nèi)使用的多層次細(xì)粒度并行幀內(nèi)MD算法.本文首先對CU幀內(nèi)MD過程進(jìn)行了子任務(wù)劃分，深入分析并解除了各個子任務(wù)在相鄰CU，PU，TU間存在的數(shù)據(jù)依賴關(guān)系，實(shí)現(xiàn)了各個子任務(wù)在整個CTU范圍的并行處理，最終實(shí)現(xiàn)了各個層次的所有CU并行模式選擇.

2.1子任務(wù)劃分

對于一個CU的模式選擇，為了減小計(jì)算量，HM對式(1)表示的模式空間的搜索分階段進(jìn)行，先選擇亮度PB預(yù)測模式，然后選擇TU劃分模式，再選擇色度PB的預(yù)測模式，如圖3所示.

Fig. 3　The flowchart of intra MD for a CU in HM encoder.圖3　HM編碼器中對一個CU的幀內(nèi)MD流程圖

對于亮度PB預(yù)測模式選擇，先對所有35種模式進(jìn)行代價粗算(roughmodecostcomputation,RMCC)，代價記作RMC，包括PB預(yù)測值與原始值之間的殘差變換絕對值(sumofabsolutetransformeddifferences,SATD)和預(yù)測模式編碼位數(shù)，從中選擇一定數(shù)量RMC最小的預(yù)測模式，與當(dāng)前PB的最可能預(yù)測模式(mostprobablemode,MPM)一起構(gòu)造候選模式列表(candidatemodelistconstruction,CMLC),記作CML,對CML里的每一個模式都去計(jì)算率失真代價(predictionmodecostcomputation,PMCC)，代價記作PMC,選擇PMC最小的預(yù)測模式作為當(dāng)前PB的最佳預(yù)測模式(PBbestpredictionmodeselection,PBBPMS),記作PBBPM.然后對TU劃分模式進(jìn)行決策，主要計(jì)算量是亮度TB的率失真代價計(jì)算(TBcostcomputation,TBCC)，代價記作TBC，使用TBC進(jìn)行TU四叉樹決策(quad-treedecision,QTD).最后選擇色度預(yù)測模式，主要計(jì)算是色度TB的TBCC計(jì)算.為便于后續(xù)引用，在表1對上述子任務(wù)以及相應(yīng)的計(jì)算結(jié)果進(jìn)行了歸納.

Table 1　Sub-Tasks and Their Output Results

如圖2所示，在串行幀內(nèi)MD時，由于CU的MD計(jì)算是按照深度優(yōu)先遍歷順序去串行進(jìn)行的，所以對于表1中的每個子任務(wù)，在串行MD時它們在CTU范圍內(nèi)的執(zhí)行路徑也是按四叉樹深度優(yōu)先遍歷順序去進(jìn)行的.本文提出的并行算法將每個子任務(wù)在CTU范圍內(nèi)進(jìn)行多層次細(xì)粒度的并行，每個子任務(wù)都能并行處理一個CTU里面的所有CU，PU或TU，即并行處理四叉樹中的所有節(jié)點(diǎn),一個節(jié)點(diǎn)對于不同的子任務(wù)表示一個CU，PU或TU.

2.2數(shù)據(jù)依賴性分析與消除

對于每個子任務(wù)，要在一個CTU范圍內(nèi)進(jìn)行并行MD計(jì)算，而相鄰塊之間有多種數(shù)據(jù)依賴關(guān)系，這些數(shù)據(jù)依賴會阻礙子任務(wù)在CTU范圍內(nèi)的并行計(jì)算.經(jīng)過本文的分析，有4種數(shù)據(jù)依賴需要解除：

1) 幀內(nèi)預(yù)測時重構(gòu)像素依賴.此依賴關(guān)系出現(xiàn)在幀內(nèi)預(yù)測時，如圖4所示，在一個PB或TB進(jìn)行代價計(jì)算時，需要進(jìn)行幀內(nèi)預(yù)測，即參考相鄰塊已經(jīng)重構(gòu)出來的像素對自身進(jìn)行預(yù)測.對于一個M×M的TB來說，需要參考周圍的4M+1個重構(gòu)像素，分別來自于其左、上、左下、右上和左上方向已經(jīng)編碼重構(gòu)完成的相鄰圖像區(qū)域.

Fig. 4　Reconstructed pixels dependencies during intra prediction.圖4　幀內(nèi)預(yù)測時重構(gòu)像素依賴

在本文的并行算法中，RMCC,PMCC，TBCC在一個CTU里面要對所有PB或TB并行進(jìn)行代價計(jì)算，需要進(jìn)行幀內(nèi)預(yù)測，如果一個PB或TB要參考的重構(gòu)像素跟它位于同一個CTU，那么重構(gòu)像素是不可用的，因?yàn)橄噜弶K也同時在進(jìn)行模式選擇，并未重構(gòu)完成.如圖4所示，blockL,blockA和當(dāng)前塊位于同一個CTU進(jìn)行并行處理，那么當(dāng)前塊所依賴的blockL和blockA的重構(gòu)像素不可用.要想并行計(jì)算，幀內(nèi)預(yù)測參考像素的依賴關(guān)系必須要解除.

為了解除這種相關(guān)性，本文提出使用原始像素代替重構(gòu)像素進(jìn)行幀內(nèi)預(yù)測.為了更準(zhǔn)確地模擬實(shí)際的編碼過程，在對一個PB或TB進(jìn)行參考像素構(gòu)造的過程中，雖然所有原始像素都是可用的，但依然按照標(biāo)準(zhǔn)遵循Z掃描順序來決定某一個像素是不是可用，對于不可用的像素則調(diào)用替換(substitution)過程去生成.另外，對參考像素的濾波操作也同樣按照標(biāo)準(zhǔn)進(jìn)行.由于原始像素是始終可用的，相鄰PB或TB之間不會再有重構(gòu)像素的依賴問題，所以同一個CTU里面所有PB和TB都可以并行地進(jìn)行幀內(nèi)預(yù)測.

2) 編碼預(yù)測模式時MPM計(jì)算依賴.為了提高壓縮效率，HEVC在編碼幀內(nèi)預(yù)測模式時需要參考相鄰(左邊和上邊)PB的預(yù)測模式，構(gòu)造出一個長度固定為3的MPM列表，如圖5(a)所示.如果左PB(leftPB,LPB)和上PB(abovePB,APB)的預(yù)測模式不可用或者相同，則還會加入DC、planar、垂直、水平等模式.令(xc,yc)表示當(dāng)前PB的左上角在當(dāng)前圖像幀中的坐標(biāo)，LPB定義為覆蓋點(diǎn)L(xc-1,yc)的PB，APB定義為覆蓋點(diǎn)A(xc,yc-1)的PB.

Fig. 5　Prediction mode dependency among adjacent PUs and the proposed dependency removing method.圖5　相鄰PU預(yù)測模式依賴和本文提出的依賴性消除方法

在本文的并行算法中，RMCC,CMLC，PMCC要對CTU內(nèi)所有PB并行地進(jìn)行MPM計(jì)算，如果當(dāng)前PB與參考的LPB或APB位于同一個CTU里面，即如式(3)所示，其中(xn,yn)對于LPB或APB分別為(xc-1,yc)或(xc,yc-1)，那么LPB和APB的預(yù)測模式是不可用的，因?yàn)樗鼈円餐瑫r在進(jìn)行模式選擇，預(yù)測模式還未得到.

為了解除此依賴關(guān)系，如果當(dāng)前PB和LPB或APB位于同一個CTU，那么本文使用已經(jīng)編碼過的CTU里面距離LPB和APB最近的對應(yīng)PB來代替它，記作LPB′和APB′,如圖5(b)所示，用LPB′和APB′的預(yù)測模式代替LPB和APB的預(yù)測模式去構(gòu)造MPM.LPB′定義為覆蓋點(diǎn)L′(xc-xc% 64-1,yc)的PB,APB′定義為覆蓋點(diǎn)A′(xc,yc-yc% 64-1)的PB，其中“%”表示取余運(yùn)算，64表示CTU大小.由于CTU是按照掃描順序進(jìn)行編碼的，所以左CTU和上CTU里面的信息一定是可以使用的，這樣，同一個CTU里面PU的預(yù)測模式依賴關(guān)系就被解除了，可以并行進(jìn)行預(yù)測以及代價計(jì)算:

(3)

3) 概率模型(contextmodel,CM)繼承依賴.HEVC中使用上下文自適應(yīng)的二進(jìn)制算術(shù)編碼(contextadaptivebinaryarithmeticcoding,CABAC)進(jìn)行語法元素的熵編碼.CABAC的主要過程包括語法元素的二進(jìn)制化、概率建模、算術(shù)編碼和CM更新.為了提高編碼效率，在編碼的過程中CM會自適應(yīng)動態(tài)更新，以更好地反映圖像的局部區(qū)域特性，獲得更高的壓縮比.在HM模式選擇過程中，熵編碼器會使用CM去估計(jì)編碼產(chǎn)生的位數(shù)以計(jì)算編碼代價，CM是模擬實(shí)際編碼過程動態(tài)更新的，Z掃描順序更小的塊的MD完成之后會將CM傳遞給Z掃描順序大于它的塊使用，如圖6(a)所示，TU1使用的CM是TU0計(jì)算之后的結(jié)果，這樣就在相鄰塊之間產(chǎn)生了CM的繼承依賴.

Fig. 6　CMs inheritance in HM and our proposed method.圖6　HM中的CM繼承依賴和本文提出的方法

在本文的并行算法中，RMCC,PMCC,TBCC，QTD任務(wù)要并行地對一個CTU內(nèi)的所有CU,PU或TU進(jìn)行代價計(jì)算，而由于相鄰CU，PU，TU之間存在CM的繼承依賴問題而導(dǎo)致無法并行，要想實(shí)現(xiàn)并行代價計(jì)算，必須要解決此依賴關(guān)系.

為了解除同一個CTU內(nèi)CM繼承依賴，本文提出以下解決方法：同一個CTU內(nèi)的所有CUPUTU使用同一套CM，該CM來自于上一個已編碼的CTU經(jīng)過訓(xùn)練之后的結(jié)果.如圖6(b)所示，為了簡潔，一個CTU內(nèi)只畫出4個TU.通過這種CM繼承方式，一個CTU里面所有的CUPUTU都有了自己的CM，所以可以并行處理.

Fig. 7　Coding depth dependency among adjacent CUs and our proposed dependency removing method.圖7　CU之間依賴和提出的依賴性消除方法

4) 概率建模依賴.為了提高編碼效率，CABAC編碼二進(jìn)制符號(binarysymbol,bin)時需要進(jìn)行概率模型選擇(也叫概率建模)，概率模型即當(dāng)前bin是01的概率，概率建模即從可選的概率模型里選擇出最能反映當(dāng)前bin概率估計(jì)的模型.為了能得到較精確的概率估計(jì)，概率建模會依賴于當(dāng)前bin序號、編碼深度、色度或亮度、周圍編碼信息等.HEVC在編碼語法元素split_cu_flag時，會根據(jù)當(dāng)前CU的深度和其左CU、上CU的劃分深度進(jìn)行概率模型選擇，如圖7(a)所示.假設(shè)左CU編碼深度為depthL,上CU編碼深度為depthA,當(dāng)前CU的深度為depth,那么當(dāng)前CU的split_cu_flag的概率模型序號如式(4)所示，其中“>”為邏輯運(yùn)算符.cu_skip_flag的概率建模與此類似.在本文的并行算法中，QTD要對CTU內(nèi)所有CU并行地進(jìn)行代價計(jì)算和模式選擇，由于相鄰CU之間在概率建模時有編碼模式依賴，所以要并行處理，這種依賴關(guān)系必須要解除.為了解除此類數(shù)據(jù)依賴性，本文采用和解除MPM計(jì)算依賴性類似的方法，即如果參考的CU和當(dāng)前CU位于同一個CTU，則使用已編碼的相鄰CTU中的對應(yīng)CU來代替它，如圖7(b)所示.另外，TB的語法元素cbf在概率建模時會依賴當(dāng)前TB在CU中的劃分深度信息，但是在本文的算法中，整個CTU里面的所有TB會并行計(jì)算代價TBCC，并無CU概念，所以TB在CU中的深度無法得到.對于這個依賴關(guān)系，本文的解決方法是：對于4×4的TB，深度設(shè)置為1，其他TB的深度設(shè)置為0.

(4)

以上對阻礙并行計(jì)算的多種數(shù)據(jù)依賴關(guān)系進(jìn)行了分析和消除.需要注意的是本文提出的數(shù)據(jù)依賴性消除算法只在模式選擇階段使用，為了保證編碼結(jié)果符合標(biāo)準(zhǔn)且保證編碼質(zhì)量，當(dāng)一個CTU的模式選擇完成之后，即確定了CU劃分方式、PU劃分方式、PU預(yù)測模式和TU劃分方式之后，在進(jìn)行實(shí)際熵編碼的過程中需要對量化系數(shù)和預(yù)測模式編碼進(jìn)行修正，即按照標(biāo)準(zhǔn)規(guī)定去參考相鄰塊的重構(gòu)像素進(jìn)行幀內(nèi)預(yù)測，對殘差重新進(jìn)行變換和量化得到量化系數(shù)，MPM的構(gòu)造也按標(biāo)準(zhǔn)規(guī)定參考相鄰的PB，CABAC的概率模型繼承和概率建模也按標(biāo)準(zhǔn)規(guī)定進(jìn)行.這個修正的過程是需要串行計(jì)算的.

2.3并行策略

在解除了以上多種數(shù)據(jù)依賴關(guān)系之后，下面給出本文提出的多層次細(xì)粒度并行算法的并行策略，為了便于表達(dá)，進(jìn)行如下符號定義：

CU,PU,TU分別表示在一個CTU里面的編碼單元、預(yù)測單元、變換單元；CB,PB,TB分別表示一個CU,PU,TU包含的亮度或色度分量塊;depthi表示當(dāng)前單元(CU,PU,TU)或分量塊(CB,PB,TB)相對于CTU的四叉樹劃分深度，其中0≤i≤4;zorderj表示第depthi層深度的某一個單元的Z掃描順序序號，其中0≤j≤4i-1;modek表示一個幀內(nèi)預(yù)測模式，其中0≤k≤34.

對表1中的各子任務(wù)，分別在CTU內(nèi)進(jìn)行如下數(shù)據(jù)級劃分和并行：

1)RMCC.對于亮度PB的RMCC任務(wù)，主要工作是計(jì)算PB的幀內(nèi)預(yù)測和SATD的計(jì)算.本文提出的并行策略：一個CTU里面所有的亮度PB的所有預(yù)測模式都并行進(jìn)行RMCC，表示為RMCi,j,k=RMCC(PB(depthi,zorderj),modek)，其中0≤i≤4,0≤j≤4i-1,0≤k≤34,i,j,k并行.

2)CMLC.在一個亮度PB的RMCC完成之后，需要從中選出一定數(shù)量RMC最小的模式，然后與當(dāng)前PB的MPM一起組成該P(yáng)B的候選模式列表CML.本文提出的并行策略：CTU內(nèi)所有亮度PB并行進(jìn)行CMLC操作，表示為CMLi,j=CMLC(PB(depthi,zorderj)),其中0≤i≤4,0≤j≤4i-1,i,j并行.

3)PMCC.當(dāng)一個亮度PB的CML構(gòu)造之后，要從中選出一個最好的模式作為當(dāng)前PB的預(yù)測模式.當(dāng)前PB在其CML里面的每一個模式都計(jì)算出一個率失真代價PMC，為了減少計(jì)算量，只有64×64的PB進(jìn)行一層TB劃分，其他的PB都直接作為一個TB計(jì)算.本文提出的并行策略：CTU里面所有的PB在其CML里面的所有模式并行,表示為PMCi,j,k=PMCC(PB(depthi,zorderj),modek),0≤i≤4,0≤j≤4i-1,k∈CMLi,j,i,j,k并行，其中對于PB(depth0,zorder0)，劃分為4個子塊并行計(jì)算.

4)PBBPMS.當(dāng)一個亮度PB的PMC計(jì)算完成之后，需要從中選擇最小PMC對應(yīng)的預(yù)測模式作為PB的最終預(yù)測模式，記為PBBPM.本文提出的并行策略：CTU內(nèi)所有亮度PB并行進(jìn)行PBBPMS操作，記為PBBPMi,j=PBBPMS(PB(depthi,zorderj)),0≤i≤4,0≤j≤4i-1,i,j并行.

5)TBCC.選出亮度PB最佳預(yù)測模式之后，需要決策每個CU的最佳TU劃分，因此要計(jì)算一個CU所包含的所有TB的率失真代價.本文提出的并行策略：整個CTU里面所有TB并行地進(jìn)行率失真代價TBC計(jì)算，表示為TBCi,j,k=TBCC(TB(depthi,zorderj),modek)，由于亮度TB最大為32，所以1≤i≤4,0≤j≤4i-1,k∈TBPMi,j,i,j,k并行，其中TBPMi,j表示TB(depthi,zorderj)所需計(jì)算的預(yù)測模式.由于本文使用原始像素取代重構(gòu)像素來進(jìn)行幀內(nèi)預(yù)測，所以任何一個TB對于同一個預(yù)測模式其預(yù)測值是完全相同的.因?yàn)橥粋€TB可能會被多個PB同時覆蓋，所以同一個TB在一個模式下只需要計(jì)算一次即可，減少了計(jì)算量.假如最大TU劃分層次為3層，那么TB(depthi,zorderj)會被PB(depthi,zorderj),PB(depthi-1,zorder)和PB(depthi-2,zorder)同時覆蓋，故TBPMi,j是它們最佳模式的并集，即：

TBPMi,j={PBBPMi,j,PBBPM,PBBPM}.

(5)

對于色度PB的預(yù)測模式選擇，色度PB在亮度PB預(yù)測模式一定的情況下有5種預(yù)測模式需要計(jì)算，如表2所示.本文直接將這5種模式全部并行計(jì)

Table2TheRelationshipofPredictionModeBetweenLuma

andChromaComponentsinaCU

表2　色度分量預(yù)測模式與亮度分量預(yù)測模式的對應(yīng)關(guān)系

算：TBCi,j,l=TBCC(TB(depthi,zorderj),model),其中1≤i≤3,0≤j≤4i-1,l=0,1,2,3,4,model表示需要計(jì)算的預(yù)測模式,i,j,l并行.

6)QTD.此任務(wù)的主要工作是根據(jù)前面所述任務(wù)的計(jì)算結(jié)果，決策出CU的最終模式.因?yàn)樵赑BBPMS中已經(jīng)得到了亮度PB的預(yù)測模式，在TBCC中已經(jīng)得到了亮度和色度的TBC，所以QTD的主要工作就是決策出當(dāng)前CU最優(yōu)的TU劃分和最優(yōu)色度預(yù)測模式，并且計(jì)算出當(dāng)前CU的率失真代價，完成模式選擇過程.本文提出的并行策略：一個CTU里面的所有CU并行進(jìn)行QTD:QTD(CU(depthi,zorderj)),其中 0≤i≤3,0≤j≤4i-1,i,j并行.

2.4理論并行度分析

為了對所提并行幀內(nèi)MD算法的理論并行度進(jìn)行近似分析，進(jìn)行2點(diǎn)假設(shè)：1)對于RMCC，PMCC，TBCC子任務(wù)，主要計(jì)算量是幀內(nèi)預(yù)測和變換量化，它們的計(jì)算時間與計(jì)算單元的面積成正比，且與預(yù)測模式無關(guān)；CMLC,PBBPMS，QTD的主要操作是結(jié)果的比較和選擇，計(jì)算量較小且與計(jì)算單元面積無關(guān).2)對于同一類子任務(wù)由于解除了相鄰數(shù)據(jù)單元之間的數(shù)據(jù)相關(guān)性，所有的數(shù)據(jù)單元都可以同時被計(jì)算，因此理論并行度由整個CTU串行計(jì)算時間和計(jì)算量最大的數(shù)據(jù)單元的計(jì)算時間決定.基于以上2點(diǎn)假設(shè)，各子任務(wù)分析如下：

1)RMCC階段.令CTi,j,k表示RMCC(PB(depthi,zorderj),modek)的計(jì)算時間，令T=CT0,0,0，那么整個CTU里所有PB的RMCC串行計(jì)算時間近似為

2)PMCC階段.令CTi,j,k表示PMCC(PB(depthi,zorderj),modek)的計(jì)算時間，令T=CT1,0,0,經(jīng)統(tǒng)計(jì)亮度PB的CML里面平均含有5個模式，所以整個CTU里所有PB的PMCC的串行計(jì)算時間近似為

最大計(jì)算量任務(wù)的計(jì)算時間為T，所以TPD=100.

3)TBCC階段.令CTi,j,k表示TBCC(TB(depthi,zorderj),modek)的計(jì)算時間，令T=CT1,0,0,假設(shè)TU最多劃分3層，在串行MD過程中整個CTU里所有TB的TBCC串行計(jì)算時間為

最大計(jì)算量任務(wù)的計(jì)算時間為T，所以TPD=44.

從以上分析可以看出，本文提出的并行幀內(nèi)MD算法的理論并行度很高，適用于眾核平臺.

3實(shí)現(xiàn)和實(shí)驗(yàn)結(jié)果

基于HEVC參考代碼HM13.0[23]，本文使用多線程實(shí)現(xiàn)本文所提出的并行模式選擇算法.本文修改了代碼中模式選擇模塊(TEncCu∷xCompressCU及相關(guān)函數(shù))使之并行化，其他的模塊保持不變.本文重點(diǎn)是提出一種適用于眾核平臺的高并行度算法，主要關(guān)注算法的并行度和對編碼質(zhì)量的影響，所以并未對單核性能進(jìn)行指令、內(nèi)存等任何優(yōu)化.實(shí)驗(yàn)采用的計(jì)算平臺為TILE-Gx36眾核平臺，共有36個處理核心，單核主頻1.2GHz.

3.1實(shí)現(xiàn)方法

為了減少頻繁創(chuàng)建和銷毀線程帶來的開銷，本文使用線程池實(shí)現(xiàn)本文算法.在編碼器剛啟動時創(chuàng)建一定數(shù)量所需線程，線程池中所有的線程在編碼器整個生命周期內(nèi)一直存在.為了減小線程切換帶來的性能影響和增加實(shí)驗(yàn)的可重現(xiàn)性，所有的線程都綁定在一個固定的核上且每個核只綁定一個線程.0號核不予使用，1號核綁定主線程，其余34個核用于線程池里的工作線程.線程池中維護(hù)一個任務(wù)鏈表，所有需要處理的任務(wù)都插入鏈表，空閑的工作線程自動從鏈表首取走任務(wù)進(jìn)行處理.主線程的主要工作就是往鏈表里面放任務(wù)，實(shí)際去完成任務(wù)計(jì)算的是工作線程.

在本文的實(shí)現(xiàn)中，定義了6種類型的任務(wù)：RMCC,CMLC,PMCC,PBBPMS,TBCC,QTD，由于這些任務(wù)之間對于同一個數(shù)據(jù)單元存在先后處理順序的依賴關(guān)系，所以本文定義了任務(wù)的優(yōu)先級，如表3所示.優(yōu)先級越大的任務(wù)表示越應(yīng)該優(yōu)先被計(jì)算，因?yàn)槠渌愋偷娜蝿?wù)可能會使用它的計(jì)算結(jié)果，在放入任務(wù)鏈表時會根據(jù)優(yōu)先級大小順序存放，優(yōu)先級越大的任務(wù)在任務(wù)鏈表中排序越靠前.另外，為了保證塊越大的任務(wù)先被計(jì)算，在每一種任務(wù)類型里面，塊越大的任務(wù)即深度越小的任務(wù)優(yōu)先級越大.對于不同數(shù)據(jù)單元，計(jì)算任務(wù)之間則沒有依賴關(guān)系，不同種類的子任務(wù)之間可以并行.

Table 3　Sub-Tasks with Their Parallel Hierarchy and Priority

3.2實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出的并行幀內(nèi)MD算法的有效性，包括編碼加速比和對編碼質(zhì)量的影響，本文用基準(zhǔn)編碼器HM和本文并行化的編碼器分別對6個1080p和2個1600p的高分辨率視頻使用HM提供的配置文件intra_main進(jìn)行了編碼，每個序列使用了前100幀，根據(jù)文獻(xiàn)[20]對每個序列分別使用4個不同的量化參數(shù)(quantizationparameter,QP):22,27,32，37.加速比按照式(6)計(jì)算，其中Enc_Timer和Enc_Timep分別表示基準(zhǔn)編碼器HM和并行編碼器的編碼時間，編碼效率的下降使用BDBR[21]來衡量.為了驗(yàn)證并行算法的可伸縮性即加速比與核數(shù)的關(guān)系，對每個序列都使用了不同數(shù)量的工作線程進(jìn)行編碼.實(shí)驗(yàn)結(jié)果如表4所示，其中的核數(shù)是用于工作線程的核數(shù)，加速比是對4個QP取平均的結(jié)果.從表4可以看出,本文提出的并行幀內(nèi)模式選擇算法在使用34個核時對所有序列平均能獲得18以上的加速比，平均BDBR為 3.04%.部分序列的率失真曲線如圖8所示.

(6)

Fig. 8　Rate distortion curves for some test sequences.圖8　部分序列的率失真曲線圖

Fig. 9　Speedup vs number of cores for our proposed method and WPP (TPD).圖9　算法加速比和WPP(TPD)與核數(shù)關(guān)系

圖9給出使用不同數(shù)量的核數(shù)(2,4,8,16,24,32,34)得到的所有序列的平均加速比與核數(shù)之間的關(guān)系曲線圖，并且與1080p和1600p的WPP的理論值進(jìn)行了對比.從圖9可以看出，本文所提出的算法在核數(shù)增多時有更高的加速比，適用于眾核計(jì)算平臺；當(dāng)核數(shù)較少時加速效果比較明顯，但是隨后曲線逐漸趨于平坦，且加速比與核數(shù)之比遠(yuǎn)小于1，離算法的TPD有較大的差距.造成這種現(xiàn)象的原因可能有3點(diǎn)：

1) 并行計(jì)算數(shù)據(jù)單元劃分不均衡.在本文的算法中，不同大小的PU和TU計(jì)算量相差較大，如果假設(shè)計(jì)算量與塊面積成正比，那么第0層TU的TBCC計(jì)算量近似是第1層TU的TBCC的4倍.任務(wù)劃分不均衡會導(dǎo)致處理器核的計(jì)算負(fù)載不均衡，造成CPU核的饑餓等待，影響并行度.

2) 由于所有的并行任務(wù)都放在一個公共鏈表里面，所有線程都會競爭此資源以取得任務(wù).隨著核數(shù)的增加，線程之間在取任務(wù)和放任務(wù)的競爭會越來越激烈，勢必會造成很大的線程同步開銷.

3) 算法只進(jìn)行了模式選擇計(jì)算的并行化，其他的部分仍然串行執(zhí)行，雖然占的比例很小，但是會對整體的并行度造成上限制約.另外，編碼階段的修正過程也是串行執(zhí)行，也會影響實(shí)際的加速比.

對于編碼質(zhì)量的下降，主要原因是代價計(jì)算的準(zhǔn)確性不高，這是本文所采取的多種數(shù)據(jù)依賴性消除算法的綜合作用結(jié)果.

由于本文提出的并行算法是在局部區(qū)域CTU內(nèi)進(jìn)行，所以可以和其他全局粗粒度并行方法如WPP和Tiles結(jié)合使用，能進(jìn)一步提高并行度.

4總結(jié)

本文提出了一種在CTU內(nèi)使用的多層次細(xì)粒度的并行HEVC幀內(nèi)模式選擇算法，一個CTU內(nèi)所有不同層次的CU,PU，TU以及所有預(yù)測模式可以并行地進(jìn)行代價計(jì)算和模式選擇.本文分析了存在的多種數(shù)據(jù)依賴性并提出了有效的依賴性解除方法.實(shí)驗(yàn)結(jié)果表明本文提出的方法能達(dá)到18倍以上的編碼加速比并且編碼質(zhì)量損失較小，比傳統(tǒng)的粗粒度并行方案更能適用于眾核平臺.

參考文獻(xiàn)

[1]BrossB,HanWJ,OhmJR,etal.JCTVC-L1003:Highefficiencyvideocoding(HEVC)textspecificationdraft10 (forfdis&lastcall)[C/OL]. 2013 [2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/12_Geneva/wg11/JCTVC-L1003-v34.zip

[2]SullivanGJ,OhmJR,HanWJ,etal.Overviewofthehighefficiencyvideocoding(HEVC)standard[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2012, 22(12): 649-1668

[3]PengXiaoming,GuoHaoran,PangJianmin.Multi-coreprocessor-technology,tendencyandchallenge[J].ComputerScience, 2012, 39(11A): 320-326 (inChinese)(彭曉明, 郭浩然, 龐建民. 多核處理器——技術(shù)、趨勢和挑戰(zhàn)[J]. 計(jì)算機(jī)科學(xué), 2012, 39(11A)：320-326)

[4]YanChenggang.Researchonkeytechniquesforparallelvideocodingonmany-coreprocessor[D].Beijing:InstituteofComputingTechnology,ChineseAcademyofSciences, 2014 (inChinese)(顏成鋼. 面向眾核處理器的并行視頻編碼關(guān)鍵技術(shù)研究 [D]. 北京: 中國科學(xué)院計(jì)算技術(shù)研究所, 2014)

[5]ChoiK,JangES.Leveragingparallelcomputinginmodernvideocodingstandards[J].IEEEMultimedia, 2012, 19(3): 7-11

[6]ZhangYongdong,YanChenggang,DaiFeng,etal.EfficientparallelframeworkforH.264/AVCdeblockingfilteronmany-coreplatform[J].IEEETransonMultimedia, 2012, 14(1): 510-524

[7]YanChenggang,ZhangYongdong,DaiFeng,etal.HighlyparallelframeworkforHEVCmotionestimationonmany-coreplatform[C] //Procofthe23rdDateCompressionConf(DCC2013).Piscataway,NJ:IEEE, 2013: 63-72

[8]YanChenggang,ZhangYongdong,XuJizheng,etal.EfficientparallelframeworkforHEVCmotionestimationonmany-coreprocessors[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2014, 24(12): 2077-2089

[9]ClareG,HenryF,PateuxS.JCTVC-F274:WavefrontparallelprocessingforHEVCencodinganddecoding[C/OL]. 2011 [2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/6_Torino/wg11/JCTVC-F274-v2.zip

[10]FuldsethA,HorowitzM,XuS,etal.JCTVC-F335:Tiles[C/OL]. 2011[2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/6_Torino/wg11/JCTVC-F335-v2.zip

[11]ZhouMinhua.JCTVC-H0082:ConfigurableandCU-grouplevelparallelmerge/skip[C/OL]. 2012[2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/8_San%20Jose/wg11/JCTVC-H0082-v2.zip

[12]ChiCC,MauricioAM,JuurlinkB,etal.ParallelscalabilityandefficiencyofHEVCparallelizationapproaches[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2012, 22(12): 1827-1838

[13]ZhangJun,DaiFeng,MaYike,etal.HighlyparallelmodedecisionmehtodforHEVC[C] //Procofthe30thPictureCodingSymp(PCS2013).Piscataway,NJ:IEEE, 2013: 281-284

[14]ZhaoYanan,SongLi,WangXiangwen,etal.EfficientrealizationofparallelHEVCintraencoding[C]//Procof2013IEEEIntConfonMultimediaandExpoWorkshops(ICMEW2013).Piscataway,NJ:IEEE, 2013: 1-6

[15]YanChenggang,ZhangYongdong,DaiFeng,etal.EfficientparallelHEVCintra-predictiononmany-coreprocessor[J].ElectronicsLetters, 2014, 50(11): 805-806

[16]JiangJie,GuoBaolong,MoWei,etal.Block-basedparallelintrapredictionschemeforHEVC[J].JournalofMultimedia, 2012, 7(4): 289-294

[17]ChoiK,ParkSH,JangES.JCTVC-F092:CodingtreepruningbasedCUearlytermination[C/OL]. 2011[2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/6_Torino/wg11/JCTVC-F092-v3.zip

[18]ChoS,KimM.FastCUsplittingandpruningforsuboptimalcupartitioninginHEVCintracoding[J].IEEETransonCircuitsandSystemsforVideoTechnology, 2013, 23(9): 1555-1564

[19]LealdaSilvaT,daSilvaCruzL,AgostiniLV.HEVCintramodedecisionaccelerationbasedontreedepthlevelsrelationship[C]//Procofthe30thPictureCodingSymp(PCS2013).Piscataway,NJ:IEEE, 2013: 277-280

[20]BossenF.JCTVC-L1100:Commontestconditionsandsoftwarereferenceconfigurations[C/OL]. 2013 [2014-11-01].http://phenix.int-evry.fr/jct/doc_end_user/documents/12_Geneva/wg11/JCTVC-L1100-v1.zip

[21]BjontegaardaG.VCEG-M33:Calculationofaveragepsnrdifferencesbetweenrd-curves[C/OL]. 2001 [2014-11-01].https://github.com/gabrieldiego/tg/blob/master/ref/VCEG-M33.doc

[22]ZhangShaobo,ZhangXiaoyun,GaoZhiyong.ImplementationandimprovementofwavefrontparallelprocessingforHEVCencodingonmany-coreplatform[C] //Procof2014IEEEIntConfonMultimediaandExpoWorkshops(ICMEW2014).Piscataway,NJ:IEEE, 2014: 1-6

[23]JCTVC.HEVCtestmodel:HM13.0[CP]. [2014-11-01]https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/branches/HM-13.0-dev

ZhangJun,bornin1987.ReceivedhisBEdegreefromXidianUniversityin2009andreceivedhisPhDdegreefromtheInstituteofComputingTechnology,ChineseAcademyofSciencesin2015.Hisresearchinterestsincludevideocodingandimageprocessing.

DaiFeng,bornin1979.ReceivedhisMSandPhDdegreesfromtheInstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China,in2008.AssociateprofessorwiththeMultimediaComputingGroup,AdvancedResearchLaboratory,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing.MemberofChinaComputerFederation.Hisresearchinterestsincludevideocoding,videoprocessingandcomputationalphotography(fdai@ict.ac.cn).

MaYike,bornin1980.ReceivedhisMSandPhDdegreesintheInstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China,in2011.MemberofChinaComputerFederation.Hisresearchinterestsincludecomputerarchitecture,parallelalgorithmandcomputationalphotography(ykma@ict.ac.cn).

ZhangYongdong,bornin1973.ReceivedhisPhDdegreeinelectronicengineeringfromTianjinUniversity,Tianjin,China,in2002.ProfessorwiththeInstituteofComputingTechnology,ChineseAcademyofSciences,Beijing,China.SeniormemberofChinaComputerFederation.Hisresearchinterestsincludemultimediacontentanalysisandunderstanding,multimediacontentsecurity,videocoding,andstreamingmediatechnology(zhyd@ict.ac.cn).

Multi-LevelandFine-GrainedParallelHEVCIntraModeDecisionMethod

ZhangJun1,2,DaiFeng1,MaYike1,andZhangYongdong1

1(Key Laboratory of Intelligent Information Processing (Institute of Computing Technology, Chinese Academy of Sciences), Chinese Academy of Sciences, Beijing 100190)2(University of Chinese Academy of Sciences, Beijing 100049)

AbstractThe coding mode space of high efficiency video coding (HEVC) is extremely large so it needs huge amount of computations for HEVC encoders to do mode decision (MD). Parallelizing HEVC encoding on many-core platforms is an efficient and promising approach to fulfill the high computational demands. Traditional coarse-grained parallelizing schemes such as Tiles and wavefront parallel processing (WPP) either cause too much quality loss or can’t afford a high parallelism degree. In this paper, the potential parallelism in HEVC intra MD process is exploited, and a multi-level and fine-grained highly parallel intra MD method which works in a coding tree unit (CTU) is proposed. Specifically, the intra MD process in a CTU is divided into six types of sub-tasks, and the data dependencies among adjacent blocks that hinder parallel processing are analyzed and removed, including intra prediction dependency, prediction mode dependency and entropy coding dependency; consequently the MD computation for all fine-grained coding blocks of different levels within the same CTU can be computed concurrently. The proposed parallel MD method is implemented on Tile-Gx36 platform. Experimental results show that the proposed parallel MD method gets an overall speed up of more than 18x with acceptable quality loss (about 3% bit-rate increasing), compared with the non-parallel baseline HM.

Key wordshigh efficiency video coding (HEVC); intra prediction; many-core; parallel mode decision; fine-grained

收稿日期：2014-12-31；修回日期：2015-04-27

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61379084,61402440);中國科學(xué)院科研裝備研制項(xiàng)目(YZ201321)

中圖法分類號TP391

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61379084,61402440)andtheInstrumentDevelopingProjectoftheChineseAcademyofSciences(YZ201321).