[컴퓨터 구조] 컴퓨터 연산[2] - 곱셈

 

 

 

 

🧐 곱셈

곱셈은 다음과 같은 과정을 통해 계산됩니다.

 

 

첫 번째 피연산자는 피승수(multiplicand)라고 부르고, 두 번째 피연산자는 승수(multiplier)라고 부릅니다.

최종 결과는 곱(product)라고 부릅니다.

 

주목할 점은 곱셈의 최종 결과의 자릿수가 피승수나 승수와 비교하여 상당히 크다는 것입니다.

부호 비트를 무시한다면 n비트의 피승수에 대한 m비트 승수의 곱셈 결과는 n + m 의 결과를 갖습니다.

 

결국 모든 가능한 곱을 표현하기 위해서는 n + m 비트가 필요합니다.

따라서 덧셈과 마찬가지로 오버플로우 문제가 발생합니다.

 

 

우선 이후 생각하도록 하고, 이진수 곱셈의 과정을 살펴보도록 하겠습니다.

 

 

 

 

 

 

 

 

🧐 곱셈 알고리즘의 기본 아이디어

승수는 64비트 승수 레지스터에 저장되어 있으며, 128비트 결과 레지스터는 0으로 초기화되어있다고 가정하겠습니다.

곱셈의 매 단계마다 피승수를 왼쪽으로 한 칸씩 이동시키고, 필요하면 중간 결과에 더해주는 식으로 계산되어야 합니다.

또한 승수는 매 단계마다 오른쪽으로 이어주어야 합니다.

 

이렇게 64단계를 거치면 64비트 피승수가 왼쪽으로 64번 이동하게 됩니다.

 

따라서 128비트 피승수 레지스터가 필요합니다.

이 레지스터의 오른쪽 절반은 64비트 피승수로, 왼쪽 절반은 0으로 초기화됩니다.

이 레지스터는 128비트 결과 레지스터에 축적되는 합과 피승수의 위치를 맞추기 위해 매 단계마다 1비트 왼쪽으로 자리이동합니다.

 

아래는 위 알고리즘의 논리도입니다.

 

 

 

아래는 위를 구현한 논리회로입니다.

 

 

 

 

 

 

⭐️ 예시

간단한 곱셈 예시를 통해 과정을 살펴보도록 하겠습니다.

반복	단계		승수	피승수	결과
0	초기값		0011	0000 0010	0000 0000
1	[승수]의 LSB가 [1]이므로 [피승수 + 결과]		0011	0000 0010	0000 0010
	[피승수]를 [왼쪽]으로 1칸 Shift		0011	0000 0100	0000 0010
	[승수]를 [오른쪽]으로 1칸 Shift		0001	0000 0100	0000 0010
2	[승수]의 LSB가 [1]이므로 [피승수 + 결과]		0001	0000 0100	0000 0110
	[피승수]를 [왼쪽]으로 1칸 Shift		0001	0000 1000	0000 0110
	[승수]를 [오른쪽]으로 1칸 Shift		0001	0000 1000	0000 0110
3	[승수]의 LSB가 [0]이므로 [수행 X]		0000	0000 1000	0000 0110
	[피승수]를 [왼쪽]으로 1칸 Shift		0000	0001 0000	0000 0110
	[승수]를 [오른쪽]으로 1칸 Shift		0000	0001 0000	0000 0110
4	[승수]의 LSB가 [0]이므로 [수행 X]		0000	0001 0000	0000 0110
	[피승수]를 [왼쪽]으로 1칸 Shift		0000	0010 0000	0000 0110
	[승수]를 [오른쪽]으로 1칸 Shift		0000	0010 0000	0000 0110

 

 

 

 

 

 

 

 

 

 

🧐 곱셈 인스트럭션

RISC-V 에서는 mul, mulh(multuply high), mulhu(multuply high unsigned),mulhsu(multuply high signed-unsigned) 의 네 가지 명령어를 사용하여 부호있는, 또는 부호없는 64비트 곱을 구합니다.

 

h가 붙은 것들은 곱셈의 결과 상위 64비트를 얻기 위하여 사용되고, 붙지 않은 것들은 하위 64비트를 얻기 위해 사용합니다.

 

두 피연산자가 모두 부호없는 수라면 u, 한쪽은 부호가 있고 다른 한쪽은 부호가 없다면 su를 사용합니다.