一種基于異構(gòu)系統(tǒng)的H.264/AVC運動估計算法

章 劍，仰楓帆

(南京航空航天大學(xué)電子信息工程學(xué)院，江蘇 南京 210016)

H.264/AVC［1］是目前新型視頻編碼標(biāo)準(zhǔn)，通過采用一些新的編碼技術(shù)獲得了更高的編碼效率以及更好的圖像質(zhì)量。但是由于運算復(fù)雜度的增加，難以進行實時編碼。而實際上這些新技術(shù)在提高編碼效率的同時也帶來了更高的計算消耗以及對系統(tǒng)內(nèi)存帶寬的需求。另一方面，近年來圖形處理器(GPU)的處理速度正在以超過摩爾定律的速度發(fā)展，而且能夠加速處理一些非圖形領(lǐng)域的應(yīng)用問題。目前人們已經(jīng)在使用圖形處理器強大的并行處理能力，研究如何對H.264/AVC視頻編碼標(biāo)準(zhǔn)中計算復(fù)雜度最大的運動估計模塊進行優(yōu)化，從而加快H.264/AVC視頻編碼速度。

目前已經(jīng)有不少基于GPU的H.264運動估計算法被提出。文獻［2］利用 CUDA［3］計算平臺，實現(xiàn)了H.264/AVC中的運動估計與離散余弦變換(DCT)系數(shù)的計算，并且給出了線程塊的劃分方法，為讀者使用GPU優(yōu)化H.264/AVC編碼一些啟示。文獻［4］提出了一種基于CUDA的塊大小可變的運動估計算法，該算法使用塊級并行，并取得了12倍的加速比。但該算法忽略了運動矢量(MV)預(yù)測，犧牲了視頻質(zhì)量。文獻［5］也提出了一種基于CUDA的并行全搜索運動算法。該算法在處理不同大小宏塊的運動估計時沒有進行進一步優(yōu)化，雖然視頻質(zhì)量沒有損失，但是計算量依然很大。

文中在基于GPU的異構(gòu)平臺上提出了一種新的H.264/AVC運動估計算法。運動估計是H.264/AVC編碼過程中最耗時的環(huán)節(jié)，其計算量占整個編碼系統(tǒng)的80%以上［6］。在X264編碼軟件的基礎(chǔ)上引進了針對GPU進行優(yōu)化的運動估計算法，該算法充分利用了GPU的并行編程模型，大量線程的并行執(zhí)行使得處理時間大幅減少。利用已得到的小宏塊數(shù)據(jù)進行合成得到整個樹形結(jié)構(gòu)的運動補償信息。最后在NVIDIA GTS450和Intel Core－i5 CPU組成的異構(gòu)計算平臺上試驗獲得了平均超過50倍的加速比。

1 CUDA硬件模型

近年來新的異構(gòu)系統(tǒng)被引入到高性能計算中［7］。比如由CPU和GPU組合而成的系統(tǒng)就是一種異構(gòu)計算系統(tǒng)。現(xiàn)在的GPU都是由上百個核心構(gòu)成，因而能獲得更佳的計算性能。然而GPU的編程方式與CPU有較大的差異，所以使用GPU編程并不是一件簡單的任務(wù)。為簡化GPU編程，NVIDIA公司推出了統(tǒng)一計算設(shè)備架構(gòu)(CUDA)。它可以像使用 CPU一樣對GPU進行編程。

與以往的GPU相比，支持CUDA的GPU在架構(gòu)上了有了顯著改進，這兩項改進使CUDA架構(gòu)更加適用于GPU通用計算。一是采用了統(tǒng)一處理架構(gòu)，可以更加有效地利用過去分布在頂點渲染器和像素渲染器的計算資源;二是引入了片內(nèi)共享存儲器，支持隨機寫入和線程間通信以減小片外訪存延遲［8］。其硬件模型如圖1所示。

圖1 CUDA硬件模型

CUDA源程序由運行于Host(CPU)上的控制程序和運行于Device(GPU)上的計算核(kernel)兩部分組成。每個Kernel由一組相同大小的線程塊(Thread Block)來并行執(zhí)行，同一線程塊內(nèi)的線程通過共享存儲空間來協(xié)作完成計算，線程塊之間是相互獨立的。運行時，每一個線程塊會被分派到一個流多處理器(Stream Multiprocessor，SM)上運行。為管理運行種不同程序的數(shù)百個線程，SM利用一種稱為SIMT(Single Instruction Multiple Thread)的新架構(gòu)。SM將各線程映射到一個線程處理器(Thread Processor，TP)核心上，各TP使用自己的指令地址和寄存器狀態(tài)獨立執(zhí)行。

SIMT單元以32個并行線程為一組來創(chuàng)建、管理、調(diào)度和執(zhí)行線程，這樣的線程組稱為Warp塊。構(gòu)成SIMT Warp塊的各個線程在同一個程序地址一起啟動，也可隨意分支、獨立執(zhí)行。為一個多處理器指定一個或多個要執(zhí)行的線程塊時，SIMT單元調(diào)度器會將其分成Warp塊，并由SIMT單元進行調(diào)度。將塊分割為Warp塊的方法總是相同的，每個Warp塊都包含連續(xù)的線程，遞增線程ID。每發(fā)出一條指令時，SIMT單元都會選擇一個已準(zhǔn)備好執(zhí)行的Warp塊，并將指令發(fā)送到該Warp塊的活動線程。

2 基于CPU－GPU異構(gòu)系統(tǒng)運動估計算法

這里將介紹一種基于CPU－GPU異構(gòu)系統(tǒng)的H.264整像素運動估計算法，而運動估計也是H.264編碼器中耗時最長的環(huán)節(jié)。在幀間預(yù)測模式下，H.264標(biāo)準(zhǔn)對一個宏塊劃分模式共有7種:16×16，16×8，8×16，8×8，8 ×4，4 ×8，4 ×4。對于任意一種劃分模式，都需要得到該宏塊在其參考幀搜索窗口中的SAD值。為此，把運動估計分為3步:首先，計算各個4×4子塊的SAD值;其次，根據(jù)第一步得到的各4×4子塊SAD值，組合得到宏塊在其他劃分模式下的SAD值;最后，對各種模式下的SAD值進行比較，得到宏塊的最小SAD值以及最佳運動向量。

針對CPU－GPU異構(gòu)系統(tǒng)，將整個計算任務(wù)作如下劃分。CPU負責(zé)將所需編碼的視頻文件讀入計算機主存并拷貝到GPU的顯存中，GPU負責(zé)核心的運動估計算法執(zhí)行，并將計算結(jié)果傳輸回計算機主存由CPU進行后續(xù)處理。在進行運動估計之前，把在編碼過程中不變的數(shù)據(jù)讀入到GPU的常量存儲器當(dāng)中。這些數(shù)據(jù)信息包括幀的大小，搜索窗口大小，和搜索方式等等。另一方面，每幀的圖像信息和參考幀信息需要傳輸?shù)紾PU的全局存儲器中。當(dāng)運動估計結(jié)束之后，得到的運動補償信息將被傳輸回CPU的主存中。

2.1 4×4子塊的SAD值計算

第一個Kernel的目的是為了獲得4×4子塊的SAD值。首先，為使提出的運動估計算法獲得更好的性能，需要對H.264/AVC的搜索方式做一些改變。圖1(a)表示了H.264編碼器的運動搜索方式。這種搜索區(qū)域的分布呈螺旋狀，第一個搜索點在整個區(qū)域的中心位置。連續(xù)的兩個搜索點在存儲器中的位置不相鄰。由于每個像素點需要用來計算多個4×4子塊的SAD值，所以需要多次訪問每一個像素點。而按照這種方式，就無法對GPU紋理存儲器Cache與共享存儲器中的數(shù)據(jù)進行復(fù)用。所以這里定義了一種新的搜索方式。如圖1(b)所示，搜索順序從整個搜索區(qū)域的左上方開始，按照先行后列的順序進行。

圖2 搜索方式

將一個宏塊劃分成16個4×4的子塊，假設(shè)搜索區(qū)域的大小為M×N，那么需要創(chuàng)建M×N個線程。每個線程計算一個宏塊在搜索窗口中一個位置的16個4×4的子塊SAD值。每個GPU的線程塊有256個線程，所以每個線程塊可以得到一個宏塊在搜索窗口中256個相鄰位置的4×4的子塊SAD值。這些4×4的SAD值將用來組合得到其他劃分模式下的SAD值。

由于使用新的搜索方式，可以充分利用GPU存儲器中的數(shù)據(jù)復(fù)用。在每個線程塊開始工作前，該線程塊中的所有線程將共同把待預(yù)測宏塊的數(shù)據(jù)與參考幀搜索窗口包含的所有數(shù)據(jù)讀入共享存儲器中。這種存儲模型對全局存儲器中的所有參考像素值只需訪問一次，減少了對同一個搜索窗口中重復(fù)使用像素的多次片外讀取，將對片外全局存儲器的訪問轉(zhuǎn)化為對片內(nèi)共享存儲器的訪問。這樣可以減少數(shù)據(jù)的訪問延時。

2.2 各種劃分模式SAD值的合成

為得到更加精確的預(yù)測值，還需要計算宏塊在其他劃分模式下的SAD值。如果對每一種劃分方式都進行全搜索，那么得到的各種劃分方式對應(yīng)的MV肯定是最佳的，但計算量也較大。文中利用已經(jīng)計算得到的4×4子塊的SAD值來合成其他劃分模式下對應(yīng)形狀塊的SAD值。雖然圖像質(zhì)量有一定損失，但顯著減少了計算量。

因此，第二個Kernel主要是為了獲得宏塊在其他劃分模式下的SAD值，同時也對不同劃分模式下得到的SAD值進行第一次歸約。該Kernel的輸入為第一步中獲得的128個位置處的4×4的SAD值。

圖3中顯示了如何使用4×4子塊的SAD值合成其他劃分模式下的運動信息。為得到8個8×4以及8個4×8子塊的SAD值，僅需要相加兩個4×4子塊的SAD值。例如，將#0與#24×4子塊的SAD值相加便可以得到#08×4子塊的SAD值，將兩個4×8子塊的SAD值相加便可得到8×8子塊的SAD值。其他形狀的子塊SAD值都可以根據(jù)這種方式計算得到。最后將所有劃分模式下得到的SAD值全部存儲在線程塊的共享存儲器當(dāng)中。

圖3 合成其他形狀子塊

第二個Kernel的另一個任務(wù)是對存儲在共享存儲器中的SAD值進行第一次歸約。對于每種宏塊的劃分模式，整個歸約過程都是相同的。在這里以16×16宏塊對應(yīng)的SAD值歸約為例說明歸約過程。為完成歸約過程，一共需要進行7次迭代。線程塊剛開始時處理128個子塊的SAD值，每進行一次迭代有效線程數(shù)目縮小1/2。在進行比較歸約的過程中，如果選擇相鄰的線程進行比較，則會出現(xiàn)兩個嚴重的問題:(1)共享存儲器訪問沖突;(2)Warp分支嚴重。為解決這兩個問題，文中約定每一次比較過程中的有效線程始終為前N個線程。每個線程取與本線程ID號相差N的線程對應(yīng)的兩個SAD值進行比較，將較小的SAD值及其對應(yīng)的MV存儲到該線程對應(yīng)的共享存儲器中。整個比較歸約的過程如圖4所示。

圖4 SAD值比較歸約

2.3 獲取最佳匹配結(jié)果

第3個Kernel對第二個Kernel歸約得到的數(shù)據(jù)繼續(xù)進行歸約。第2個Kernel的歸約因子為128，所以每個宏塊還有M×N/128個候選位置。該Kernel使用與第2個Kernel中相同的歸約方法，最終得到每個宏塊的最小SAD值以及最佳運動向量。

3 實驗結(jié)果

為驗證文中提出的運動估計算法性能，使用X264［9］開源軟件作為試驗基礎(chǔ)。X264是一款免費的、開放源代碼的H.264編碼器，并且引入了MMX、SSE、SSE2等多媒體匯編指令來提高編碼速度。實驗環(huán)境配置如下:(1)Intel Core－i52.53 GHz CPU，4 GB內(nèi)存，Microsoft Visual Studio 2010;(2)GeForce GTS450，1 GB顯存，49152 kB Shared Memory，CUDA Toolkit 4.0。

通過選取幾種不同分辨率的視頻序列進行測試，試驗結(jié)果如表1所示。

表1 CPU與GPU上運動估計實驗結(jié)果比較

從實驗結(jié)果可以看出，在GPU上執(zhí)行的運動估計算法相比CPU有了較大的性能提升，并且在分辨率越大的視頻序列獲得的加速比也大。這是因為GPU特別適合計算密集型任務(wù)，所需處理的數(shù)據(jù)量越大，獲得的性能提升效果也越明顯。

4 結(jié)束語

闡述了一種基于CUDA的運動估計算法，并在X264開源編碼軟件上進行了測試。試驗結(jié)果表明在不同的視頻序列上獲得了平均超過50倍的加速比。使用GPU完成視頻編碼器中計算密集且計算量最大的運動估計模塊，獲得了顯著的性能提升。文中所提出的算法也可作為設(shè)計基于GPU的完整H.264/AVC視頻編碼器的基礎(chǔ)，進一步研究編碼器其他模塊在GPU上的實現(xiàn)方法。

［1］畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)－H.264/AVC［M］.北京:人民郵電出版社，2009.

［2］高智勇，萬雙，舒振宇，等.基于CUDA的H.264/AVC視頻編碼的設(shè)計與實現(xiàn)［J］.中南民族大學(xué)學(xué)報，2009，28(3):67 －72.

［3］張舒，褚艷利，趙開勇，等.GPU高性能運算之 CUDA［M］.北京:中國水利水電出版社，2009.

［4］CHEN Weinien，HANG Hsuehming.H.264/AVC motion estimation implmentation on compute unified device architecture(CUDA)［C］.IEEE International Conference on Multimedia and Expo，2008:697 －700.

［5］甘新標(biāo)，沈立，王志英.基于CUDA的并行全搜索運動估計算法［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2010，22(3):457－470.

［6］FENG W C，MANOCHA D.High －performance computing using accelerators［J］.Parallel Computing，2007，33(10 －11):645－647.

［7］席迎來.H.264/AVC編碼的關(guān)鍵算法與VLSI架構(gòu)研究［D］.西安:西北工業(yè)大學(xué)，2006.

［8］NVIDIA.CUDA programming guide 2.0［M］.Santa Clara:NVIDIA Corportion，2008.