High Speed Multiplication

개요

고속으로 처리할 수 있는 곱셈기를 만드는 방법은 두가지로 나뉜다. 

1) Partial Product의 개수를 줄인다

2) 덧셈 처리 시간을 줄인다

- Parallel Multiplier

병렬로 partial product를 처리한 후 고속으로 결과들을 더하여 처리한다

- High Speed Sequential Multiplier

축적하는 형태로 새로운 partial product의 결과를 기존의 것에 더해준다

- Array Multiplier

>??

6.1 Reducing The Number Of Partial Products

Booth Algorithm

두개 이상의 partial product를 동시에 처리할 수 있게 만들어 졌다.

예를 들어 2개의 partial product를 동시에 처리하기 위해서 A x B 에서 A, 2A, 3A 값을 미리 알고 있어야 한다

그러나 3A값을 알기 위해서는 1bit shift 후 A를 한번더 더해줘야한다는 복잡함이 있다.

이를 해결하기 위해서 Booth Algorithm을 사용한다

* 원리

                      

위의 과정을 통해 m 개의 1들의 partial product를 모두 구하지 않고 단 2개의 partial product로 결과가 구해질 수 있다. 

그중 하나는 -1이 곱해져야한다 (complemented)

우리는 위와 같이 동작하는 방식을 recoding이라고 하며 가장 간단한 방법으로 booth algorithm이 있다

		Operation
0	0	shift only	0
1	1	shift only	0
1	0	subtract and shift	-1
0	1	add and shift	1

Xi의 가중치를 -1, Xi-1의 가중치를 1로 둔 후 더해주면 Yi가 구해진다

multiplier 가 0011110011 일 때 booth recoding을 사용하면 01000(-1)010(-1) 이 되어 6번의 add/subtract 연산이 4번으로 줄어든다.

가장 앞에 bit에 임의로 0을 추가해 주어야한다 (x_-1 = 0)

* two's complement 를 고려할 경우

       

---

기본적인 곱셈 연산에서는 A를 signed bit 이전 까지 진행한 후 signed bit가 1일경우 결과 값에 A를 빼주었다 

signed bit에서는 마지막 shift가 없다

booth 알고리즘에서는 2의 보수가 추가되어도 결과는 동일하다. 이는 다음표로 설명이 가능하다.

multiplier를 5bit라고 할 경우.

1	0	1	1	0	0 (Added)
4'	3'	2'	1'	0'	-1'
				-1	1
			-2	2
		-4	4
	-8	8
-16	16

2'에 1이 있을 경우 4 가 추가 되지만 signed bit에 1이 또한 존재할 경우 -16 또한 추가되어 -12를 나타낼 수 있다 

00100 => 4

10100 => -12

Ex) 10110 을 A에 곱한면 -16, 4, 2가 살아남아 -10 의 결과가 나온다

* Verilog

// 5bit booth multiplier

module BoothMul(a, b, s);

input [4:0] a, b;

output [2*5-1:0] s;

wire [2*5-1:0] s;

wire [4:0] pp1, pp2, pp3, pp4, pp5; // partial product

wire [5:0] ps1, ps2, ps3, ps4, ps5;

assign pp1 = {5{b[0]}} ^ ({5{(b[0] ^ 1'b0)}} & a);      

assign pp2 = {5{b[1]}} ^ ({5{(b[1] ^ b[0])}} & a);

assign pp3 = {5{b[2]}} ^ ({5{(b[2] ^ b[1])}} & a);

assign pp4 = {5{b[3]}} ^ ({5{(b[3] ^ b[2])}} & a);

assign pp5 = {5{b[4]}} ^ ({5{(b[4] ^ b[3])}} & a);

assign ps1 = {pp1[4],pp1} + b[0];

assign ps2 = {pp2[4],pp2} + {ps1[5],ps1[5:1]} + b[1];

assign ps3 = {pp3[4],pp3} + {ps2[5],ps2[5:1]} + b[2];

assign ps4 = {pp4[4],pp4} + {ps3[5],ps3[5:1]} + b[3];

assign ps5 = {pp5[4],pp5} + {ps4[5],ps4[5:1]} + b[4];

assign s = { ps5, ps4[0], ps3[0], ps2[0], ps1[0] };

endmodule

Verilog. radix-2 booth multiplier

시뮬레이션 결과

* 단점

 1) sub/add 연산의 개수가 곱셈 마다 달라진다  , synchronous multiplier을 만들 수 없다.

 2) 001010101 을 recoding 할 경우 01(-1)1(-1)1(-1)1(-1) 이 되어 연산이 더욱 복잡해 진다.

 이러한 단점들을 radix-4 modified Booth's algorithm 을 사용하여 줄일 수 있다.

Radix-4 Modified Booth's Algorithm

세개의 partial product를 한번에 처리하기 위해서 사용된다

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	2
1	0	0	-2
1	0	1	-1
1	1	0	-1
1	1	1	0

Xi의 가중치를 -2, Xi-1의 가중치를 1, Xi-2의 가중치를 로 둔 후 더해주면 Yi가 구해진다

0	1	0	1	0	1	0 (Added)
5'	4'	3'	2'	1'	0'	-1'
				-2	1	1
		-8	4	4
-32	16	16

2의 보수 표기 법에 대해서도 성립 한다는 것을 알 수 있으며 해당 알고리즘을 사용하기 위해서

bit의 개수가 짝수이어야 한다는 것을 알 수 있다. 홀수 개일 경우 signed bit extention이 필요하다.

ex)

010101    =>    010101

001010    =>    010(-1)0(-1) 와 같이 연산의 개수가 늘어나는 경우도 생기지만 radix-2에 비해 매우 적어 안심하고 사용가능하다.

* synchronous

n/2 partial product를 갖는 n-bit synchronous multiplier을 제작할 수 있다. 

alternative 2-bit-at-a-time multiplication

Booth 알고리즘을 이용할 때 위와 같은 경우만 있는 것이 아니다. 위의 방법은 기준점을 오른쪽으로 잡고 -2,1,1 배 되도록 했지만 기준점을 중심으로 잡는 방법도 있다. 기준이 중심으로 왔기 때문에 가중치는 2배 더 커진 -4,2,2 가 된다

0	0	0	0
0	0	1	2
0	1	0	2
0	1	1	4
1	0	0	-4
1	0	1	-2
1	1	0	-2
1	1	1	0

signed bit (0)	0	1	0	1	0	1
	5'	4'	3'	2'	1'	0'
				-4	2	2
		-16	8	8
-64	32	32
-64	32	16	8	4	2	2

그러나 이 방법을 사용할 때 1번째 bit의 값이 1을 가져야 하지만 2를 갖게 되므로 A만큼 한번 빼줘야 한다

x0 이 1일 경우 initial 값을 0으로 두지 않고 -1로 둔다  (example 6.5 확인)

Canonical recording

주어진 숫자를 가장 적은 개수의 1과 -1 로 표현 할 수 있도록 한다

0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	-1	1
1	1	0	-1	1
1	1	1	0	1

ex) 

01101110 => 0100(-1)00(-1)0

5번의 partial product가 3번으로 줄었다 , 3번이 110의 가장 적은 partial product이다.

[참고] Computer Arithmetic Algorithms , Israel Koren