Computer Architecture CHAPTER 컴퓨터산술과논리연산
제 3 장 컴퓨터산술과논리연산 3.1 ALU의구성요소 3.2 정수의표현 3.3 논리연산 3.4 시프트연산 3.5 정수의산술연산 3.6 부동소수점수의표현 3.7 부동소수점산술연산
3.1 ALU 의구성요소 산술연산장치 : 산술연산들 (+, -,, ) 을수행 논리연산장치 : 논리연산들 (AND, OR, XOR, NOT 등 ) 을수행 시프트레지스터 (shift register) : 비트들을좌측혹은우측으로이동시키는기능을가진레지스터 보수기 (complementer) : 2진데이터를 2의보수로변환 ( 음수화 ) 상태레지스터 (status register) : 연산결과의상태를나타내는플래그 (flag) 들을저장하는레지스터 3
ALU 의내부구성요소들 4
3.2 정수의표현 2 진수체계 : 0, 1, 부호및소수점으로수를표현 [ 예 ] -13.625 10 = -1101.101 2 부호없는정수표현의예 00111001 = 57 00000000 = 0 00000001 = 1 10000000 = 128 11111111 = 255 n- 비트 2 진수를부호없는정수 A 로변환하는방법 : 5
소수와음수의표현 최상위비트인 a n-1 의좌측에소수점이있는소수의 10진수변환방법 A = a n-1 2-1 + a n-2 2-2 +... + a 1 2 -(n-1) + a 0 2 -n [ 예 ] 2 3 2 2 2 1 2 0 2-1 2-2 2-3 : 자리수 (weight) 1 1 0 1. 1 0 1 = 1 2 3 + 1 2 2 + 0 2 1 + 1 2 0 + 1 2-1 + 0 2-2 + 1 2-3 = 8 + 4 + 1 + 0.5 + 0.125 = 13.625 음수표현방법 부호화-크기표현 (signed-magnitude representation) 1의보수표현 (1's complement representation) 2의보수표현 (2's complement representation) 6
3.2.1 부호화 - 크기표현 맨좌측비트는부호비트, 나머지 n-1 개의비트들은수의크기 (magnitude) 를나타내는표현방식 [ 예 ] + 9 = 0 0001001 + 35 = 0 0100011-9 = 1 0001001-35 = 1 0100011 부호화-크기로표현된 2진수 (a n-1 a n-2... a 1 a 0 ) 를 10진수로변환 A = (-1) an-1 (a n-2 2 n-2 + a n-3 2 n-3 +... + a 1 2 1 + a 0 2 0 ) [ 예 ] 0 0100011 = (-1) 0 (0 2 6 +1 2 5 +0 2 4 +0 2 3 +0 2 2 +1 2 1 +1 2 0 ) = (32 + 2 + 1) = 35 1 0001001 = (-1) 1 (0 2 6 +0 2 5 +0 2 4 +1 2 3 +0 2 2 +0 2 1 +1 2 0 ) = - (8 + 1) = - 9 7
부호화 - 크기표현 ( 계속 ) 결점 덧셈과뺄셈을수행하기위해서는부호비트와크기부분을별도로처리해야함 0 에대한표현이두개존재 n- 비트단어로표현할수있는수들이 2 n 개가아닌, (2 n -1) 개로감소 0 0000000 = + 0 1 0000000 = - 0 8
3.2.2 보수표현 1의보수 (1's complement) 표현 모든비트들을반전 (0 1, 1 0) 2의보수 (2's complement) 표현 모든비트들을반전하고, 결과값에 1을더한다 [ 예 ] + 9 = 0 0001001 + 35 = 0 0100011-9 = 1 1110110 (1의보수 ) - 35 = 1 1011100 (1의보수 ) - 9 = 1 1110111 (2의보수 ) - 35 = 1 1011101 (2의보수 ) 9
8- 비트 2 진수로표현할수있는 10 진수의범위 1 의보수 : - (2 7-1) + (2 7-1) 2 의보수 : - 2 7 + (2 7-1) 10
2 의보수 10 진수변환 2 의보수로표현된양수 (a n-1 = 0) 를 10 진수로변환하는방법 A = a n-2 2 n-2 + a n-3 2 n-3 +... a 1 2 1 + a 0 2 0 2 의보수로표현된음수 (a n-1 = 1) 를 10 진수로변환하는방법 A = - 2 n-1 + (a n-2 2 n-2 + a n-3 2 n-3 + a 1 2 1 + a 0 2 0 ) [ 예 ] 10101110 = - 128 + (1 2 5 + 1 2 3 + 1 2 2 + 1 2 1 ) = - 128 + (32 + 8 + 4 + 2) = - 82 [ 다른방법 ] 10101110 01010010 으로먼저변환한후, 음수표시 01010010 = - (1 2 6 + 1 2 4 + 1 2 1 ) = - (64 + 16 + 2) = - 82 11
3.2.3 비트확장 (Bit Extension) 데이터의길이 ( 비트수 ) 를늘리는방법 목적 : 데이터를더많은비트의레지스터에저장하거나더긴데이터와의연산수행 12
비트확장 ( 계속 ) 2 의보수표현의경우 : 확장되는상위비트들을부호비트와같은값으로세트 부호 - 비트확장 (sign-bit extension) 이라함 13
3.3 논리연산 기본적인논리연산들 14
논리연산을위한하드웨어모듈 하드웨어의구성 입력비트들은모든논리게이트들을통과 선택신호들에의하여멀티플렉서의네입력들중의하나를출력 15
N- 비트논리연산장치 N- 비트데이터들을위한논리연산장치 기본논리모듈들을병렬로접속 [ 예 ] 4- 비트논리연산장치 16
AND 연산 / OR 연산 AND 연산 : 두데이터단어들의대응되는비트들간에 AND 연산을수행 A = 1 0 1 1 0 1 0 1 B = 0 0 1 1 1 0 1 1 -------------------------- 0 0 1 1 0 0 0 1 ( 연산결과 ) OR 연산 : 두데이터단어들의대응되는비트들간에 OR 연산수행 A = 1 0 0 1 0 1 0 1 B = 0 0 1 1 1 0 1 1 -------------------------- 1 0 1 1 1 1 1 1 ( 연산결과 ) 17
XOR 연산 / NOT 연산 XOR 연산 : 두데이터단어들의대응되는비트들간에 exclusive-or 연산을수행 A = 1 0 0 1 0 1 0 1 B = 0 0 1 1 1 0 1 1 --------------- ㅡㅡㅡㅡㅡ ---- 1 0 1 0 1 1 1 0 ( 연산결과 ) NOT 연산 : 데이터단어의모든비트들을반전 (invert) A = 1 0 0 1 0 1 0 1 ( 연산전 ) ------------------------------- 0 1 1 0 1 0 1 0 ( 연산결과 ) 18
선택적 - 세트연산 / 선택적 - 보수연산 선택적 - 세트 (selective-set) 연산 : B 레지스터의비트들중에서 1 로세트된비트들과같은위치에있는 A 레지스터의비트들을 1 로세트 <OR 연산이용 > A = 1 0 0 1 0 0 1 0 ( 연산전 ) B = 0 0 0 0 1 1 1 1 -------------------------- A = 1 0 0 1 1 1 1 1 ( 연산결과 ) 선택적 - 보수 (selective-complement) 연산 : B 레지스터의비트들중에서 1 로세트된비트들에대응되는 A 레지스터의비트들을보수로변환 <XOR 연산이용 > A = 1 0 0 1 0 1 0 1 ( 연산전 ) B = 0 0 0 0 1 1 1 1 -------------------------- A = 1 0 0 1 1 0 1 0 ( 연산결과 ) 19
마스크연산 마스크 (mask) 연산 : B 레지스터의비트들중에서값이 0 인비트들과같은위치에있는 A 레지스터의비트들을 0 으로바꾸는 (clear 하는 ) 연산 <AND 연산이용 > 용도 : 단어내의원하는비트들을선택적으로 clear 하는데사용 [ 예 ] A = 1 1 0 1 0 1 0 1 ( 연산전 ) B = 0 0 0 0 1 1 1 1 --------------------------- A = 0 0 0 0 0 1 0 1 ( 연산결과 ) 20
삽입연산 삽입 (insert) 연산 : 새로운비트값들을데이터단어내의특정위치에삽입 방법 : 1 삽입할비트위치들에대하여마스크 (AND) 연산수행 2 새로이삽입할비트들과 OR 연산을수행 A = 1 0 0 1 0 1 0 1 B = 0 0 0 0 1 1 1 1 마스크 (AND 연산 ) -------------------------- A = 0 0 0 0 0 1 0 1 첫단계결과 B = 1 1 1 0 0 0 0 0 삽입 (OR 연산 ) -------------------------- A = 1 1 1 0 0 1 0 1 최종 ( 삽입 ) 결과 21
비교연산 비교 (compare) 연산 A 와 B 레지스터의내용을비교 XOR 연산 만약대응되는비트들의값이같으면, A 레지스터의해당비트를 0 으로세트 만약서로다르면, A 레지스터의해당비트를 1 로세트 모든비트들이같으면 (A = 00000000), Z 플래그를 1 로세트 A = 1 1 0 1 0 1 0 1 B = 1 0 0 1 0 1 1 0 ------------------- A = 0 1 0 0 0 0 1 1 ( 연산결과 ) 22
3.4 시프트 (shift) 연산 논리적시프트 (logical shift) : 레지스터내의데이터비트들을왼쪽혹은오른쪽으로한칸씩이동 좌측시프트 (left shift) 모든비트들을좌측으로한칸씩이동 최하위비트 (A 1 ) 로는 0 이들어오고, 최상위비트 (A 4 ) 는버림 (drop-out) 우측시프트 (right shift) 모든비트들이우측으로한칸씩이동 최상위비트 (A 4 ) 로 0 이들어오고, 최하위비트 (A 0 ) 는버림 23
시프트레지스터 (shift register) 시프트기능을가진레지스터의내부회로 24
순환시프트 (circular shift) : 회전 (rotate) 이라고도부르며, 최상위혹은최하위에있는비트를버리지않고반대편끝에있는비트위치로이동 순환좌측 - 시프트 (circular shift-left) : 최상위비트인 A 4 가최하위비트위치인 A 1 으로이동 순환우측 - 시프트 (circular shift-right) A 4 A 3, A 3 A 2, A 2 A 1, A 1 A 4 25
직렬데이터전송 (serial data transfer) 시프트연산을데이터비트수만큼연속적으로수행함으로써두레지스터들사이에한개의선을통하여전체데이터를이동하는동작 26
직렬데이터전송의예 27
산술적시프트 (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 28
C 플래그를포함한시프트연산 C 플래그를포함한좌측 - 시프트 (SHLC : shift left with carry) C 플래그를포함한우측 - 시프트 (SHRC : shift right with carry) 30
RLC(rotate left with carry): C 플래그를포함하는좌측순환시프트 ( 회전 ) 연산 RRC(rotate right with carry): C 플래그를포함하는우측순환시프트 ( 회전 ) 연산 31
3.5 정수의산술연산 기본적인산술연산들 32
3.5.1 덧셈 2 의보수로표현된수들의덧셈방법 두수를더하고, 만약올림수가발생하면버림 33
병렬가산기 (parallel adder) 덧셈을수행하는하드웨어모듈 비트수만큼의전가산기 (full-adder) 들로구성 덧셈연산결과에따라해당조건플래그들 (condition flags) 을세트 C 플래그 : 올림수 (carry) S 플래그 : 부호 (sign) Z 플래그 : 0(zero) V 플래그 : 오버플로우 (overflow) 34
4- 비트병렬가산기와상태비트제어회로 35
덧셈오버플로우 덧셈결과가그범위를초과하여결과값이틀리게되는상태 검출방법 : 두올림수 (carry) 들간의 exclusive-or 를이용 V = C 4 C 3 36
3.5.2 뺄셈 덧셈을이용하여수행 (A : 피감수 (minuend), B : 감수 (subtrahend)) A - (+B) = A + (-B) [ 예제 3-22] ================ A - (-B) = A + (+B) 37
덧셈과뺄셈겸용하드웨어의블록구성도 38
뺄셈오버플로우 뺄셈결과가그범위를초과하여결과값이틀리게되는상태 검출방법 : 덧셈과동일 (V = C 4 C 3 ) [ 예제 3-23] ================================== 39
3.5.3 부호없는정수의곱셈 방법 각비트에대하여부분적 (partial product) 계산 부분적들을모두더하여최종결과를얻음 [ 예제 3-24] =================================== 40
부호없는정수승산기의하드웨어구성도 M 레지스터 : 피승수 (multiplicand) 저장 Q 레지스터 : 승수 (multiplier) 저장 두배길이의결과값은 A 레지스터와 Q 레지스터에저장 41
곱셈이수행되는과정에서의레지스터내용들 42
2 의보수들간의곱셈 Booth 알고리즘 (Booth's algorithm) 사용 하드웨어구성 부호없는정수승산기의하드웨어에다음부분을추가 M 레지스터와병렬가산기사이에보수기 (complementer) 추가 Q 레지스터의우측에 Q -1 이라고부르는 1- 비트레지스터를추가하고, 출력을 Q 0 와함께제어회로로입력 43
Booth 알고리즘의흐름도 44
Booth 알고리즘을이용한곱셈의예 (-7x3) 45
3.5.4 나눗셈 나눗셈의수식표현 A B = q r 단, A : 피제수 (dividend), B : 제수 (divisor) q : 몫 (quotient) r : 나머지수 (remainder) 부호없는 2진나눗셈 46
부호없는 2 진나눗셈알고리즘의흐름도 47
2 의보수나눗셈과정 48
[ 예 ] 2 의보수나눗셈 {7 (-3)} 과정
나눗셈결과값 [ 예 ] A B = q r [ 예 ] 7 3 몫 (q) = 2 (0010) 나머지 (r) = 1 (0001) 7 (-3) 몫 = - 2 (1110) 나머지 = 1 (0001) (-7) 3 몫 = - 2 (1110) 나머지 = - 1 (1111) (-7) (-3) 몫 = 2 (0010) 나머지 = - 1 (1111) 50
3.6 부동소수점수의표현 부동소수점표현 (floating-point representation) : 소수점의위치를이동시킬수있는수표현방법 수표현범위확대 부동소수점수 (floating-point number) 의일반적인형태 N = (-1) S M B E 단, S : 부호 (sign), M : 가수 (mantissa), B : 기수 (base), E : 지수 (exponent) 51
부동소수점표현 ( 계속 ) 10 진부동소수점수 (decimal floating-point number) [ 예 ] 274,000,000,000,000 2.74 ⅹ10 14 0.00000000000274 2.74 ⅹ10-12 2진부동소수점수 (binary floating-point number) 기수 B = 2 단일-정밀도 (single-precision) 부동소수점수형식 : 32 비트 복수-정밀도 (double-precision) 부동소수점수형식 : 64 비트 52
단일 - 정밀도부동소수점수형식의예 S : 1 비트, E : 8 비트, M : 23 비트 표현가능한수크기의범위 : 0.5 x 2-128 ~ 0.5 x 2 127 1.47 x 10-39 ~ 1.7 x 10 38 [ 비교 ] 32- 비트고정소수점표현의경우 : 1.0 x 2-31 ~ 1.0 x 2 31 2.0 x 10-9 ~ 2.0 x 10 9 지수 (E) 필드의비트수증가 표현가능한수의범위확장 가수 (M) 필드의비트수증가 정밀도 (precision) 증가 53
같은수에대한부동소수점표현 같은수에대한부동소수점표현이여러가지가존재 0.1101 2 5 11.01 2 3 0.001101 2 7 정규화된표현 (Normalized representation) 수에대한표현을한가지로통일하기위한방법 ± 0.1bbb...b 2 E 위의예에서정규화된표현은 0.1101 2 5 54
부동소수점표현의예 (0.1101 25) 부호 (S) 비트 = 0 지수 (E) = 00000101 가수 (M) = 1101 0000 0000 0000 0000 000 소수점아래첫번째비트는항상 1 이므로, 반드시저장할필요는없음 가수 23 비트를이용하여소수점아래 24 자리수까지표현가능 55
바이어스된지수 (biased exponent) 지수를바이어스된수 (biased number) 로표현 바이어스값 = 127 혹은 128 ( 단일 - 정밀도형식의경우 ) = 1023 혹은 1024 ( 복수 - 정밀도형식의경우 ) 사용목적 0 에대한표현에서가장작은지수값을이용하면모든비트들이 0 이되므로, 0- 검사 (zero-test) 가용이해짐 56
8- 비트바이어스된지수값들 (8-bit biased exponents) 57
바이어스된지수를사용한부동소수점표현의예 바이어스 = 128일때, N = -13.625에대한부동소수점표현 13.625 10 = 1101.101 2 = 0.1101101 2 4 부호 (S) 비트 = 1 (-) 지수 (E) = 00000100 + 10000000 = 10000100 ( 바이어스 128을더한다 ) 가수 (M) = 10110100000000000000000 ( 소수점우측의첫번째 1은제외 ) 58
부동소수점수의표현범위 부동소수점수의표현범위 0.5 2-128 에서 (1-2 -24 ) 2 127 사이의양수들 ( 대략 1.47 x 10-39 ~ 1.7 x 10 38 ) -(1-2 -24 ) 2 127 에서 -0.5 2-128 사이의음수들 제외되는범위 (1-2 -24 ) 2 127 보다작은음수 음수오버플로우 (negative overflow) 0.5 2-128 보다큰음수 음수언더플로우 (negative underflow) 0 0.5 2-128 보다작은양수 양수언더플로우 (positive underflow) (1-2 -24 ) 2 127 보다큰양수 양수오버플로우 (positive overflow) 59
32- 비트데이터형식의표현가능한수의범위 60
IEEE 754 표준부동소수점수의형식 부동소수점수의표현방식의통일을위하여미국전기전자공학회 (IEEE) 에서정의한표준 표현방법 N = (-1) S 2 E-127 (1.M) 가수 : 부호화 - 크기표현사용 지수필드 : 바이어스 -127 사용 1.M 2 E 의형태를가지며, 소수점아래의 M 부분만가수필드에저장 ( 소수점왼쪽의저장되지않는 1 을 hidden bit 라고부름 ) 64- 비트복수 - 정밀도부동소수점형식을사용하는경우 N = (-1) S 2 E-1023 (1.M) 61
IEEE 754 표준부동소수점수의형식 ( 계속 ) 62
IEEE 754 표현예 (N = -13.625 ) 13.625 10 = 1101.101 2 = 1.101101 2 3 부호 (S) 비트 = 1 (-) 지수 E = 00000011 + 01111111 = 10000010 ( 바이어스 127을더한다 ) 가수 M = 10110100000000000000000 ( 소수점좌측의 1은비트표현에서제외 ) 63
예외경우를포함한 IEEE 754 표준 예외경우를포함한정의 (32- 비트형식 ) 만약 E = 255이고 M 0이면, N = NaN 만약 E = 255이고 M = 0이면, N = (-1) S 만약 0 < E < 255 이면, N = (-1) S 2 E-127 (1.M) 만약 E = 0이고 M 0이면, N = (-1) S 2-126 (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 2 E-1023 (1.M) 만약 E = 0이고 M 0이면, N = (-1) S 2-1022 (0.M) 만약 E = 0이고 M = 0이면, N = (-1) S 0 64
3.7 부동소수점산술연산 3.7.1 덧셈과뺄셈 지수들이일치되도록조정 (alignment) 가수들간의연산 ( 더하기혹은빼기 ) 수행 결과를정규화 (normalization) [10 진부동소수점산술의예 ] 65
부동소수점산술의파이프라이닝 연산과정을독립적단계들로분리가능 단계수만큼의속도향상 대규모의부동소수점계산을처리하는거의모든슈퍼컴퓨터들에서채택 [ 예 ] 수배열 (number array) 들간의덧셈 C(I) = A(I) + B(I) 67
3.7.2 부동소수점곱셈 / 나눗셈 2 진수부동소수점곱셈과정 1 가수들을곱한다 2 지수들을더한다 3 결과값을정규화 2 진수부동소수점나눗셈과정 1 가수들을나눈다 2 피제수의지수에서제수의지수를뺀다 3 결과값을정규화 [ 부동소수점곱셈의예 ] (0.1011 2 3 ) (0.1001 2 5 ) < 가수곱하기 > 1011 1001 = 01100011 < 지수더하기 > 3 + 5 = 8 < 정규화 > 0.01100011 2 8 = 0.1100011 2 7 ( 결과값 ) 68
부동소수점연산과정에서발생가능한문제점 지수오버플로우 (exponent overflow) 양의지수값이최대지수값을초과 수가너무커서표현될수없는상태이므로, + 또는 - 로세트 지수언더플로우 (exponent underflow) 음의지수값이최대지수값을초과 수가너무작아서표현될수없는상태이므로, 0 으로세트 69
부동소수점연산과정에서발생가능한문제점 ( 계속 ) 가수언더플로우 (mantissa underflow) 가수의소수점위치조정과정에서비트들이가수의우측편으로넘치는상태 반올림 (rounding) 적용 가수오버플로우 (mantissa overflow) 같은부호를가진두가수들을덧셈하였을때올림수가발생 재조정 (realignment) 과정을통하여정규화 70