矢量基二维DCT在DSP上的内存存取减少方法

刘项洋，许 勇，陈付龙，郑孝遥

(安徽师范大学 计算机与信息学院，安徽 芜湖 241002)

1 引 言

自从文献[1]中定义了信号处理领域中的离散余弦变换(Discrete Cosine Transform，以下简称为DCT)，它便在图像和视频应用中起着举足轻重的作用.并且它也成为诸如JPEG、MPEG、H.264等图形影像编码标准中的重要组成成分[2，3].这是因为它在很多条件下能表现出非常近似于优化的卡南-洛维变换(Karhunen-Loeve transform又称KL变换)的性质[4].随着DCT的广泛应用，学术界和业界中也逐渐提出了一些直接的和间接的计算DCT的算法[4].后来提出的算法也包括诸如基2-DCT[5]、混合基DCT[6]、质因子DCT[7]以及近期的蝶形DCT[8]、脉动阵列DCT[9]、矢量矩阵DCT[10]和自适应近似DCT[11]等算法.

目前二维DCT的计算又可以分为直接计算和分解计算，其中分解计算是将二维DCT按行或列逐步分解成一维DCT来计算[12]，但这种计算需要进行非常耗时的矩阵转置运算，因而其运算量远高于直接计算.在文献[13-20]等中都提出了一些比较有效的直接计算二维DCT的算法.而矢量基二维快速DCT算法在目前这些算法中具有最低的计算复杂度[15].

矢量基二维DCT也因其规则的运算流程，使它可以在很多硬件以及软件平台上运行，包括针对具体应用程序的集成硬件电路(ASIC)[20].可是硬件平台一般是针对具体条件下的特定应用，因此不具备可扩展性，而软件平台虽具备可扩展性，但速度又远低于同类的硬件平台.因此经过广泛实验，本文最终采用一类特殊的专用处理器：数字信号处理器(Digital Signal Processor，简称DSP)来作为矢量基二维DCT运算的实现平台.DSP的优点是性能上兼具硬件实现和软件实现的长处，因为他们是经过专门优化以用来快速运行各种信号处理程序，如FIR滤波器、FFT傅里叶变换以及DCT等.目前美国模拟器件公司(ADI)，德州仪器(TI)和飞思卡尔(freescale)等DSP厂商生产了各类DSP芯片、以及他们的各类评估板材，以供工业界和学术界研究使用.

可惜的是，DSP系统中的内存存取会消耗大量时钟周期，并且也会因此导致了大量功耗.比如在TI TMS320C64x DSP处理器中，向内存中写入信息的基本指令就要消耗掉四个CPU时钟周期.而且频繁的内存存取更是会严重降低CPU的执行效率.因此在DSP上高效的实现矢量基二维DCT还是非常困难.核心问题就是在具体DSP上运行算法时会产生大量因信号输入和权重因子导致的内存存取.进而这不仅会严重降低CPU执行效率，而且也会消耗大量电能.

本文中，我们提出了一个新的减少内存存取的方法来实现矢量基二维DCT.该方法首先利用权重因子的属性将计算流程图内每相邻两阶段内的蝴蝶运算单元进行融合，然后再以较少的权重因子来计算.它是基于之前我们在一维DCT上的研究[21]，并且将其拓展到本文中的二维DCT的问题上.这样研究的目的不仅是因为本文中的矢量基二维DCT比一维DCT有更广的用途，也是为了通过这些研究更进一步验证本文提出的方法的正确性和普适性.这为了更好的检测方法的通用性，本文选取当前通用的DSP作为实验平台，从实验数据得知，本文的方法不仅可以大幅提高CPU的执行效率，显著减少运算中的内存存取，而且可以用更少的内存来保存权重因子.

2 矢量基二维DCT

二维DCT中的离散信号x[m，n](m，n=0，1，2，… ，N-1)可用如下公式来计算[4]：

(1)

本文考虑N是2的整数幂的情况，将公式右边的比例系数一起整合到X[k，l]中，并应用以下输入映射.

(2)

1)可改写成

(3)

(4)

(5)

[2k，2l+1]=

(6)

(7)

然后进一步分解直到一系列(2×2)点输入DCT，便得到了按频率分解的矢量基二维DCT[15].图1给出了(4×4)点输入的矢量基二维DCT运算流程图.

图1 4×4点矢量基二维DCTFig. 1 4×4-pt vector-radix 2D DCT

它由蝴蝶计算和后序操作这两部分构成.蝴蝶计算部分由一系列蝴蝶运算单元组成.它可以进一步划分为若干阶段，每个阶段都包含固定数量的蝴蝶运算单元.例如N×N点矢量基二维DCT图中的蝴蝶计算部分可以被划分为lgN阶段，其中每个阶段都包含N×N/4个蝴蝶运算单元.同一阶段内的蝴蝶运算单元相互之间保持独立，但不同阶段的蝴蝶运算单元之间却存在数据依赖关系.例如阶段1中的所有蝴蝶运算单元都可以独立计算，但必须在阶段2内的蝴蝶运算单元计算前就被计算出来.每个阶段中相互重叠的蝴蝶运算单元可进一步划分成块.例如，阶段1中的蝴蝶运算单元可以分成4块，而阶段2中的蝴蝶运算单元只能分成1块.具体来说，阶段s中所有蝴蝶运算单元可根据权重因子划分为N×N/4s块，而整个蝴蝶计算部分被这样划分出(N2-1)/3块.从图中不难看出，在蝴蝶计算与后序操作这两部分当中，蝴蝶计算部分包含了主要的CPU运算和内存存取.因此本文将内存存取减少方法应用于蝴蝶计算部分.

3 内存存取减少方法

本文提出的内存存取减少方法，将分两步应用于矢量基二维DCT运算.

步骤1.在计算N×N点矢量基二维DCT时，根据权重因子的余弦函数性质(8)，将它的数量由(N2-1)/3减少到「4(N2-1)/15⎤

(8)

步骤2.利用权重因子的属性将计算流程图内每相邻两阶段内的蝴蝶运算单元进行融合.

图2 用4个权重因子计算8个蝴蝶运算单元Fig. 2 Computing 8 butterflies together with four weighting factors

根据这个属性，该方法可将计算流程图内每相邻两阶段内的蝴蝶运算单元进行融合，然后再以较少的权重因子来计算，如图2(b)所示.这样，N×N点矢量基二维DCT的运算流程图的蝴蝶计算部分便可以划分为(lgN)/2个阶段.当lgN是奇数时，虽然所有蝴蝶运算单元可以融合到(lgN-1)/2个阶段内后由新方法来计算，但是仍需用常规方法来计算第lgN阶段(即第奇数阶段)的蝴蝶运算单元.根据该方法，图3重新绘制出原图1中的蝴蝶计算部分.

图3 使用内存存取减少方法后的4×4点矢量基二维DCT 中的蝴蝶计算部分Fig. 3 Butterfly computation of 4×4-pt vector-radix 2D DCT with memory access reduction method applied

该方法可以大幅度减少由权重因子和信号输入产生的内存存取量.假设图1和3中需计算16个二维DCT系数，如图所示，图1的常规矢量基二维DCT 需调用5个权重因子，而图3中则仅需调用4个权重因子.另外，图中黑点表示由信号输入x[]产生的内存存取.两图对比明显：图1的蝴蝶计算部分中，共有64个黑点，而图3的蝴蝶计算部分中，只有32个黑点.

4 实验结果

用常规方法实现N×N点矢量基二维DCT时，由权重因子而产生的内存存取量是(N2-1)/3，这与N×N点矢量基二维DCT的流程图中组的数量相等(组是按照不同权重因子而划分的).本文的方法将它减少到「4(N2-1)/15⎤.

考虑到通用性，本文选用了三款主流DSP为测试平台：德州仪器的TI TMSC320C64x(表中用“DSP1”表示，下同)、模拟器件公司(ADI)的ADSP-TS101 TigerSHARC (DSP2)、以及飞思卡尔的SC3400 StarCore DSP (DSP3).在这些平台上，本文编写了两段C程序来分别进行比对.程序1是用常规的算法实现N×N点矢量基二维DCT，而程序2是运用内存存取减少方法来实现N×N点矢量基二维DCT.两个程序均包含了相同的后续操作部分代码.由于篇幅限制，本文用如下三个表来报告性能对比数据：表1给出运算所需CPU时钟周期数的对比；表2给出由权重因子和信号输入导致的内存存取量的对比；表3给出用于存储权重因子的内存空间的对比.

表1 CPU时钟周期数的对比Table 1 Comparison of the number of CPU clock cycles

表2 内存存取量的对比Table 2 Comparison of the number of memory reference

实验数据说明，运用内存存取减少方法实现的矢量基二维DCT相比于常规方式可以平均减少63.1%的运算所需CPU时钟周期数、平均减少47.4%的由权重因子和信号输入导致的内存存取量、以及平均减少20%的存储权重因子的内存空间.

表3 存储权重因子的内存空间(字节)的的对比Table 3 Comparison of the storage for weighting factors(bytes)

5 结 论

本文提出了实现矢量基二维DCT算法的内存存取减少方法.它首先利用权重因子的属性将计算流程图内每相邻两阶段内的蝴蝶运算单元进行融合，然后再以较少的权重因子来计算.考虑到通用性，本文选用了三款主流DSP为测试平台.这些平台上的测试数据显示：该方法相比于常规算法可以平均减少63.1%的运算所需CPU时钟周期数、平均减少47.4%的内存存取量、以及平均减少20%的内存空间.由于超过一倍的提速以及近半内存存取的减少，使得该方法可以有效节省电能消耗，所以本文的方法对将来二维DCT在手持及移动设备上的应用具有重要的意义.在后续研究中，我们不仅要继续研发进一步减少内存存取、提高速度的优化方案，而且要将该方案应用到其他类型DCT变换上，以使其可以得到更广泛的应用.