漫谈超前进位加法器CLA及其FPGA实现

Diabloa · 发表于 2018-11-27 17:51

EDA365欢迎您登录！

您需要登录才可以下载或查看，没有帐号？注册

x

漫谈超前进位加法器CLA及其FPGA实现

目前在所有的cpu中，为了提高加法的计算速度。都采用了超前进位加法器。

普通的加法器我们很好理解，通常的16位行波进位加法器RCA结构图如下。

可以想象最简单的加法计算就是每一位都进行一次全加器计算，然后产生一个进行c，下一个全加器在取得进位以后再进行他的位的计算，循环下去直到最后一位。这样的问题是进行一次32位的加法计算就需要至少串行的经过32个全加器，如果CPU的频率是3Ghz，那么一个时钟周期，大约333皮秒内，是无法完成一次简单的加法运算的。

那么超前进位加法器是如何做到高速计算的？
可以想象肯定是把计算平行化了，而且是用数量来换了速度。
但是具体是怎么做的呢？
我们来一起分析下。

首先考虑所有的加法情况。

我们用这公式来描述所有2进制加法的进位的计算公式。
      Ci+1 = Xi Yi + Xi Ci + Yi Ci

这里C表示的是进位。
举个例子来说就是第一位的进位C1，它是由第零位的X0*Y0+X0*C0+Y0*C0，这里很明显C0是始终为0的。那么C1=X0*Y0
然后这个提取公因子公式就变成了
      Ci+1 = XiYi + Ci(Xi + Yi)

然后是不是发现，这样一来只有Ci是不确定的。
其它的Xi和Yi都是直接输入。
但是Ci其实呢通过循环inline（迭代）的一个替换，其实会变成类似
      Ci+1 = XiYi + (Xi + Yi)（Xi-1 Yi-1 + Ci-1(Xi-1 + Yi-1)）
然后可以一直这样替换下去，直到C0这一层。或者是最右端的输入。
一般的通常会把这几个变量成为G、P变量（Generate和Propagate）
      Gi = XiYi
      Pi = Xi + Yi

这样理论上可以实现任何位数都在有限次内完成，但是这样的代价是位数越多需要的电路也就越多。
这里附上一张wiki中的图来说明。

这里第一步的时候，所有的4个全加器对每一位计算出自身的和Si、Gi和Pi。
然后第二步，超前进位器计算出C1、C2、C3、C4，当然这里的C1、C2、C3、C4计算需要的逻辑门数量是逐步递增的。
然后C1、C2、C3对S1、S2、S3进行进位，C4会传递给更上面的位。
基本就是这样了。

但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算，能保证在一个时钟周期内完成基本就可以了。
取得一个成本和性能上的平衡。

4位超前进位加法器CLA的FPGA实现

module cla4_adder (a, b, cin, s, cout); //顶层模块

      input [3:0] a, b;
      input cin;

      output [3:0] s;
      output cout;

      wire gg, gp;             //

      bitslice4 b0 (a[ 3: 0], b[ 3: 0], cin, s[ 3: 0], gp, gg);

      assign cout = gg | (gp & cin);

endmodule

其调用的4个子模块如下。
以后不论位数怎么变，只会修改顶层调用的模块，以下4个子模块均不需变化。

//求和并按输出a,b,cin分组
module bitslice4 (a, b, cin, s, gp, gg);

      input [3:0] a,b;
      input cin;
      output [3:0] s;
      output gp,gg;

      wire [3:0] p,g,c;

      pg4 i1 (a, b, p, g);
      cla4 i2 (p, g, cin, c, gp, gg);
      sum4 i3 (a, b, c, s);

endmodule

//计算传播值和产生值的PG模块
module pg4 (a, b, p, g);

      input [3:0] a, b;

      output [3:0] p, g;

      assign p = a | b;
      assign g = a & b;

endmodule

//计算sum值的sum模块
module sum4 (a, b, c, s);

      input [3:0] a,b,c;

      output [3:0] s;

      wire [3:0] t = a ^ b;

      assign s = t ^ c;

endmodule

//n-bit 超前进位模块
module cla4 (p, g, cin, c, gp, gg);

      input [3:0] p,g; //输出的propagate bit 和generate bit
      input cin; //进位输入
      output [3:0] c; //为每一位产生进位
      output gp, gg; //传播值和进位制

      assign {c,gp,gg} = do_cla4 (p, g, cin);

//       function [99:0] do_cla4; //该函数内将为每个位计算其进位值
      function [5:0] do_cla4; //该函数内将为每个位计算其进位值
            input [3:0] p, g;
            input cin;

            begin: label
                     integer i;
                     reg gp, gg;
                     reg [3:0] c;
                     gp = p[0];
                     gg = g[0];
                     c[0] = cin;

                     for (i=1;i<4;i=i+1)
                              begin
                              //C0=G0+P0C_1
                              //C1=G1+P1C0=(G1+P1G0)+P1P0C_1
                                    gp = gp & p;
% _1 u# Z4 d# [( ^+ W( @                                     gg = (gg & p) | g;
2 i5 J& L+ ?* ]6 u0 M" f                                     c = (c[i-1] & p[i-1]) | g[i-1];8 g% w) |5 i: w& ]) b; n; g& L. I. i
                              end
/ y* U; y& Q8 D( ~  h                      do_cla4 = {c,gp,gg};
, d" w; i% W7 u             end
4 ?, e- N# d) ^7 b       endfunction( c. k' ?3 }- j7 @, ?5 P5 ~/ S
" w( e; X) [8 j6 r8 m
endmodule

4位超前进位加法器CLA的FPGA实现架构图如下。

cla4_adder的架构图

编写cla4_adder的testbench。
编写cla4_adder_tb.v代码如下。
`timescale 1ns/1ps

module cla4_adder_tb;

      reg [3:0] a, b;
      reg cin;

      wire [3:0] s;
      wire cout;

      cla4_adder dut(.a(a), .b(b), .cin(cin), .s(s), .cout(cout));

      integer i;

      initial begin
            a = 0; b = 0; cin = 0;
            forever begin
                     for (i=0; i<16; i=i+1) begin
                              #10 a = i; b = i; cin = 0;
                              #10 a = i; b = i; cin = 1;
                     end
            end
      end

      initial #1000 $stop;

endmodule

设置好仿真之后，cla4_adder仿真结果如下图。

Diabloa · 发表于 2018-11-27 18:31

本帖最后由 Diabloa 于 2018-11-27 18:35 编辑

转网友的，写的很不错，大家可以看看

ygcgsa · 发表于 2018-11-27 18:34

好东东

帐号		自动登录	找回密码
密码			注册

漫谈超前进位加法器CLA及其FPGA实现

EDA365欢迎您登录！

浏览过的版块

推荐内容 /1