基于BWDSP平台的信号处理库函数优化

于海洋 陈冠林 蒋天翔 蒋慧丽 彭昌

（国家计算机网络与信息安全管理中心安徽分中心 安徽省合肥市 230041）

1 引言

信号处理库函数包括数字滤波器、窗函数、变换、倒谱分析、统计信号处理等函数。本文从变换、窗函数这两部分中选取若干函数进行优化。

本文的主要工作如下：

（1）针对变换部分中FFT（快速傅里叶变换）、IFFT（逆快速傅里叶变换）、CZT（线性调频Z变换）这三个函数的串行算法在BWDSP上运行效果不理想的状况，作者参考x86环境下c语言函数使用嵌入汇编的优化方式，在保留测试文件、头文件使用c语言的形式下，嵌入汇编语言库函数或者子函数。根据BWDSP的VLIW（超长指令字）特性，使用指令级并行的方式，将FFT、IFFT、CZT函数并行化，提高了FFT、IFFT、CZT函数的运行效率。实验结果显示，FFT的相对加速比从2.92到3.05；IFFT的相对加速比从2.94到3.08；CZT函数的相对加速比从2.70到2.74。

（2）针对窗函数中巴特利特-汉宁窗、巴特利特窗、切比雪夫窗、高斯窗这四个函数，在结合使用指令级并行及循环展开、减少访存、变量替换等c语言层次的优化方式下，使程序性能提升比例从9.49%到68.75%。

2 BWDSP介绍

BWDSP处理器可广泛地运用于各种高性能计算领域，是一款32位浮点DSP，同时也支持16位和32位定点数据格式（本文中定点均指整数），采用超长指令字架构，具备强大的并行处理能力。BWDSP处理器采用16条指令发射、SIMD（单指令多数据流）架构，共有11级流水线，分别为取指令3级、指令缓冲池3级、译码2级、取操作数1级、执行操作1级和数据写回1级，采用多级取指支持分支预测以减少流水线的性能开销。

3 FFT算法优化介绍

FFT被广泛地应用于信号处理、图形图像、功率谱估计等领域。FFT算法源于研究人员对DFT（离散傅里叶变换）算法运算量的不可容忍性，直接计算DFT可能使得计算机无法承受其运算量。

3.1 FFT串行算法研究现状

一些算法对逆序过程进行优化后，可以使得循环次数减少，如张学智等在快速实现FFT的逆序方法中，从逆序数的生成规律入手，发现逆序数的生成是一个递归的形式。该方法生成过程简单明了，排序速度比标准程序块，但缺点在于在占用内存较多。当点数规模较大时，该方法占用的内存空间也会非常大。考虑到BWDSP缓存较小，不便于采用这种方法。

高丽等在文章FFT标准整序算法的优化中，构思巧妙，将逆序序列分为前后两部分，然后重新排列，由前面的序列可以分别在每个数上加1得到后面的序列。但重排过程要多次交换数据，会多次产生访存，并且不利于在BWDSP上进行更进一步的改善。

方志红等在文章利用逆序循环实现FFT运算中倒序算法的优化中，针对MPC7400硬件提供的128比特浮点矢量[即一次可以取出4个32位浮点数，采用IQIQ（实部虚部实部虚部）的存储方式。这种方法理论上能明显减少循环次数，然而在使用c语言程序进行移植后，实验测试发现其性能并未达到甚至接近理论值。究其原因在于无论BWDSP或glibc均未拥有类似于MPC7400提供的浮点矢量部件及交换部件。

FFT算法另一优化点在于针对蝶形因子的优化。王非非等人给出了一种旋转系数访存优化的FFT算法，该方法根据旋转系数的访存比率统计情况，提出了一种旋转系数访问存储器的优化方法。通过仅存储使用率较高的旋转系数，而对于其他使用率较低的旋转系数则采用泰勒插值计算方法生成。这样做既节省存储空间，又提供处理器缓存的命中率，保持计算精确度。

综上可知，FFT串行算法的优化方向主要集中在三个领域：

（1）针对逆序算法进行优化，减少循环的循环次数。如n点复数FFT，共有2n个点，逆序循环时，按照Cooley-Tukey算法，需要进行n-2次循环。使用某些特定算法后，可以使得逆序循环次数大为减少。

（2）针对计算部分进行优化，这部分需要从流水线的角度合理安排访存操作与计算操作，使得处理器一直处于工作状态。这部分工作主要需要通过汇编指令进行。

（3）针对蝶形因子进行优化，根据该系数的周期性质、可约性质，使得对蝶形因子的计算减少。

3.2 FFT并行算法研究现状

张燕燕等利用OpenMp（用于共享内存并行系统的多线程程序设计的编译方法），将串行FFT修改后，实现了FFT的并行算法。

王刚强等根据多核体系结构机器拥有多级存储结构及支持线程级并行程序的特点，将数据划分为满足二级高速缓存大小的子序列。再将各个子序列进行二次划分，分批进入一级高速缓存中，然后开始子序列的计算。

Amir A 等人提出了一个可以执行于任意个处理器核数的机器上的并行FFT算法，该算法对一维的傅里叶变换实验结果接近线性加速。该算法的特点是实现在共享内存MIMD机器上。

汪清等围绕FFT如何在多核架构上高效并行实现这一问题，对并行FFT算法优化改进并在SCC、龙芯等多核架构上高效并行实现。

刘红侠等人分析基-2 FFT数据流，得出每次蝶形计算的操作数其结果按照原读取地址返回，并且由于蝶形因子地址相同，可以使用一个地址产生器。实现了两条流水线并行所需的操作数级旋转系数的并行访问，并且减少了蝶形因子的计算次数。

胡灏等人利用多线程特点，针对多处理器机器，创建与处理器数目相同的线程，使得每个线程负载均衡，平均分配计算工作，提高了FFT程序的运行效率。缺点是机器需要支持多线程技术。

综上可知，国内外针对FFT算法的并行化工作主要有三个方向：

（1）针对多核处理器，根据其硬件特性为FFT算法提供较高的进入缓存的可能，避免因访存操作造成长时间的处理器等待情况。

（2）针对支持多线程等技术的机器，使较多的线程均衡地分配任务，同时计算，达到并行效果。

（3）针对FFT算法自身并行性，如蝶形因子的计算、输入序列的存取操作，找到其并行操作后，使得算法本身能够以流水线的方式执行。

以上是关于FFT并行化的部分国内外研究成果，这些并行方法分别从不同角度对FFT的运行效率进行改善，对于面向BWDSP的FFT等算法并行化有着重要的参考意义。但由于BWDSP处理器的自身架构特性、寄存器使用及所支持的编程环境自成一格，因此以上方法不适合运用于BWDSP上。这就需要针对BWDSP本身硬件特点，结合FFT的内在并行性，进行并行化程度较高的优化。

4 FFT等函数的指令级并行优化

4.1 并行化安排汇编指令

作为一款拥有超长指令字特性的DSP处理器，BWDSP为程序的指令级并行提供了可能。研究发现串行FFT算法、IFFT算法、CZT算法具备良好的串行特性及函数调用关系。针对这三个函数，在不造成数据相关的前提下，通过合理地布局不同的指令，进行并行优化处理。

作为一种专用的类c汇编，BWDSP不支持x86情况下的嵌入式汇编。它支持如下两种情况：

第一种情况：

第一种情况是主函数由c语言编写，子函数则由BWDSP汇编语言编写。第二种情况是主函数由汇编代码编写，子函数则由c语言编写。

由于线性调频z变换函数多次调用基-2 DIT-FFT，基-2 DIT-IFFT程序，可以断定这两个程序是本函数的热点函数，将FFT、IFFT两个函数改写为BWDSP汇编程序这种枯燥易错工作显得十分必要。考虑到单纯的汇编代码显然会有性能上的提升，加之BWDSP的VLIW特点，可以利用这一特性，实现指令级别的FFT并行。

这段代码较少使用VLIW方式布局代码，是为了示意，以免因不了解该汇编语言语法而造成困惑。使用VLIW方式安排代码后，会显得混乱，更加不易于理解代码。BWDSP共有4个核，每个核上面有15个部件，其中包括8个算术逻辑运算部件，4个乘法部件，2个移位部件，1个超算部件。这种在不造成数据相关情况下的并行排放方式，可以使得每一行尽量安排较多的指令，机器一次能够执行多条代码，极大程度上发挥BWDSP的并行性能。

VLIW布局代码：

xr10 = 1 || xfr11 =0.5 || xr39 = [u9 +-27,0]

代码采用了VLIW方式布局代码，以第一行代码为例，对x核上十号、十一号寄存器分别赋值整数、浮点数据，将存储器中地址寄存器u9-27指向的数据取出来并赋给第三十九号寄存器。这一行代码包括三条指令，其中有两个赋立即数指令、一个访存指令，由于每个核上均有两个位宽为64比特的读总线及一个位宽为64比特的写总线，它们互相之间并不干扰。

4.2 实验结果对比

4.2.1 FFT指令级并行化实验

按照超长指令字思想布局代码，对基-2 DIT-FFT 及基-2 DIT-IFFT串行程序进行汇编代码改写并进行指令级别并行化处理。针对FFT程序，取八组数据进行对比。

基-2 FFT串行程序被修改为BWDSP汇编级指令并行化后性能得到了极大程度上的提升，n等于8192点时间上节省了81739000 ns，n等于4096点时间节省了37854900 ns，...，n等于64点时间节省了313282 ns。本例中所选择各个采样点的节省时间均有较好的表现。所选择的八个样点的相对加速比也比较理想，平均加速比接近3倍。

当FFT取样点数小于1024时，时间性能虽然有提升，但是由于样点本身数量较少使得运算量较低。当样点数大于1024点时，时间上的差距开始拉开。当取8192个样点时，时间差达到了一个较大的值。不难得出结论，随着取样点数的增加，指令级并行FFT算法的优势会愈来愈凸显出来。

4.2.2 IFFT指令级并行化实验

基-2逆FFT的算法处理过程类似于基-2 FFT算法，不同之处是需要对输入序列进行除法操作。可以看出两者区别不大，最终的运算量也是相当的，其结果数据也近似。取样点小于1024点时，优化效果不是十分的明显；当取样点数大于1024时，优化后的并行程序优势十分明显。

4.2.3 CZT指令级并行化实验

线性调频z变换函数调用了基-2 FFT、基-2 IFFT、向量乘法等函数，采用主干代码使用c语言编写，这样做有利于阅读与理解，使得用户迅速熟悉该函数。将该函数调用的基-2 FFT、基-2 IFFT、向量乘法这三个函数进行汇编代码改写。线性调频z变换的优化效果十分明显，以2000点取样结果为例，节省时间118574868纳秒，相对加速比例为2.721320。取六组数据，其平均加速比大于2.70，可以认为该程序得到了较为不错的性能提升。

5 窗函数的优化

针对BWDSP信号处理库中的巴特利特-汉宁窗、巴特利特窗、切比雪夫窗、高斯窗进行优化。以使用常规的优化方法为主，以使用汇编语言的方式为辅。实验结果表明，窗函数的性能提升从9.49%到68.75%。

5.1 常规优化手段介绍

常规优化手段主要包括：循环展开、矩阵分块、减少访存、指令替换、数据预取等操作。

其他优化方法如从循环中提取固定的代码；用后置条件的循环替代前置条件的循环；用自加自减替换加一减一；将多重循环中循环次数较多的循环体放置在最内层以减少处理器跨切循环层的次数；将逻辑表达式中为真概率高的子表达式放置在最前方、将逻辑与表达式中为假概率高的子表达式放置在最后面等。

5.1.1 巴特利特-汉宁窗优化

巴特利特-汉宁窗，是信号处理领域中常用的基本窗函数，也称为广义余弦窗。在主要程序循环体外声明一个浮点型临时变量temp，赋值为1/(n-1)。然后将循环体中的除以n-1修改为乘以temp。将函数调用fabs修改为增加一个判断语句，若变量ftmp小于零，则将其赋值为正即可。其性能对比如图1所示。

图1：Barthannwin性能优化对比

5.1.2 巴特利特窗优化

在主要程序循环体前添加变量声明并赋值n-1的倒数。然后在循环体中替换除以n-1的操作。

其性能提升如图2所示。

图2：巴特利特窗性能优化对比

5.1.3 切比雪夫窗优化

切比雪夫窗主要占用时间的地方有三处循环体。考虑到第二个主要循环操作并没有调用子函数，且内部表达式较多，不利于汇编实现，选择第一、第三两个循环体进行实现。将第二、第三个循环体整合为一个汇编接口程序。使用第三部分中介绍的指令并行技术。优化前后切比雪夫窗的性能对比如图3。

图3：chebwin优化前后性能对比

5.1.4 高斯窗优化

在函数主要循环体前声明变量以替换循环体中的除法，然后将对pow函数修改为对exp函数的调用。

其性能对比如图4所示。

图4：高斯窗性能优化对比

6 总结

（1）对FFT、IFFT、CZT函数进行指令级并行化、对FFT、IFFT使用循环展开及减少访存再次优化。FFT函数的指令级并行化结果与串行结果对比显示各个采样点相对加速比从2.92到3.05；IFFT函数指令级并行化结果与串行结果对比显示各个采样点相对加速比从2.94到3.08；CZT函数的指令级并行化结果与串行结果对比相对加速比从2.70到2.74。

（2）对窗函数部分中的巴特利特-汉宁窗、巴特利特窗、切比雪夫窗、高斯窗这四个函数进行优化。在以使用c语言层次的优化为主，以使用嵌入汇编为辅的方式下，性能提升比例从9.49%到68.75%。

本文的工作主要基于BWDSP信号处理库中的变换、窗函数的性能优化，所使用的优化方法主要在指令并行级别及编程语言使用技巧上，未曾涉及到算法层次的优化。