本发明涉及集成电路技术领域，具体涉及一种针对大位宽需求，基于fpga实现的高性能加法器结构。
背景技术：
加法器是各种高性能计算模块或系统的关键部件。目前实现加法器的常用方法有行波进位加法器、选择进位加法器和超前进位加法器等。每种加法器结构各有其特点：行波进位加法器消耗的资源最少，超前进位加法器运算速度最快，选择进位加法器介于二者之间。但是随着操作数位宽的增大，这些加法器占用的资源越来越多，性能也越来越差。如今，加密运算等应用的操作数位宽越来越大，例如rsa加密方法的操作数位宽达到了1024bits(或2048bits)，为了保证数据处理与运算的实时性，迫切需要高性能、大位宽的加法器。
fpga(fieldprogrammablegatearray)，即现场可编程门阵列，是一种具有丰富的硬件资源、强大的并行处理能力和灵活的可配置可编程的逻辑器件。基于fpga的加法器通常由进位链(carrychain)实现。但是由于fpga架构上的限制(以xilinx的fpga为例)，所有进位链的进位输入端位于每列可编程逻辑单元的最下方，而进位输出端位于其最上方；当一条进位链的进位输出端与另一条进位链的进位输入端连接，必会引入较长的可编程互连线，增加不必要的延时。因此，当操作数达到几百位，甚至上千位时，对加法器的运算速度产生较大的影响。
技术实现要素：
本发明针对上述fpga进位链结构的特点，提出了一种新型的大位宽加法器结构，通过利用进位选择和进位压缩的方法产生进位信号ci，使得进位链之间的互连不再受fpga架构上的限制，由此实现了对速度和面积的优化。在大位宽操作数的情况下，性能要比传统结构的加法器有显著的提升，优势更为明显。
本发明的技术方案是：本发明提出的基于fpga的大位宽高性能加法器结构由进位产生电路和求和计算模块构成。
进位产生电路采用进位选择的设计思想，并利用进位压缩结构快速计算出进位ci。进位压缩结构的相关文献，见t.b.preuβer,m.zabel,andr.g.spallek在第20届ieeesymposiumoncomputerarithmetic(arith)发表的“acceleratingcomputationsonfpgacarrychainsbyoperandcompaction.”如图2所示，进位压缩结构充分利用了可编程逻辑单元中的查找表lut，使得进位产生电路不仅减少了资源，同时大大降低了延时。
求和计算模块利用占用资源最少的加法器，即行波进位加法器计算得出最终的和si。该类型的加法器完全由fpga中的进位链结构实现，具体的实现原理参考xilinx官网提供的用户指导“virtex-5fpgauserguide(ug190)”中的“chapter5configurablelogicblocks(clbs)”。
进位产生电路和求和计算模块都利用了fpga中的专用进位链，充分发挥了进位链的运算速度快的优势。
将加法器结构映射到fpga芯片的过程中，如图6所示，采用了合理的布局布线尽可能减少对可编程互连线的使用，使加法器的延时进一步减小。
根据文献“acceleratingcomputationsonfpgacarrychainsbyoperandcompaction.”，altera公司提供的fpga中亦包含专用进位链，与xilinx的fpga相比，功能和特点一致，只是结构和布局上略有不同。因此，本发明亦适用于altera的fpga。
本发明的有益效果在于：与目前已有的fpga加法器相比，本发明提出的加法器占用的资源更少，运算速度更快。
附图说明
图1为本发明用于说明进位链在fpga中的布局示意图。
图2为本发明用于说明在进位产生电路中进位压缩结构的示意图。
图3为本发明用于说明基于fpga的高性能加法器结构的示意图。
图4为本发明用于说明传统的进位选择加法器的电路结构示意图。
图5为本发明用于说明图3的加法器基于fpga芯片的布局布线示意图。
图6为本发明用于说明图1、图3和图4的加法器结构在不同位宽下运算速度和占用资源的表格。
具体实施方式
为进一步阐明本发明的目的、技术方案及优点，以下结合具体实施例，并参照附图，对本发明进一步详细说明。
图1为本发明用于说明进位链在fpga中的布局示意图。在xilinxfpga中，进位链嵌入在可配置逻辑单元clb的slice中，两个slice构成一个可配置逻辑单元clb。输入信号cin从slice的下端输入，输出信号cout从其上端输出。呈一列排列的多个slice中的进位链级联可以实现位宽大于4bits的加法器。需要指出的是，用于进位链级联的互连线是专用的，即该互连线与通用的可编程互连线不同，它只用于一列slice中的进位链级联，且它的传播延时是通用互连线的十分之一。然而，构成一条进位链的slice呈一列排布，而且进位逻辑的计算方向只能从下向上单向传输。
图2为本发明用于说明进位产生电路中进位压缩结构的示意图，该结构包括一个六输入查找表lut和一个复用器m1。该电路具有五个输入信号(第一输入信号ai，第二输入信号bi，第三输入信号ai 1，第四输入信号bi 1和第五输入信号ci)，第一输出信号ci 2，两个内部信号(第一内部信号o5和第二内部信号o6)。
六输入查找表lut可以实现两个任意五输入的布尔表达式，但两个表达式的输入端必须是相同的。所以在该电路中，第一输入信号ai，第二输入信号bi，第三输入信号ai 1和第四输入信号bi 1作为六输入查找表lut的输入信号，并通过六输入查找表lut(等价于两个五输入查找表lut5_0、lut5_1)实现两个布尔表达式。这两个布尔表达式的结果分别从第一内部信号o5和第二内部信号o6输出。具体的布尔表达式为：
o5＝ai(ai 1 bi 1) (ai 1·bi 1)。
第二内部信号o6作为复用器m1的选择控制信号，第一内部信号o5和第五输入信号ci作为复用器m1的数据输入，第一输出信号ci 2是复用器m1的数据输出，布尔表达式为：
ci 2＝o6′·o5 o6·ci。
如图2所示，仅用一个六输入查找表和一个复用器就实现从进位ci到ci 2的计算。与fpga默认的行波进位加法器相比，该电路所消耗的资源是原来的一半，延时也为原来的一半，换句话说，通过使用进位压缩结构，在一条原本只能计算出进位cn的进位链上就可以实现进位c2n的电路。进位产生电路就是由图2所示的电路级联构成的。
图3为本发明用于说明基于fpga的高性能加法器电路结构的示意图。该电路结构由进位产生电路cc、求和计算模块rca以及复用器mux(由查找表lut实现)构成。其中，进位产生电路cc由图2的电路级联构成，求和计算模块rca采用fpga默认的行波进位加法器，复用器mux的功能由一个查找表lut实现。该加法器的两个操作数a、b分为n段，即a0a1…an，b0b1…bn。该加法器的输出和s亦分为n段，即s0s1…sn。
如图3所示，输出和s0的计算过程为：操作数a0和b0以及进位输入cin通过求和计算模块rca求得输出和s0；输出和s1的计算过程为：操作数a0和b0以及进位输入cin通过进位产生模块cc求得进位c1，操作数a1和b1以及进位c1通过求和计算模块rca求得输出和s1；输出和s2的计算过程为：首先，操作数a1和b1以及低电平‘0’通过进位产生模块cc求得一种可能的进位c2_0，操作数a1和b1以及高电平‘1’通过进位产生模块cc求得另一种可能的进位c2_1，然后，进位c1作为复用器mux的控制信号，两种可能的进位c2_0和c2_1作为其数据输入，通过复用器mux得到真实的进位c2，最后，操作数a2和b2以及进位输入c2通过求和计算模块rca求得输出和s2；输出和s3、s4…sn的计算过程类似于输出和s2的计算过程。
本发明提出的加法器的求和过程与传统的进位选择加法器不同，如图4所示，传统的进位选择加法器由进位ci控制多个复用器求得输出和si，但本发明提出的加法器的输出和si是由进位链组成的求和模块rca实现的。
图5为本发明用于说明图3的加法器基于fpga芯片的布局布线示意图。图5表示了可配置逻辑块(clb)在fpga芯片中的排列布局。在图5中，“\”标注的slice用于实现进位产生电路cc，互相垂直的交叉线“ ”标注的slice用于实现复用器mux的逻辑功能，“/”标注的slice用于实现求和计算模块rca。
图6为本发明用于说明fpga默认的行波进位加法器、传统的进位选择加法器(图4所示)和本发明提出的加法器(图3所示)在不同位宽下运算速度和消耗资源的表格。在该表中，rca表示fpga默认的行波进位加法器结构，csla表示传统进位选择加法器结构，ccrc表示本发明提出的加法器结构。该表展示了操作数a,b分别在200bits,400bits,600bits,800bits,1000bits,1200bits,1400bits,1600bits,1800bits,2000bits的运算速度和占用资源的情况，延时单位为ns，占用的资源用lut的数目表示。
由图6所示，本发明提出的加法器结构ccrc在操作数高于600bits下的延时要比传统进位选择加法器结构csla小，且本发明提出的加法器结构ccrc的延时以0.5ns/200bits的速率增加，而传统的进位选择加法器结构csla的延时以1.1ns/200bits的速率增加；加法器结构rca的延时远远超过csla和ccrc。当操作数达到千位以上时，本发明提出的加法器结构ccrc在运算速度方面有更大的优势。如图6所示，与传统的进位选择加法器结构csla消耗的资源(lut数目)相比，本发明提出的加法器结构ccrc消耗的资源较少，当操作数较大时，仅为传统进位选择加法器的60％。
综上所述，本发明提出的fpga大位宽加法器结构，由两部分构成：进位产生电路和求和计算模块，且都采用了fpga中的专用进位链。在实现过程中，通过合理的布局规划减少对可编程互连线的使用，减小了整个加法器的面积与延时。图3的加法器结构与图4的传统加法器结构相比，资源消耗和运算速度均有明显改善。
以上所述的具体实施例，对本发明的目的，技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
1.一种基于fpga的高性能加法器结构，其特征在于：针对加法器大位宽需求，结合进位选择方法和进位压缩结构，提出了一种基于fpga快速进位链的进位产生电路；加法器的所述输出信号由求和计算模块产生，该模块亦是由fpga快速进位链产生；当加法器的操作数达到1000位以上时，与其他加法器结构相比，该加法器结构在性能上具有明显的优势。
2.根据权利要求1所述的进位产生电路，其特征在于：加法器的操作数被分为n段，每一段可能的进位信号ci_0/ci_1由进位压缩结构产生，就xilinxfpga而言，该结构由进位链中的复用器以及6输入端、2个输出端的查找表lut实现；然后，通过进位选择的方法快速计算出准确的进位信号ci；整个电路充分发挥了fpga的特点，因此，不仅减少了资源消耗，还降低了延迟时间。
3.根据权利要求1所述的求和计算模块，其特征在于：该模块采用行波进位方法，利用fpga快速进位链就得到最终的和si。
4.根据权利要求1所述的基于fpga的高性能加法器结构，其特征在于：加法器的操作数被分为n段，根据fpga的特点采用合理的布局，进位产生电路在进位链的下部，高度约占进位链的三分之一，求和计算模块在进位链的上部，高度约占进位链的三分之二。
5.根据权利要求1所述的基于fpga的高性能加法器结构，其特征在于：进位产生电路输出的进位信号ci通过可编程互连线与求和计算模块连接。
6.根据权利要求1所述的方法，其特征在于，所述高性能fpga加法器结构同样适用于主流的altera公司的fpga。
技术总结