Kogge-Stone 树形加法器
Kogge-Stone 树形加法器
1. Kogge-Stone
Kogge-Stone 加法器是利用 Peter M. Kogge 和 Harold S.Stone 于 1972 年提出的一
种并行算法生成的一种树形加法器。此种加法器在树形加法器中,具有逻辑层数低和较
低的扇入扇出的特点,美中不足的是布线拥塞度高。
2. 超前进位加法器
(1)超前进位加法器
S
i
=
p
i
⊕
C
i
−
1
S_i=p_i \oplus C_{i-1}
Si=pi⊕Ci−1
C
i
=
g
i
+
C
i
−
1
⋅
g
i
C_i=g_i + C_{i-1} \cdot g_i
Ci=gi+Ci−1⋅gi
C
0
=
C
i
n
C_0=C_{in}
C0=Cin
C
o
u
t
=
C
i
n
C_{out}=C_{in}
Cout=Cin
进位项和产生项如下:
p
i
=
A
i
⊕
B
i
p_i=A_i \oplus B_i
pi=Ai⊕Bi
g
i
=
A
i
⋅
B
i
g_i=A_i \cdot B_i
gi=Ai⋅Bi
重点要解决的是进位链问题,进位链表达式形似一阶递归。
C
i
=
g
i
+
C
i
−
1
⋅
p
i
C_i=g_i + C_{i-1} \cdot p_i
Ci=gi+Ci−1⋅pi
x
i
=
a
i
⋅
x
i
−
1
+
b
i
x_i=a_i \cdot x_{i-1} + b_i
xi=ai⋅xi−1+bi
3. Koggle-Stone 并行算法
对于序列
x
1
x_1
x1,
x
2
x_2
x2,
x
3
x_3
x3,
⋯
\cdots
⋯,
x
N
x_N
xN,满足
x
i
=
f
(
x
i
−
1
,
x
i
−
2
,
⋯
,
x
i
−
m
)
x_i=f(x_{i-1},x_{i-2},\cdots,x_{i-m})
xi=f(xi−1,xi−2,⋯,xi−m)。一阶递归问题如下:
x
i
=
a
i
⋅
x
i
−
1
+
b
i
x_i=a_i \cdot x_{i-1} + b_i
xi=ai⋅xi−1+bi
定义函数:
Q
^
(
m
,
n
)
=
∑
j
=
n
m
(
∏
r
=
j
+
1
m
a
r
)
⋅
b
r
\displaystyle \hat Q(m,n)= \sum \limits_{j=n}^{m} (\prod_{r=j+1}^{m} a_r) \cdot b_r
Q^(m,n)=j=n∑m(r=j+1∏mar)⋅br
此外:
∏
r
=
m
+
1
m
a
r
=
1
\displaystyle \prod_{r=m+1}^{m} a_r=1
r=m+1∏mar=1
可得到如下结果:
x
1
=
b
1
=
Q
^
(
1
,
1
)
\displaystyle x_1=b_1=\hat Q(1,1)
x1=b1=Q^(1,1)
x
2
=
a
2
⋅
x
1
+
b
2
=
a
2
⋅
b
1
+
b
2
=
Q
^
(
2
,
1
)
\displaystyle x_2=a_2 \cdot x_1 + b_2=a_2 \cdot b_1 + b_2=\hat Q(2,1)
x2=a2⋅x1+b2=a2⋅b1+b2=Q^(2,1)
x
3
=
a
3
⋅
x
2
+
b
3
=
a
3
⋅
a
2
⋅
b
1
+
a
3
⋅
b
2
+
b
3
=
Q
^
(
3
,
1
)
\displaystyle x_3=a_3 \cdot x_2 + b_3=a_3 \cdot a_2 \cdot b_1+a_3 \cdot b_2 +b_3=\hat Q(3,1)
x3=a3⋅x2+b3=a3⋅a2⋅b1+a3⋅b2+b3=Q^(3,1)
x
4
=
a
4
⋅
x
3
+
b
4
=
⋯
=
Q
^
(
4
,
1
)
\displaystyle x_4=a_4 \cdot x_3 + b_4= \cdots =\hat Q(4,1)
x4=a4⋅x3+b4=⋯=Q^(4,1)
x
5
=
a
5
⋅
x
4
+
b
5
=
⋯
=
Q
^
(
5
,
1
)
\displaystyle x_5=a_5 \cdot x_4 + b_5= \cdots =\hat Q(5,1)
x5=a5⋅x4+b5=⋯=Q^(5,1)
x
6
=
a
6
⋅
x
5
+
b
6
=
⋯
=
Q
^
(
6
,
1
)
\displaystyle x_6=a_6 \cdot x_5 + b_6= \cdots =\hat Q(6,1)
x6=a6⋅x5+b6=⋯=Q^(6,1)
x
7
=
a
6
⋅
x
6
+
b
7
=
⋯
=
Q
^
(
7
,
1
)
\displaystyle x_7=a_6 \cdot x_6 + b_7= \cdots =\hat Q(7,1)
x7=a6⋅x6+b7=⋯=Q^(7,1)
x
8
=
a
8
⋅
x
7
+
b
8
=
⋯
=
Q
^
(
8
,
1
)
\displaystyle x_8=a_8 \cdot x_7 + b_8= \cdots =\hat Q(8,1)
x8=a8⋅x7+b8=⋯=Q^(8,1)
即可得到如下形式:
Q
^
(
1
,
1
)
=
x
1
=
b
1
\displaystyle \hat Q(1,1)=x_1=b_1
Q^(1,1)=x1=b1
Q
^
(
2
,
1
)
=
x
2
=
a
2
⋅
b
1
+
b
2
=
a
2
⋅
Q
^
(
1
,
1
)
+
Q
^
(
2
,
2
)
\displaystyle \hat Q(2,1)=x_2=a_2 \cdot b_1 + b_2=a_2 \cdot \hat Q(1,1) + \hat Q(2,2)
Q^(2,1)=x2=a2⋅b1+b2=a2⋅Q^(1,1)+Q^(2,2)
Q
^
(
3
,
1
)
=
x
3
=
a
3
⋅
x
2
+
b
3
=
a
3
⋅
a
2
⋅
Q
^
(
1
,
1
)
+
Q
^
(
3
,
2
)
\displaystyle \hat Q(3,1)=x_3=a_3 \cdot x_2 + b_3=a_3 \cdot a_2 \cdot \hat Q(1,1) + \hat Q(3,2)
Q^(3,1)=x3=a3⋅x2+b3=a3⋅a2⋅Q^(1,1)+Q^(3,2)
Q
^
(
4
,
1
)
=
x
4
=
a
4
⋅
x
3
+
b
4
=
a
4
⋅
a
3
⋅
Q
^
(
2
,
1
)
+
Q
^
(
4
,
3
)
\displaystyle \hat Q(4,1)=x_4=a_4 \cdot x_3 + b_4=a_4 \cdot a_3 \cdot \hat Q(2,1) + \hat Q(4,3)
Q^(4,1)=x4=a4⋅x3+b4=a4⋅a3⋅Q^(2,1)+Q^(4,3)
Q
^
(
5
,
1
)
=
x
5
=
a
5
⋅
x
4
+
b
5
=
a
5
⋅
a
4
⋅
a
3
⋅
a
2
⋅
Q
^
(
1
,
1
)
+
Q
^
(
5
,
2
)
\displaystyle \hat Q(5,1)=x_5=a_5 \cdot x_4 + b_5=a_5 \cdot a_4 \cdot a_3 \cdot a_2 \cdot \hat Q(1,1) + \hat Q(5,2)
Q^(5,1)=x5=a5⋅x4+b5=a5⋅a4⋅a3⋅a2⋅Q^(1,1)+Q^(5,2)
Q
^
(
6
,
1
)
=
x
6
=
a
6
⋅
x
5
+
b
6
=
a
6
⋅
a
5
⋅
a
4
⋅
a
3
⋅
Q
^
(
2
,
1
)
+
Q
^
(
6
,
3
)
\displaystyle \hat Q(6,1)=x_6=a_6 \cdot x_5 + b_6=a_6 \cdot a_5 \cdot a_4 \cdot a_3 \cdot \hat Q(2,1) + \hat Q(6,3)
Q^(6,1)=x6=a6⋅x5+b6=a6⋅a5⋅a4⋅a3⋅Q^(2,1)+Q^(6,3)
Q
^
(
7
,
1
)
=
x
7
=
a
7
⋅
x
6
+
b
7
=
a
7
⋅
a
6
⋅
a
5
⋅
a
4
⋅
Q
^
(
3
,
1
)
+
Q
^
(
7
,
4
)
\displaystyle \hat Q(7,1)=x_7=a_7 \cdot x_6 + b_7=a_7 \cdot a_6 \cdot a_5 \cdot a_4 \cdot \hat Q(3,1) + \hat Q(7,4)
Q^(7,1)=x7=a7⋅x6+b7=a7⋅a6⋅a5⋅a4⋅Q^(3,1)+Q^(7,4)
Q
^
(
8
,
1
)
=
x
8
=
a
8
⋅
x
7
+
b
8
=
a
8
⋅
a
7
⋅
a
6
⋅
a
5
⋅
Q
^
(
4
,
1
)
+
Q
^
(
8
,
5
)
\displaystyle \hat Q(8,1)=x_8=a_8 \cdot x_7 + b_8=a_8 \cdot a_7 \cdot a_6 \cdot a_5 \cdot \hat Q(4,1) + \hat Q(8,5)
Q^(8,1)=x8=a8⋅x7+b8=a8⋅a7⋅a6⋅a5⋅Q^(4,1)+Q^(8,5)
树形图:
4. 树形结构
进位链
C
i
=
g
i
+
C
i
−
1
⋅
p
i
C_i=g_i + C_{i-1} \cdot p_i
Ci=gi+Ci−1⋅pi
x
i
=
a
i
⋅
x
i
−
1
+
b
i
x_i=a_i \cdot x_{i-1} + b_i
xi=ai⋅xi−1+bi
8比特的加法器进位链并行计算的Kogge-Stone形式的树形结构如下图所示:
以此类推:16比特的加法器进位链并行计算的Kogge-Stone形式的树形结构如下图所示:
5. 16位加法器实现
-
仿真
-
RTL原理图
-
源代码及测试代码在资源界面,可下载获取
6. 参考资料
- 论文:A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
- 知乎:纸上谈芯