关键字 |
| Kogge-Stone，稀疏Kogge-Stone，生成树加法器，Brent-kung加法器，FPGA |
介绍 |
| 二进制加法器是大多数数字电路设计中的关键元件，包括数字信号处理器(DSP)和微处理器数据路径单元。因此，大量的研究继续集中在提高加法器的功率延迟性能上。在VLSI实现中，并行前缀加法器被认为具有最好的性能。可重构逻辑，如现场可编程门阵列(fpga)近年来越来越受欢迎，因为它在速度和功耗方面优于基于DSP和基于微处理器的解决方案，适用于许多涉及移动DSP和电信应用的实际设计，并且与特定应用集成电路(ASIC)设计相比，大大减少了开发时间和成本。随着移动和便携式电子产品的日益普及，电源优势尤其重要，这些电子产品广泛使用DSP功能。然而，由于fpga中可配置逻辑和路由资源的结构，并行前缀加法器将具有与VLSI实现不同的性能。特别是，大多数现代fpga采用快速携带链，为简单的Ripple进位加法器(RCA)优化携带路径。本文描述了在fpga上设计和实现基于树的加法器所涉及的实际问题。讨论了一种有效的测试策略来评估这些加法器的性能。在FPGA上实现了几种基于树的加法器结构，并与Ripple进位加法器(RCA)和进位跳过加法器(CSA)进行了比较。 Finally, some conclusions and suggestions for improving FPGA designs to enable better treebased adder performance are given. |
相关工作 |
| 在Xilinx 4000系列fpga上，当加法器操作数大于56位时，只有一种优化形式的进阶加法器性能优于纹波进位加法器。在Xilinx t II上进行的一项加器研究得到了类似的结果。本文介绍了在Xilinx Virtex 5 FPGA上实现的几种并行前缀加法器。结果表明，常规的RCA加法器具有较快的进位链优势，优于并行前缀加法器设计。本文主要研究在Xilinx Spartan 3E的FPGA上实现的携带树加法器。本文的独特贡献有两个方面。首先，我们考虑了基于树的加法器和一种混合形式，它结合了树结构和波纹进位设计。前一类加法器的代表是古格-石加法器，后一类加法器的代表是改良古格-石加法器。其次，本文考虑了加法器测试中涉及的实际问题，并提供了实际测量数据与仿真结果进行比较。除了能够使用高速逻辑分析仪将模拟数据与测量数据进行比较之外，我们的结果在结果和加法器类型方面都呈现了不同的视角。 |
| 所研究的加器设计为不同的位宽，最高可达128位，并用VHDL进行编码。利用Xilinx ISE 10.1i软件将设计综合到Spartan 3E FPGA上。从Kogge-Stone加法器和改良Kogge-Stone加法器的合成报告来看，即使减少改良Kogge-Stone加法器的黑细胞，两者的合成结果是相同的。也就是说我们减少了加法器的实现空间。 |
携带树加器设计 |
| 高性能加法器，也称为携带树加法器，预先计算传播和生成信号。在树形加法器中，并行生成进位，以增加面积和功率为代价获得快速计算。该设计的主要优点是进位树通过并行生成进位来减少逻辑层数(N)。 |
| 并行前缀树加法器与其他加法器相比，由于通过进位路径的复杂度为O(log2N)延迟，在速度方面更有利。突出的并行前缀树加法器是Kogge-Stone, Brent-Kung, Han-Carlson和Sklansky。从文献中发现，与其他加法器相比，Kogge-stone加法器是最快的加法器。从最坏情况的延迟来看，加法器的优先级是波纹进位、进位提前查找、进位选择和Kogge-Stone。这是由于“简化阶段”的数量。Kogge-Stone加法器的实现是最直接的，而且它具有所有加法器中最短的关键路径之一。Kogge- Stone加法器实现的缺点是占用较大的面积和互连的更复杂的路由(扇出)。并行前缀加法器(PPA)等价于CLA加法器。两者在实现进位生成块的方式上有所不同。并行前缀进位超前加法器是20多年前作为超大规模集成电路技术中加速n位加法的一种方法首次提出的。 It widelyconsidered as the fastest adder and used for high performancearithmetic circuits in the industries. A three step process isgenerally involved in the construction of a Parallel PrefixAdder. The first step involves the creation of generate andpropagate signals for the input operand bits. The second stepinvolves the generation of carry signals. In the final step, the sum bits of the adder following stagesof the operand bits and the preceding stage carry bit using a xor gate. |
| 1.预处理阶段。 |
| 2.往前看舞台。 |
| 3.后期处理阶段。 |
预处理 |
| 这一步涉及到生成和传播对应于A和B中的每对比特的信号的计算。 |
 |
| Gi = Ai和Bi… |
进位生成网络 |
| 在这一阶段，我们计算每个位对应的进位数。这些操作的执行是并行进行的。在并行计算进位后，它们被分割成更小的片段。它使用进位、传播和生成作为中间信号，由逻辑方程(3和4)给出。 |
 （3） |
 （4） |
后置处理 |
| 这是最后一步，也是这个家族中所有的蝰蛇都要做的(向前看)。它涉及到和位的计算。 |
 （5） |
 (6） |
不同类型的并行前缀加法器 |
1.Kogge-stone加法器 |
| Kogge-Stone加法器是一种并行前缀形式的进位前向加法器。它在O (log2N)时间内生成进位信号，被广泛认为是最快的加法器设计。它是工业中最常用的高性能加法器架构。Kogge-Stone加法器的概念最初是由Peter M. Kogge和Harold S. Stone提出的。在Kogge-stone加法器中，以增加面积为代价并行计算进位，从而快速生成进位。8位Kogge-Stone加法器(KSA)中携带、传播和产生信号的树状结构如图1所示。进位生成网络是树加法器中最重要的部分，它由黑单元、灰单元和缓冲单元三部分组成。黑色单元用于生成信号和传播信号的计算。灰色单元用于生成信号的计算，这些信号是后处理阶段计算和所需要的。缓冲器用于平衡加载效果。 |
2.修改Kogge-Stone加法器 |
| 图1中的Kogge-Stone加法器比其他著名的并行前缀加法器要快，并且在所有阶段都有2的扇出。我们可以通过消除冗余单元来减少计算量，从而补偿增加的延迟。Kogge-Stone加法器可以通过减少黑单元和重路由来进行修改，以补偿加法器的功能。改进的8位Kogge-stone加法器传播生成(PG)网络如图2所示。Kogge-Stone加法器的延迟也可以通过重新布线来减少，但这不是很有效，因为面积保持不变。我们还可以通过消除冗余黑单元来增加加法器的速度，从而减少加法器的面积。 |
3.路由技术 |
| 所有树加法器中一个重要的概念是，每个单元在整体输出中都有自己的任务，例如，在左边的8位Kogge-Stone加法器的第二阶段中，如果只有第6位和第7位存在，则计算生成位。它只需要从第0位到第-5位的生成位，当这两个生成位结合在一起时，它给出了从第0位到第-7位的生成位。重要的概念是，生成位6和7需要从位0到5的计算中生成位，但相反，可以给它使用位0到6计算的生成位，并将获得相同的结果。这是因为generate bit from 6已经被包括在内，但是从generate bit of 0到6的计算中又被添加了，这并不影响最终结果。但是最终生成位-i不能接受任何高于i的生成位，如果是这样，最终结果将受到影响，因为我们包括了更高位的生成值。上面提到的方法是一个很好的开始，但我们甚至可以进一步尝试去除一些多余的单元格。多余的细胞可以去除而没有任何不良后果，但它必须得到适当的补偿，否则延迟将大大增加。这可以通过改变路由(布线)来补偿。只在第一和第二阶段执行重路由可以提高速度，但在携带生成网络的所有三个阶段执行相同的重路由会增加延迟。 |
| 实现 |
| 采用Xilinx ISE design Suite 10.1i中的结构建模，在Verilog硬件描述语言中对不同的树加器进行设计，并使用Xilinx ISIM模拟器进行仿真。为Spartan-3 FPGA XC3S400合成，速度等级为4级。在kogge石加法器的仿真过程中，以8位的x=A8 h和y=AC h作为输入，以sum=54 h和cout=1作为输出。在Modified Kogge-Stone加法器的仿真过程中，以x=A4h和y=92 h作为输入，以sum=36 hand cout=1作为输出。然而，两个加法器都执行正确的加法操作，但唯一的变化是改进的Kogge-Stone加法器需要的空间更少，组件数量更少。 |
结论 |
| 本文提出了一种改进现有Kogge-Stone加法器的创新方法，通过重新布线和黑细胞约简来提高执行速度。该设计源于去除多余的黑色单元，并通过重新布线来补偿这些被移除的单元的原理。上述设计的延迟比与之相比的架构要小得多。使用的逻辑级别数量也减少了。 |
数字一览 |
|
|
参考文献 |
- AhmetAkkas和Michael J Schult(2011)，“一种具有新型十进制前导零预测器的十进制浮点融合乘加单元”，AMD IEEE。
- Anitha R和BagyaveereswaranV(2012)，“具有快速进位链逻辑的高性能并行前缀加器”，国际杂志超大规模集成电路设计与通信系统，第3卷第2期，第2页01-10, issn 0976-6499。
- David Jeff Jackson和Sidney Joel Hannah(1993)，“用Verilog HDL建模和比较加法器设计”，第25届东南系统理论研讨会，3月，406-410页。
- Kogge P和Stone H(1973)，“一类一般递归关系有效解的并行算法”，IEEE事务在电脑上，卷C-22，第8号，第786-793页。
- Krishna Kumari V, Sri Chakrapani Y和Kamaraju M(2013)，“Koggestone的设计和表征，稀疏Koggestone，生成树和Brentkung Adders”，国际科学与工程研究杂志中国科学院学报，Vol. 4, No. 10, pp. 1502-1506, ISSN 2229-5518。
- Madhu Thakur和Javed Ashraf(2012)，“用Kogge-Stone加法器设计Braun乘法器及其在FPGA上的实现”，国际科学与工程研究杂志，卷三，第10期，页03-06, issn 2229-5518。
- NurdianiZamhari, Peter Voon, KuryatiKipli, Kho Lee Chin和MaimunHujaHusin(2012)，“并行前缀加法器的比较”，世界工程大会论文集，WCE，第2卷，7月4-6日，伦敦，英国。
- PakkiraiahChakali和Madhu Kumar Patnala(2013)，“基于Kogge-Stone的高速进位选择加法器设计”，国际期刊新兴科学与工程学院中国科学院学报，Vol. 1, No. 4, ISSN: 2319-6378。
- Weste Neil, Harris David和BanerjeeAyan(2009)，“CMOS VLSI设计:电路和系统
|
菜单
（3）
（4）
（5）
(6）
