可重构系统中基于定点算法的Jacobi奇异值分解SVD性能分析

© 2013由Elsevier B.V.发布。信息工程研究院负责评选和同行评议可在www.sciencedirect.com上在线获取ScienceDirectIERI Procedia 7（2014）21 - 272013年应用计算、计算机科学与计算机工程国际会议可重构系统Ramanarayan Mohantya，Gonnabhaktula Anirudha，Tapan Pradhana，BibekKabia，Aurobinda Routraya *印度理工学院Kharagpur，Kharagpur，West Bengal，721302，India摘要这 本文介绍了设计和性能分析固定点双面Jacobi奇异值分解 （SVD） 算法 可重构系统使用流水线最先进的CORDIC架构该算法已实现在可重构硬件与建议的架构，以实现更快的性能与更大的尺寸矩阵。这种设计不仅降低了计算复杂度，而且利用了数据传输方法的并行性。讨论了各种量化模式及其相对误差的范围。执行时间的比较研究表明，FPGA实现与增加的维度被发现优于其浮点对应。基于FPGA和SystemC的定点实现的精度进行比较的基础上，精确的小数位数，信号量化噪声比（SQNR），正交性和因式分解误差方面的双精度浮点结果。© 2014作者。由爱思唯尔公司出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究院负责评选和同行评议关键词：CORDIC，定点算法，奇异值分解（SVD），可重构结构，信号量化噪声比（SQNR）。* Ramanarayan Mohanty联系电话：+91-947-633-3547;电子邮件：ramanarayan.mohanty@ hotmail.com。2212-6678 © 2014作者由爱思唯尔公司出版 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。信息工程研究所负责的选择和同行评审22Ramanarayan Mohanty等人/ IERI Procedia 7（2014）21M=Z M Z1. 介绍随着嵌入式计算的广泛应用，基于FPGA的定点架构在通信[12]、信号和图像处理[13]领域获得了相当大的重要性。在过去几十年的快速发展的同时，各种瓶颈，如计算速度和精度一直是一个主要问题。这些影响了数值算法的实时实现，如奇异值分解（SVD）。为了提高系统的性能，奇异值分解在并行结构的可重构系统中实现。利用Jacobi类和QR类[1]和[3]等已建立的算法计算对称矩阵的SVD。Jacobi类是最古老和最慢的一类，但它 更精确，确保稳定性，具有更高程度的并行性潜力。由于奇异值分解算法包括大量的计算，如正交变换，获得高吞吐量取决于算术单元的设计。这些单元是高性能计算的构建块。坐标旋转数字计算机（CORDIC）架构为算术设计提供了更好的数据独立模型[6]，[14]和[15]。它通过使用简化的硬件组件，主要是加法器和移位器[7]和[5]，借助平面旋转降低了设计的复杂性。因此，大量的研究致力于将SVD算法集成到专门的并行架构上，用于模式识别，信号和图像处理应用[4]。到目前为止，大多数论文只关注使用经典CORDIC架构的并行Jacobi SVD，计算一个矩阵的奇异值[2]。另一方面，本文贡献了一个架构设计的固定点雅可比SVD算法使用流水线的最先进的CORDIC技术的大矩阵（并行计算的奇异值分解）。对双精度浮点和定点FPGA实现的执行时间进行了比较研究。随着尺寸的增加，发现FPGA实现要优于它的浮点对应物。它还分析了该体系结构的性能，基于精确小数位数、信号量化噪声比（SQNR）、正交性和因子分解误差，本文的其余部分组织如下。第二节讨论了基于CORDIC的Jacobi奇异值分解算法和所提出的结构。在第3节中讨论了SystemC和基于FPGA的定点实现的精确小数位数、SQNR、正交性和因式分解误差方面的结果。最后在第4节中对本文进行了总结。2. 基于流水线CORDIC的Jacobi奇异值分解算法对于任何实矩阵，存在两个正交矩阵，并且存在一个对角矩阵，使得''的SVDM=UT-V-T（一）美恩美恩文恩其中，π（πi）的对角元素称为奇异值，U，V称为左奇异向量和右奇异向量。如果m=n且矩阵是对称的，则U和V跨越相同的向量空间。在几种奇异值分解算法中，雅可比算法通过执行一系列正交相似性变换来工作。通过旋转的变换使用Z（p，q，q）完成，并且可以表示为不i1ii我其中Z（p，q，q）矩阵通过改变（二）的单位矩阵的第p和第q行和列，同样的尺寸。每次迭代更新的矩阵Mi1是 更 对角 比 它的前身。通过右旋转计算（2）中的MZ需要n次CORDIC运算，并且ZT（MZ）需要另一个n我我我我我CORDIC操作导致总共2n个CORDIC操作。得到了奇异向量Ramanarayan Mohanty等人/ IERI Procedia 7（2014）2123U Z且V =Z 一22a作为p pT TK K（三）k=0k = 0每次迭代的旋转角θ的值是使用（5）获得的，其涉及2π 2的元素从对称矩阵M中依次选择的矩阵。因此我的天啊阿格拉appc s' =PP PQ（四）aqs c拉瓜qpaqc其中a，a' 得双曲余切值.，a'并且分别是旋转之前和之后的输入矩阵的元素。QQ QQ QQ=1tan（五）QQ pp在该设计中，首先使用矢量方法计算Δ k，并将其用于（2）中提到的变换过程。由于我们打算计算较大矩阵的SVD，CORDIC是一种递归算法，因此需要流水线建筑被认为是更合适的。然而，这种架构会导致维数小于21  21的矩阵出现数据风险，因为CORDIC和增益补偿单元的延迟为20个时钟周期。为了避免这个问题，我们在迭代的第二次循环中停止流水线，但这增加了执行时间（小矩阵<21 - 21）。对于较大的矩阵，单个CORDIC时钟周期应包括两次内存读取和两次内存写入。这在使用双端口块RAM时是不可行的。因此，存储器以CORDIC单元的两倍速度运行，以容纳所有数据传输。该算法需要log2n次扫描。在足够数量的扫描之后，二次收敛是在计算M的非对角元素的范数时观察到。 每次扫描具有n（n<$1）/2迭代每次迭代有2nCORDIC旋转和一个CORDIC反正切计算奇异值。 为了找到奇异向量，我们需要每次迭代n次cordic旋转。因此，CORDIC操作需要：C（n）= log n<$（n（n <$1）） 2）n（2n<$n<$1）.2.1. 拟议架构拟议设计的基本工作流程图如图1所示。在该实现中，用于计算的输入矩阵存储在FPGA的双端口块RAM中。每次迭代所需的矩阵元素使用多路复用器从相应的块RAM中取出，并发送到CORDIC模块，CORDIC模块将它们旋转通过反正切单元提供的角度。然后将这些元素存储回它们各自的地址。地址和定时模块控制在每个时钟周期中对块RAM的读/写地址的生成。该模块保持所有其他块之间的同步，并控制提供给每个块的时钟信号。反正切模块使用向量化模式CORDIC FSM（有限状态机）来计算每次迭代开始时的角度。2a24Ramanarayan Mohanty等人/ IERI Procedia 7（2014）21Fig. 1. 流水线Jacobi算法工作流程图DEMUX（解复用器）控制旋转模式CORDIC（奇异向量）和反正切块之间的切换。在每次迭代开始时，它们将输入路由到反正切模块进行角度计算，然后路由到CORDIC（旋转）模块进行旋转。奇异值和向量的计算同时使用两个并行排列的流水线CORDIC模块。在每个CORDIC（旋转）模块之后使用乘法器，以使系统处理增益一致。用于旋转的CORDIC具有14个流水线级，CORDIC增益补偿需要额外的6个时钟周期。每个CORDIC使用4个16位乘法器进行增益补偿。使用16位乘法器代替32位乘法器，以获得最大时钟速度。所提出的流水线CORDIC架构的资源利用率总结在表1中。2.2. 执行实现基于Xilinx Spartan-3e开发板和XC 3S 500 E（UG 230封装，速度5级）FPGA [10]。我们使用Verilog来描述设计，并使用Xilinx ISE 14.4软件包进行综合和映射到目标平台。整个设计采用单个50MHz时钟。我们的FPGA设计使用恒定定点表示。在这种格式中，变量被赋值为一个单一的Q点定义，在整个程序中保持不变。32-位字长，Q25格式 用于我们的定点实现。通过迭代过程以最小误差选择最佳Q点。当变量具有接近的动态范围时，常数定点表示是合适的。我们在SystemC中使用从距离估计过程中获得的不同Q格式来模拟定点Jacobi算法。在SystemC中，定点数据使用以下属性表示[11]。<字长（WL），整数字长（IWL），量化模式，溢出模式>（6）字长、整数字长、量化和溢出模式是决定定点算法精度的最重要因素[16]。量化和溢出是两个严重的限制Ramanarayan Mohanty等人/ IERI Procedia 7（2014）2125而将浮点程序转换成其定点对应程序则分别由于不足的分数和整数字长。存在各种量化模式来处理这些误差。当使用有限精度算术表示或存储数据时，会出现量化噪声。在此过程中，多余的位被消除，数据近似使用有限数量的位或字长。在算法中，这些误差通过定点算术运算传播，并在输出端累积。量化噪声被假定为与信号不相关并且它们之间也不相关。主要有两种类型的量化误差截断和舍入[8]和[9]。在截断的情况下，丢弃b位之后的因此，对于正数，量化值总是小于实际值值导致负误差。舍入类似于截断，除了“1”与LSB向上或向下舍入示出了在各种量化模式期间的不同相对误差的范围表2中Q是量化步长，并且等于Q=2-B，K是在量化期间从N比特中消除的比特数，B是小数部分的比特数。溢出或下溢受以下保护：饱和或环绕处理的方法。表1.Jacobi算法CORDIC流水线设计的FPGA资源资源使用可用利用率（%）切片数目2756465659Slice Flip Flop39249312424个输入LUT5283931256块RAM82040MULT18× 18SIO数量122060GCLK数量2248表2.不同量化模式的相对误差范围量化误差类型数字表示相对误差截断符号量值年（2个月b） 2不年（2个月b） 2002年2月）四舍五入所有数字 1 1 （2个月b） R（2个月b） 年2月）2 23. 结果和讨论基于Jacobi SVD实现的流水线CORDIC架构的性能如表所示图3和图2。在这里，已经进行了比较研究与双精度浮点和基于SystemC的顺序定点模拟在工作站与英特尔酷睿（TM）2四，2.5 GHz的处理器和4GB的DDR2内存。准确性进行比较的基础上的数量准确的小数位，SQNR，正交性和因式分解错误。使用（7）计算精确小数位的数量。数量 精确小数位计数器- log2（max（abs（x float - x固定 ）（7）图2. (a)我们观察到，由于可变Q格式，在基于SystemC的定点仿真的情况下，SQNR和精确小数位的数量更高。然而，FPGA实现比双精度浮点实现更快（表3）。这是因为所提出的架构涉及流水线的优点。图二、（a）显示了不同矩阵的SQNR的变化图2. (b)显示输出向量中正交性和因子分解误差的累积。FPGA实现中这些误差的演变和积累的主要原因是：（i）26Ramanarayan Mohanty等人/ IERI Procedia 7（2014）21表3. 执行时间比较（秒）矩阵维度浮点定点（FPGA）102.0e-43.57064e-3203.0e-34.28464e-33094.0e-312.54604e-340484e-326.86384e-3拉瓜b图二、（a）Jacobi SVD的精确小数位数和SQNR的变化;（b）Jacobi SVD的可伸缩性和因子分解误差Ramanarayan Mohanty等人/ IERI Procedia 7（2014）21274. 结论本文提出了高阶矩阵Jacobi SVD算法的流水线CORDIC结构。的准确性进行了比较，在准确的小数位数，SQNR，正交性和因式分解误差与SystemC为基础的结果。执行时间的结果表明，流水线CORDIC结构的执行速度（1000倍）比双精度浮点实现更大的矩阵。通过增加流水线级数以及为不同变量分配优化的整数和分数字长，可以提高精度。通过在GPU上实现Jacobi SVD算法，可以实现更快的Jacobi SVD算法。基于SystemC的优化实现可以通过在FPGA上进行高层次综合。引用[1] G. Golub和W.王文，矩阵的奇异值和伪逆的计算，数学学报，2001。Anal. ，1965，Ser. B，2，2.[2] J. R. Cavallaro，F. T.陆，SVD处理器的CORDIC算法，并行与分布式计算杂志，1988年5月，3日，pp. 271-290。[3] T.普拉丹A.鲁特雷湾Kabi，Comparative Evaluation of Symmetric SVD Algorithms for Real-Time Faceand Eye Tracking，Matrix Information Geometry，2012，pp. 323-340[4] S. F.萧敬腾李文，应用多维CORDIC算法实现复杂矩阵的并行奇异值分解，IEEETrans.Signal Processing，1996，44，3，pp. 685-697[5] M. D. Ercegovac，T. Lang，“冗余和在线CORDIC：应用于矩阵三角化和SVD”，IEEE Trans.onComputers，1990，39，6，pp. 第725-740页。[6] R.王文，“基于FPGA的计算机CORDIC算法研究”，第六届国际FPGA门阵列学术研讨会，1998年9月，第10191-200[7] P. K. Meher，S. Y.林志玲，“旋转角度固定的CORDIC设计”，IEEE Trans.on VLSI Systems。，2013，21，2，pp. 217-228[8] D.梅纳德河Rocher和O.李文，线性时不变系统的解析定点精度评估，电路与系统学报- 1：常规文件，2008年，55，19。[9] R. Rocher，D. Menard，P. Scalart和O.李文，基于平滑运算的固定点系统数值精度估计的分析方法，电路与系统学报，- I：Regular papers，2012，59，10.[10] Spartan-3e入门套件FPGA：完整数据表，Xilinx Datasheet DS 312（v4.1），Xilinx Inc.，加利福尼亚州圣何塞，2013年7月[在线]。可访问：http://www.xilinx.com/support/documentation/data_sheets/ds312.pdf[11] IEEE STD 1666-2005 IEEE标准SystemC语言参考手册，http：standards.ieee.org/getieee/1666/download/1666-2005.pdf。[12] J. Liu，Y. V. Zakharov和B.韦华，二分法坐标下降算法的体系结构和FPGA设计，IEEE电路与系统学报。[1] Regular papers，56，（2009）.[13] H. Huang和L.肖，基于CORDIC的快速基2 DCT算法，IEEE信号处理。Lett. ，20，（2013）.[14] P. M. Szecowka，P. Malinowski，CORDIC和SVD在数字硬件中的实现，第17届国际会议。MIXDES会议，2010，pp. 237-242[15] P. K. Meher ， J. Valls ， T. B. Juang ， K. Sridharan 和 K. Maharatna ， 50 years of CORDIC ：Algorithms，architectures，and applications，IEEE Trans. on Circuits and Systems I：Regular Papers，2009，56（9），1893- 1907.[16] T.普拉丹湾Kabi和A. Routray，对称矩阵奇异值分解的不动点Hestenes算法。2013年电子、信号处理和通信系统国际会议论文集。