[컴퓨터구조] 컴퓨터 산술연산

컴퓨터 산술

컴퓨터의 출발은 4칙연산 계산기이며 지금도 근본적인 기능은 수치의 산술연산 및 논리연산이다. 산술연산은 정수와 이외의 실수 (부동소수점으로 표현)에 대한 계산이고 논리연산은 2진수로 표현되는 데이터에 대해서 (AND, OR, NOT) 등 이루어진다.

 

 

산술 및 논리연산은 ALU에서 수행하며 ALU란 CPU를 구성하는 모듈들 중 하나로 수치 및 논리 데이터에 대한 연산을 수행하는 하드웨어이다.

1. Addition and Subtraction

• bit에서의 덧셈은 십진수의 덧셈과 매우 흡사하다. 단지 컴퓨터에서는 표현할 수 있는 범위가 제한적이므로, 특정한 경우 오버플로우가 발생하게 된다.

• 덧셈에서의 overflow는 같은 sign일 때 발생한다. 두 양수를 더했을 때 음수가 나오면 overflow이다.

• Subtraction은 add로 구현하며 2의 보수로 음수를 구한다. 맨 마지막에 나온 carry-out은 무시한다.
• 양수와 음수의 뺄셈, 음수와 양수의 뺄셈일 때 오버플로우가 발생할 수 있다.

Overflow Handling

ovweflow가 무시되어야하는 메모리 주소에는 unsigned integer를 사용한다.

주소는 음수가 없기 때문에 가능한 것이다.

그럼에도 불구하고 overflow가 발생할 수 있는데 이것은 branch instruction에 의해 쉽게 처리할 수 있다.

a + b = s // s < a or s < b 이면 오버플로우
a - b = s // s > a 이면 오버플로우

 

다만, 이는 컴파일러와 같은 소프트웨어에서 처리해야 하며, 하드웨어 에서는 처리할 수 없다.

2. Multiflication

사람이 곱셈을 하게 되면

이렇게 자릿수마다 곱한 값을 더하는 방식으로 하게 된다. 이것이 그대로 2진수에도 적용된다.

 

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

 

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

 

 

 

 

 

곱셈기

 

64-bit multiplicand register, 64-bit ALU, 64-bit Product, 32-bit multiplier가 있다.

계산 순서는 아래와 같다.

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

• multiplicand register 를 left shift 하는 이유는 자리수를 올려주려고 하는 것이고
• multiplier register를 right shift 하는 이유는 LSB를 계속해서 빼내 주기 위함이다.

아래 Multiplicand 의 논리도가 있다.

• 2 X 3 = 6 예제

• 4비트이기 때문에 4번의 단계를 거친다. 결과는 8비트에 저장
• Multiplier의 LSB가 1일 때 마다 Product에 Multiplicand 를 더한다.

Optimized Multiplier

Multiplication 의 연산기가 너무 커지는 것을 방지하기 위해 이를 최적화한 곱셈기가 등장한다.

새로운 곱셈기는 Multiplier를 위한 레지스터가 없다 => 그럼 어떻게 하지?

• Multiplier 는 Product의 오른쪽에 위치하고, Product의 왼쪽은 0으로 초기화한다.

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

계속해서 right shift를 함으로써 product register의 상위 32bit는 점점 자리수가 내려가게 된다. 따라서 오른쪽 32bit에 해당하는 칸은 더 이상 연산에 쓰이지 않고, 고정된다.

원래는 multiplicand를 left shift 했는데 지금 multiplicand 는 가만히 있고 product만 계속 shift right를 한다.

1. multiplier의 LSB가 1이면 multiplicand 와 product의 상위 32-bit을 더한다.
2. product register는 shift right

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

Signed Multiplication

부호가 있을 때는 2의 보수로 치환해서 곱셈을 한다.
그리고 최종 결과로 MSB에 올바른 signbit을 넣는다.
하지만 32bit의 곱셈에도 불구하고 연산은 31 iteration을 갖는다.
따라서 최종 sign bit에 올바른 bit를 넣는다.

Booth's Multipliction

부호가 있는 이진수의 곱셈을 수행할 수 있도록 해주는 알고리즘으로, 영국의 컴퓨터 과학자인 Andrew Donald Booth에 의해 개발되었다.

매번 덧셈을 하는 것보다 더 효율적이며 한번에 2-bit씩 살핀다.

• **계산에 사용되는 수
• M : Multiplicand
• Q : Multiplier
• A : M의 비트 수 만큼 0으로 초기화 한 후 계산에 사용된다.
• q0 : 계산에 사용하는 최하위 비트
• Count : loop를 돌리는 횟수로 계산하려는 2진수의 bit수이다.
• **플로우차트

• 구현

간단하게 말하면 multplier가 처음 1을 만날 때 빼고 다음 0을 만나면 더하면 되는 것이다.

0111110

처음 1을 만날 때 Multiplicand를 빼고 1이 끝나고 0을 만날 때 Multiplicand를 더할 것이다.
이 과정에서 bit shift는 계속 일어나며 위의 Muliplier를 기준으로 2^7 - 2^1이 된다.

처음 만나는 1과 마지막 1을 어떻게 판별할까??
원래는 q0만 체크하던 걸 q0, q-1을 같이 체크한다.

• 10 : 처음 1이 시작되는 자리 Multiplicand를 뺀다.
• 01 : 1이 끝나는 자리, Multiplicand를 더한다.
• 00, 11 : 아무것도 하지 않는다.

• 의의 : 1이 연속으로 올 때는 이 방법을 사용하면 덧셈숫자가 줄어들기 때문에 더 빠른 곱셈 연산이 가능하다.
• 단점 : 하지만 01010101 과 같은 경우는 일반적이라면 4번만 더하면 되지만 Booth의 알고리즘을 사용하면 4번 더하고 4번 뺌으로써 연산 횟수가 늘어난다.
  • Modify Booth's Algorithm : q1, q0, q-1 3비트를 본다. (고립된 0 혹은 1을 알 수 있어서)

32비트 곱셈은 평균적으로 16개의 0, 16개의 1을 사용하기 때문에 덧셈을 많이 하게 되어 비효율적이다.

Faster Multiplier

한꺼번에 다 하겠다. 병렬로 구현한 Multiplier,

• 32비트 기준으로 처음에는 32번의 덧셈 , 16번의 덧셈, 8번 ... 처럼 점점 연산횟수가 줄어든다. -> 6step 만에 가능하다.
• 하지만 하드웨어 cost가 많이 들고 공간도 많이 사용하고 성능을 높이는데 돈이 많이 든다.

Multiplication instruction

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

왜 상위 32-bit만 계산할까?

 

보다시피 하위 bit는 모두 같고 상위 bit만 다르기 때문이다.

 

같은 bit를 가지고 있다고 하더라도 Unsigned와 Signed에 따라 값이 달라진다.

 

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

3. Division

Multiplication보다 훨씬 복잡하다.

Division을 당하는 값은 Dividend, Division을 하는 값은 Divisor, 몫은 Quotient, 나머지는 Remainder 이다.

우리는 나눗셈을 할 때 Dividend의 맨 처음부터 Divisor를 빼고, 만약에 빼진다면 Quotient에 1을 적는다.
만약 빼지지 않는다면, 그 다음 비트에서 Divisor를 뺀다.

$$ Dividend = Quotient X Divisor + Remainder $$

이 때 해당 수식이 성립해야 한다.

Divisor는 0이 되면 안되므로 항상 0이 아니다.

Division Hardware

몫 레지스터 64비트를 0으로 초기화하고 시작한다.

 

나눗셈 알고리즘은 매번 반복할 때마다 Divisor를 오른쪽으로 한 비트씩 이동해야 한다.

 

따라서 Divisor를 128비트 Divisor register의 왼쪽 절반에 넣고 시작한다.

 

그리고 Dividend 와 자리를 맞추기 위해 반복할 때마다 오른쪽으로 한 비트씩 자리이동한다.

 

remainder register는 Dividend로 초기화한다.

 

또한 컴퓨터는 두 수 중 어느 수가 작은지 한 번에 보고 판단할 수 없기 때문에 Dividend에서 Divisor를 빼주며 판단하는데, 이 때

 

Dividend는 나머지 레지스터에 담겨있다.

 

만약 이 결과가 양수이면 Divisor는 Dividend와 같거나 더 작다.

 

따라서 몫의 LSB에 1을 추가한다.

 

만약 결과가 음수라면 Divisor를 나머지 레지스터에 다시 더함으로써 원래의 값을 회복하며, 몫에서는 0을 넣는다.

 

이를 논리도로 살펴보자

1. Remainder를 Dividend로 초기화한다.
2. Remainderd에서 Divisor를 빼준다.
   • 빼고난 값이 0 이상이면 몫 LSB 1 더해준다.
   • 0보다 작으면 다시 Remainder에 Divisor를 더해준다.
3. Divisor Register를 shift right 한다.
4. 비트수만큼 반복한다.

이를 논리회로로 구현하면

Optimized Divisor

Remainder Register의 우측 32비트는 Dividend로 초기화한다.

연산을 진행함에 따라서 Remainder Register의 좌측은 Remainder, 우측은 Quotient가 위치한다.

1. 우선 Remainder의 Register에서 Divisor를 뺀다.
2. Remainder Register의 MSB가 1이라면 복구하고, Shift left(0이 추가) 한다.
3. Remainder Register의 MSB가 0이라면 그대로 놔두고, Remainder Register에 Shift left(1이 추가)를 한다.
4. 해당 과정을 bit + 1만큼 반복하고, Remainder Register의 좌측 절반을 Right shift 한다.

우선 Remainder Register를 shift left를 하는 이유는 Dividend의 자릿수를 올림으로써 나눗셈을 진행하기 위함이다.

Signed Division

부호가 있는 나눗셈을 할 때는 Remainder 부호와 Dividend의 부호를 맞춰준다.

 

-7 / 2라면 Q는 -3, R은 -1이 된다.

 

실제로는 절댓값으로 Quotient, Remainder를 계산한 후 remainder와 Dividend의 부호를 맞춰줌

Non-Restoring Division

복원하지 않는 나눗셈이다.

Resotring 하는데 많은 시간이 소요되기 때문에 더 효율적으로 동작하기 위해 나왔다.

Remainder의 MSB가 1이라면 (음수라면) 복원하지 않고, divisor를 더해준다.
만약 MSB가 0이라면 divisor를 빼준다.

• V: divisor
• R: remainder의 오른쪽

1. Remainder를 shift left 한다.
2. Remainder의 MSB를 확인
   • 0일경우 : Divisor를 빼준다.
   • 1일경우 : Divisor를 더해준다.
3. Remainder의 부호 확인
   • 양수일 경우 : R[0] 에 1을 더해준다.
   • 음수일 경우 : R[0] 을 그대로 둔다 (값 : 0)
4. Divisor의 비트 수 만큼 반복한다.

이해하는데 정말 힘들었다.

참고

https://hi-guten-tag.tistory.com/254
https://ttl-blog.tistory.com/1012
https://dogrushdev.tistory.com/206
https://suintodev.tistory.com/3
https://scarletbreeze.github.io/articles/2018-04/%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0%EB%A1%A0(%EB%B3%B4%EC%B6%A93)