基于FPGA的内积算法优化
2008-03-31
作者：肖顺文，陈亚军
摘 要：针对在FPGA中直接运用分布式算法" title="分布式算法">分布式算法实现内积运算时，内积运算的系数大小、存储资源、运算速度" title="运算速度">运算速度难于达到最佳配置的问题，从算法、存储规模、查表" title="查表">查表速度三个方面进行了详细的分析和讨论，并给出了相应的优化和改进措施。
关键词：FPGA 内积算法 优化
基于分布式算法通过FPGA查找表" title="查找表">查找表实现内积运算，实现如下算法：
其中：Am为固定系数，Xm为输入数据(Xm<1)。利用分布式算法将内积运算转化为移位求和实现，用二进制补码表示，将Xm表示成如式(2)形式：
式(3)中，由于Xmn的取值为0或1，所以
存在2M种不同的结果。如果事先构造一个查找表，该表存储了所有可能的组合值，即可以预先计算这2M个值，并存入查找表（LUT）中，用Xmn作为查找表的地址信号，将查找表的输出结果移位(2-1运算)和相加，经过N-1个周期即可直接获得乘法累加的结果。这样就将复杂的乘法累加运算转化为移位相加运算。为提高运算速度，采用并行运算。其硬件电路简化结构如图1所示。
直接运用分布式算法实现内积运算,虽然实现了把复杂的内积运算转化为移位相加运算，但其查找表的规模随着系数呈指数增加。如果系数小，则可以方便地通过FPGA丰富的查找表结构实现；如果系数大，则将占用FPGA大量的存储资源，使运算速度降低。同时N-1个周期也使查表时间过长，运算速度降低。
本文针对系数大小、存储资源、运算速度的配置问题，对算法进一步改进、优化，使算法达到存储规模小、运算速度快，进一步提高运算的性能。
1 算法的优化
将Xm用下式表示：
根据二进制补码的运算，-Xm可表示为：
存在2M种不同的结果，但其中φmn的取值为±1，结果呈现出正负对称性。如果不考虑正负号，则只有2M-1种不同结果。存储规模减少了一半。用φmn作为LUT的地址信号，查找表存储器上一半地址对应的预存值将会是下一半的取负。其硬件电路简化结构如图2所示。
其中括号内的地址为X的下一半地址。该地址查找上一半地址对应的预存值，同时作为Ctrl控制加/减器，完成下一半地址和上一半地址对应的预存值的正负转换，送到累加器，经过N-1个周期即可获得乘法累加的结果。
2 存储规模的优化
由图2可知，算法优化后式(8)可以简化为：
虽然经过算法优化后存储规模减少了一半，但查找表的规模随着m呈指数增加。为了进一步减少所用查找表的规模，可采用减小m的方法来实现。式(9)中
可以定义为：
3 查表速度优化
为便于并行处理,可将图3中的查找表设计为相同深度，则每一个输人数据Xm(N-1)，分为C(为了与FPGA的4输入LUT相关，令C为4的倍数)段，则xmn可以表示为：
从式(12)并结合图4可以看出，查找表只需N/c-1个周期就可以得到内积的结果。与前面需N-1个周期相比较，速度提高了近c倍，实现了高速、高效运算处理。其硬件电路简化结构如图4所示。
用分布式算法将复杂的内积运算转化为移位相加运算，可清晰地表示内积结果。针对实现过程中系数大小、存储资源、运算速度的最佳配置问题，从存储规模、算法、查表速度三个方面对算法进行进一步改进和优化。算式推导过程层次清楚，电路结构合理，使内积算法达到存储规模小、运算速度快的目的，性能得到大大提高。
参考文献
1 褚振勇．FPGA设计与应用［M］．西安：西安电子科技大学出版社，2002
2 徐以涛，王呈贵，王金龙．基于DA算法的FIR滤波器硬件实现［J］．解放军理工大学学报：自然科学版，2003；4(3)：22～25
3 梁学东，卜 天，田日才.基于分布式算法和FPGA实现基带信号成形的研究［J］．电子技术应用，2004；30(5)：67～69
4 单长虹，刘小平．基于VHDL语言的快速查表电路［J］．开云棋牌官网在线客服技术，2002；27(11)：42～46
5 毕占坤，吴伶锡.FIR数字滤波器分布式算法的原理及FPGA实现［J］.电子技术应用，2004；30(7)
6 Wang Wei，Swamy M.N.S，Ahmad，M.O.Novel Design and FPGA Implemention of DA-RNS FIR Filters［J］.Journal of Circuits，Systems and Computers，2004；13(06)：1233～1249
7 Girard Patrick，Hbron Olivier，Pravossoudovitch Serge et al.Delay Fault Testing of Look-Up Tables in SRAM-Based FPGAs［J］．Journal of Electronic Testing，2005；21(1)：43～55
8 Lu Shyue-Kung，Yeh Fu-Min，Shih Jen-Sheng.Fault Detection and Fault Diagnosis Techniques for Lookup Table FPGAs［J］．VLSI Design 2002；15(1)：397～406