一種基于異構系統的H.264/AVC運動估計算法

章 劍，仰楓帆

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

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

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

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

1 CUDA硬件模型

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

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

圖1 CUDA硬件模型

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

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

2 基于CPU－GPU異構系統運動估計算法

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

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

2.1 4×4子塊的SAD值計算

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

圖2 搜索方式

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

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

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

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

因此，第二個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值都可以根據這種方式計算得到。最后將所有劃分模式下得到的SAD值全部存儲在線程塊的共享存儲器當中。

圖3 合成其他形狀子塊

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

圖4 SAD值比較歸約

2.3 獲取最佳匹配結果

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

3 實驗結果

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

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

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

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

4 結束語

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

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

［2］高智勇，萬雙，舒振宇，等.基于CUDA的H.264/AVC視頻編碼的設計與實現［J］.中南民族大學學報，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］甘新標，沈立，王志英.基于CUDA的并行全搜索運動估計算法［J］.計算機輔助設計與圖形學學報，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編碼的關鍵算法與VLSI架構研究［D］.西安:西北工業大學，2006.

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