Computer Arithmetic

Arithmetic & Logic Unit 논리연산장치

- 컴퓨터에서 계산을 수행하는 부분. control unit, register, memory, I/O와 같은 것들은 ALU를 동작시키기 위해 데이터를 가져오고, 그 결과값을 가져간다. 

- 위 그림에서 레지스터를 통해 데이터들이 들어가고, 연산 결과가 레지스터에 저장된다. 그리고 ALU는 연산의 결과로 flag를 셋한다. 예를 들어 연산 결과값이 저장될 레지스터의 길이보다 커지면 overflow flag는 1로 set된다

Integer Representation

- binary system에서, 0과 1만으로 다 표현한다

- 보통 양수만 표현하고, - 표시가 없다. 음수를 표현하기 위해 sign-magnitude, 2's complement를 쓴다

1) Sign-Magnitude

* 가장 왼쪽에 있는 비트가 sign bit이다. 0이면 양수, 1이면 음수를 의미한다 (11은 -1, 01은 1)

* 문제점 : sign과 magnitude를 둘 다 고려해야 하며, 0에 대해 두 가지 표현법이 생긴다. (+0, -0)

2) Two's Complement

* 원래 비트열에서 모든 0을 1로, 모든 1을 0으로 바꾼 뒤(Boolean complement) 1을 더한다

* 0의 표현법이 하나이고, 계산이 잘 처리된다 (부호 생각안하고 더하면 되므로 h/w 비용이 낮아진다)

A=−2n−1an−1+∑n−2i=0ai2i

* 숫자의 표현 범위는 2n−1~ 2n−1  (n은 비트 수)

- 비트 길이가 다른 것들에 대한 표현법

* Sign Extension : 양수는 가장 왼쪽에 0을 늘리고 싶은 길이만큼 추가, 음수는 1을 추가

- Negation

* 0=0000000 -> bitwise not 1111111 -> add 1 to LSB -> result 1 0000000 오버플로우는 무시되므로 똑같이 ~0=0

* -128=10000000) -> bitwise not 01111111 -> add 1 to LSB -> result 10000000 따라서 -(-128)은 에러 (8bit에서 가장 크게 표현할 수 있는 값은 127. 01111111)

- Addition & Subtraction

* 일반 2진 계산 -> monitor sign bit for overflow -> 뺄셈 연산에서는 빼는 값을 2의 보수법으로 변환 후 다른 값과 더하면 된다.

 => 따라서 addition과 complement circuit만 있으면 된다

- Multiplication

* 복잡

* 그림 8.8은 Q1101(13)과 M1011(11)을 곱하는 것이다. Unsigned Binary Mutiplication이며, 계산 방법은 위에 있는 그림 8.9의 플로우차트를 따라가면 된다

어떻게 계산하는지 보자!

* Initial Values

Q와 M을 각각 세팅하고, C와 A는 0으로 초기화한다. Count, 즉 Cycle은 4인데 아마 4비트 연산이라 4인 것 같다

* First Cycle

Initial value에서 Q0, 즉 가장 오른쪽에 있는 비트가 1인가? 그렇다. A+M, 즉 1011이 A에 들어간다. 그다음 C, A, Q를 전체적으로 오른쪽으로 shift하고 count-=1이 되어 3 사이클이 남은 상태다. Shift Right 후의 C, A, Q는 각각 0 0101 1110이고 Q0의 원래 자리에 있던 비트는 그냥 버려진다

* Second Cycle

플로우차트를 따라 다시 위로 올라갔다. Q0이 0이기 때문에 No를 따라서 밑으로 내려와 오른쪽 시프트만 하고 카운트를 하나 내린다.

* Third Cycle

이번엔 Q0이 1이기 때문에 A에 A+M의 값을 넣고 오른쪽 시프트, 카운트--한다. 이때 A의 값은 0110+1011 = 1 0001 즉 캐리가 발생한다. C에 캐리값 1을 넣고 0001은 A에 넣는다

* Fourth Cycle

또 Q0이 1이라 A에 A+M, 오른쪽 시프트, 카운트-- 한다. 카운트가 0이 되었으므로 결과값을 출력한다

=>A와 Q 값을 보면 1000 1111이고 이것이 곱셈의 결과!

* 그럼 음수를 곱할 때엔 위 알고리즘을 사용할 수 없다. 그래서 다른 솔루션이 Booth's algorithm을 이용한다.

* Principle of Booth's Algorithm

01000000 =00111111 + 1   (임의로 이렇게 자른 것)

= 00111000 + 00000111 + 1

= 00111000 + 00001000 - 1 + 1

= 00111000 + 00001000

=> 00111000 = 01000000 - 00001000  (보면 0에서 1로 변하거나 1에서 0으로 변하는 부분이 두 군데 있다 = 두 개의 형식이 나온다)

다시 표현하자면 2^n + 2^(n-1)...+2^(n-k) = 2(n+1) - 2(n-k) 이다.

예를 들면

M * (00011110) 을 한다고 했을 때 0->1, 혹은 1->0 인 부분이 두 군데 있는 것을 알 수 있다. 2^5,  2^1 부분이다

= M * (2^4 + 2^3 + 2^2 + 2^1)

= M * (16 + 8 + 4 + 2)

= M * (30)

= M * (32 - 2)

= M * (2^5 - 2^1)

* 그럼 아까처럼 알고리즘을 풀어본닷! Q = 3, M = 7로, 3*7 연산을 수행한다.

  위와 다른 점은 C 대신 Q-1이 있다는 점이다. 플로우차트를 따라가 보겠다. 마찬가지로 4비트여서 count가 4인 것 같다

* Initial Value

A와 Q-1은 0으로 초기화하고 count=4, Q=0011 M=0111이다.

* First Cycle

Q0과 Q-1을 보니 10이다. A에 A-M한 값을 넣는다. A에는 1001이 들어간다.(A가 0000이므로 단순하게 M을 2의 보수로 생각했다) A, Q, Q-1을 오른쪽으로 차례로 shift한다. A의 가장 왼쪽 부분의 비트가 1이므로 1로 채운다.

* Second Cycle

Q0과 Q-1이 11이다. 바로 시프트 시켜주고 카운트를 하나 깐다

* Third Cycle

Q0과 Q-1이 01이므로 A에 A+M인 0101을 넣는다. 오버플로우된 비트는 과감히 버린다

시프트 후 카운트도 깐다. 플로차트만 보고 하면 정말 쉽군..

* Fourth Cycle

Q0과 Q-1이 00이라 시프트만 한다. 카운트를 까서 0이 되었으므로 결과값 0001 0101을 얻었다. 십진수로 표현하면 21로 딱 맞다.

양수*음수 해도 값이 잘 나오는데 결과값이 2의 보수 값으로 표현되어 나온다

- Division

* 훠얼씬 복잡하다. 음수가 사용되면 더 그렇다. 기본적인 이진 연산은 초등학교때 배운 것처럼 상자 안에 숫자를 가둔 모양으로 할 수 있다. Unsigned binary division의 플로우차트는 둘 다 양수일 때만 성립되며, 음수가 있을 땐 둘 다 양수로 바꾼 후 계산 다 끝나고 -를 붙인다.

Floating-Point Representation

- Real Numbers

* 분수를 가진 숫자. 2진법으로도 표현 가능하긴 하다. 그런데 1/2, 1/4.. 같은 건(Fixed Point) 되는데 1/3이나 1/5같은 내용들이 생기면 안된다.

- Floating Point

* +/- . significand/Mantissa * 2^exponent

* Floating point 계산방법!

1) 십진수 -> 2진수

(-5) 를 바꿔보자. 우선 음수이므로 sign bit는 1이다. 그 다음 5를 2진수로 바꿔보면 101이다. 

이를 소수점으로 표현하면 1.01 * 2^(2)로 나타낼 수 있다. 01은 significand 부분인데, 맨 앞의 1은 무조건 채워지므로 뒤의 01만 들어가면 된다.

(2)는 biased에 들어갈 부분인데, 127과 더한다. 그러면 129! 이것을 이진으로 바꾼 것이 biased.

따라서 => 1 10000001 01000...0

(1/16) 을 해보겠다. 양수이므로 sign bit은 0이다. 1/16 값을 이진으로 바꾸면 0.0001이다. 소수점 앞에 1이 하나 오고 뒤에 알아서 해야 하기 때문에 값을 다시 표현해보면 1.0 * 2^(-4)이다. 127-4=123이고 이진으로 표현하면 01111011.

따라서 => 0 0111011 0000...0

2) 2진수 -> 10진수

그냥 위 방법에서 거꾸로 하면 된다. 위에 있는 그림의 맨 첫번째 줄을 예로 들면

biased의 10010011은 십진수로 고치면 147이다. 127 + ? = 147이므로 ?는 20, 즉 2^20이었다는 소리가 된다

significand 부분의 1010001을 1. 뒤에 붙여주어 정리하면 나와있는 것처럼 1.1010001*2^20임을 알 수 있다. 1.1010001은 고치면 1+(2^(-1) + 2^(-3) + 2^(-7)), 즉 1.638125가 된다