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

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

[复制链接]

该用户从未签到

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

EDA365欢迎您登录!

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

x
漫谈超前进位加法器CLA及其FPGA实现
目前在所有的cpu中,为了提高加法的计算速度。都采用了超前进位加法器
1 l/ }1 C6 j- U" S( Q6 t0 R6 Y, _$ \
9 }6 r: J9 k9 v' g- ^普通的加法器我们很好理解,通常的16位行波进位加法器RCA结构图如下。

, c1 F+ j, n( t8 W  A8 Q( |4 h2 {: d
% w9 N" X* Y3 X. _) P3 y可以想象最简单的加法计算就是每一位都进行一次全加器计算,然后产生一个进行c,下一个全加器在取得进位以后再进行他的位的计算,循环下去直到最后一位。这样的问题是进行一次32位的加法计算就需要至少串行的经过32个全加器,如果CPU的频率是3Ghz,那么一个时钟周期,大约333皮秒内,是无法完成一次简单的加法运算的。
那么超前进位加法器是如何做到高速计算的?+ F8 V8 L: `2 ]
可以想象肯定是把计算平行化了,而且是用数量来换了速度。
& {' t' e" _+ n- g% x; _6 C但是具体是怎么做的呢?
( U- ^  Y7 N, b5 N4 j我们来一起分析下。
) d( T! I3 w. K/ }( x6 ~" Y% ?! q% F2 }8 t
首先考虑所有的加法情况。
- ?/ G. ]: x8 G* R

$ n9 E  V  |- Z+ F8 W我们用这公式来描述所有2进制加法的进位的计算公式。
3 S% V; h% ]& H/ ?% f8 v; P        Ci+1 = Xi Yi + Xi Ci + Yi Ci0 w; {+ W+ I) d1 e6 {, @: Y
1 h- D: r* \  Z$ S* ?
这里C表示的是进位。
( W7 B; ?  [& {: N: E% n% J举个例子来说就是第一位的进位C1,它是由第零位的X0*Y0+X0*C0+Y0*C0, 这里很明显C0是始终为0的。那么C1=X0*Y0) z# x. ~$ r6 L$ c
然后这个提取公因子公式就变成了
0 j4 L5 q. r$ x- k, v" w6 z7 F, F        Ci+1 = XiYi + Ci(Xi + Yi). l( r0 E& y9 y  f" e/ P  P
2 w) e' x0 g* s
然后是不是发现,这样一来只有Ci是不确定的。5 p+ A* D9 S# {& G' ]6 w% G
其它的Xi和Yi都是直接输入。% h, U  p9 S9 `! V1 a: D" I
但是Ci其实呢通过循环inline(迭代)的一个替换,其实会变成类似7 t* M) }$ X5 _  K
        Ci+1 = XiYi + (Xi + Yi)(Xi-1 Yi-1 + Ci-1(Xi-1 + Yi-1))
- i( I! k' [  w$ j1 N& E然后可以一直这样替换下去,直到C0这一层。或者是最右端的输入。
. Z$ o4 |: S5 k4 B$ O1 ?( Z一般的通常会把这几个变量成为G、P变量(Generate和Propagate)3 Z# y2 `7 a: k/ y
        Gi = XiYi ( A- G- A! U" ?' V1 H7 b  p3 n
        Pi = Xi + Yi* C( h, [2 H( M+ ^0 {
. ^, s' u  h2 U8 f% j7 [

. P% ^/ r0 ^0 r& Q- c; p这样理论上可以实现任何位数都在有限次内完成,但是这样的代价是位数越多需要的电路也就越多。
. O+ D$ a9 {$ \6 ?这里附上一张wiki中的图来说明。
这里第一步的时候,所有的4个全加器对每一位计算出自身的和Si、Gi和Pi。  J4 o# [5 P9 }) U
然后第二步,超前进位器计算出C1、C2、C3、C4,当然这里的C1、C2、C3、C4计算需要的逻辑门数量是逐步递增的。
1 s8 L* I$ d# j2 e! c' y1 B; u9 X然后C1、C2、C3对S1、S2、S3进行进位,C4会传递给更上面的位。) C& W, }' z6 D
基本就是这样了。
; h. M4 m) ~" O7 Z; |) [$ C1 ^4 W: U2 b# x8 `  Q/ s2 m
但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算,能保证在一个时钟周期内完成基本就可以了。1 e0 H) W! {2 {6 S2 d2 v
取得一个成本和性能上的平衡。
4位超前进位加法器CLA的FPGA实现; w6 }6 t/ X! t7 M

& i  D. @% {, |module cla4_adder (a, b, cin, s, cout); //顶层模块+ ?1 ~8 ?8 V6 B

* ^  J) _/ j& M; [7 c        input [3:0] a, b;1 a( \5 }$ Y1 q6 w" v# J
        input cin;0 V) A& e& j( p4 T) W: n1 t
        
( `3 b) Q# L2 ?9 p+ ^& W2 d        output [3:0] s; ; p$ v( p, w/ ~# i4 x
        output cout;" |1 j, e. k! K" p4 _0 |
9 z+ h! r: M% L# A' @' V
        wire gg, gp;                //, i4 y* E9 Z% {
; `. C) J$ x( v* y( ^3 P
        bitslice4 b0 (a[ 3: 0], b[ 3: 0], cin, s[ 3: 0], gp, gg);
! C7 Q' C/ d' v6 g: N' m2 v        
* {! t4 j9 G$ y3 E$ d  x$ q        assign cout = gg | (gp & cin);
7 @# L5 S" r9 ~2 a6 C& O# t5 G0 {! Y1 H3 ~) V
endmodule
其调用的4个子模块如下。" c+ @7 A, o. H0 K  P. C: e8 a
以后不论位数怎么变,只会修改顶层调用的模块,以下4个子模块均不需变化。
5 R( \* \& W; _0 X
0 g* d4 W+ ]' j6 v) k! D$ ?/ e//求和并按输出a,b,cin分组
" n! ^+ [0 E! c; _. h* U& g! xmodule bitslice4 (a, b, cin, s, gp, gg);0 n  i, |: |& |
% ^- V; A1 ~. y. V/ Q! D$ K
        input [3:0] a,b;1 ?0 H: A( v$ S% C) b
        input cin;
( ?& c1 f, T! t# I+ K        output [3:0] s;8 b, m0 \# y' T7 O$ F: k: G
        output gp,gg;
0 V, U% J& e. C/ F% @" T
, K# Q# L0 M/ {+ t6 C' a        wire [3:0] p,g,c;
+ G0 I3 [' k' O3 u# v
+ b; ?& B: _+ f( @& I        pg4 i1 (a, b, p, g); 4 Q5 x( e+ J8 ?7 G: Q) ?8 Z
        cla4 i2 (p, g, cin, c, gp, gg);
6 R$ c4 S$ [. f        sum4 i3 (a, b, c, s);
1 Y9 \6 p, A$ V2 c8 S+ v
; z* K2 T- f8 V" A9 n) K( B1 s. Jendmodule
* S5 \! t' Z/ w$ ]1 h3 a
* V. V1 @+ _$ l) c2 f  X//计算传播值和产生值的PG模块3 ?& f  z+ d1 o8 ]3 S
module pg4 (a, b, p, g);
5 u+ \, U, P! D2 n, u) T! m7 L( x& o
        input [3:0] a, b;
0 r1 E$ M' P- T1 [, l
' X! V# G0 x! h( l0 c/ j1 R' n        output [3:0] p, g;
: M3 `# a, j: v  J9 |# g1 B* N9 S' n7 S9 Y; s# f1 U% d$ z
        assign p = a | b;4 ?! l4 C9 |( l& a/ v6 h* z
        assign g = a & b;( w" u: U/ y2 }; P" W" g) ?
- ~# f6 E( S* {7 B  ~; r
endmodule
1 O5 j2 O7 ^. p$ D' [1 A. ]! l- U0 v( F& n# W' b$ ~
//计算sum值的sum模块1 p. D3 P# n; B, w0 |9 E; h1 a
module sum4 (a, b, c, s);& ?( F7 L8 U8 E7 f1 o" A

- [* h  W2 {! n, \        input [3:0] a,b,c;1 I& Y) ?; p" C6 K; F/ _9 d
        
2 B- v" w& Z' T$ w8 n8 Y        output [3:0] s;0 r# L1 h. Y& y+ E4 M+ O) k
        
5 W( D. Z: o+ Y  f        wire [3:0] t = a ^ b;
9 ~$ G/ O' n7 D# T         ! p' g; w9 A9 c- F; _7 H
        assign s = t ^ c;! h, b3 j- _. \: s  J9 t

+ |0 [7 z& u0 c. H( S& M) j9 ^endmodule
+ `" J2 r4 I% Q  p: S. b. s7 e1 R% o, [/ ~" V0 z
! F# C. }4 O! ]$ f. M' ]
; j7 o+ E* ?! Z. {& Z8 R2 T
//n-bit 超前进位模块0 Q$ I* u) W" I  x. o8 r
module cla4 (p, g, cin, c, gp, gg);
- k8 \* c% Q* A4 e7 I
( c4 q8 L  M/ p+ _, |; _1 y        input [3:0] p,g; //输出的propagate bit 和generate bit' ?" B2 a! L/ l5 `8 z% |5 W
        input cin; //进位输入
) Q0 L  @, f) c6 n) B        output [3:0] c; //为每一位产生进位
( J7 q& ~0 m) O% b1 ^) p        output gp, gg; //传播值和进位制
) b! T  D) N- P; m$ i+ m: o/ G( Q& K# s" ?
        assign {c,gp,gg} = do_cla4 (p, g, cin);
# F1 }0 C) L- M: s$ j
5 x1 B! ^, E4 }& q//        function [99:0] do_cla4; //该函数内将为每个位计算其进位值; G, c6 }0 x9 v! C1 ^3 L
        function [5:0] do_cla4; //该函数内将为每个位计算其进位值
, Q1 E9 o7 q% c: Y                input [3:0] p, g;
! J3 V$ U2 c  N4 ?: a                input cin;- B# c7 ~/ P/ y! P2 n/ g  z  J. h
* ^9 u3 O2 g+ P- @
                begin: label" R0 G1 Y7 X, q
                        integer i;
# x5 N8 I' b" s2 K$ J                        reg gp, gg;5 Z- }" w  p. g  a9 A
                        reg [3:0] c;
- U( V" n; C" e. t1 p3 b$ g                        gp = p[0];
6 J6 W! {8 j1 d                        gg = g[0];, K+ q: M5 D) G7 t' e, u, b
                        c[0] = cin;
0 v1 z- Y( _3 T                 8 \5 Q- V- ~$ }  j; d/ h% x- v% p
                        for (i=1;i<4;i=i+1)
! e$ g3 Z8 q+ i* {/ w                                begin ! r# @1 }+ ~4 Q$ S
                                //C0=G0+P0C_14 F! G& S, e3 U& a1 C
                                //C1=G1+P1C0=(G1+P1G0)+P1P0C_1  E* f$ b+ V2 W& {1 g9 \; N
                                        gp = gp & p; / U# a& N! Q  l& d* @$ f
                                        gg = (gg & p) | g; & k- i, |4 V- ~& o/ P. [& P
                                        c = (c[i-1] & p[i-1]) | g[i-1];
5 r# z4 m( _, \$ x! V
                                end8 {. V) p2 u5 g; u) a
                        do_cla4 = {c,gp,gg};
  `5 M# t6 R) A  k# \! ]0 U
                end% ?6 l# x. \- r/ n
        endfunction( k* |$ r$ Q! T" W$ X( e

, P- |+ J  K7 g3 A- r) ~
endmodule
4位超前进位加法器CLA的FPGA实现架构图如下。
cla4_adder的架构图
编写cla4_adder的testbench。, q* E" n$ z+ g# S
编写cla4_adder_tb.v代码如下。
$ s( N% ]- J( r: X' k' ~`timescale 1ns/1ps( ~5 O2 `7 n; ~
1 A4 Z, T/ i9 \6 x2 w  _
module cla4_adder_tb;) m, p- V, w, h: P

2 P' x/ o! F7 T. X4 T5 ~        reg [3:0] a, b;
+ C) i2 ]6 a$ g        reg cin;/ P% Z3 t! D/ T/ i2 D) i5 u5 d
        2 V0 @) S3 V. Z) l& f  f" k
        wire [3:0] s;$ f" O. G9 W! W$ g* X
        wire cout;5 h! P. L1 z- l& i
        
0 [) K) U2 C- `' A* U  M' v  z        cla4_adder dut(.a(a), .b(b), .cin(cin), .s(s), .cout(cout));8 W7 ]9 e# E  I7 h" K
        ' ]! m- Y2 i8 \9 E% V: C- S3 ]1 t" _: K
        integer i;
& O5 r/ B0 Z5 h: @
9 z/ J3 u  E. }  m. ^        initial begin8 {) o( n% I5 S: u# N7 B' C
                a = 0; b = 0; cin = 0;
5 u1 `% T$ S6 V" ^# v; p                forever begin2 d6 k# V7 w0 N2 w( K2 p
                        for (i=0; i<16; i=i+1) begin9 j' r- P' t+ _1 S
                                #10 a = i; b = i; cin = 0;5 F3 R( l- K* |# g. G
                                #10 a = i; b = i; cin = 1;
1 o: R0 U$ V3 s3 c9 W" _$ W                        end
4 X% O% T2 c: S- z8 b                end9 O' i& B- w, D8 L
        end% A6 r3 n+ n9 k% a: ^8 c

, Y$ H  K; K; W. \& B+ L        initial #1000 $stop;
, \) d9 n2 Z( D* \7 I9 X) H8 U
6 S& L5 m7 m& ^! @/ @endmodule
设置好仿真之后,cla4_adder仿真结果如下图。
# l4 S; Y# p/ o6 |- t7 S) b# D

+ f" P8 L' t, U* P, I" A

该用户从未签到

2#
 楼主| 发表于 2018-11-27 18:31 | 只看该作者
本帖最后由 Diabloa 于 2018-11-27 18:35 编辑 - V) F0 t- t6 A
, p& c; G/ O* z& R* B* s
转网友的,写的很不错,大家可以看看
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

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

EDA365公众号

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

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

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

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

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