魂芯DSP上滤波算法的高效实现

王向前　马宏星

摘要： 滤波算法是数字信号处理、图形图像处理领域的一个重要算法。分析了滤波算法的并行性，结合魂芯DSP的体系结构特征，提出对滤波算法的优化方法。实验表明，滤波算法蕴含的并行性在魂芯平台得到了充分的发挥。

关键词： 滤波；FIR；魂芯DSP；并行性

中图分类号：TP314 文献标识码：A 文章编号：1009-3044（2014）14-3421-04

Abstract：Filtering algorithm is an important algorithm for digital signal processing， graphics and video processing. The parallelism of filtering algorithm is analyzed， architecture features of BWDSP is combined with and an optimization method for filtering algorithm is proposed. Experiment result shows that inherent parallelism in the filtering algorithm has been fully exploited on BWDSP hardware platform.

Key words：filtering；FIR；BWDSP；parallelism

在数字信号处理领域，自适应信号处理占有重要地位。其中一个重要类型的自适应滤波器[1，2]是自适应有限滤波器（FIR），它可以近似描述一个未知的零极点系统模型。

本文分析了自适应滤波器算法的并行性，提出了针对魂芯DSP平台的优化方法。

接下来的文章安排如下。第2节简要介绍魂芯DSP的体系结构特征；第3节结合魂芯DSP的体系结构特征分析自适应有限滤波器的并行性，提出优化方法，并给出优化结果。第4节是结论。

1 魂芯DSP介绍

魂芯DSP是一款中国电科38所自主设计、分簇结构、支持SIMD的16发射的VLIW结构的浮点运算信号处理器，主要结构如图1。它采用7级流水线，有4个计算簇， 分别是X簇、Y 簇、Z 簇、T 簇， 每个计算簇上有8个加法器， 2个乘法器。计算簇与计算簇之间通过簇间传输总线通信。有3个地址簇即地址生成器，分别是U 簇， V 簇， W 簇，分别有16个地址寄存器。每个计算核上有64个通用寄存器，计算核与计算核之间通过核间传输总线通信。每个计算核可同时向其他3个计算核输出64bit数据。片内有3块数据存储器，每块8M bit。存储器和运算部件之间有两条读总线和一条写总线，每条总线256bit， U、V、W三个AGU保证了存储器和运算部件之间全速的数据交换。

2 滤波算法在魂芯DSP的实现

自适应有限滤波器（FIR） [3，4，5]计算公式为：

R（n）=[i=0nr-1HiX（n-i）]

其中nr为滤波器的阶数，[Hi]为滤波器的系数，X（n）为输入数据。

用C语言实现该算法如图2所示，其中参数意义为：x为待滤波的实数输入样本序列；h为滤波器系数；r为滤波输出序列；nh为滤波器系数的个数；nr 为输入样本的个数。

外层循环次数为nr，内层循环次数为nh，正常情况下，nr远比nh大，时间复杂度为O（nr*nh）。同时对x数组访存操作总次数为nr*nh次，对h数组访存总次数也为nr*nh。

考虑到魂芯DSP是多发射的、分簇的、具有大量的运算单元；并且每簇的大寄存文件特征，具有64个寄存器；还支持高通量的数据并行，即支持同时16个字的内存读取操作和8个字的内存写操作，置换内外层循环，特设计优化[6，7，8]算法，如图3所示。

由图2的C算法可知，每次计算滤波输出序列r的每个值时，都需要读取滤波系数数组h，h数组一般是一个比x数组小得多的数组。考虑到该数组数据的共有性和魂芯DSP的大寄存器文件特征，可以把h数组平均划分成[h1]，[h2]，…，[hn]，分别与样本输入序列进行滤波，把每次滤波的结果对齐之后累加，也可得到正确的滤波结果。

优化算法步骤主要如下。

步骤一：设置外层循环次数，对访存操作基地址进行初始化操作。

步骤二：外层循环迭代。从滤波系数数组h用向量化访存指令读取80个滤波系数，置于每个簇中寄存器的0至19号寄存器（此处用每个簇的0至19号寄存器共计80个寄存器来保存每次迭代的滤波系数）；与此同时从样本输入序列用向量化访存指令连续读取80个数据，置于每个簇的20至39号寄存器（此处用每个簇的20至39号寄存器总计80个寄存器保存可以和每个簇的0至19号寄存器存储的滤波系数对应计算的输入样本数据；设置内层循环次数。

步骤三：计算对应滤波输出序列8个分量的值，并输出到滤波输出序列对应的位置。主要是使用滤波系数和对应的输入样本数据的乘累加操作；计算第2至第8个滤波输出序列分量之前，需要进行对齐操作。对齐操作如图4所示。

对齐操作是每次乘累加运算之后按照图4中的箭头进行的数据复制操作。显然xr20，xr21，yr20，yr21，zr20，zr21，tr20，tr21，……，xr38，xr39，yr38，yr39，zr38，zr39，tr38，tr39，这八十个数据在每次堆对齐操作时，依次从xr60，xr61，yr60，yr61，zr60，zr61，tr60，tr61获得每次对齐操作的右端更新。

该算法的时间复杂度为O（（nh/80）* 10*（nr/8）），即为O（（nh/8）*（nr/8））。可见优化方法充分利用了魂芯DSP的高通量的访存并行性、每个簇的64个寄存器以及多发射等多种并行特性。表1是不同的输入参数的条件下的该优化滤波算法fir的优化性能。可见在该优化方法下，FIR在几个输入条件下的实际运行周期数与理论性能基本在一个量级上，说明该优化方法是有效的。

3 结论

基于提供高并行性的魂芯DSP，针对有限滤波算法FIR，挖掘其并行化，提出优化方法。并给出了该优化方法的原理、步骤以及在魂芯DSP平台的测试结果。并与其理论性能对比，说明优化算法的有效性。

参考文献：

[1] 邹艳碧，高鹰.自适应滤波算法综述[J]. 广州大学学报：自然科学版，2002，1（2）：44-50.

[2] 郑存生， 潘维瀚. FIR 数字滤波器的分步量化设计法[J].北京航空航天大学学报，1983（4）：5.

[3] 张田仓，罗锐.FIR 数字滤波优化设计及在信号处理中的应用[J].导航，2004，40（2）：83-88.

[4] 叶华，吴伯修.变步长自适应滤波算法的研究[J].电子学报，1990，18（4）：63-69.

[5] 王芳，冯新喜，李鸿艳.一种新的自适应滤波算法[J].现代雷达，2003，25（7）：33-35.

[6] 胡辉，叶鑫华.离散 Walsh 变换并行性分析与实现[J].计算机工程与应用， 2009，45（2）：82-84.

[7] 奚杰，陈杰，刘建，等. H. 264 在多核平台上的并行性分析[J].哈尔滨工程大学学报，2010，31（6）：736-742.

[8] 高念书.循环交换与递归消除[J].计算机研究与发展，1991（2）：5.endprint

摘要： 滤波算法是数字信号处理、图形图像处理领域的一个重要算法。分析了滤波算法的并行性，结合魂芯DSP的体系结构特征，提出对滤波算法的优化方法。实验表明，滤波算法蕴含的并行性在魂芯平台得到了充分的发挥。

关键词： 滤波；FIR；魂芯DSP；并行性

中图分类号：TP314 文献标识码：A 文章编号：1009-3044（2014）14-3421-04

Abstract：Filtering algorithm is an important algorithm for digital signal processing， graphics and video processing. The parallelism of filtering algorithm is analyzed， architecture features of BWDSP is combined with and an optimization method for filtering algorithm is proposed. Experiment result shows that inherent parallelism in the filtering algorithm has been fully exploited on BWDSP hardware platform.

Key words：filtering；FIR；BWDSP；parallelism

在数字信号处理领域，自适应信号处理占有重要地位。其中一个重要类型的自适应滤波器[1，2]是自适应有限滤波器（FIR），它可以近似描述一个未知的零极点系统模型。

本文分析了自适应滤波器算法的并行性，提出了针对魂芯DSP平台的优化方法。

接下来的文章安排如下。第2节简要介绍魂芯DSP的体系结构特征；第3节结合魂芯DSP的体系结构特征分析自适应有限滤波器的并行性，提出优化方法，并给出优化结果。第4节是结论。

1 魂芯DSP介绍

魂芯DSP是一款中国电科38所自主设计、分簇结构、支持SIMD的16发射的VLIW结构的浮点运算信号处理器，主要结构如图1。它采用7级流水线，有4个计算簇， 分别是X簇、Y 簇、Z 簇、T 簇， 每个计算簇上有8个加法器， 2个乘法器。计算簇与计算簇之间通过簇间传输总线通信。有3个地址簇即地址生成器，分别是U 簇， V 簇， W 簇，分别有16个地址寄存器。每个计算核上有64个通用寄存器，计算核与计算核之间通过核间传输总线通信。每个计算核可同时向其他3个计算核输出64bit数据。片内有3块数据存储器，每块8M bit。存储器和运算部件之间有两条读总线和一条写总线，每条总线256bit， U、V、W三个AGU保证了存储器和运算部件之间全速的数据交换。

2 滤波算法在魂芯DSP的实现

自适应有限滤波器（FIR） [3，4，5]计算公式为：

R（n）=[i=0nr-1HiX（n-i）]

其中nr为滤波器的阶数，[Hi]为滤波器的系数，X（n）为输入数据。

用C语言实现该算法如图2所示，其中参数意义为：x为待滤波的实数输入样本序列；h为滤波器系数；r为滤波输出序列；nh为滤波器系数的个数；nr 为输入样本的个数。

外层循环次数为nr，内层循环次数为nh，正常情况下，nr远比nh大，时间复杂度为O（nr*nh）。同时对x数组访存操作总次数为nr*nh次，对h数组访存总次数也为nr*nh。

考虑到魂芯DSP是多发射的、分簇的、具有大量的运算单元；并且每簇的大寄存文件特征，具有64个寄存器；还支持高通量的数据并行，即支持同时16个字的内存读取操作和8个字的内存写操作，置换内外层循环，特设计优化[6，7，8]算法，如图3所示。

由图2的C算法可知，每次计算滤波输出序列r的每个值时，都需要读取滤波系数数组h，h数组一般是一个比x数组小得多的数组。考虑到该数组数据的共有性和魂芯DSP的大寄存器文件特征，可以把h数组平均划分成[h1]，[h2]，…，[hn]，分别与样本输入序列进行滤波，把每次滤波的结果对齐之后累加，也可得到正确的滤波结果。

优化算法步骤主要如下。

步骤一：设置外层循环次数，对访存操作基地址进行初始化操作。

步骤二：外层循环迭代。从滤波系数数组h用向量化访存指令读取80个滤波系数，置于每个簇中寄存器的0至19号寄存器（此处用每个簇的0至19号寄存器共计80个寄存器来保存每次迭代的滤波系数）；与此同时从样本输入序列用向量化访存指令连续读取80个数据，置于每个簇的20至39号寄存器（此处用每个簇的20至39号寄存器总计80个寄存器保存可以和每个簇的0至19号寄存器存储的滤波系数对应计算的输入样本数据；设置内层循环次数。

步骤三：计算对应滤波输出序列8个分量的值，并输出到滤波输出序列对应的位置。主要是使用滤波系数和对应的输入样本数据的乘累加操作；计算第2至第8个滤波输出序列分量之前，需要进行对齐操作。对齐操作如图4所示。

对齐操作是每次乘累加运算之后按照图4中的箭头进行的数据复制操作。显然xr20，xr21，yr20，yr21，zr20，zr21，tr20，tr21，……，xr38，xr39，yr38，yr39，zr38，zr39，tr38，tr39，这八十个数据在每次堆对齐操作时，依次从xr60，xr61，yr60，yr61，zr60，zr61，tr60，tr61获得每次对齐操作的右端更新。

该算法的时间复杂度为O（（nh/80）* 10*（nr/8）），即为O（（nh/8）*（nr/8））。可见优化方法充分利用了魂芯DSP的高通量的访存并行性、每个簇的64个寄存器以及多发射等多种并行特性。表1是不同的输入参数的条件下的该优化滤波算法fir的优化性能。可见在该优化方法下，FIR在几个输入条件下的实际运行周期数与理论性能基本在一个量级上，说明该优化方法是有效的。

3 结论

基于提供高并行性的魂芯DSP，针对有限滤波算法FIR，挖掘其并行化，提出优化方法。并给出了该优化方法的原理、步骤以及在魂芯DSP平台的测试结果。并与其理论性能对比，说明优化算法的有效性。

参考文献：

[1] 邹艳碧，高鹰.自适应滤波算法综述[J]. 广州大学学报：自然科学版，2002，1（2）：44-50.

[2] 郑存生， 潘维瀚. FIR 数字滤波器的分步量化设计法[J].北京航空航天大学学报，1983（4）：5.

[3] 张田仓，罗锐.FIR 数字滤波优化设计及在信号处理中的应用[J].导航，2004，40（2）：83-88.

[4] 叶华，吴伯修.变步长自适应滤波算法的研究[J].电子学报，1990，18（4）：63-69.

[5] 王芳，冯新喜，李鸿艳.一种新的自适应滤波算法[J].现代雷达，2003，25（7）：33-35.

[6] 胡辉，叶鑫华.离散 Walsh 变换并行性分析与实现[J].计算机工程与应用， 2009，45（2）：82-84.

[7] 奚杰，陈杰，刘建，等. H. 264 在多核平台上的并行性分析[J].哈尔滨工程大学学报，2010，31（6）：736-742.

[8] 高念书.循环交换与递归消除[J].计算机研究与发展，1991（2）：5.endprint

摘要： 滤波算法是数字信号处理、图形图像处理领域的一个重要算法。分析了滤波算法的并行性，结合魂芯DSP的体系结构特征，提出对滤波算法的优化方法。实验表明，滤波算法蕴含的并行性在魂芯平台得到了充分的发挥。

关键词： 滤波；FIR；魂芯DSP；并行性

中图分类号：TP314 文献标识码：A 文章编号：1009-3044（2014）14-3421-04

Abstract：Filtering algorithm is an important algorithm for digital signal processing， graphics and video processing. The parallelism of filtering algorithm is analyzed， architecture features of BWDSP is combined with and an optimization method for filtering algorithm is proposed. Experiment result shows that inherent parallelism in the filtering algorithm has been fully exploited on BWDSP hardware platform.

Key words：filtering；FIR；BWDSP；parallelism

在数字信号处理领域，自适应信号处理占有重要地位。其中一个重要类型的自适应滤波器[1，2]是自适应有限滤波器（FIR），它可以近似描述一个未知的零极点系统模型。

本文分析了自适应滤波器算法的并行性，提出了针对魂芯DSP平台的优化方法。

接下来的文章安排如下。第2节简要介绍魂芯DSP的体系结构特征；第3节结合魂芯DSP的体系结构特征分析自适应有限滤波器的并行性，提出优化方法，并给出优化结果。第4节是结论。

1 魂芯DSP介绍

魂芯DSP是一款中国电科38所自主设计、分簇结构、支持SIMD的16发射的VLIW结构的浮点运算信号处理器，主要结构如图1。它采用7级流水线，有4个计算簇， 分别是X簇、Y 簇、Z 簇、T 簇， 每个计算簇上有8个加法器， 2个乘法器。计算簇与计算簇之间通过簇间传输总线通信。有3个地址簇即地址生成器，分别是U 簇， V 簇， W 簇，分别有16个地址寄存器。每个计算核上有64个通用寄存器，计算核与计算核之间通过核间传输总线通信。每个计算核可同时向其他3个计算核输出64bit数据。片内有3块数据存储器，每块8M bit。存储器和运算部件之间有两条读总线和一条写总线，每条总线256bit， U、V、W三个AGU保证了存储器和运算部件之间全速的数据交换。

2 滤波算法在魂芯DSP的实现

自适应有限滤波器（FIR） [3，4，5]计算公式为：

R（n）=[i=0nr-1HiX（n-i）]

其中nr为滤波器的阶数，[Hi]为滤波器的系数，X（n）为输入数据。

用C语言实现该算法如图2所示，其中参数意义为：x为待滤波的实数输入样本序列；h为滤波器系数；r为滤波输出序列；nh为滤波器系数的个数；nr 为输入样本的个数。

外层循环次数为nr，内层循环次数为nh，正常情况下，nr远比nh大，时间复杂度为O（nr*nh）。同时对x数组访存操作总次数为nr*nh次，对h数组访存总次数也为nr*nh。

考虑到魂芯DSP是多发射的、分簇的、具有大量的运算单元；并且每簇的大寄存文件特征，具有64个寄存器；还支持高通量的数据并行，即支持同时16个字的内存读取操作和8个字的内存写操作，置换内外层循环，特设计优化[6，7，8]算法，如图3所示。

由图2的C算法可知，每次计算滤波输出序列r的每个值时，都需要读取滤波系数数组h，h数组一般是一个比x数组小得多的数组。考虑到该数组数据的共有性和魂芯DSP的大寄存器文件特征，可以把h数组平均划分成[h1]，[h2]，…，[hn]，分别与样本输入序列进行滤波，把每次滤波的结果对齐之后累加，也可得到正确的滤波结果。

优化算法步骤主要如下。

步骤一：设置外层循环次数，对访存操作基地址进行初始化操作。

步骤二：外层循环迭代。从滤波系数数组h用向量化访存指令读取80个滤波系数，置于每个簇中寄存器的0至19号寄存器（此处用每个簇的0至19号寄存器共计80个寄存器来保存每次迭代的滤波系数）；与此同时从样本输入序列用向量化访存指令连续读取80个数据，置于每个簇的20至39号寄存器（此处用每个簇的20至39号寄存器总计80个寄存器保存可以和每个簇的0至19号寄存器存储的滤波系数对应计算的输入样本数据；设置内层循环次数。

步骤三：计算对应滤波输出序列8个分量的值，并输出到滤波输出序列对应的位置。主要是使用滤波系数和对应的输入样本数据的乘累加操作；计算第2至第8个滤波输出序列分量之前，需要进行对齐操作。对齐操作如图4所示。

对齐操作是每次乘累加运算之后按照图4中的箭头进行的数据复制操作。显然xr20，xr21，yr20，yr21，zr20，zr21，tr20，tr21，……，xr38，xr39，yr38，yr39，zr38，zr39，tr38，tr39，这八十个数据在每次堆对齐操作时，依次从xr60，xr61，yr60，yr61，zr60，zr61，tr60，tr61获得每次对齐操作的右端更新。

该算法的时间复杂度为O（（nh/80）* 10*（nr/8）），即为O（（nh/8）*（nr/8））。可见优化方法充分利用了魂芯DSP的高通量的访存并行性、每个簇的64个寄存器以及多发射等多种并行特性。表1是不同的输入参数的条件下的该优化滤波算法fir的优化性能。可见在该优化方法下，FIR在几个输入条件下的实际运行周期数与理论性能基本在一个量级上，说明该优化方法是有效的。

3 结论

基于提供高并行性的魂芯DSP，针对有限滤波算法FIR，挖掘其并行化，提出优化方法。并给出了该优化方法的原理、步骤以及在魂芯DSP平台的测试结果。并与其理论性能对比，说明优化算法的有效性。

参考文献：

[1] 邹艳碧，高鹰.自适应滤波算法综述[J]. 广州大学学报：自然科学版，2002，1（2）：44-50.

[2] 郑存生， 潘维瀚. FIR 数字滤波器的分步量化设计法[J].北京航空航天大学学报，1983（4）：5.

[3] 张田仓，罗锐.FIR 数字滤波优化设计及在信号处理中的应用[J].导航，2004，40（2）：83-88.

[4] 叶华，吴伯修.变步长自适应滤波算法的研究[J].电子学报，1990，18（4）：63-69.

[5] 王芳，冯新喜，李鸿艳.一种新的自适应滤波算法[J].现代雷达，2003，25（7）：33-35.

[6] 胡辉，叶鑫华.离散 Walsh 变换并行性分析与实现[J].计算机工程与应用， 2009，45（2）：82-84.

[7] 奚杰，陈杰，刘建，等. H. 264 在多核平台上的并行性分析[J].哈尔滨工程大学学报，2010，31（6）：736-742.

[8] 高念书.循环交换与递归消除[J].计算机研究与发展，1991（2）：5.endprint