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=piCi1

C

i

=

g

i

+

C

i

1

g

i

C_i=g_i + C_{i-1} \cdot g_i

Ci=gi+Ci1gi

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=AiBi

g

i

=

A

i

B

i

g_i=A_i \cdot B_i

gi=AiBi

重点要解决的是进位链问题,进位链表达式形似一阶递归。

C

i

=

g

i

+

C

i

1

p

i

C_i=g_i + C_{i-1} \cdot p_i

Ci=gi+Ci1pi

x

i

=

a

i

x

i

1

+

b

i

x_i=a_i \cdot x_{i-1} + b_i

xi=aixi1+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(xi1,xi2,,xim)。一阶递归问题如下:

x

i

=

a

i

x

i

1

+

b

i

x_i=a_i \cdot x_{i-1} + b_i

xi=aixi1+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=nm(r=j+1mar)br

此外:

r

=

m

+

1

m

a

r

=

1

\displaystyle \prod_{r=m+1}^{m} a_r=1

r=m+1mar=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=a2x1+b2=a2b1+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=a3x2+b3=a3a2b1+a3b2+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=a4x3+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=a5x4+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=a6x5+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=a6x6+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=a8x7+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=a2b1+b2=a2Q^(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=a3x2+b3=a3a2Q^(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=a4x3+b4=a4a3Q^(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=a5x4+b5=a5a4a3a2Q^(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=a6x5+b6=a6a5a4a3Q^(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=a7x6+b7=a7a6a5a4Q^(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=a8x7+b8=a8a7a6a5Q^(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+Ci1pi

x

i

=

a

i

x

i

1

+

b

i

x_i=a_i \cdot x_{i-1} + b_i

xi=aixi1+bi

8比特的加法器进位链并行计算的Kogge-Stone形式的树形结构如下图所示:在这里插入图片描述
以此类推:16比特的加法器进位链并行计算的Kogge-Stone形式的树形结构如下图所示:
在这里插入图片描述

5. 16位加法器实现

  1. 仿真
    在这里插入图片描述

  2. RTL原理图
    在这里插入图片描述

  3. 源代码及测试代码在资源界面,可下载获取

6. 参考资料

  1. 论文:A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
  2. 知乎:纸上谈芯

版权声明:本文为qq_36215315原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>