基于CUDA的并行全搜索运动估计算法

计算机辅助设计与图形学学报

JournalofComputer2AidedDesign&ComputerGraphicsVol.22No.3Mar.2010

基于CUDA的并行全搜索运动估计算法

甘新标,沈 立,王志英

(国防科学技术大学计算机学院 长沙 410073)(xinbiaogan@163.com)

摘要:为了提高H.264视频编码效率,基于计算统一设备架构(CUDA)的并行全搜索运动估计算法,并利用GPU

强大的计算能力和CUDA优化的存储层次结构,以加速H.264编码中的运动估计.与传统的以牺牲视频质量来提升运动估计性能的方法不同,该算法在保证视频质量的同时,结合运动估计计算密集、计算量大等特点,充分利用CUDA架构的并行性加快运动估计的速度,从而达到提高实时编码速度的目的.在GTX280实验平台上的实验结果显示,采用文中算法比优化的CPU实现可获得高达70倍的加速比.关键词:图形处理器;运动估计;并行;CUDA中图法分类号:TP312

ParallelizingFullSearchAlgorithmforMotionEstimationUsingCUDA

GanXinbiao,ShenLi,andWangZhiying

(CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha 410073)

Abstract:ImprovingmotionestimationisessentialforH.264system.TospeedupthefullsearchformotionestimationH.264encodingprocess,aframeworkisproposedinthepaperforparallelprocessingonGPUusingcomputingunifieddevicearchitecture(CUDA).TheproposedmethodcantheadvantageofGPUpspowerfulcomputingresourcesandoptimalmemoryhierarchyaswellasthepotentialparallelisminCUDA.ExperimentalresultsshowthatourimplementationonnVidiapsGTX280demonstratessubstantialimprovementupto70timesspeedupthanCPUcounterpartavailable.

Keywords:GPU;motionestimation;parallelization;CUDA 近年来,拥有高度并行性和可编程性的GPU已经广泛应用于数值计算[122]、流体模拟[2]、数据库操作[3]等通用计算领域.同时GPU作为流处理器的一种,已经广泛应用于流计算中

[4]

因此,高效、快速地实现运动估计模块是编码系统设

计的关键.全搜索(fullsearch,FS)算法是最简单可靠的运动估计算法,它通过对搜索范围内所有可能的候选位置计算SAD(sumofabsolutedifference)值,从中找出最小的SAD,其对应偏移即为所求的运动矢量.FS算法虽能得到全局最优的结果,但计算量大,限制了它在实时压缩场合的应用.

基于传统GPU架构的运动估计算法虽然取得了一定的性能提升,但不能充分利用GPU强大的

.H.264视频编

码是一种典型的流处理应用,适合于在支持计算统一设备架构(computingunifieddevicearchitecture,CUDA)的GPU上进行优化加速.

运动估计是一个计算密集、计算量大的编码模块,其计算量占整个编码系统计算量的50%~90%[5].

收稿日期:2009-05-15;修回日期:2009-10-09.基金项目:国家/九七三0重点基础研究发展计划项目(2007CB310901);国家自然科学基金(60803041);国防科技大学优秀研究生创新资助(B0906603).甘新标(1982)),男,博士研究生,主要研究方向为计算机体系结构、并行计算、编译优化;沈 立(1976)),男,博士,副教授,硕士生导师,主要研究方向为计算机体系结构、编译优化、虚拟化技术等;王志英(1956)),男,博士,教授,博士生导师,CCF高级会员,主要研究方向为计算机体系结构、微处理器设计、虚拟化技术等.

458

计算机辅助设计与图形学学报 第22卷

计算资源[627].2008年,Chen等[8]基于CUDA架构实现了块大小可变的FS算法,并取得了12@的加速比,然而该算法忽略了运动矢量预测(motionvectorprediction,MVP),牺牲了视频质量.本文的工作就是保证视频质量的同时,基于CUDA的并行性提出了SAD并行计算模型,优化实现了FS算法.

SIMT单元以32个并行线程为一组来创建、管理、调度和执行线程,这样的线程组称为warp块.构成SIMTwarp块的各个线程在同一个程序地址一起启动,也可随意分支、独立执行.为一个多处理器指定一个或多个要执行的线程块时,SIMT单元调度器会将其分成warp块,并由SIMT单元进行调度.将块分割为warp块的方法总是相同的,每个warp块都包含连续的线程,递增线程ID,第一个1 CUDA执行模型

CUDA是NVIDIA推出的一种高性能GPU体系架构,支持CUDA的GPU与传统GPU的最大区别在于它拥有片内共享存储空间用以减小片外访存延迟[9]

.CUDA执行模型以CUDA为基础,其硬件架构如图1所示.

图1 CUDA硬件架构

CUDA源程序由运行于host(CPU)上的控制程序和运行于device(GPU)上的计算核心(kernel)两部分组成.每一个kernel由一组相同大小的线程块(threadblock)来并行执行,同一线程块内的线程通过共享存储空间来协作完成计算,线程块之间是相互独立的.运行时,每一个线程块会被分派到一个流多处理器(streammulti2processor,SM)上运行.为了管理运行各种不同程序的数百个线程,SM利用了一种称为SIMT(singleinstructionmultiplethread)的新架构[9].SM将各线程映射到一个线程处理器(threadprocessor,TP)核心上,各TP使用自己的指令地址和寄存器状态独立执行.

warp块中包含线程0.每发出一条指令时,SIMT单元都会选择一个已准备好执行的warp块,并将下一条指令发送到该warp块的活动线程.

2 基于CUDA的FS算法

基于CUDA的并行FS算法将以运动估计评估模型为基础,构建并行SAD计算模型以加快运动估计的搜索过程,规范运动估计过程,强调MVP机制对视频质量的重要性.2.1 运动估计评估模型

运动估计的实质就是消除相邻帧之间的时间冗余度,目的是使得视频传输的比特数开销(cost)大为减少,即使用最小的比特数开销来表示宏块的运动.

在x264实现中,cost的计算包括参差编码开销和运动矢量编码开销2部分,即

cost=SAD+K[C(MVx-MVpx)+C(MVy-MVpy)].

其中参差编码开销通常近似表示为SAD开销.式(1)中,K为经验值,C取决于运动矢量参差的比特数;SAD的计算复杂度直接影响着视频编码的速度,忽略MVP将牺牲编码后的视频质量.因此在

CUDA中,并行FS算法将以式(1)为依据,构建并行SAD计算模型和运动矢量预测机制.2.2 SAD并行计算模型

H.264运动估计的基本处理单元是16@16的宏块,其运动补偿的方法采用树结构的运动补偿,即一个16@16的宏块可以按照16@16,16@8,8@16和8@8进行分割,而如果选择了8@8分割,还可以按照8@8,8@4,4@8和4@4进行亚分割,总共有7种分割方式.因此在kernel中可以并行启动7个SAD计算实体来求解每一种分割方式下最小的SAD,分别记为SAD1,SAD2,SAD3,SAD4,SAD5,SAD6和SAD7,则FS算法最小的SAD为帧间预测模式,即为最小SAD对应的分割方式

SADFS=min{SADi},i=1,2,3,4,5,6,7.

第3期甘新标,等:基于CUDA的并行全搜索运动估计算法

459

下面以基本块16@16为例介绍SAD并行计算的方法.如图2所示,假设帧规格为W@H,搜索半径为Rx@Ry,则需要计算SAD的数目为

num_sad=W@H@Rx@Ry.

1616

算出来SAD就没有必有存储在外部DRAM中,可直接存储在共享存储空间,为接下来的SAD比较准备数据;同时,将计算出来的最小的SAD存储在DRAM可以避免从DRAM存取数据,减少了数据的存取时间.2.3 MVP

由于运动矢量在空间域上存在很强的相关性,同时由于物体运动的连续性使得运动矢量在时间域也存在一定相关性,因此采用MVP机制可以避免图2 SAD并行计算模型

若分派一个线程去完成一个对应位置的SAD,每256个线程组成一个线程块,需要的线程块的数目计算公式如

num_thread=num_sad,

block_dim=num_thread@1256

.

SAD值的计算采用CUDA运行时支持的内部函数_usad(x,y,z),计算各位置对应SAD后,需快速选择出最小的SAD.若分派送给每个线程的任务包括读出2个SAD的值,然后比较选择出较小者,则每次比较需要的线程数为

num_thread=num_sad@12

.

比较选出最小SAD的过程如图3所示.

图3 SAD并行比较模型

在SAD的并行计算和比较模型中,使用了共享存储空间.由于同一个线程块里面的线程可以通过共享存储空间进行通信,所以同一线程块的线程计

花费大量的比特数对每个块的运动矢量进行编码,还可以提高视频质量.大量的实验证明,空间域的预测更为准确[10].因此本文采用基于空间域的运动矢量中值预测方式,其基本思想是利用当前块cur相邻的宏块:左边块left,上边块above和右上方的块above_right的运动矢量,取其中值作为当前块cur的预测运动矢量,即

MVpre_x_cur=(x_median,y_median)

x_median=(MVleft(x),MVabove(x),MVabove_right(x))y_median=(MVleft(y),MVabove(y),MVabove_right(y))

图4 中值预测

3 实验结果及性能分析

为了验证基于本文算法的有效性,实验环境配置如下:

1)IntelCore2Quad2.33GHzCPU,4GB内存,MicrosoftVisualStudio2005.

2)GeForceGTX280,1GB显存,32KBSharedMemory,CUDAtoolkit和SDK2.0,NVIDIADriverforMicrosoftWindowsXP(177.98).

3)标准测试系列:akiyo_qcif,foreman_qcif和paris_cif.

4)X264是H.264规范的开源C实现版本,该

实现引入了MMX,SSE等汇编优化指令,并且还加入了多线程执行机制.

本文算法与面向CPU实现的FS算法的性能比较如表1所示.

460

表1 2种算法性能比较

运行时间Pms

测试集

CPU

akiyo_qcifforeman_qcifparis_cif

281.7281.71282

CUDA5.35.318.9

计算机辅助设计与图形学学报 第22卷

[2]WuEnhua,LiuYouquan.Generalpurposecomputationon

GPU[J].JournalofComputer2AidedDesign&Computer

加速比53.253.267.83

Graphics,2004,16(5):6012612(inChinese)

(吴恩华,柳有权.基于图形处理器(GPU)的通用计算[J].计算机辅助设计与图形学学报,2004,16(5):6012612)[3]CaoFeng,ZhouAoying.Fastclusteringofdatastreams

usinggraphicsprocessors[J].JournalofSoftware,2007,18(2):2912302(inChinese)

(曹 锋,周傲英.基于图形处理器的数据流快速聚类[J].软件学报,2007,18(2):2912302)[4]BuckI.

Streamcomputingongraphicshardware[D].

Stanford:StanfordUniversity,2005

由表1可以看出:本文算法可获得近70倍的加速比;同时,数据越密集、数据量越大,越利于CUDA加速,.cif文件(288@352)与.qcif(2144@176)文件相比可获得更大的加速比.

4 结 语

基于CUDA实现x264视频编码器其是一件极富挑战性的工作.本文基于CUDA实现了视频编码器中计算密集且计算量最大的运功估计模块,取得了显著的性能提升,通过实验验证了基于CUDA的视频编码系统的可行性,为其实现奠定了基础.参考文献(References):

[1]ZhouJifu,ZhongChengwen,YinShiqun,etal.Numerical

simulationalgorithmofLattice2BoltzmannonGPGPU[J].JournalofComputer2AidedDesign&ComputerGraphics,2008,20(7):9122918(inChinese)

(周季夫,钟诚文,尹世群,等.基于GPGPU的Lattice2Boltzmann数值模拟算法[J].计算机辅助设计与图形学学报,2008,20(7):9122918)

[5]HuangYW,ChenCY,TsaiCH.Surveyonblockmatching

motionestimationalgorithmsandarchitectureswithnewresults[J].JournalofVLSISignalProcessing,2006,42(5):2972320

[6]HoCW,AuOC,ChanS,etal.MotionestimationforH.

264PAVCusingprogrammablegraphicshardware[C]PPProceedingsofIEEEInternationalConferenceonMultimediaandExpo,Piscataway,2006:204922052

[7]LeeCY,LinYC,WuCL,etal.Multi2passandframe

parallelalgorithmsofmotionestimationinH.264PAVCforgenericGPU[C]PPProceedingsofIEEEInternational

ConferenceonMultimediaandExpo,Piscataway,

2007:

160321606

[8]ChenWN,HangHM.H.264PAVCmotionestimation

implementation

on

compute

unified

devicearchitecture

(CUDA)[C]PPProceedingsofIEEEInternationalConferenceonMultimediaandExpo,Piscataway,2008:6972670[9]NVIDIA.CUDAprogrammingguide2.0[M].SantaClara:

NVIDIACorporation,2008

[10]BiHoujie.Newvideocompressioncodingstandard)H.264P

AVC[M].Beijing:Posts&TelecomPress,2005(inChinese)(毕厚杰.新一代视频压缩编码标准)H.264PAVC[M].北京:人民邮电出版社,2005)