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

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

[复制链接]

该用户从未签到

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

EDA365欢迎您登录!

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

x
漫谈超前进位加法器CLA及其FPGA实现
目前在所有的cpu中,为了提高加法的计算速度。都采用了超前进位加法器$ q- _5 x/ u$ h
2 a  o# p7 y4 M1 ?% b
普通的加法器我们很好理解,通常的16位行波进位加法器RCA结构图如下。

% o' j1 p9 |! d2 _9 o; [3 S% f! y' l' W% v2 W5 L3 U, J& Z
可以想象最简单的加法计算就是每一位都进行一次全加器计算,然后产生一个进行c,下一个全加器在取得进位以后再进行他的位的计算,循环下去直到最后一位。这样的问题是进行一次32位的加法计算就需要至少串行的经过32个全加器,如果CPU的频率是3Ghz,那么一个时钟周期,大约333皮秒内,是无法完成一次简单的加法运算的。
那么超前进位加法器是如何做到高速计算的?
3 b1 Z) k, W! _- Z可以想象肯定是把计算平行化了,而且是用数量来换了速度。& V: \3 E( v0 F$ I" D
但是具体是怎么做的呢?
3 s" h& O( ]. e3 v' p- J3 ^我们来一起分析下。  y2 B" _$ C1 v
$ }' r! n4 J) [4 B' l: d
首先考虑所有的加法情况。
; t% S7 b4 s+ l( A1 j4 D  X
, @+ S* |. J0 G2 a* D9 S8 t
我们用这公式来描述所有2进制加法的进位的计算公式。
) F. D9 ?6 y, n9 ?* n6 q        Ci+1 = Xi Yi + Xi Ci + Yi Ci- i! L8 x3 p" f6 d7 B" u
* F# K# z: H' W! o0 Y5 K% l# B+ p
这里C表示的是进位。$ Z# \% C5 k  w/ y
举个例子来说就是第一位的进位C1,它是由第零位的X0*Y0+X0*C0+Y0*C0, 这里很明显C0是始终为0的。那么C1=X0*Y0
2 i+ `0 J# w. n- o然后这个提取公因子公式就变成了( Z& \& {, v" Y& U
        Ci+1 = XiYi + Ci(Xi + Yi). c# ~! |3 P; |& @; K7 X

& s  Y2 X- Y" t然后是不是发现,这样一来只有Ci是不确定的。' E- B0 q, w* C( L
其它的Xi和Yi都是直接输入。
) B. j: O; j0 I6 w但是Ci其实呢通过循环inline(迭代)的一个替换,其实会变成类似  P7 s6 u! W3 @- }' B6 @
        Ci+1 = XiYi + (Xi + Yi)(Xi-1 Yi-1 + Ci-1(Xi-1 + Yi-1))6 e! w5 V2 Q. P% g, m3 u( k- E; }
然后可以一直这样替换下去,直到C0这一层。或者是最右端的输入。$ f- n$ G4 P, z3 N4 K! n
一般的通常会把这几个变量成为G、P变量(Generate和Propagate), z  x4 \' h; |2 O7 e
        Gi = XiYi ; v( I" U4 V/ \3 k8 w
        Pi = Xi + Yi1 h3 Z3 H" V. w: o# O
3 E2 r4 w0 b- _) @( Z. @- b$ I) U

1 s7 n7 b# a6 B; ~$ K, m& ?4 d4 y这样理论上可以实现任何位数都在有限次内完成,但是这样的代价是位数越多需要的电路也就越多。: Y! P; w; @% j0 K9 ^/ m" o% P- S
这里附上一张wiki中的图来说明。
这里第一步的时候,所有的4个全加器对每一位计算出自身的和Si、Gi和Pi。. m5 F. P- D7 o
然后第二步,超前进位器计算出C1、C2、C3、C4,当然这里的C1、C2、C3、C4计算需要的逻辑门数量是逐步递增的。
8 r4 n7 h' k  N- Z1 L/ L0 p然后C1、C2、C3对S1、S2、S3进行进位,C4会传递给更上面的位。
, l6 H% O, k7 V' K; e( j7 J基本就是这样了。
, f. G6 x$ F* ~; z! d( a( C+ t, h' v. `5 S3 y
但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算,能保证在一个时钟周期内完成基本就可以了。
& I8 g  K& ?6 |. k8 w' Q* D取得一个成本和性能上的平衡。
4位超前进位加法器CLA的FPGA实现
) J4 r! C' T) p
1 z4 y, X, n- F  e: X- @module cla4_adder (a, b, cin, s, cout); //顶层模块4 j# S; k) J5 `6 s4 a

" T1 r$ E% S7 R7 u" ~$ q        input [3:0] a, b;! u+ c, x6 M/ v1 w
        input cin;% ]5 t! P5 A2 v) t
        " D# j; D3 _: e
        output [3:0] s; + [; ]; C, D& |' a& _$ i
        output cout;
9 W5 h7 C" x+ a7 R! a6 x; x$ M3 A8 k  i- V
        wire gg, gp;                //8 ?; m* q9 q. J5 b& d" x& z* N

; {7 Y2 N6 A) U+ i  ]        bitslice4 b0 (a[ 3: 0], b[ 3: 0], cin, s[ 3: 0], gp, gg);7 J5 p6 a$ v: o# t4 n9 U# e
        
9 V& E! z( Q$ S9 d* {9 z        assign cout = gg | (gp & cin);
, k' k/ |2 w2 U  Y- }5 k
! \. h$ k% x8 x& J8 v9 J, y5 ~endmodule
其调用的4个子模块如下。5 i, K* g- g" X  U$ ~
以后不论位数怎么变,只会修改顶层调用的模块,以下4个子模块均不需变化。( S# v* J" S7 E) P, [

) s" t7 _$ [1 x+ F, X; H//求和并按输出a,b,cin分组/ r4 `7 `% @5 f! x$ d
module bitslice4 (a, b, cin, s, gp, gg);6 `3 d9 U5 n3 e1 f; O

. l8 H, T! k- I0 m( X( L# A* z        input [3:0] a,b;( X1 B( C0 v- {- ]3 l) x
        input cin;
5 Q5 S: d0 ?9 ]. v# D# c& O        output [3:0] s;) k$ U8 Q; K1 g  F& u  w( X5 ^
        output gp,gg;
5 L" w7 m- A& J, r4 O
& Q, l7 g% ~  O2 `4 p: D) M        wire [3:0] p,g,c;
5 k' X4 n# g) Y7 Q4 ~3 U
. P! L$ E1 d; N$ B- M        pg4 i1 (a, b, p, g); 7 Y) o* h7 t* Q/ n5 Z
        cla4 i2 (p, g, cin, c, gp, gg);: f: t+ }3 A% c. x, c3 ^4 w' S
        sum4 i3 (a, b, c, s);) v6 e( {9 b. h" j0 F# z+ [3 J
& Z# o# h7 z, R5 c
endmodule
% n3 R4 q) q  l7 r4 a" ~8 c  U9 ^* v. H: {0 U
//计算传播值和产生值的PG模块6 K4 R7 c% N; w; M
module pg4 (a, b, p, g);
; c+ m5 H" s& w' y' _
$ o& y7 @4 O- ^- Z% z. t        input [3:0] a, b;
4 \% O( M9 m7 h* j/ Q1 u2 g9 D, J
* f8 S* ?0 C" Y! b+ Y        output [3:0] p, g;; ]8 o3 N5 d- i
7 [: T- E$ x. ?& X. T1 z: T
        assign p = a | b;
7 V/ F7 |) s( r        assign g = a & b;5 N# ?, |$ S/ P5 x8 Z+ n8 m
, h6 [% k$ E$ ?) }$ L
endmodule , R; R/ J* Q( w4 p; l5 a7 Y+ L
9 A: j+ v; d3 @3 ?, D# x
//计算sum值的sum模块  J2 e4 Y, e. N) x; @0 A2 |! r
module sum4 (a, b, c, s);' w( p5 n3 o2 F( g. }2 z. K. B
3 `2 I& t# O2 y/ ]; y, P
        input [3:0] a,b,c;9 \1 ~# A' o& v
        8 k  v( r) a& r0 X. P
        output [3:0] s;! q' M! [  x" ~4 ]- M# l
        
9 K3 j0 M3 ~% u% ]5 v  P1 f9 p- q        wire [3:0] t = a ^ b; ; @4 L7 z1 J( f* U
         
6 n# M  Q/ f" e; T        assign s = t ^ c;
. Q6 a# r. o+ ^5 s& ?, T/ V7 @' M/ n9 o! a; m7 X
endmodule
+ c8 k' u, \( G# ^3 H: w& R! D/ p1 y" ]- G$ u( Q# D, g
" x+ |. m! R  \9 X5 |. ^

7 B! `* A* d) L- G/ l//n-bit 超前进位模块
& `1 D; l3 a0 A& S9 k- x: ?module cla4 (p, g, cin, c, gp, gg);& F8 j2 W9 }9 m) }5 P

0 A" P* N) n) C& i/ l$ w" x        input [3:0] p,g; //输出的propagate bit 和generate bit* r: L( _# ?# D! T6 Y2 k
        input cin; //进位输入) G8 r5 c: s0 H
        output [3:0] c; //为每一位产生进位
/ k2 a# w% h9 c$ R        output gp, gg; //传播值和进位制) {9 K0 c1 U1 }& ?8 y
- R% l6 x" ?2 ]! g( z
        assign {c,gp,gg} = do_cla4 (p, g, cin);) f% R0 G' z# K+ _0 J' X

2 ?1 e7 ?) `2 y. m9 {1 x& t. M/ l5 u//        function [99:0] do_cla4; //该函数内将为每个位计算其进位值
5 |' z6 ~3 v3 r0 @7 m" b        function [5:0] do_cla4; //该函数内将为每个位计算其进位值' g8 d4 G6 o! `/ t: a
                input [3:0] p, g;
/ c" }# |" N1 F3 @8 C0 |                input cin;, A+ a% t6 h# m# C+ A

8 e" q, o+ S& o                begin: label* L( w" U, A" x2 |
                        integer i;6 d/ r7 ]8 n8 \% C# T
                        reg gp, gg;3 r6 y+ ^+ F1 X4 L( m3 k
                        reg [3:0] c;
  y% {3 @  K4 [                        gp = p[0];
: K1 J( B/ Z" E& N7 B1 |                        gg = g[0];1 F* Z* T7 b% f) C. ~7 @0 j  K- Y
                        c[0] = cin;
3 N7 `. r+ G0 v/ B                 
8 D& l$ R4 B; e+ K7 q: {& Y" I  Y                        for (i=1;i<4;i=i+1)5 z) J  {* @- }$ M
                                begin " o9 w- |. B% `" A
                                //C0=G0+P0C_1
7 a+ J9 E* b$ {( ?                                //C1=G1+P1C0=(G1+P1G0)+P1P0C_1
9 I/ {$ o2 }9 O* h: F0 R; C: G' }" v                                        gp = gp & p; , B3 Q* t  n; a3 F9 m
                                        gg = (gg & p) | g;
& ?( a6 w: W4 a2 p& r' p; ]
                                        c = (c[i-1] & p[i-1]) | g[i-1];9 _. U* Y  F4 ?2 y) N
                                end
  r( ^, m5 |: \% O7 ^& \- T
                        do_cla4 = {c,gp,gg};! M$ E8 S+ M# |: Q6 p' `6 e
                end
5 k# b8 a9 Y! D% r; y2 [: w- `+ V
        endfunction
3 f6 ?9 A8 p4 o* k& A7 f6 b

0 n3 }6 v, G$ a) ^0 q& D& R0 O3 V$ N
endmodule
4位超前进位加法器CLA的FPGA实现架构图如下。
cla4_adder的架构图
编写cla4_adder的testbench。5 o& t& H: t- B( k& x
编写cla4_adder_tb.v代码如下。5 G2 `. K0 J+ n4 C% S+ N) `& p& B
`timescale 1ns/1ps' W) e: n) w2 l5 C& d8 y9 `' S$ J

/ s+ F1 h# K5 x2 x$ ^( K+ t# D# tmodule cla4_adder_tb;
8 J5 Q0 \8 x+ I; R
% D0 C1 s+ i$ R6 `% `" x/ t        reg [3:0] a, b;
0 _* D- x, J0 K! f5 ]        reg cin;
. N; s% Y2 [; ]        # X7 E9 l& P3 @9 ^" [
        wire [3:0] s;3 R7 V7 E# x* U; U5 E
        wire cout;+ D2 ]$ \! C# }5 Y
        / F" B2 a, M; \5 }2 E5 Y" h
        cla4_adder dut(.a(a), .b(b), .cin(cin), .s(s), .cout(cout));
0 M4 P- j& I& O        
2 x$ r/ e4 ]! D7 j6 F$ L        integer i;; m5 Z' A( H  o" e* A3 j5 w; p
8 e/ ~" h9 C2 J+ t8 c" x4 x
        initial begin
8 n& ^. h, b( f$ |, ]                a = 0; b = 0; cin = 0;* q9 S& c  w; Y& C1 F. G
                forever begin
! y  r! i% p6 }                        for (i=0; i<16; i=i+1) begin
- T: \3 S6 E1 ?3 i                                #10 a = i; b = i; cin = 0;
5 T' o: d$ v& s( P2 O                                #10 a = i; b = i; cin = 1;
4 b- R9 g1 p7 k; w0 y                        end) H* ^/ R' _2 L$ f" p0 I$ l# }, h
                end* ]0 M0 D, A/ g8 q  t! Q; v
        end( y9 k# R3 T. }" Y
7 R) K: N, R8 q+ Z2 u
        initial #1000 $stop;2 k; W; c0 [3 @2 Y" k2 |: K
! h; [- g! m1 T  `7 S1 r+ ^
endmodule
设置好仿真之后,cla4_adder仿真结果如下图。
7 {9 g. d6 F8 m4 k4 H

1 F+ T4 D8 ]; P. @* j. A; s8 \

该用户从未签到

2#
 楼主| 发表于 2018-11-27 18:31 | 只看该作者
本帖最后由 Diabloa 于 2018-11-27 18:35 编辑
, v" H$ I- d+ l, l5 l/ e& b" A
; ~' h+ H" w% U5 n8 d0 M转网友的,写的很不错,大家可以看看
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

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

EDA365公众号

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

GMT+8, 2025-7-23 21:09 , Processed in 0.140625 second(s), 26 queries , Gzip On.

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

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

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