[컴퓨터 구조] Multiplication

 

 

---

앞의 글을 읽으시면 이해에 도움이 됩니다.

 

2022.10.22 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Add, Sub, OverFlow

[컴퓨터 구조] Add, Sub, OverFlow

---

1. Multiplication에 들어가기에 앞서

 

 

우선 bit multiplication을 하기 전에 십진수에서의 곱셈에 대해 알아보겠습니다.

곱셈의 주축이 되는 수를 Multiplicand, 곱셈의 행위자를 Multiplier, 결과물을 Product라고 합니다.

따라서 Product의 최대 길이는 Multiplicand와 Multiplier의 길이의 합이 됩니다.

 

이미지를 통해 나타내면,

우리는 곱셈을 할 때, LSB부터 MSB까지 숫자 하나하나씩 Multiplicand와 곱해갑니다.

이때 각각의 곱셈에서 나오는 결과물은 왼쪽(자리수가 올라가는 방향)으로 shift를 합니다.

 

이것이 그대로 2진수에서도 적용됩니다.

---

2. Multiplicand

 

 

 

곱셈 회로

64-bit multiplicand register, 64-bit ALU, 64-bit Product, 32-bit multiplier이 있습니다.

이유는 아래에서 차차 설명하겠습니다.

그리고 이제 multiplicand는 mul-and로, multiplier은 mul-er로 적겠습니다. 너무 기네요..

 

mul-and register의 초깃값은 오른쪽에 mul-and가 들어가고, 남은 32-bit는 0으로 초기화합니다.

mul-er register의 초깃값은 mul-er이 그대로 들어갑니다.

product register는 모두 0으로 초기화합니다.

 

계산 순서는 아래와 같습니다.

1. mul-er reg의 LSB를, control에게 보낸다.
2. 만약 1이라면 아래의 작업(3~5)을 실행하고, 0이라면 5번 작업만 한다.
3. mul-and를 기존의 Product와 더한다. (ALU에서)
4. 덧셈 결과를 Product에 저장한다.
5. mul-and reg는 left shift, mul-er reg는 right shift한다.
6. 해당 작업은 mul-er의 bit 수만큼 진행한다.

간단하죠?

 

이때 shift를 하는 이유는 다음과 같습니다.

mul-er reg가 shift하는 이유는 LSB를 계속해서 빼내 주기 위함이고, 

mul-and reg가 shift하는 이유는 자릿수를 올려주기 위함입니다.

(mul-and reg의 자릿수를 올림으로써 product에도 똑같이 자릿수가 올라간다.)

 

0010 x 0011으로 4bit 곱셈을 그려보겠습니다.

1. multiplier의 LSB를 test하고 필요하다면 product에 mul-and를 더한다.
2. mul-and는 left shift
3. mul-er는 right shift

따라서 총 3개의 cycle이 4번 실행하므로 총 12 cycle이 진행됩니다.

 

이해가 안 된다면 따로 댓글 달아주세요.

---

3. Optimized Multiplication

 

 

위의 multiplication이 꽤 잘 작동함에도 불구하고, 저렇게 만들면 multiplication을 위한 연산기가 너무 커지기 때문에 이를 최적화해야 합니다.

 

새로운 optimized multiplication의 회로는 다음과 같습니다.

mul-and reg는 32-bit, ALU도 32-bit, product는 64-bit입니다.

 

앞선 회로와 다르게 mul-er reg가 사라졌습니다.

대신 mul-er는 product의 오른쪽에 위치하고, product의 왼쪽은 0으로 초기화합니다.

size는 줄였는데, 해당 회로에서도 곱셈이 잘 되는지는 밑에서 보도록 하겠습니다.

 

이때의 계산 순서는 아래와 같습니다.

1. Product의 LSB를 보고, control에게 보낸다.
2. LSB가 1이라면 3~5를 실행, LSB가 0이라면 5만 실행
3. mul-and와 product의 왼쪽 32-bit를 더한다. (ALU)
4. 결과를 product의 왼쪽 32-bit에 저장한다.
5. product reg를 right shift한다.
6. 해당 과정은 mul-er의 bit 수만큼 진행한다.

shift를 하는 이유는 다음과 같습니다.

계속해서 shift를 함으로써 product reg의 상위 32-bit는 자릿수가 계속 내려가게 됩니다.

따라서 오른쪽 32-bit에 해당하는 칸은 더 이상 연산에 쓰이지 않고, 고정됩니다.

 

만약 12 * 23을 한다고 가정해봅시다.

우리는 먼저 12 * 3을 하고, 36를 얻습니다.

그다음 12 * 2를 하고, 24를 얻는데, 이때 240 + 036을 합니다.

따라서 이전 연산(12 * 3)을 통해 나온 LSB(6)는 다음 연산(12 * 2)을 통해 나온 값(24)과의 덧셈에서 아무런 영향을 끼치지 않습니다.

 

따라서 상위 32-bit만 연산에 참여합니다.

 

이것도 0010 x 0011을 통해 봅시다.

mul-and는 가만히 있고, product만 계속 shift right를 합니다.

최초 연산을 통해 나온 값 0010은 shift right를 하여 0001로 만듭니다.

계속해서 shift right를 함으로써 자릿수를 내려주고, 연산에 사용하지 않는 값들은 오른쪽으로 내려줍니다.

 

1. mul-er의 LSB가 1이면 mul-and와 product의 상위 32-bit를 더한다.
2. product reg는 shift right

따라서 4 cycle만에 연산이 완료됩니다.

---

4. Signed Multiplication

 

 

부호가 있을 때는 2의 보수로 치환해서 곱셈을 합니다.

그리고 최종 결과로 MSB에 올바른 sign bit를 넣습니다.

하지만 32-bit의 곱셈임에도 불구하고, 연산은 31 iteration을 가집니다.

따라서 최종 sign bit에 올바른 bit를 넣습니다.

 

추가적으로 병렬로 multiplication을 진행하기도 하는데,

이때는 ALU가 많이 들어가기 때문에 속도는 빠르지만, 크기가 크기 때문에 trade-off 관계입니다.

---

5. Instruction

 

 

RISC-V에서는 64-bit product를 표현하기 위한 명령어가 4개나 있는데, 알아보겠습니다.

• mul (multiply) : 결과물이 32-bit
• mulh (mul high) : 두 개의 operand가 signed일 때, 64-bit product 중 상위 32-bit를 계산
• mulhu (mulh unsigned) : 두 개의 operand가 unsigned일 때, 64-bit product 중 상위 32-bit를 계산
• mulhus (mulh signed - unsigned) : operand가 signed와 unsigned일 때, 64-bit product 중 상위 32-bit를 계산

상위 32-bit만 계산하는 이유는 다음과 같습니다.

보시다시피 하위 bit는 모두 똑같고, 상위 bit만 다르기 때문입니다.

 

같은 bit를 가지고 있다 하더라도, Unsigned와 signed에 따라 값이 달라집니다.

근데 상위 bit만 달라지기 때문에 명령어를 4개로 나누어서 진행합니다.

 

다음 글에서는 나눗셈에 대해서 적겠습니다.

2022.10.23 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Division

[컴퓨터 구조] Division

 

감사합니다.

 

 

지적 환영합니다.