EDA365欢迎您登录!
您需要 登录 才可以下载或查看,没有帐号?注册
x
目前在所有的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$ Nendmodule | 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 \ |