Lecture #4 제3장. 컴퓨터 산술과 논리 연산.

Presentation on theme: "Lecture #4 제3장. 컴퓨터 산술과 논리 연산."— Presentation transcript:

1 Lecture #4 제3장. 컴퓨터 산술과 논리 연산

2 강의 목차 3.1 ALU의 구성 요소 3.2 정수의 표현 3.3 논리 연산 3.4 쉬프트 연산 3.5 정수의 산술 연산
3.6 부동소수점 수의 표현 3.7 부동소수점 산술 연산

3 3.1 ALU의 구성 요소 산술 연산장치 : 산술 연산들(+, -, ×, ÷)을 수행
논리 연산장치 : 논리 연산들(AND, OR, XOR, NOT 등)을 수행 쉬프트 레지스터(shift register) : 비트들을 좌측 혹은 우측으로 이동시키는 기능을 가진 레지스터 보수기(complementer) : 2진 데이터를 2의 보수로 변환(음수화) 상태 레지스터(status register) : 연산 결과의 상태를 나타내는 플래그(flag)들을 저장하는 레지스터 Computer Architecture

4 ALU의 내부 구성 요소들 Computer Architecture

5 3.2 정수의 표현 2진수 : 0, 1, 부호 및 소수점으로 표현 = 컴퓨터 내부에서의 정수 표현 : 고정소수점 수(Fixed-point Number) 일정한 수의 비트만을 사용하여 2진수 형태로 표현 부호와 소수점을 사용하지 않는다  최하위 비트 우측에 소수점이 있다고 가정 n-비트 2진수를 부호 없는 수 A로 변환하는 방법 최하위 비트인 a0의 우측에 소수점이 있는 정수의 10진수 변환방법 A = an-1 × 2n-1 + an-2 × 2n a1 × 21 + a0 × 20 최상위 비트인 an-1의 좌측에 소수점이 있는 소수의 10진수 변환방법 A = an-1 × an-2 × a1 × 2-(n-1) + a0 × 2-n 예 : = 1×23 + 1×22 + 0×21 + 1×20 + 1× × ×2-3 = = Computer Architecture

6 음수의 표현 음수 표현 방법 부호화-크기 표현(signed-magnitude representation)
1의 보수 표현(1's complement representation) 2의 보수 표현(2's complement representation) 공통점: 단어의 맨좌측 비트(leftmost bit)를 부호 비트(sign bit)로 사용 an-1 = 0 : 양의 정수 an-1 = 1 : 음의 정수 Computer Architecture

7 3.2.1 부호화-크기 표현 (1) 맨 좌측 비트는 부호 비트, 나머지 n-1 개의 비트들은 수의 크기(절대값:magnitude)를 나타내는 표현 방식 [예] + 9 = = - 9 = = 부호화-크기로 표현된 2진수(an-1 an a1 a0)를 10진수로 변환 A = (-1)an-1 (an-2 × 2n-2 + an-3 × 2n a1 × 21 + a0 × 20) = (-1)0(0×26+1×25+0×24+0×23+0×22+1×21+1×20) = ( ) = 35 = (-1)1(0×26+0×25+0×24+1×23+0×22+0×21+1×20) = - (8 + 1) = - 9 Computer Architecture

8 부호화-크기 표현 (2) 결점 덧셈과 뺄셈을 수행하기 위해서는 부호비트와 크기 부분을 별도로 처리 ‘0’ 표현이 두 개 존재
예: 두 수의 덧셈 (1) 두 수의 부호를 비교한다 (2) 부호가 같은 경우에는 크기 부분을 더하고, 다른 경우에는 차이를 구한다 (3) 크기 부분의 절대값이 더 큰 수의 부호를 결과값의 부호로 한다 ‘0’ 표현이 두 개 존재 n-비트 단어로 표현할 수 있는 수들이 2n 개가 아닌, (2n - 1)개로 감소 = + 0 = - 0 Computer Architecture

9 3.2.2 보수 표현 1의 보수(1's complement) 표현 2의 보수(2's complement) 표현
모든 비트들을 반전 (0  1, 1 0) 2의 보수(2's complement) 표현 모든 비트들을 반전하고(1의 보수), 결과값에 1을 더한다 [예] + 9 = = - 9 = (1의 보수) = (1의 보수) 9 = (2의 보수) = (2의 보수) 컴퓨터 내부에서는 주로 음수를 2의 보수로 표현 산술 계산의 편리성  뺄셈을 덧셈으로 계산 가능 1의 보수 표현는 ‘0’에 대한 표현이 두 가지  표현할 수 있는 수의 범위가 적다 Computer Architecture

10 8-비트 보수로 표현된 정수들 8-비트 2진수로 표현할 수 있는 10진수의 범위
1의 보수 : - (27 - 1) ∼ + (27 - 1) 2의 보수 : ∼ + (27 - 1) Computer Architecture

11 2의 보수  10진수 변환 2의 보수로 표현된 양수(an-1 = 0)를 10진수로 변환하는 방법
A = an-2 × 2n-2 + an-3 × 2n a1 ×21 + a0 ×20 2의 보수로 표현된 음수(an-1 = 1)를 10진수로 변환하는 방법 A = - 2n-1 + (an-2×2n-2+ an-3×2n-3+… a1×21+ a0×20 ) [예] = (1 × × × × 21) = ( ) = - 82 [다른 방법]  으로 먼저 변환한 후, = - (1 × × × 21) = - ( ) = - 82 Computer Architecture

12 3.2.3 비트 확장 (Bit Extension) (1)
데이터의 길이(비트 수)를 늘리는 방법 목적: 데이터를 더 많은 비트의 레지스터에 저장하거나 더 긴 데이터와의 연산 수행 예: 8-비트 데이터를 16-비트 데이터로 확장 부호화-크기 표현의 경우 : 부호 비트를 맨좌측 위치로 이동시키고, 그 외의 비트들은 0으로 채운다 +21 = (부호화-크기, 8 비트) +21 = (부호화-크기, 16 비트) -21 = (부호화-크기, 8 비트) -21 = (부호화-크기, 16 비트) Computer Architecture

13 비트 확장 (Bit Extension) (2)
예: 8-비트 데이터를 16-비트 데이터로 확장 2의 보수 표현의 경우 : 확장되는 상위 비트들을 부호 비트와 같은 값으로 세트 = 부호 비트 확장(sign-bit extension) +21 = (2의 보수, 8 비트) +21 = (2의 보수, 16 비트) -21 = (2의 보수, 8 비트) -21 = (2의 보수, 16 비트) Computer Architecture

14 3.3 논리 연산 기본적인 논리 연산들 논리 데이터는 단어 내의 각 비트 단위로 의미를 가짐 논리 연산도 비트 단위로 처리
Computer Architecture

15 논리 연산을 위한 하드웨어 모듈 하드웨어의 구성 입력 비트들은 모든 논리 게이트들을 통과
출력 선택 신호들에 의하여 멀티플렉서의 네 입력들 중의 하나를 출력 Computer Architecture

16 N-비트 논리 연산장치 N-비트 데이터들을 위한 논리 연산장치 4-비트 논리 연산장치 기본 논리 모듈들을 병렬로 접속
Computer Architecture

17 AND 연산 / OR 연산 AND 연산 : 두 데이터 단어들의 대응되는 비트들 간에 AND 연산을 수행
B = (연산 결과) OR 연산 : 두 데이터 단어들의 대응되는 비트들 간에 OR 연산을 수행 A = (연산 결과) Computer Architecture

18 XOR 연산 / NOT 연산 XOR 연산 : 두 데이터 단어들의 대응되는 비트들 간에 exclusive-OR 연산을 수행
A = B = (연산 결과) NOT 연산 : 데이터 단어의 모든 비트들을 반전(invert) A = (연산 전) (연산 후) Computer Architecture

19 선택적-세트 연산 / 선택적-보수 연산 선택적-세트(selective-set) 연산 : B 레지스터의 비트들 중에서 1로 세트된 비트들과 같은 위치에 있는 A 레지스터의 비트들을 1로 세트 <OR 연산 이용> A = (연산 전) B = A = (연산 후) 선택적-보수(selective-complement) 연산 : B 레지스터의 비트들 중에서 1로 세트된 비트들에 대응되는 A 레지스터의 비트들을 보수로 변환 <XOR 연산 이용> A = (연산 전) A = (연산 후) Computer Architecture

20 마스크 연산 마스크(mask) 연산 : B 레지스터의 비트들 중에서 값이 0인 비트들과 같은 위치에 있는 A 레지스터의 비트들을 0으로 바꾸는(clear하는) 연산 <AND 연산 이용> 용도 : 단어내의 원하는 비트들을 선택적으로 clear하는 데 사용 [예] A = (연산 전) B = A = (연산 후) Computer Architecture

21 삽입 연산 삽입(insert) 연산 : 새로운 비트 값들을 데이터 단어내의 특정 위치에 삽입
방법 : ① 삽입할 비트 위치들에 대하여 마스크(AND) 연산 수행 ② 새로이 삽입할 비트들과 OR 연산을 수행 A = B = 마스크 (AND 연산) A = 첫 단계 결과 B = 삽입 (OR 연산) A = 최종(삽입) 결과 Computer Architecture

22 비교 연산 비교(compare) 연산 A와 B 레지스터의 내용을 비교  exclusive-OR 연산
모든 비트들이 같으면, Z 플래그를 1 세트 A = B = A = (연산 결과) Computer Architecture

23 3.4 쉬프트(shift) 연산 논리적 쉬프트 (logical shift) : 좌측 쉬프트(left shift)
레지스터내의 데이터 비트들을 왼쪽 혹은 오른쪽으로 한 칸씩 이동 좌측 쉬프트(left shift) 모든 비트들을 좌측으로 한 칸씩 이동 최하위 비트(A1)로는 0 이 들어오고, 최상위 비트(A4)는 버림 우측 쉬프트(right shift) 모든 비트들이 우측으로 한 칸씩 이동 최상위 비트(A4)로 0이 들어오고, 최하위 비트(A0)는 버림 Computer Architecture

24 쉬프트 레지스터 (shift register)
D-F/F을 이용한 쉬프트 레지스터 Computer Architecture

25 순환 쉬프트(circular shift)
회전(rotate)이라고도 부르며, 최상위 혹은 최하위에 있는 비트를 버리지 않고 반대편 끝에 있는 비트 위치로 이동 순환 좌측-쉬프트(circular shift-left) 최상위 비트인 A4가 최하위 비트 위치인 A1으로 이동 순환 우측-쉬프트(circular shift-right) A4  A3, A3  A2, A2  A1, A1  A4 Computer Architecture

26 쉬프트 레지스터 응용 (1) 직렬 데이터 전송(Serial Data Transfer)
쉬프트 연산을 데이터 비트 수만큼 연속적으로 수행함으로써 두 레지스터들 사이에 한 개의 선을 통하여 전체 데이터를 이동하는 동작 Computer Architecture

27 쉬프트 레지스터 응용 (2) 4-비트 레지스터들 간의 직렬 전송의 예 Computer Architecture

28 산술적 쉬프트 (arithmetic shift)
수(number)를 나타내는 데이터에 대한 쉬프트 방법: 쉬프트 과정에서 부호 비트는 그대로 유지시키고, 수의 크기를 나타내는 비트들만 쉬프트 (1) 산술적 좌측-쉬프트(arithmetic shift-left) A4 (불변), A3  A2, A2  A1, A1  0 (2) 산술적 우측-쉬프트(arithmetic shift-right) A4 (불변), A4  A3, A3  A2, A2  A1 [예] A = (-2) ; 초기 상태 (-4) ; 산술적 좌측-쉬프트 결과 (-2) ; 산술적 우측-쉬프트 결과 (-1) ; 산술적 우측-쉬프트 결과 Computer Architecture

29 3.5 정수의 산술 연산 정수의 산술 연산을 위한 기본적인 마이크로 연산들 A  A'+ 1 ; 보수화(2의 보수 변환)
A  A + B ; 덧셈 A  A - B ; 뺄셈 A  A x B ; 곱셈 A  A / B ; 나눗셈 A  A + 1 ; 증가(increment) A  A - 1 ; 감소(decrement) Computer Architecture

30 3.5.1 덧셈 2의 보수로 표현된 수들의 덧셈 방법 두 수를 더하고, 만약 올림수가 발생하면 버림
Computer Architecture

31 병렬 가산기(Parallel Adder) (1)
덧셈을 수행하는 하드웨어 모듈 비트 수만큼의 전가산기(full-adder)들로 구성 덧셈 연산 결과에 따라 해당 조건 플래그들(condition flags)을 세트 C 플래그 : 올림수(carry) S 플래그 : 부호(sign) Z 플래그 : 0(zero) V 플래그 : 오버플로우(overflow) Computer Architecture

32 병렬 가산기(Parallel Adder) (2)
4-비트 병렬 가산기와 상태 비트 제어회로 Computer Architecture

33 덧셈 오버플로우 덧셈 결과가 그 범위를 초과하여 결과값이 틀리게 되는 상태 검출 방법 V = C4  C5
두 올림수(carry)들 간의 exclusive-OR를 이용 V = C4  C5 덧셈에서 오버플로우가 발생하는 예 Computer Architecture

34 3.5.2 뺄셈 덧셈을 이용하여 수행 A - (+B) = A + (-B) A - (-B) = A + (+B)
단, A : 피감수(minuend), B : 감수(subtrahend) Computer Architecture

35 덧셈과 뺄셈 겸용 하드웨어의 블록 구성도 Computer Architecture

36 뺄셈 오버플로우 뺄셈 결과가 그 범위를 초과하여 결과값이 틀리게 되는 상태
검출 방법 : 덧셈과 동일 (V = C4  C5 ) Computer Architecture

37 3.5.3 곱셈 부호 없는 정수의 곱셈 각 비트에 대하여 부분 적(partial product) 계산
부분적들을 모두 더하여 최종 결과를 얻음 두 개의 n-비트 2진 정수를 곱하면 결과값은 최대 2n 비트가 된다 Computer Architecture

38 부호 없는 정수 승산기 (1) 정수 승산기의 하드웨어 구성 M 레지스터 : 피승수(multiplicand) 저장
Q 레지스터 : 승수(multiplier) 저장 두 배 길이의 결과값은 A 레지스터와 Q 레지스터에 저장 Computer Architecture

39 부호 없는 정수 승산기 (2) 곱셈이 수행되는 과정에서의 레지스터 내용들 Computer Architecture

40 2의 보수들 간의 곱셈 Booth 알고리즘(Booth's algorithm) 사용 하드웨어 구성
부호 없는 정수 승산기의 하드웨어에 다음 부분을 추가 M 레지스터와 병렬 가산기 사이에 보수기(complementer) 추가 Q 레지스터의 우측에 Q-1 이라고 부르는 1-비트 레지스터를 추가하고, 출력을 Q0와 함께 제어 회로로 입력 Computer Architecture

41 Booth 알고리즘의 흐름도 Computer Architecture

42 Booth 알고리즘을 이용한 곱셈의 예 (-7x3)
Computer Architecture

43 3.5.4 나눗셈 나눗셈의 수식 표현 부호 없는 2진 나눗셈 D ÷ V = Q --- R
단, D = 피젯수(dividend), V = 젯수(divisor), Q = 몫(quotient) V = 젯수(divisor), R = 나머지 수(remainder) 부호 없는 2진 나눗셈 Computer Architecture

44 부호 없는 2진 나눗셈 알고리즘의 흐름도 Computer Architecture

45 2의 보수 나눗셈 과정 [초기 상태] 젯수는 M 레지스터에, 피젯수는 A와 Q 레지스터에 저장 각 레지스터가 n 비트일 때, 피젯수는 2n 비트 길이의 2의 보수로 표시 [사이클 1] A와 Q 레지스터를 좌측으로 한 비트씩 쉬프트 [사이클 2] 만약 M과 A의 부호가 같으면 A  A - M, 다르면 A  A + M을 수행한다. [사이클 3] 연산 전과 후의 A의 부호가 같으면 위의 연산은 성공 연산이 성공이거나 A = 0 이면, Q0  1로 세트 연산이 실패이고 A ≠ 0 이면, Q0  0으로 하고 A를 이전의 값으로 복구 [사이클 4] Q에 비트 자리 수가 남아있다면, 단계 2에서 4까지를 반복 [사이클 5] 나머지 수는 A. 만약 젯수와 피젯수의 부호가 같으면 몫은 Q의 값이고, 그렇지 않으면 Q의 2의 보수가 몫 Computer Architecture

46 2의 보수 나눗셈의 예 (7 ÷ (-3)) Computer Architecture

47 3.6 부동소수점 수의 표현 부동소수점 표현(floating-point representation) : 소수점의 위치를 이동시킬 수 있는 표현 방법 부동소수점 수(floating-point number)의 일반적인 형태 N = (-1)S M × BE 단, S: 부호(sign), M: 가수(mantissa), B: 기수(base), E: 지수(exponent) 2진 부동소수점 수(binary floating-point number) 기수 B = 2 단일-정밀도(single-precision) 부동소수점 수 : 32 비트 복수-정밀도(double-precision) 부동소수점 수 : 64 비트 Computer Architecture

48 단일-정밀도 부동소수점 수 형식의 예 S: 1 비트, E: 8 비트, M: 23 비트
가수(M) 필드의 비트 수가 늘어나면, 정밀도(precision) 증가 Computer Architecture

49 같은 수에 대한 부동소수점 표현 같은 수에 대한 부동소수점 표현이 여러 가지가 존재
× 25 × 22 × 26 정규화된 표현(normalized representation) 수에 대한 표현을 한 가지로 통일하기 위한 방법 ± 0.1bbb...b × 2E 위의 예에서 정규화된 표현은 × 25 Computer Architecture

50 비트 배열의 예 (0.1101 × 25) 부호(S) 비트 = 0 지수(E) = 00000101
가수(M) = 소수점 아래 첫 번째 비트는 항상 1이므로, 저장할 필요가 없음  가수 23비트를 이용하여 소수점 아래 24 자리 수까지 표현 가능 Computer Architecture

51 바이어스된 지수 (biased exponent)
지수를 바이어스된 수(biased number)로 표현 사용 목적 0에 대한 표현에서 모든 비트들이 0이 되게 하여, 0-검사(zero-test)가 용이하게 하기 위함  0-검사가 정수에서와 같은 방법으로 가능 Computer Architecture

52 8-비트 바이어스된 지수값들 Computer Architecture

53 바이어스된 지수를 사용한 부동소수점 표현의 예
바이어스값 = 128일 때, N = 에 대한 부동소수점 표현 = = × 24 부호(S) 비트 = 1 (-) 지수(E) = = (바이어스 128을 더한다) 가수(M) = (소수점 우측의 첫 번째 1은 제외) Computer Architecture

54 부동소수점 수의 표현 범위 부동소수점 수의 표현 범위 제외되는 범위
0.5 × 2-128에서 ( ) × 2127 사이의 양수들 (대략 1.47 x ~ 1.7 x 1038) -( ) × 2127 에서 -0.5 × 사이의 음수들 제외되는 범위 ( ) × 2127보다 작은 음수  음수 오버플로우(negative overflow) 0.5 × 보다 큰 음수  음수 언더플로우(negative underflow) 0.5 × 보다 작은 양수  양수 언더플로우(positive underflow) ( ) × 2127 보다 큰 양수 양수 오버플로우(positive overflow) Computer Architecture

55 32-비트 데이터 형식의 표현 가능한 수의 범위 Computer Architecture

56 IEEE 754 표준 부동소수점 수의 형식 부동소수점 수의 표현 방식의 통일을 위하여 미국전기전자공학회(IEEE)에서 정의한 표준 표현 방법 N = (-1)S 2E-127 (1.M) 가수 : 부호화-크기 표현 사용 지수 필드 : 바이어스 127 사용 1.M × 2E의 형태를 가지며, 소수점 아래의 M 부분만 가수 필드에 저장 (소수점 왼쪽의 표현되지 않는 1을 hidden bit라고 지칭) 64-비트 복수-정밀도 부동소수점 형식을 사용하는 경우 N = (-1)S 2E-1023 (1.M) Computer Architecture

57 IEEE 754 표준 부동소수점 수의 형식 Computer Architecture

58 IEEE 754 표현 예 (N = ) = = × 23 부호(S) 비트 = 1 (-) 지수 E = = (바이어스 127을 더한다) 가수 M = (소수점 좌측의 1은 제외한다) Computer Architecture

59 예외 경우를 포함한 IEEE 754 표준 예외 경우를 포함한 정의 (32-비트 형식)
만약 E = 255이고 M ≠ 0이면, N = NaN 만약 E = 255이고 M = 0이면, N = (-1)S ∞ 만약 0 < E < 255 이면, N = (-1)S 2E-127 (1.M) 만약 E = 0이고 M ≠ 0이면, N = (-1)S (0.M) 만약 E = 0이고 M = 0이면, N = (-1)S 0 예외 경우를 포함한 정의 (64-비트 형식) 만약 E = 2047이고 M ≠ 0이면, N = NaN 만약 E = 2047이고 M = 0이면, N = (-1)S ∞ 만약 0 < E < 2047 이면, N = (-1)S 2E-1023 (1.M) 만약 E = 0이고 M ≠ 0이면, N = (-1)S (0.M) Computer Architecture

60 부동소수점 덧셈 / 뺄셈 덧셈과 뺄셈 지수들이 일치되도록 조정 (alignment) 가수들 간의 연산(더하기 혹은 빼기) 수행
결과를 정규화 (normalization) Computer Architecture

61 부동소수점 산술의 파이프라이닝 단계 수만큼의 속도 향상 대규모의 부동소수점 계산을 처리하는 거의 모든 슈퍼컴퓨터들에서 채택
Computer Architecture

62 부동소수점 곱셈 / 나눗셈 2진수 부동소수점 곱셈 과정 2진수 부동소수점 나눗셈 과정 가수들을 곱한다 지수들을 더한다
결과값을 정규화 2진수 부동소수점 나눗셈 과정 가수들을 나눈다 피젯수의 지수에서 젯수의 지수를 뺀다 [부동소수점 곱셈의 예] ( × 23) × ( × 25) <가수 곱하기> 1011 × 1001 = <지수 더하기> 3 + 5 = 8 <정규화> × 28 = × 27 (결과값) Computer Architecture

63 부동소수점 연산 과정에서 발생 가능한 문제들 지수 오버플로우(exponent overflow)
양의 지수값이 최대 지수값을 초과 수가 너무 커서 표현될 수 없는 상태이므로, +∞ 또는 -∞로 세트 지수 언더플로우(exponent underflow) 음의 지수값이 최대 지수값을 초과 수가 너무 작아서 표현될 수 없는 상태이므로, 0으로 세트 Computer Architecture

64 부동소수점 연산 과정에서 발생 가능한 문제들 가수 언더플로우(mantissa underflow)
가수의 소수점 위치 조정 과정에서 비트들이 가수의 우측 편으로 넘치는 경우  반올림(rounding) 적용 가수 오버플로우(mantissa overflow) 같은 부호를 가진 두 가수들을 덧셈하였을 때 올림수가 발생하는 경우  재조정(realignment) 과정을 통하여 정규화 Computer Architecture