章 劍，仰楓帆

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

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

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

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

1 CUDA硬件模型

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

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

圖1 CUDA硬件模型

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

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

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

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

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

2.1 4×4子塊的SAD值計(jì)算

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

圖2 搜索方式

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

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

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

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

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

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

圖3 合成其他形狀子塊

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

圖4 SAD值比較歸約

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

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

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

為驗(yàn)證文中提出的運(yùn)動(dòng)估計(jì)算法性能，使用X264［9］開(kāi)源軟件作為試驗(yàn)基礎(chǔ)。X264是一款免費(fèi)的、開(kāi)放源代碼的H.264編碼器，并且引入了MMX、SSE、SSE2等多媒體匯編指令來(lái)提高編碼速度。實(shí)驗(yàn)環(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。

通過(guò)選取幾種不同分辨率的視頻序列進(jìn)行測(cè)試，試驗(yàn)結(jié)果如表1所示。

表1 CPU與GPU上運(yùn)動(dòng)估計(jì)實(shí)驗(yàn)結(jié)果比較

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

4 結(jié)束語(yǔ)

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

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

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

［3］張舒，褚艷利，趙開(kāi)勇，等.GPU高性能運(yùn)算之 CUDA［M］.北京:中國(guó)水利水電出版社，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的并行全搜索運(yùn)動(dòng)估計(jì)算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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］席迎來(lái).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.