[컴퓨터 구조]Chapter 3. Arithmetic for Computers

계산하는 방법에 대해서 강의를 촬영하고 Youtube업로드 할 예정입니다.

[Multiplication]

- 개선전 곱셈

[인터넷 강의 준비중 - 10월 말 촬영]

곱셈 방법

[1 단계] 승수의 최하위비트는 피승수를 곱레지스터에 더할지 말지를 결정

-> 승수의 최하위비트가 1이라면 피승수를 곱레지스터에 더한다. 승수의 최하위비트가 0이라면 피승수를 곱레지스터에 더하지 않고 대신 0을 더한다. 

[2 단계] 피연산자를 왼쪽으로 이동시키는 역할

[3 단계] 다음번 반복에서 검사할 승수의 다음비트를 준비하기 위해 오른쪽 자리이동

-> 32비트 숫자를 곱할 때 약 100개 정도의 클락싸이클 

- 최적화 곱셈

곱셈 방법

승수를 곱레지서트의 64비트의 오른쪽에 넣는다.

Product와 피승수(Multiplicand)의 덧셈결과는 Product Register 64비트의 왼쪽에 넣는다. 

이후  Product를 Shift Right을 한다. 

[인터넷 강의 준비중 - 10월 말 촬영]

[Division]

- 개선전 나눗셈

[인터넷 강의 준비중 - 10월 말 촬영]

나눗셈 방법

[1 단계] Check for 0 divisor

[2 단계] Long division approach

If divisor <= dividend bits, 1 bits in quotient, subtract.

Otherwise, 0 bits in quotient, bring down next dividend bit.

[3 단계] Restoring division

Do the subtract, and if remainder goes < 0, add divisor back

[4 단계] Signed division

Divide using absolute values/

Adjust sign of quotient and remainder as required.

- 최적화 나눗셈

[인터넷 강의 준비중 - 10월 말 촬영]

[Floating Point]

- IEEE Floating-point Format

	Single : 8 bits	Single : 23bits
	Double : 11bits	Double : 52bits
S	Exponents	Fraction

(이미지 출처 : https://archive.cnx.org/contents/cd645ee4-27ff-4f36-9a50-1d2947da0711@3/floating-point-numbers-history-of-ieee-floating-point-format)

x = (-1)^s * (1 + Fraction) * 2 ^(Exponent - Bias)

-    s : 부호 비트(sign bit), 0이면 양수, 1이면 음수이다.

-    Normalize significand : 1.0 <= |significand| < 2.0

Always has a leading pre-binary-point 1 bit, so no need to represent it explicitly(hidden bit) - Normalize된  floating point는 항상 정수부에 1이 들어간다. 따라서 이를 다 표현할 필요 없이 생략한다. 바이너리 표현을 소수로 표현할 때 이를 복구해줘야 한다.

Significand is Fraction with the "1" restored.

Exponent : excess representation : actual Exponent + Bias

Ensure exponent is unchanged

Single: Bias = 127, Double: Bias = 1203

[Denormal Numbers]

- Exponent 000 ... 000과 11111111은 예약되어 있는 수이다.

- Exponent = 000 ... 000일 경우 히든 비트가 0이라는 뜻이다. 

- Exponent = 1111111이고 Faction이 000 ... 000라면 결과가 ±Infinity 이다.

- Exponent = 1111111이고 Faction이 000 ... 000아니라면 Not-a-number(NaN)이다. 이 말은 정의 되지 않는 결과를 말한다. 예를 들어서 0.0 / 0.0이다. 

[Floating Point Addition]

 수가 있다고 가정하자.

1. Align decimal points

Shift number with smaller exponent(작은 지수를 갖는 수의 소수점을 정렬)

2. Add significands

3. Normalize result & check for over/underflow 

4. Round and renormalize if necessary

(유호숫자 자리수를 네 자리수로 가정)

- Normalized 하면 다음과 같은 이점이 있다. 

[1] 데이터 전송이 간단하게 할 수 있다.  

[2] floating-point 연산 알고리즘을 단순화 할 수 있다.

[3] 선행되는 0이 없어지기 떄문에 수의 정확도가 증가한다.

- Extraordinary

Overflow : exponent is too large to be re

Underflow : negative exponent is too large to fit in the exponent field.

[Single-Precision Range]

- Exp

[Problem solving]

3.12 [20] <§3.3> Using a table similar to that shown in Figure 3.6, calculate the product of the octal unsigned 6-bit integers 62 and 12 using the hardware described in Figure 3.3. You should show the contents of each register on each step.

[해석] 그림 3.6에서 보여주는 표를 사용하기, 그림 3.3에서 설명한 하드웨어를 사용하여 8진수 부호 없는 6비트 정수인 62와 12의 곱을 계산하라. 각 단계에서 레지스터의 내용들을 보여 주어야 한다.

 

[풀이]

Iteration	Step	Multiplier	Multiplicand	Product
0	Initial value	110010	0000 0000 1010	0000 0000 0000
1	1: 0 -> No operation	110010	0000 0000 1010	0000 0000 0000
	2: Shift right Multiplier	011001	0000 0000 1010	0000 0000 0000
	3: Shift left Multiplicand	011001	0000 0001 0100	0000 0000 0000
2	1: a: 1-> Prod = Prod + Mcand	011001	0000 0001 0100	0000 0001 0100
	2: Shift right Multiplier	001100	0000 0001 0100	0000 0001 0100
	3: Shift left Multiplicand	001100	0000 0010 1000	0000 0001 0100
3	1: 0 -> No operation	001100	0000 0010 1000	0000 0001 0100
	2: Shift right Multiplier	000110	0000 0010 1000	0000 0001 0100
	3: Shift left Multiplicand	000110	0000 0101 0000	0000 0001 0100
4	1: 0 -> No operation	000110	0000 0101 0000	0000 0001 0100
	2: Shift right Multiplier	000011	0000 0101 0000	0000 0001 0100
	3: Shift left Multiplicand	000011	0000 1010 0000	0000 0001 0100
5	1: a: 1-> Prod = Prod + Mcand	000011	0000 1010 0000	0000 1011 0100
	2: Shift right Multiplier	000001	0000 1010 0000	0000 1011 0100
	3: Shift left Multiplicand	000001	0001 0100 0000	0000 1011 0100
6	1: a: 1-> Prod = Prod + Mcand	000001	0001 0100 0000	0001 1111 0100
	2: Shift right Multiplier	000000	0001 0100 0000	0001 1111 0100
	3: Shift left Multiplicand	000000	0010 1000 0000	0001 1111 0100

3.13 [20] <§3.3> Using a table similar to that shown in Figure 3.6, calculate the product of the hexadecimal unsigned 8-bit integers 62 and 12 using the hardware described in Figure 3.5. You should show the contents of each register on each step.

[해석] 그림 3.6에서 보인 것과 같은 표를 이용하고, 그림 3.5에서 설명한 하드웨어를 사용하여 16진수 부호 없는 8비트 정수인 62와 12의 곱을 계산하라. 각 단계에서 레지스터의 내용을 보여 주어야 한다.

Iteration	Step	Multiplicand	Product
0	Initial value	0110 0010	0000 0000 0001 0010
1	1	0110 0010	0000 0000 0001 0010
	2, 3	0110 0010	0000 0000 0000 1001
2	1a	0110 0010	0110 0010 0000 1001
	2, 3	0110 0010	0011 0001 0000 0100
3	1	0110 0010	0011 0001 0000 0100
	2, 3	0110 0010	0001 1000 1000 0010
4	1	0110 0010	0001 1000 1000 0010
	2, 3	0110 0010	0000 1100 0100 0001
5	1a	0110 0010	0110 1110 0100 0001
	2, 3	0110 0010	0011 0111 0010 0000
6	1	0110 0010	0011 0111 0010 0000
	2, 3	0110 0010	0001 1011 1001 0000
7	1	0110 0010	0001 1011 1001 0000
	2, 3	0110 0010	0000 1101 1100 1000
8	1	0110 0010	0000 1101 1100 1000
	2, 3	0110 0010	0000 0110 1110 0100

 

3.18 [20] <§3.4> Using a table similar to that shown in Figure 3.10, calculate 74 divided by 21 using the hardware described in Figure 3.8. You should show the contents of each register on each step. Assume both inputs are unsigned 6-bit integers.

해석] 그림 3.10에서 보인 것과 유사한 표를 이용하고, 그림 3.8에서 설명된 하드웨어를 사용하여 74 나누기 21을 계산하여라. 각 단계에서 각 레지스터의 내용을 보여라. 두 입력은 부호 없는 6비트 정수라고 가정하라.

(문제에서 진수 조건이 나오지 않았으므로 8진수로 가정하고 풀이를 하겠습니다.)

Iteration	Step	Quotient	Divisor	Remainder
0	Initial value	000000	010001 000000	000000 111100
1	1: Rem = Rem - Div	000000	010001 000000	101111 111100
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000000	010001 000000	000000 111100
	3: Shift Div right	000000	001000 100000	000000 111100
2	1: Rem = Rem - Div	000000	001000 100000	111000 011100
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000000	001000 100000	000000 111100
	3: Shift Div right	000000	000100 010000	000000 111100
3	1: Rem = Rem - Div	000000	000100 010000	111100 101100
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000000	000100 010000	000000 111100
	3: Shift Div right	000000	000010 001000	000000 111100
4	1: Rem = Rem - Div	000000	000010 001000	111110 110100
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000000	000010 001000	000000 111100
	3: Shift Div right	000000	000001 000100	000000 111100
5	1: Rem = Rem - Div	000000	000001 000100	111111 111000
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000000	000001 000100	000000 111100
	3: Shift Div right	000000	000000 100010	000000 111100
6	1: Rem = Rem - Div	000000	000000 100010	000000 011010
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000001	000000 100010	000000 011010
	3: Shift Div right	000001	000000 010001	000000 011010
7	1: Rem = Rem - Div	000001	000000 010001	000000 001001
	2b: Rem < 0 -> +Div, sll Q, Q0=0	000011	000000 010001	000000 001001
	3: Shift Div right	000011	000000 001000	000000 001001

 

 

 

 3.19 [30] <§3.4> Using a table similar to that shown in Figure 3.10, calculate 74 divided by 21 using the hardware described in Figure 3.11. You should show the contents of each register on each step. Assume A and B are unsigned 6-bit integers. This algorithm requires a slightly different approach than that shown in

Figure 3.9. You will want to think hard about this, do an experiment or two, or else go to the web to figure out how to make this work correctly. (Hint: one possible solution involves using the fact that Figure 3.11 implies the remainder register can be shifted either direction.)

해석] 그림 3.10에서 보인 것과 같은 유사한 표를 이용하고, 그림 3.11에서 설명된 하드웨어를 사용하여 74나누기 21을 계산하라. 각 단계에서 각 레지스터의 내용들을 보여라. A와 B는 부호 없는 6비트 정수라고 가정하라. 이 알고리즘은 그림 3.9에서 보인 것과 약간 다른 방식을 요구한다. 이 방식이 어떻게 작동되는가를 이해하기 위해서 여러 방식을 고려하거나 웹을 참조하라. (힌트 : 한 가지 가능한 방법은 그림 3.11의 나머지 레지스터가 좌우 어느 방향으로도 이동될 수 있음을 이용하는 것이다. )

(문제에서 진수 조건이 나오지 않았으므로 8진수로 가정하고 풀이를 하겠습니다.)

Iteration	Step	Divisor	Remainder
0	Initial values	010001	000000 111100
	Shift Rem left	010001	000001 111000
1	1: Rem = Rem - Div	010001	110000 111000
	2b : Rem < 0 => +Div, sll R, R0 = 0	010001	000011 110000
2	1: Rem = Rem – Div	010001	110010 110000
	2b : Rem < 0 => +Div, sll R, R0 = 0	010001	000111 100000
3	1: Rem = Rem – Div	010001	110110 100000
	2b : Rem < 0 => +Div, sll R, R0 = 0	010001	001111 000000
4	1: Rem = Rem – Div	010001	111110 000000
	2b : Rem < 0 => +Div, sll R, R0 = 0	010001	011110 000000
5	1: Rem = Rem – Div	010001	001101 000000
	2a:Rem >= 0 => sll R, R0 = 1	010001	011010 000001
6	1: Rem = Rem – Div	010001	001001 000001
	2a:Rem >= 0 => sll R, R0 = 1	010001	010010 000011
Done	Shift left half of Rem right	010001	001001 000011

 

 

참고 : COMPUTER ORGANIZATION AND DESIGN 5th(컴퓨터 구조 및 설계) David A Patterson. John L. Hennessy

본 계시글은 배워서 남주자라는 가치를 실현하기 위해서 작성되었습니다.

<><