基于片上存储器的视频编码优化

摘　要：为了提高视频编码器性能，并降低功耗，本文提出了一种缩短数据生命期减小存储器需求的方法。分阶段计算中间结果，减少临时结果存储，可减小存储器需求和存储器访问次数。另外提出了一种有效利用CPU寄存器字宽和桶型寄存器移位能力，缩减变字长编码输出运算复杂性的方法。实验结果表明，该方法能显著缩短视频编码中变字长编码的时间。

关键词：　存储器；视频编码；变字长编码

引言
　　
CPU运算速度迅速提高，外部数据存储器的访问能力相对较低，为了匹配CPU和外部存储器的速度差异，通常采用片上Cache或者片上存储器。片上Cache采用硬件控制数据的存取，片上存储器的使用则完全受软件的控制。Cache结构由于采用更多的硬件，因而具有更大的功耗。低功耗是嵌入式设备的基本要求，因而在嵌入式处理器中，片上RAM可能作为Cache的替代。目前主要的半导体厂商都生产包含片上存储器的高性能处理器，尤其是用于手持设备的嵌入式低功耗芯片，如TI公司的OMAP系列媒体处理器。多媒体应用的数据访问具有较大的数据集和较少的数据再利用，而应用程序的执行时间主要消耗在一些较小的循环上，目前针对片上数据存贮器结构的视频算法优化却很少研究。本文试图讨论针对这类处理器的视频编码器优化，以改善实时性能，同时尽可能降低片外存储器访问次数，以便降低算法的功耗。

减少存储器需求
　　
通过减小存储器需求，可以缩减存储在片外存储器的数据数量，从而缩减片外存储器访问次数，降低功耗。为了减小存储器需求，数据在其生命期一结束，就立即释放其所占的存储器，并用来存储其它数据。生命期不相交的变量或者矩阵可以共用相同的存储器，从而缩减存储器需求。数据的生命期定义为从初始化或者产生(CPU写)到不再被CPU读取进行处理间隔。称CPU采用与i无关的值改写i的过程为变量i初始化。如“i=0”为i的初始化，“i=i+1”或者“i= f(i)”称为对i的修改。为了缩短数据的生命期，调整数据的初始化或者改写操作到CPU读取该数据的前面，可减小数据的生命期。图1中i和j的生命期有重叠，图2中调整i变量的初始化到CPU读取i的前面，缩短了变量的生命期，从而变量i和j的生命期不相交。将不相交的变量共用存储器，减少了对j变量的存储器需求，结果见图3。

图1 原始程序

图2 调整数据初始化顺序

图3 共用存储器

在视频编码中运动搜索采用单一参考帧情况下，通常的方法采用两个帧存，一帧存储当前编码帧重建图像，一帧用来存储前一帧重建图象，用作当前帧的预测参考。当运动搜索范围为[-16，16]时，也就是说在编码第j个GOB时，搜索窗位于前一帧重建图像的第j-1、j、j+1个GOB，前一帧重建图像里前j-2个GOB已经不再用作搜索参考图像，生命期结束可尽快释放，用来存储新编码宏块的重建图像。因此存放重建图像的存储器大小为：当前编码帧的j个GOB加上前一帧M-(j-2)个GOB，总计为M+2个GOB，其中M为一帧图像包含的GOB数量，重建图像减少了(M-2)个GOB。

分阶段计算中间结果
数据处理算法总是处理一些数据，得到一些结果，程序的执行表现为周期性读入原始数据并计算得到最终结果。在图像编码算法中，中间结果的存储需要大量的存储器。一次计算很多中间数据，每次计算最终结果只需要利用其中部分数据，这相当于延长了数据的生命期。每个数据处理任务的输出数据用作相邻的数据处理任务的输入，可以缩减中间结果的的生命期。分阶段地计算中间结果，可显著减小存储中间结果的存储器需求。在H.263编码器中，除了输入图像数据和最后输出的H263码流外，其它为计算最后输出CPU计算的大量数量可以统称为中间结果。在INTER帧编码过程中，为了在整像素运动搜索以后，进行半像素运动搜索，必需对参考图像进行半像素内插。通常先对整帧图像进行半像素内插，内插结果为一帧中所有的宏块编码所利用，半像素图像为原始图像的4倍，存储半像素内插结果需要大量的存储器。单个宏块的码流只用到少数半像素图像，因而在编码前只计算编码该宏块所必需的半像素，存储器需求将显著减少。半像素搜索是在整像素搜索后以整像素运动矢量为中心的搜索，为减小中间结果的生命期，半像素内插这一处理任务应与半像素搜索相邻，位于整像素搜索和半像素搜索的中间。因而可以在半像素搜索前对整像素运动矢量指向的18×18的块进行内插，存储器需求大约为33×33。

减少中间结果存储
减少中间结果不必要的存储，不仅可以减少存储器需求，而且可以减少存储器的访问。在图4的C代码片段中，存在三个矩阵A、B、C，其中B矩阵元素与A矩阵元素一一对应，C矩阵元素与B矩阵元素一一对应，因而C矩阵元素与A矩阵元素一一对应。f1，f2为矩阵基元值的映射。省去中间结果存储后计算方法见图5 和图6 ，中间结果B[i]并不写入存储器，直接由保存在寄存器的B[i]计算C[i] ，从而节省存储了存储B矩阵和读取B矩阵的操作。

图4　两个循环

图5 　按照结果索引递增计算

图6 　按照源索引递增计算

在H.263编码器中，INTRA宏块编码过程包括离散余弦变换(DCT)、量化、扫描输出码字、逆扫描、逆量化、逆DCT等步骤。但DCT和逆DCT变换中的每个结果矩阵元素是源矩阵中的所有元素的函数，变换前后矩阵的元素不是一一映射关系。而量化、逆量化、扫描、逆扫描中结果矩阵的每个元素只与源矩阵中唯一的元素对应，是一一映射，每种操作都对应一个循环，将这些循环合并，可以省掉中间结果的存储。

数据处理任务
　　
算术运算和逻辑运算通常由CPU或协处理器来完成，若CPU访问数据不会引起延迟，则程序的实时性能主要取决于CPU的处理能力。因而将应用程序按照功能分成CPU顺序执行的若干数据处理任务，应用程序表现为数据处理任务的循环执行和条件执行等形式。这样划分主要是为了分析数据处理过程中的存储器需求。多媒体应用总是需要处理大量数据，每个数据处理任务处理一个或者多个输入数据块，并得到一个或多个输出数据。某个数据处理任务的输入可能来自于前面某个任务的输出，也可能是程序的原始数据输入。某个数据处理任务的输出可能作为后面某个任务的输入，也可能是该程序的目标输出。数据处理任务是数据处理的基本单元，一旦开始执行，就不必停下来等待数据转移。数据处理任务具有以下两方面的性质：一是输入数据必需包含成块的数据(矩阵)，若一段代码仅仅处理了几个标量数据就不列入数据处理任务的范畴。当然数据处理后必然会有计算结果输出，但输出数据可以不包含成块数据(矩阵)，输出数据是一个或者几个标量数据是可以的。二是数据处理的连续性。由于片外存储器的访问速度远远低于CPU，因而数据处理任务执行过程中，CPU不能直接读写片外存储器，也不能停下来等待直接存储器存取(DMA)转移数据后再读写片上存储器。数据处理任务表现为CPU不间断地处理某个数据块。

精细同步减小片上缓冲区需求
DMA控制器的转移能力直接影响数据输入输出缓冲区所需的存储器数量，从而影响存储器的分配。若DMA转移和CPU保持精细的同步，可以有效减小片上存储器缓冲区。称存储输入片外数据的片上存储器为输入缓冲区，存储需要转移到片外的输出数据的片上存储器为输出缓冲区。假设某个处理任务处理输入缓冲区数据，在该处理任务前的一个或多个处理任务并不访问该缓冲区，并且DMA也可利用这些间隔转移数据到输入缓冲区，这时并不需要设置乒乓缓冲区。同样，某数据处理任务产生输出结果，其后的一个或多个处理任务并不改写该输出缓冲区，DMA也可利用这些间隔转移输出缓冲区数据到片外，从而减小片上存储器缓冲区需求。

链表能力减小缓冲区需求
当DMA转移控制器的转移同步事件可以为其它DMA通道的转移结束事件(称之为DMA控制器的链表能力)时，就可以同时初始化两个DMA转移上下文，用一个通道的转移结束事件去触发另外一个通道的转移，当一个转移的源地址是另外一个转移的目的地址时，仍能保证两个数据转移任务的正确结果，由于共用了相同的存储器，所以减小了存储器需求。两个数据块的转移具有确定的先后顺序，后一个转移的源地址为前一转移的目的地址，或者后一个转移的目的地址为前一个转移的源地址时，当DMA控制器不具有链表能力时，这两个数据转移任务的上下文就不能同时初始化。

利用数据局域性
　　
多媒体数据的处理可以分成一些基本数据对象，处理基本数据对象后，会得到与基本数据对象相对应的最后输出，计算过程中可能会利用已处理数据对象的输出。将对应基本数据对象的处理时间可以称为一个一级时间片，每个一级时间片根据需要可进一步分成若干个二级时间片，每个二级时间片对应于数据处理任务。每个同级的时间片并不代表时间的绝对相等，而只代表这个时间片中含有类似的数据处理任务或者相同数量的数据处理任务。H.263编码器和H.264编码器中，每编码一个16×16的宏块，就能产生对应该宏块的最终输出码流，因而把宏块看成是H.263和H.264编码器中的基本数据对象，称宏块的处理为一级时间片。占用较多存储器的是前面数据对象的处理输出将要用作后面处理输入的矩阵数据。对各个基本数据单元的处理，经常会出现不同程度的数据重复利用，这通常表现为对相邻几个数据单元的处理存在相同的输入数据，或者一个单元的输出用作另一个单元的输入。对于图像而言，相邻的数据单元包括水平方向或者垂直方向的相邻。规定基本数据对象处理的时间间隔为1，该次数据被CPU读入与相邻前一次CPU读写该数据的间隔称为该数据的间隔。例如在H.263编码器中，重建宏块(x，y)用作下一帧中以该宏块为中心的9个宏块的运动搜索参考图像，假设图像大小为QCIF，该重建宏块的9次访问间隔分别为87、1、1、9、1、1、9、1、1。需要采用DMA转移该数据的时刻为访问间隔较大的时刻，如在第一次读访问前(间隔为87)，或者在第1、4、7次读访问前(时间间隔分别为87、9、9)。若仅在第一次读访问前转移该宏块数据到片上，该宏块数据仅需从片外到片上转移1次，需要片上存储器至少(1+1+1+9+1+1+9+1+1)共25 个宏块；若在第1、4、7次读访问前前转移，需要转移3次，存储器至少需要(1+1+1)共3个宏块。若全部重建图像存储在片上，不需要转移，至少需要存储器(87+1+1+9+1+1+9+1+1)共计111个宏块。实际应用中，算法对访问数据格式有一定的要求，需要的存储器比上面结果稍大一些。这需要CPU硬件特点及指令寻址方式作具体分析。上述问题也可这样分析：INTER 帧编码中相邻两个宏块(水平相邻或者垂直相邻)的搜索窗仅有三个宏块不同，若仅分配9个宏块片上存储器用于存储参考图像，编码每个宏块至少需要新转移三个宏块重建图像到片上，每个重建宏块至少需要3次片外到片上转移。若分配三个GOB，能将已经转移到片上的重建宏块保存在片上直到它不再使用为止，这时每编码一个宏块只需新转移一个宏块到片上，大大缩减重建图像从片外转移到片外的次数。

变字长编码输出
　　
变字长编码(VLC)是一种广泛应用的熵编码方法，对于大概率事件采用较短的码字编码，小概率事件采用较长的码字编码，以使得平均码长最短。每帧图像的编码比特数一般要求为整数个字节，若整帧图像的有效信息不是8比特的整数倍，最后添加一定的冗余比特，构成8比特的整数倍。目前代码中普遍使用的VLC码流输出方法是每次处理1个比特，每达到8比特就写入存储器，需要较多的条件判断和存储操作。这种方法没有充分利用CPU移位寄存器一次移位操作可左移或者右移多个比特这一特点。

现在CPU寄存器普遍是32比特，甚至64比特(如AMDAthloN4)，现在的码流输出方法也没有充分利用CPU寄存器字宽。改进的算法流程见图7，假设CPU为bigendiaN工作模式，寄存器字宽是N，N为2的幂，VLC码字的最大长度N不超过CPU寄存器字宽N。为了充分利用移位寄存器的移位能力，每次写存储器的单位为N比特，则未能输出到码流中的比特数nLeft不大于N-1比特，输出新码字时，总的信息长度n+nLeft不大于2N-1，可分成两种情况：n+nLeft大于等于N或者n+nLeft小于N。

图7 改进VCL输出

当n+nLeft大于等于N时(图7中左边分支)，码流输出见图8，首先将剩余信息(a)左移到寄存器的最左边(c)，再将当前码字(b)右移到(c)的后面(d)，(c)和(d)占据了整个寄存器，将寄存器内容写入存储器。这次编码未写入存储器的信息位于新的码字中。当n+nLeft小于N时(图2中右边分支)，码流输出见图9，将剩余信息(a)左移N比特到当前码字的左边(c)，再与当前码字或，得到最后的剩余信息(d)。图3是原始算法和改进算法的运算复杂性对比。只要平均码长大于2比特，改进方法的运算次数都少于原始算法。

图8 n+nLeft>=N分支

图9 n+nLeft<分支

图10　算法复杂性对比

实验结果
　　
实验：为了验证本文提出的VLC码流输出算法的有效性，测试了H263编码器算法TMN30的码流输出原始算法与建议算法所需时间对比。测试序列为miss.qcf ，编码6帧，编码模式为IPPP，量化参数为8，调用次数4584次。在intel Pentium4平台上原始算法和改进算法所花时间分别为0.350毫秒和0.109毫秒，时间缩短了68%。在TIOMAP1510中C55x处理器上，原始算法和改进算法所消耗CPU周期分别为1776104毫秒和285442毫秒，时间缩短了83%。

结论
　　
本文提出的减少存储器需求的方法已经成功应用在OMAP平台上H.263优化中。在H.263编码器中，运动估计等模块采用了快速算法及优化后，变字长编码输出由于有较多的条件判断，数字信号处理器中的条件操作需要消耗更多的周期，因而减少变字长编码输出的时间对于运算能力有限的移动媒体处理器仍是十分重要的。