本发明涉及一种对称FIR算法的并行化二维分割方法，包括设定对称FIR算法的参数：源向量点数，滤波系数长度；2）采用支持四路并行运算的乘法器、加法器通过对称FIR算法处理源数据；3）根据源数据长度，采用不同的算法完成DMA搬运阶段。有益效果为：解决了DMA搬运阶段基于并行化设计的数据细粒度分割、数据存放问题，以及向量长度过大而内存容量受限，需要作多次DMA搬入、处理、搬出，由此带来的源数据粗粒度分割问题。
1.一种对称FIR算法的并行化二维分割方法，其特征在于包括
1)对称FIR算法的参数设定为源向量点数：fir_number，滤波系数长度：fir_order；
2)采用支持四路并行运算的乘法器、加法器通过对称FIR算法处理源数据；
3)若源数据长度较小，以至于现有的内存容量可以支持一次性完成所有处理时，按照基于结果数量的平均划分或者基于运算量的平均划分，转入步骤4)；若给定参数fir_number较大，以致源数据无法一次性导入内存，将源数据进行分割，转入步骤5)；
4)在DMA搬运阶段，依次把每一部分的数据写入到指定的bank中，把第一部分的源数写入之前，需要预先写入fir_order-1个零，紧接着导入源数据，在最后一路源数据写入之后，需写入fir_order-1个零至相应bank，最终形成(fir_numer+fir_order-1)个结果；
5)设定bank的容量为8K，以30K为临界区间，当点数在30(n-1)K～30nK之间时，共需n次DMA数据搬运操作，且第n次搬运得到fir_number+fir_order-1-30(n-1)K个结果，其中n为任意正整数。
2.根据权利要求1所述的对称FIR算法的并行化二维分割方法，其特征在于所述乘法器采用4个单精度浮点复数乘法器，16个单精度浮点加法器。
3.根据权利要求1所述的对称FIR算法的并行化二维分割方法，其特征在于所述步骤4)中第一路到第四路实际运算得到的结果数量分别对应的RTL代码分别为(fir_numer+fir_order-1)>>2，((fir_numer+fir_order-1)>>1)–((fir_numer+fir_order-1)>>2)，(fir_numer+fir_order-1)>>2以及(fir_numer+fir_order-1)-((fir_numer+fir_order-1)>>
1)-((fir_numer+fir_order-1)>>2)。
4.根据权利要求1所述的对称FIR算法的并行化二维分割方法，其特征在于所述步骤4)与步骤5)中的DMA数据搬运操作中通过采用乒乓操作存取源数据及结果数据，源数据及结果数据的存取仅使用了总内存容量的一半。
5.根据权利要求1-4所述的对称FIR算法的并行化二维分割方法提供一种硬件结构，其特征在于包括两路数据存储单元与四路乘累加器，所述两路数据存储单元分别与所述乘累加器通信连接，所述每路存储单元分别包括源操作数存储模块与结果存储模块，所述源操作数存储模块包括八个地址连续的源操作数存储块与一个系数存储块；所述结果存储模块包括四个地址连续的结果数存储块。
6.根据权利要求5所述的硬件结构，其特征在于，每个存储块的深度为8kb。
7.根据权利要求5所述的硬件结构，其特征在于所述乘累加器包括一级乘法器、第一级加法器输入选择单元、第一级加法器、第一级加法器结果寄存单元、第二级加法器输入选择单元、第二加法器以及第二级加法器结果寄存单元，所述一级乘法器、第一级加法器输入选择单元、第一级加法器、第一级加法器结果寄存单元、第二级加法器输入选择单元、第二加法器以及第二级加法器结果寄存单元依次通信连接。
8.根据权利要求7所述的硬件结构，其特征在于所述第一级加法器输入选择单元为第一多路选择器，所述第二级加法器输入选择单元由第二多路选择器与第三多路选择器并接组成，所述第一级加法器结果寄存单元由第一寄存区间与第二寄存区间串接组成，每个寄存区间又由两个寄存器串接组成，所述第二级加法器结果寄存单元为一个寄存器，所述两个寄存区间的输入端、输出端分别连接所述第三多路选择器，所述第一多路选择器的一输入端与第一寄存区间的输入端连接，所述第三多路选择器的的一输入端与第二级加法器结果寄存单元连接。
9.根据权利要求7所述的硬件结构，其特征在于所述乘累加器设有三个输入端分别为第一源操作数输入端、第二源操作数输入端以及系数输入端，所述乘累加器分别通过第一源操作数输入端、第二源操作数输入端与源操作数存储块通信连接，通过所述系数输入端与系数存储块通信连接。
一种对称FIR算法的并行化二维分割方法及其硬件结构
技术领域
[0001] 本发明涉及基于固定资源的硬件系统的对称FIR算法及其硬件实现，尤其涉及一种对称FIR算法的并行化二维分割方法及其硬件架构。
背景技术
[0002] 数字信号处理技术广泛应用于多媒体、数据通信、雷达成像、地质探测、航空航天等工程技术领域，近年来又成为人工智能、模式识别、神经网络等新兴学科的理论基础之一，涉及范围非常广泛。而随着半导体工艺技术的不断提升，为大批量数据的实时处理提供了可能。
[0003] 对称系数FIR滤波器，最为重要的数字信号处理方法，常用于相位失真要求较高的场合。例如希尔伯特变化器，高保真音响系统。基于不同的应用需求以及侧重点，对称FIR算法有不同的设计架构。设计方法上有基本的串、并行乘累加器，同时也可采用傅里叶重建技术，麦克米兰方法等。
发明内容
[0004] 本发明目的在于克服以上现有技术之不足，提供一种对称FIR算法的并行化二维分割方法，具体有以下技术方案实现：
[0005] 所述对称FIR算法的并行化二维分割方法，包括
[0006] 1）对称FIR算法的参数设定为源向量点数：fir_number，滤波系数长度：fir_order；
[0007] 2）采用支持四路并行运算的乘法器、加法器通过对称FIR算法处理源数据；
[0008] 3）若源数据长度较小，以至于现有的内存容量可以支持一次性完成所有处理时，按照基于结果数量的平均划分或者基于运算量的平均划分，转入步骤4）；若当需要处理的源数据是个很大的向量，即给定参数fir_number较大，以致源数据无法一次性导入内存，将源数据进行分割，转入步骤5）；
[0009] 4）在DMA搬运阶段，依次把每一部分的数据写入到指定的bank中，把第一部分的源数写入之前，需要预先写入fir_order-1个零，紧接着导入源数据，在最后一路源数据写入之后，需写入fir_order-1个零至相应bank，最终形成(fir_numer+fir_order-1)个结果；
[0010] 5）设定bank的容量为8K，以30K为临界区间，当点数在30（n-1）K 30nK之间时，共需~n次DMA数据搬运操作，得到fir_number+ fir_order -1-30（n-1）K个结果，其中n为任意正整数。
[0011] 所述对称FIR算法的并行化二维分割方法的进一步设计在于，所述乘法器采用4个单精度浮点复数乘法器，16个单精度浮点加法器。
[0012] 所述对称FIR算法的并行化二维分割方法的进一步设计在于，所述步骤4）中第一路到第四路实际运算得到的结果数量分别对应的RTL代码分别为(fir_numer+fir_order-1)>>2，((fir_numer+fir_order-1)>>1) – ((fir_numer+fir_order-1)>>2)，(fir_numer+fir_order-1)>>2以及(fir_numer+fir_order-1) - ((fir_numer+fir_order-1)>>1) -[0013] ((fir_numer+fir_order-1)>>2)。
[0014] 所述对称FIR算法的并行化二维分割方法的进一步设计在于，所述步骤4）与步骤5）中的DMA数据搬运操作中通过采用乒乓操作存取源数据及结果数据，源数据及结果数据的存取仅使用了总内存容量的一半。
[0015] 如上述对称FIR算法的并行化二维分割方法提供一种硬件结构，包括两路数据存储单元与四路乘累加器，所述两路数据存储单元分别与所述累加器通信连接，所述每路存储单元分别包括源操作数存储模块与结果存储模块，所述源操作数存储模块包括八个地址连续的源操作数存储块与一个系数存储块；所述结果存储模块包括四个地址连续的结果数存储块。
[0016] 所述的硬件结构的进一步设计在于，每个存储块的深度为8kb。
[0017] 所述的硬件结构的进一步设计在于，所述乘累加器包括一级乘法器、第一级加法器输入选择单元、第一级加法器、第一级加法器结果寄存单元、第二级加法器输入选择单元、第二加法器以及第二级加法器结果寄存单元，所述一级乘法器、第一级加法器输入选择单元、第一级加法器、第一级加法器结果寄存单元、第二级加法器输入选择单元、第二加法器以及第二级加法器结果寄存单元依次通信连接。
[0018] 所述的硬件结构的进一步设计在于，所述第一级加法器输入选择单元为第一多路选择器，所述第二级加法器输入选择单元由第二多路选择器与第三多路选择器并接组成，所述第一级加法器结果寄存单元由第一寄存区间与第二寄存区间串接组成，每个寄存区间又由两个寄存器串接组成，所述第二级加法器结果寄存单元为一个寄存器，所述两个个寄存区间的输入端、输出端分别连接所述第三多路选择器，所述第一多路选择器的一输入端与第一寄存区间的输入端连接，所述第三多路选择器的的一输入端与第二级加法器结果寄存单元连接。
[0019] 所述的硬件结构的进一步设计在于，所述乘累加器设有三个输入端分别为第一源操作数输入端、第二源操作数输入端以及系数输入端，所述乘累加器分别通过第一源操作数输入端、第二源操作数输入端与源操作数存储块通信连接，通过所述系数输入端与系数存储块通信连接。
[0020] 本发明的优点如下：
[0021] 本发明基于运算资源、存储资源固定的硬件系统，充分研究对称FIR算法的乘累加结构特点，给出对称FIR算法的并行化“二维分割”方法，实现了硬件并行化及对任意向量点数的覆盖。该方法解决了DMA搬运阶段基于并行化设计的数据细粒度分割、数据存放问题，以及向量长度过大而内存容量受限，需要作多次DMA搬入、处理、搬出，由此带来的源数据粗粒度分割问题。
附图说明
[0022] 图1是对称FIR算法补零及滑窗示意图。
[0023] 图2是对称FIR算法并行设计划分图示。
[0024] 图3是对称FIR算法乘累加器内部结构示意图。
[0025] 图4是对称FIR算法硬件顶层模块互联示意图。
具体实施方式
[0026] 下面结合附图对本发明方案进行详细说明。
[0027] 对称系数FIR滤波器，最为重要的数字信号处理方法，常用于相位失真要求较高的场合。例如希尔伯特变化器，高保真音响系统。基于不同的应用需求以及侧重点，对称FIR算法有不同的设计架构。设计方法上有基本的串、并行乘累加器，同时也可采用傅里叶重建技术，麦克米兰方法等。
[0028] 对于N阶数字FIR滤波器，滤波器系数为，其中，。对于信号， FIR滤波器输出为：
[0029] （1）
[0030] 当系数对称时，滤波系数满足以下条件：
[0031] （2）
[0032] 根据这个特点，滤波器的传输可以写成下面的形式：
[0033] （3）
[0034] 由上式可以看出，对称系数FIR可以先执行源数据对应项首尾相加，然后将所得结果依次与滤波系数对应乘累加。宏观来看，每次滤波的乘累加次数减少为之前的一半，流水时间应缩小为非对称FIR的一半，即理论性提升近一倍，这是算法层面对称FIR相比非对称FIR的区别及优势所在。
[0035] 本实施例提供的方法
[0036] 设定对称FIR算法的参数设定为源向量点数：fir_number，滤波系数长度(阶数)：fir_order。乘法器、加法器等运算单元的数量可支持算法作四路并行运算。
[0037] 数字滤波器的执行过程依然是基于滑窗的乘累加运算，由于对称FIR算法的系数长度通常较小，如果在DMA搬运阶段将源数据的首尾进行补零操作(对于点数为fir_order的系数，首尾应各补fir_order-1个零)，即相当于把源数据扩展成点数为fir_number+fir_order*2-2的向量，那么整个运算过程可视为固定阶数乘累加运算，则调用基本的流水乘累加器即可满足需求。下图1是算法补零及滑窗示意图，图中给出了第一次及最后一次滤波处理。
[0038] 假设源数据长度较小，以至于现有的内存容量可以支持一次性完成所有处理。并行划分时，可按照基于结果数量的平均划分或者基于运算量的平均划分，其本质都是一致的。图1所示是源向量的划分示意图，由图2可见，相邻两路获得的源数据会存在一定的交叠。在DMA搬运阶段，依次把每一部分的数据写入到指定的bank中，当然在把第一部分的源数写入之前，需要预先写入fir_order-1个零，紧接着导入源数据；在最后一路源数据写入之后，同样需写入fir_order-1个零至相应bank。
[0039] 以下是记录每一路生成结果数量的RTL代码，算法共需生成(fir_numer+fir_order-1)个结果，如果该结果不能被4整除，那么每一路的实际运算量会有微小差别。因此不能简单的将每一路的结果设定为(fir_numer+fir_order-1)>>2。以下constant1~constant4分别对应第一路到第四路实际运算得到的结果数量。
[0040] assign constant1=(fir_numer+fir_order-1)>>2;
[0041] assign constant2=((fir_numer+fir_order-1)>>1) – ((fir_numer+fir_order-1)>>2);
[0042] assign constant3=(fir_numer+fir_order-1)>>2;
[0043] assign constant4=(fir_numer+fir_order-1) - ((fir_numer+fir_order-1)>>1) -
[0044] ((fir_numer+fir_order-1)>>2);
[0045] 当需要处理的源数据是个很大的向量，即给定参数fir_number较大，使得源数据无法一次性导入内存，那么需要将源数据进行分割，通过多次DMA的“写入，运算，读出”，从而完成全部运算。每个bank容量为8K，但由于FIR算法固有的补零操作及分割处的重叠，分界点会略小于32K。设计中以30k为分界，具体可以分成以下5种情况：
[0046] （1）当点数在0 30K之间时，仅需搬运一次数据，得到结果的个数为fir_number+ ~fir_order-1。
[0047] （2）当点数在30K 60K之间时，共需搬运两次数据。第一次搬运数据地址：0 30k-1，~ ~得到30K个结果；第二次搬运数据地址：30K- fir_order+1 fir_number-1，得到fir_number~
+ fir_order -1-30K个结果。
[0048] （3）当点数在60K 90K之间时，共需搬运三次数据。第一次搬运数据地址为0 30k-~ ~1，得到30K个结果；第二次搬运数据地址：30K-fir_order+1 60k-1，得到30K个结果；第三次~
搬运数据地址：60K- fir_order+1 fir_number-1，得到fir_number+fir_order-1-60K个结~
果。
[0049] （4）当点数在90K 120K之间时，共需搬运四次数据。第一次搬运数据地址：0 30k-~ ~1，得到30K个结果，；第二次搬运数据地址：30K- fir_order+1 60k-1，得到30K个结果；第三~
次搬运数据地址：60K-fir_order+1 90K-1，得到30K个结果；第四次搬运数据地址：90K-~
fir_order+1 fir_number-1，得到fir_number+fir_order-1-90K个结果。
~
[0050] （5）由上依次类推，基于该分割方法的对称FIR设计是没有点数上限的，即可支持任意点数的对称FIR算法硬件实现。
[0051] 如上述对称FIR算法的并行化二维分割方法提供一种硬件结构，参见图4。该硬件结构主要由两路数据存储单元与四路乘累加器组成。两路数据存储单元分别与累加器通信连接，每路存储单元分别包括源操作数存储模块与结果存储模块。源操作数存储模块包括八个地址连续的源操作数存储块与一个系数存储块；结果存储模块包括四个地址连续的结果数存储块。每个存储块的深度为8kb。
[0052] 进一步设计在于，如图3所示，乘累加器是在传统串行乘累加器的基础上通过增加加法器个数和相应控制逻辑设计而成。由于实现了流水操作，从而提高了对称FIR算法的运算效率。由图3可见，该乘累加器主要由一级乘法器，两级加法器，用于控制的mux（多路选择器），FF（寄存器）等构成。
[0053] 乘累加模块的输入端分别为源操作数和滤波系数，经由乘法器处理后交给第一级加法器。该加法器主要实现数据的累加，其中数据输入端分别来自乘法器输出端和该加法器自身的输出端。当乘加操作完成后，由于加法器内部存在流水级（本实施例设定为四级），那么需要将四个值相加，得到的才是最终的滤波结果。这也是增加第二级加法器的目的。另一方面，为了实现该过程，必须将第一级加法器的输出寄存，同时，第二级加法器的两级数据输入分别由相应的控制逻辑根据加法器内部实际的流水级数进行选择。最后基于FIR的向量长度，通过计数器来控制最终的输出结果，即当计数器达到某一值时，数据写使能（wen）有效。
[0054] 图4是对称系数FIR硬件设计顶层互联示意图。采用四组图3所示的乘累加器。每组乘加器需要有三路输入，两路来自源操作数、另一路来自系数。设计中系数向量的地址生成器四路是一致的，所以仅需要一个bank存放系数，其数据流可以共用。其余仅需开辟八个bank提供八路源操作数，具体指定为bank0 bank7，bank8用来存放系数。同时bank9 bank12~ ~用于存放每一路的结果数(每路生成的结果小于8K，因此一个bank即满足需求)。
[0055] 设计中源数据及结果的存放都定位在前十六个bank，仅用了所有内存容量的一半。因此可采用乒乓设计提高性能。对于多块数据等待处理，当第一块源数据写入前十六个bank，并启动运算的同时，将第二块源数据导入后十六个bank，在第一块向量滤波结束后，启动DMA将结果搬出的同时，执行第二块数据的运算。由于运算时间复杂度高于数据搬运时间，使得数据的搬运时间被湮没掉。
[0056] 后一半内存源数据、系数及结果的存放，与前一半内存保持对应。数据流的供给由控制器顶层输入信号“pingpang”选择。start脉冲到来时，如果pingpang信号为高，代表前十六个bank有效，数据流来源于前一半内存；如果pingpang信号为低电平，则处理后一半内存中的数据。各输入输出地址分别由相应AGU控制。
[0057] 仿真实验通过在start和finish_all信号之间建立标杆，来确定系统运行的clk数，系统运行在1GHz主频。表1反映了三个特征向量点的系统实际运行时间，满足项目指标要求。
[0058] 表1 对称复数FIR性能指标
[0059]序号 点数、阶数 系统运行周期数/clk 运行时间 性能指标要求 结论
1 1k点、16阶 2123 2.123μs ≤2.5μs 符合
2 1k点、64阶 8771 8.771μs ≤9μs 符合
3 1k点、128阶 18531 18.531μs ≤19μs 符合
