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