找回密码
 注册
关于网站域名变更的通知
查看: 732|回复: 2
打印 上一主题 下一主题

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

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2018-11-27 17:51 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式

EDA365欢迎您登录!

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

x
漫谈超前进位加法器CLA及其FPGA实现
目前在所有的cpu中,为了提高加法的计算速度。都采用了超前进位加法器+ q; X4 s4 k  G8 n" J

7 `1 r" ^  }2 Y+ m6 ~普通的加法器我们很好理解,通常的16位行波进位加法器RCA结构图如下。

; J7 C" J, N4 p& |8 m
3 Q; T# I, x; \# d可以想象最简单的加法计算就是每一位都进行一次全加器计算,然后产生一个进行c,下一个全加器在取得进位以后再进行他的位的计算,循环下去直到最后一位。这样的问题是进行一次32位的加法计算就需要至少串行的经过32个全加器,如果CPU的频率是3Ghz,那么一个时钟周期,大约333皮秒内,是无法完成一次简单的加法运算的。
那么超前进位加法器是如何做到高速计算的?4 v# \* d& j4 |  |
可以想象肯定是把计算平行化了,而且是用数量来换了速度。& a0 \2 i  a/ u% y2 W
但是具体是怎么做的呢?
2 r: }& Z: [0 L- P我们来一起分析下。( {- Y3 P  S) J& j
! g8 G! O; L# d9 W
首先考虑所有的加法情况。
) O9 l7 R. ]8 Q" U/ _% M
! x  F: @6 ]+ r# j* r9 Q8 ~
我们用这公式来描述所有2进制加法的进位的计算公式。
  L* K0 X6 L0 p& @8 x8 ~        Ci+1 = Xi Yi + Xi Ci + Yi Ci* H) O: j" Q3 W! K
! X7 L- F6 \4 y5 ?, h5 y
这里C表示的是进位。
' U) Q! |& M* z, [' x举个例子来说就是第一位的进位C1,它是由第零位的X0*Y0+X0*C0+Y0*C0, 这里很明显C0是始终为0的。那么C1=X0*Y0
: q& @0 j8 Z! ?! J$ p3 r7 K. Z然后这个提取公因子公式就变成了
$ g7 @9 r6 D+ w, i. h& S$ S        Ci+1 = XiYi + Ci(Xi + Yi)
  ?, {* R+ N9 \- E, K7 l
5 z7 h8 O6 d5 E, y5 x8 a. Z! F然后是不是发现,这样一来只有Ci是不确定的。* n! T2 j: C; R% |
其它的Xi和Yi都是直接输入。! e/ u* c' ~! p. E: S/ |4 b
但是Ci其实呢通过循环inline(迭代)的一个替换,其实会变成类似
9 G% T6 g- e% S6 G1 V, q! z9 @- A        Ci+1 = XiYi + (Xi + Yi)(Xi-1 Yi-1 + Ci-1(Xi-1 + Yi-1))
1 @& v$ v0 v- K% p然后可以一直这样替换下去,直到C0这一层。或者是最右端的输入。
& Q8 \7 Q: e8 S$ v: Y: n3 Q一般的通常会把这几个变量成为G、P变量(Generate和Propagate)
5 p, P; U. ^; Q7 s# j8 ?8 T" v        Gi = XiYi ! n! ]: Q7 B7 s" b5 D; _6 H1 ]
        Pi = Xi + Yi7 y5 W% `/ K2 q$ ^* o) U

, W) T! O/ a7 b9 F$ W+ i/ F6 h* M# w" C3 E9 K
这样理论上可以实现任何位数都在有限次内完成,但是这样的代价是位数越多需要的电路也就越多。
) B) U2 J% Q; K- o8 ?9 I这里附上一张wiki中的图来说明。
这里第一步的时候,所有的4个全加器对每一位计算出自身的和Si、Gi和Pi。
" G" Y7 Q/ n9 k% `! |然后第二步,超前进位器计算出C1、C2、C3、C4,当然这里的C1、C2、C3、C4计算需要的逻辑门数量是逐步递增的。
* E) V$ e+ k7 @, ^7 D然后C1、C2、C3对S1、S2、S3进行进位,C4会传递给更上面的位。
' ~! w( H9 @. t' t& R# h2 H基本就是这样了。
% {; a$ O8 q0 k2 ]; `1 N! L" @9 E" k+ }) ^- @2 S% R' @
但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算,能保证在一个时钟周期内完成基本就可以了。
* i  k3 h0 T+ W& H$ r9 S7 B. n取得一个成本和性能上的平衡。
4位超前进位加法器CLA的FPGA实现
2 f; q5 X- S  A% I0 c. @
1 V! Y8 E& o/ `* h/ f6 Amodule cla4_adder (a, b, cin, s, cout); //顶层模块
% Z) ]( ]: J* ~4 [2 L4 q# z' G- R7 e: h' f4 q' N* `
        input [3:0] a, b;
# e0 t1 R9 k4 T# ?3 l. V; ~5 \        input cin;
: k- |0 ^4 C* o5 w4 o2 v        
# j8 t5 V# I* ~! o; m% V3 x6 t        output [3:0] s; % Q$ \$ ~! j) A  @# }9 ~, g
        output cout;* F  i1 ]& G" O! A9 a7 o

$ M: k; D) [% `8 B  s  R2 N4 ^        wire gg, gp;                //
- C9 r3 ?/ i8 L) n6 ~& i
8 t8 U4 a% V/ K        bitslice4 b0 (a[ 3: 0], b[ 3: 0], cin, s[ 3: 0], gp, gg);
6 @1 B2 h; P& @( G8 ^        
# s8 N. u: D% e        assign cout = gg | (gp & cin);
$ J7 o. ~- s# w) Z$ n7 T8 C
, U! `/ b0 U0 iendmodule
其调用的4个子模块如下。. [: x4 o0 A. `0 l
以后不论位数怎么变,只会修改顶层调用的模块,以下4个子模块均不需变化。: f# M9 T. Z8 @, _

  i+ K7 Q+ |) [/ f//求和并按输出a,b,cin分组
' o# w6 Z* V% t! F3 H& Y, C7 ]7 Wmodule bitslice4 (a, b, cin, s, gp, gg);
" m5 i3 N, C: z- H# c1 i3 k" Y  N- f7 d5 t8 u
        input [3:0] a,b;
- H& D7 G1 L' a$ f4 ]8 y- p8 D        input cin;
0 J6 t) s2 ^' N% q4 D8 c5 o        output [3:0] s;2 c7 ^/ b4 e0 I  _& s7 ]. P# R
        output gp,gg;
' G# f; g7 H% E; i
; }6 @9 y5 S' v, O        wire [3:0] p,g,c;
4 E0 x4 o+ G& B! |: z) \5 ~; w& B, J" ]0 E, {
        pg4 i1 (a, b, p, g);
% z( h& P  O9 T# w8 ~8 J        cla4 i2 (p, g, cin, c, gp, gg);1 I; k9 O3 V$ S( Q" m
        sum4 i3 (a, b, c, s);
' W7 N3 N# }# G+ q+ o8 i$ O; Z5 y3 P8 n' J! G' e4 v
endmodule
3 U4 f( k  s) X3 o  M2 E
- y' F# s/ {6 B1 O& k//计算传播值和产生值的PG模块
5 d0 F# E% h/ tmodule pg4 (a, b, p, g);
2 h# }7 n7 l+ w) @9 _2 E7 E' e. w+ U1 m5 H- ~0 g/ z4 G0 y: o7 t# A( {4 i& ~
        input [3:0] a, b;  `4 K7 _  R2 ?- u5 t3 e3 ?

8 A! j+ x" P0 C5 r) y        output [3:0] p, g;( D; e6 y) I7 e; K3 Y0 F0 r6 m
7 G8 y- }' v, \! u9 Q5 f: k9 {' l& n8 M
        assign p = a | b;
7 Q3 M, `" ?7 |( {        assign g = a & b;
1 w1 I# r. i2 u) a# e" z) k& \
) S4 {1 a* @! d$ z' ]8 _3 gendmodule
$ G, J. u  R! e5 H, r4 |6 D* x, J6 H8 j9 y0 r
//计算sum值的sum模块
. Y5 K3 x4 i- H% M3 A. W) `module sum4 (a, b, c, s);- Y1 P/ [4 H) D! \3 m( p% ~

5 }/ L$ T9 R3 _: ~- C        input [3:0] a,b,c;! l" N( a1 G% ~; F8 }
        " c4 D: d* a' Y% G( h
        output [3:0] s;
) ^& a' X% ~7 y- ~8 B% I        % T4 h* @& @0 [* C% G
        wire [3:0] t = a ^ b;
& j8 j8 S5 j# Q         , k  a5 @! d; R7 v! w3 `2 i
        assign s = t ^ c;/ s. B: Q& I" [3 ^' n9 N4 I$ H' r1 d9 V

' S: a9 l% ?4 @, d) h8 Wendmodule
$ z8 ?+ e9 I) c; S2 m. o' s1 G7 |: N7 a- D
& Q9 J" y  c- @! \
* v0 c* e; M" t$ R& d
//n-bit 超前进位模块$ E* v# {" O, L: f) W" e; J/ V
module cla4 (p, g, cin, c, gp, gg);: a7 @6 r( Q9 X1 t

' q" X! o% O! q0 O7 ~4 F        input [3:0] p,g; //输出的propagate bit 和generate bit. |+ _$ l0 q- C3 y' h" e9 @
        input cin; //进位输入! k( ~  ?2 x& ], M0 _
        output [3:0] c; //为每一位产生进位
1 [5 v; Z* [! ]- l5 T( ?) U        output gp, gg; //传播值和进位制9 s" _+ |4 q8 h& O+ e
7 w7 u7 g& ?+ A! p
        assign {c,gp,gg} = do_cla4 (p, g, cin);& o' d: D9 R# _

: _  u  \" Q0 @2 e, s; P& j! M//        function [99:0] do_cla4; //该函数内将为每个位计算其进位值# m1 q0 D2 t, B) F5 ?" m) D0 n* Z
        function [5:0] do_cla4; //该函数内将为每个位计算其进位值) ?7 n$ @* {, }6 b4 A6 n3 T
                input [3:0] p, g;2 h2 _2 f5 c8 {+ f+ Y
                input cin;. N. g6 R! P- a% f* A* b5 R; E
0 d2 E; w+ t: c* \
                begin: label
! e% R6 ~) B# J* n                        integer i;
7 x- n* W6 G" d& D: G                        reg gp, gg;$ A. B6 |" E) J/ x6 ^
                        reg [3:0] c;
! e, K4 ^1 x3 |8 t4 ^3 F. M7 c/ _; ?- {                        gp = p[0];
% {3 ]1 ?" ^/ l( u0 q& g6 {: M5 z                        gg = g[0];
7 ~& Y: B4 y3 a  U                        c[0] = cin;
7 n" T% f  o+ Z: w! s                 ' i& e# P! S4 o, s0 F: a4 F# @
                        for (i=1;i<4;i=i+1). |; [0 I9 z' A  K3 C$ W
                                begin
% r3 k- y1 Q+ [# w0 q. _: N. `# j                                //C0=G0+P0C_1% a' F8 v0 x: c" b' t! m; U5 x  ?. T
                                //C1=G1+P1C0=(G1+P1G0)+P1P0C_1
) A% W- A/ s$ }3 M; n                                        gp = gp & p;
( g4 |% l. \1 n' o3 F+ b! h9 g
                                        gg = (gg & p) | g; * O7 B2 x$ {# ]$ J3 d
                                        c = (c[i-1] & p[i-1]) | g[i-1];* l3 f( Q7 q! m+ n( g/ h# W
                                end
, ]+ w' F. `0 ~& K% j9 n! Q1 T, _
                        do_cla4 = {c,gp,gg};2 D3 ?3 d1 E4 V8 Q
                end9 a7 U* u* p2 X' D2 X( Z; a" d- q$ J
        endfunction  A( M# D6 D. t) d

1 u9 A. F% ^; ^+ W& g1 S
endmodule
4位超前进位加法器CLA的FPGA实现架构图如下。
cla4_adder的架构图
编写cla4_adder的testbench。
: w# {' @1 F: \! C$ w. K6 z+ ~( e% L编写cla4_adder_tb.v代码如下。3 B5 c' g2 B. Q7 }
`timescale 1ns/1ps2 }+ y. H  `8 Z! y  h

4 b: {2 Q# a7 m0 K5 j* s% pmodule cla4_adder_tb;" u5 R# i+ A2 t! e, f

+ J0 B0 o/ F+ P2 l        reg [3:0] a, b;( ^/ U% l9 R" s
        reg cin;+ c: K0 `' t9 l' h
        
1 z0 o: @6 w4 R; y        wire [3:0] s;# x1 k5 R+ u/ H0 g8 l4 }1 b
        wire cout;% O0 w& b* F, i. }7 o
        7 J) U! _9 @0 ?/ e5 P, X; D
        cla4_adder dut(.a(a), .b(b), .cin(cin), .s(s), .cout(cout));
$ J* f! h4 M" R5 M" T; z        ! j9 i& Y2 ~+ h$ f
        integer i;
7 Y- a% J" X6 @" _, L  I: C9 \8 D% i2 r% W
        initial begin2 T6 ]' n% n' q* @. ^, K
                a = 0; b = 0; cin = 0;
" G7 J0 x! J( R3 }( m: c                forever begin5 @# Q* H% S+ _/ \
                        for (i=0; i<16; i=i+1) begin
, w# r/ |. {* y: x. C5 N2 l                                #10 a = i; b = i; cin = 0;
# o8 `( K( O6 ~4 @                                #10 a = i; b = i; cin = 1;, _* o3 v: b! g4 j* `8 p
                        end
' L$ N. _6 B; h8 {6 O+ l                end
% g2 c( s; h: M4 @        end/ ?9 R4 w: I& j' P

! s' l3 n, g5 L, F2 H, H) ^        initial #1000 $stop;( D- k1 t9 j: w2 X" m* x% n

: p( w2 d( r; R) M( F4 qendmodule
设置好仿真之后,cla4_adder仿真结果如下图。

9 k5 |2 F5 s% A( y' C% a
7 K4 S/ S# u# [& O

该用户从未签到

2#
 楼主| 发表于 2018-11-27 18:31 | 只看该作者
本帖最后由 Diabloa 于 2018-11-27 18:35 编辑
" T5 L7 X3 `: ~# P+ _# n: \
' t' x) |3 M+ g; W转网友的,写的很不错,大家可以看看
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-7-26 10:27 , Processed in 0.125000 second(s), 26 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表