Computer System Architecture 제 4 장 연산 컴퓨터구조 Computer System Architecture 멀티미디어공학과 김 해영 hykim@tu.ac.kr

제 4 장 연산 수치 연산 비수치 연산 구성

제 4 장 연산 컴퓨터 연산이란? 컴퓨터 외부에서 들어오는 입력 데이터, 컴퓨터 내부의 기억장치 내에 저장 되어 있는 데이터와 중앙처리장치 내의 레지스터 내에 저장 되어 있는 데이터 등을 가지고 중앙 처리장치 내의 산술 논리 연산장치를 이용하여 처리하는 것 비수치 연산 : 논리 연산과 문자 데이터의 처리에 대한 연산 수치 연산 : 덧셈, 뺄셈, 곱셈, 나눗셈 등의 사칙 연산에 의한 산술연산 데이터의 수에 따라 단항 연산(unary operation) : 입력데이터의 수가 하나 뿐일 때의 연산, 논리 시프트, 로테이트, 산술 시프트, 보수 등 이항 연산 (binary operation) : 입력데이터가 2개일 때의 연산, 사칙 연산, AND, OR, XOR 등 중앙처리장치 내의 산술 논리 연산장치가 연산을 수행하기 위해서는 연산에 사용될 데이터를 준비  중앙처리장치의 레지스터(register)에 적재

제 4 장 수치 연산 수치연산 : 고정 소수점 표현 방식으로 나타낸 수의 연산을 기본으로 부동 소수점 표현 방식으로 나타낸 수의 연산을 병용하여 사칙연산 수행 감 산 : 보수의 가산으로 연산을 수행 곱 셈 : 가산의 반복이나 산술 시프트 연산을 이용 나눗셈 : 감산의 반복이나 산술 시프트 연산을 이용 산술 시프트(Arithmetic Shift) 곱셈과 나눗셈 연산에 보조적으로 사용 좌측/우측 시프트, 클록과 동기 되어 모든 비트들이 좌측/우측으로 이동 부호 없는 n비트 양의 정수에 대한 산술 시프트 우측 시프트 : 최소 유효비트 A0 가 손실되고, An-1자리에 0이 첨가됨, truncation 발생 a) 1110 (우측시프트) 0111 : 14  7 : 2 로 나눈 값고 같음 b) 1111 (우측시프트)0111 : 15 7 : 2로 나눈값의 소수점 이하가 없어짐  truncation 좌측 시프트 : 최대 유효비트 An-1 가 손실되고, A0에 0이 첨가됨, overflow 발생 a) 0111 (좌측시프트) 1110 : 7  14 : 2를 곱한 값과 같음 b) 1001 (좌측시프트)0010 : 9 2 : 2를 곱한 값보다 훨씬 작은 값이 됨  overflow 우측 시프트 좌측 시프트

제 4 장 수치 연산 부호가 있는 n 비트 수에 대한 산술 시프트 고려 부호 절대값 부호와 2의 보수 부호와 1의 보수 부호 비트는 불변, 첨가되는 비트는 항상 ‘0’ 1 01100 (왼쪽 시프트) 1 11000 우측시프트 : 부호 비트가 복사되어 한 비트씩 우측으로 이동 좌측시프트 : A0 에 ‘0’이 첨가되어 한 비트씩 왼쪽으로 이동 1 10100 (왼쪽 시프트) 1 01000 좌/우측 시프트 : 부호 비트가 복사되어 한 비트씩 좌/우측으로 이동 1 10011 (왼쪽 시프트) 1 00111

제 4 장 수치 연산 부호가 있는 n 비트 수에 대한 산술 시프트 고려 양수 : +12 : 0 01100 오른쪽 시프트 +6 : 0 00110 부호가 있는 수 - 부호 + 절대값 : -12 : 1 01100 오른쪽 시프트 -6 : 1 00110 - 부호 + 1의 보수 : -12 : 1 10011 오른쪽 시프트 -6 : 1 11001 - 부호 + 2의 보수 : -12 : 1 10100 오른쪽 시프트 -6 : 1 11010

제 4 장 수치 연산 고정 소수점 수의 연산 덧셈 부호와 절대값, 부호와 1의 보수, 부호와 2의 보수 연산 방법 서로 상이 부호 절대값 두 수의 부호 비트가 같으면 덧셈 두 수의 부호비트가 다르면 뺄셈(큰 수 – 작은 수), 부호(sign) : 큰 수의 부호 부호와 1의 보수 : 두 수를 더한다 +6 0 000110 -6 1 111001 +) - 9 + 1 110110 +) +9 + 0 001001 -3 1 111100 +3 1 0 000010 + 1 0 000011 부호와 2의 보수 : 부호 비트를 포함하여 두 수를 더한다 +6 0 000110 -6 1 111010 +) -9 + 1 110111 +) +9 + 0 001001 -3 1 111101 +3 1 0 000011 (-12) + (-13) = -25 (+12) + (+13) = +25 (+25) + (-37) = 37 - 25 = -12 캐리가 발생  1을 한번 더 더함 버린다 캐리는 버린다.

제 4 장 수치 연산 뺄셈 (± A) - (+ B) = (± A) + (- B) 뺄셈 : 감수를 보수로 바꾸어 가산 n자리의 두 수를 더해 (n+1)자리의 합이 발생  범람(overflow) 범람 발생  f/f  1로 set 2의 보수 덧셈과 뺄셈을 위한 하드웨어 블록도

제 4 장 수치 연산 범람 (overflow) 레지스터의 길이  한정, 범람 발생 범람 : n자리의 두 수를 더해서 n+1자리의 합이 발생할 시 범람이 발생  오버플로 플립플롭을 세트 범람의 검사 부호가 없는 수 : 최상위 비트(MSB)에서 end carry가 발생  범람 부호가 있는 수 주의 : MSB는 부호 비트이며, 부호 비트도 수의 일부분으로 간주 end carry(부호비트)는 오버 플로로 간주하지 않음 (1) 부호 절대값 : 절대값의 최대 유효비트(MSB)에서 캐리 발생 범람 (2) 부호와 2의 보수  ①,②의 carry 가 서로 다르면 범람 발생 (① 부호비트에서 발생된 캐리) XOR (② 부호비트 아래에서 발생된 캐리) ① ② * 예제 carries 0 1 carries 1 0 + 70 0 1000110 - 70 1 0111010 + 80 0 1010000 - 80 1 0110000 + 150 1 0010110 - 150 0 1101010 Overflow f/f 세트 양수  음수부호 음수  양수부호

제 4 장 수치 연산 곱셈 : 소프트웨어적 연산, 하드웨어적 연산 가산기 : 소프트웨어적으로 연산 수행 곱셈 : 소프트웨어적 연산, 하드웨어적 연산 가산기 : 소프트웨어적으로 연산 수행 배열 승산기(Array processor) : 하드웨어적 연산 수행 소프트웨어에 의한 곱셈 : 덧셈이 기본 (1) 2(피승수) × 5(승수) (2) 2(피승수) × 5(승수) 0010 × 0101 0010(부분적) 0000 (부분적) 0010 (부분적) 0000 (부분적) 0001010(곱셈 결과) (1) 피승수를 승수의 횟수 반복 가산 (2) 좌측 시프트와 부분적(partial product)을 이용(10진수 곱셈과 동일) 0010 × 0101 = 0010 + 0010 + 0010 + 0010 + 0010 = 1010 (1) 승수의 각 자리에 하나씩 부분적이 나타나며, 이 부분적은 최종 곱셈 결과를 얻기 위해 합산된다. (2) 승수의 비트가 0이면 부분적 모두가 0, 승수의 비트가 1이면 피승수의 값(0010)이 부분적이 된다. (3) 각 부분적은 직전의 부분적에 비해 한 자리 왼쪽으로 자리이동(shift)된다. (4) n비트 부호가 없는 양의 정수에 대해 곱셈 결과를 오차 없이 나타내기 위하여 곱하는 두 수의 비트 합인 최대 2n 비트가 필요하다.

제 4 장 수치 연산 곱셈 두 번째 방법의 요점 반복적인 자리 이동(shift) 및 덧셈 올림수와 함께 오른쪽 로테이트 (1) 최종 부분적이 나타날 때까지 기다리지 않고 부분적이 나타날 때마다 합산을 수행한 후 결과를 오른쪽으로 한 자리 이동시킨다. (2) 승수의 값을 시험하여 1이면 피승수의 값을 누적시킨 후 한 자리 오른쪽으로 이동시키고, O이면 오른쪽으로 이동만 시킨다. (3) 승수의 각 비트가 1인지 0인지를 시험할 때는 승수를 올림수와 함께 오른쪽으로 한 비트씩 로테이트 하여 시험코자 하는 비트를 올림수 플립플롭에 넣어 시험하면 된다. 올림수와 함께 오른쪽 로테이트

제 4 장 수치 연산 곱셈 양의 정수 곱셈 알고리즘 (1) Z ← 0 (2) i ← 0 (3) 승수 Yi = 0이면 (4)를 수행하고, Yi=1이면 Z ← Z + X·2n (X와 Z의 최대 유효 비트를 같은 위치에 오도록 하고 덧셈을 함)를 수행 (4) 오른쪽으로 한 비트 시프트(Z ← Z·2-1) (5) i = n-1이면 (6)을 수행하고, 아니면 i = i+1한 후 (3)을 반복 수행 (6) Y를 원상으로 환원(즉 Y의 값을 한번 더 로테이트 하면 원래의 값이 된다)

제 4 장 수치 연산 곱셈 부호와 절대값 : 부호를 제외하고 곱셈, 부호가 같으면 양수, 부호가 Booth 알고리즘 서로 다르면 음수 부호와 2의 보수 : 음수를 양수호 변환 후 두 수의 곱을 구하고, 곱셈결과에 따라 음수일 경우에는 다시 2의 보수로 변환 Booth 알고리즘 - 2진수 00001110(+14)는 23에서 21(k=3, m=1) 자리 값이 1  00001110 = 2k+1 – 2m = 24 – 21 = 14 곱셈 동작은 승수의 값 0 : 부분적을 더할 필요 없이 시프트 승수의 값 1 : 2k+1 – 2m - M×14 = M × 24 - M × 21 피승수 M을 좌측으로 4번 시프트 한 수에서 좌측으로 한 번 시프트 한 수를 빼면 얻을 수 있음을 의미 (1) 승수의 1의 그룹에서 처음 0을 만나게 되면 피승수를 부분적으로부터 뺀다. (2) 승수의 0의 그룹에서 처음 1을 만나게 되면 피승수를 부분적에 더한다. (3) 승수에서 이전의 비트와 같은 비트가 나오면 부분적은 바뀌어지지 않는다.

제 4 장 수치 연산 곱셈 Booth 알고리즘을 위한 하드웨어 구성 승수 : Q 레지스터, Qn+1 플립플롭 : 승수의 값(0인지 1인지 구별) SC : 승수의 비트 수, 최종 결과 : A, Q 레지스터 Fig. 4-6 Booth 알고리즘을 위한 하드웨어

제 4 장 수치 연산 Booth 알고리즘 10 : 부분적 - 피승수 01 : 부분적 + 피승수 Fig. 4-7

제 4 장 수치 연산 예제 7 × 3 Booth 알고리즘을 이용한 곱셈 예

제 4 장 수치 연산 나눗셈 뺄셈을 기본 피제수에서 제수를 뺄 수 없을 때까지 반복하여 뺀 후 횟수는 몫 뺀 후 남은 값은 나머지 피제수(A)와 제수(B)를 비교 부분 나머지(피제수) >= 제수  몫은 1, 제수를 우측 시프트, 부분나머지(피제수) - 제수 부분 나머지(피제수) < 제수  몫은 0, 제수를 우측 시프트

제 4 장 수치 연산 나눗셈 앞의 과정 변형 제수를 오른쪽 시프트 하지 않고 피제수 혹은 부분 나머지를 왼쪽으로 시프트 피제수 혹은 부분 나머지 – 제수 = 피제수 혹은 부분 나머지 + 제수(B)의 2의 보수 E : 피제수와 제수의 크기 비교(E=1이면 몫 Qn = 1, E=0이면 Qn = 0) Fig. 4-8 부호 없는 양의 정수 나눗셈 하드웨어

제 4 장 수치 연산 나눗셈 알고리즘의 순서도

제 4 장 수치 연산 예제 48÷7 Q : 몫, A : 나머지 피제수 = 48 나머지 몫

제 4 장 수치 연산 음의 정수의 나눗셈 부호와 절대값 부호와 2의 보수, 부호와 1의 보수의 경우 부호와 절대값 부호를 제외한 절대값의 계산은 양의 정수에 대한 알고리즘과 동일 몫과 나머지의 부호는 각각 피제수와 제수의 부호에 의해 결정 - 몫은 피제수와 제수의 부호가 같을 때는 양수가 되고, 부호가 서로 다를 때에는 음수 - 나머지의 부호는 피제수의 부호와 동일 부호와 2의 보수, 부호와 1의 보수의 경우 부호와 절대값 음수를 양수로 변환한 후 양수의 나눗셈과 동일한 알고리즘을 적용하되 피제수와 제수의 부호가 다른 경우에는 몫을 다시 각각의 음수 표현 방법으로 변환 피제수가 음수일 경우에는 나머지도 각각의 음수 표현 방법으로 변환해 주어야 함

제 4 장 수치 연산 부동 소수점 수의 연산 덧셈과 뺄셈 지수 부분과 소수 부분 ( 0.123 x 102, 0.123 x 10-2 ) 두 개의 부분에 대해 각각 독립적으로 연산, 고정 소수점 연산 방식 사용 덧셈과 뺄셈 가수의 정렬 필요 즉, 지수부 조정 작은 지수 값을 가진 가수를 시프트 덧셈과 뺄셈 알고리즘 예 # 정규화된 두 수의 덧셈에서 범람이 발생 할 경우에는 그 합을 오른쪽 으로 한자리 시프트 시킨 후 지수를 하나 증가 시킴 (0.91 + 0.32 =1.23  0.123 x 10-1 ) (1) 0인지 여부를 검사 (2) 가수의 위치 조정 (3) 가수의 덧셈 혹은 뺄셈 (4) 결과를 정규화 A=0.12345×104 B=0.6789×103 A ＋ B = 0.12345×104 ＋ 0.6789×103 = (0.12345 ＋ 0.06789) × 104 = 0.19134×104 A － B = 0.12345×104 － 0.6789×103 = (0.12345 － 0.06789) × 104 = 0.05556×104 = 0.5556×103

제 4 장 수치 연산 곱셈과 나눗셈 가수의 정렬 불필요 곱셈과 나눗셈 알고리즘 예 (1) 가수가 0인지 여부를 검사 곱셈 : 지수 부분  덧셈, 가수부분  곱셈 나눗셈 : 지수 부분  뺄셈, 가수 부분  나눗셈 곱셈과 나눗셈 알고리즘 예 제수가 0이면 에러, 피제수가 0이면 몫은 0 (1) 가수가 0인지 여부를 검사 (2) 지수를 더한다. (3) 가수를 곱한다. (4) 결과를 정규화 한다. (1) 0인지 여부를 검사 (2) 지수의 뺄셈을 한다. (3) 가수의 나눗셈을 한다. (4) 결과를 정규화 한다. A=0.123×105 B=0.3×10-4 지수부 : 5 + (-4) = 1 가수부 0.123 × 0.3 = 0.0369 A × B = (0.123×105 ) × (0.3×10-4 ) = 0.0369×101 = 0.369 지수부 5 - (-4) = 9 가수부 0.123 ÷ 0.3 = 0.41 A / B = (0.123×105 ) / (0.3×10-4 ) = 0.41×109

제 4 장 비수치 연산 비수치 연산 논리 연산 OR SET 연산 논리 연산과 문자 데이터 처리 연산, 부울 연산을 기반으로 함 기본 논리연산 : AND, OR, XOR, NOT 논리 연산 SET 연산 B 레지스터의 1에 대응하는 A 레지스터의 비트를 1로 세트 한 레지스터의 일부분을 선택하고자 할 때 사용 결과는 A와 B의 OR 연산 OR ALU : Arithmetic logic unit 산술논리장치 ( )

제 4 장 비수치 연산 논리 연산 MASK 연산 B 레지스터의 0에 대응하는 A 레지스터의 비트를 0으로 클리어 주로 자료의 특정 비트 혹은 문자를 삭제하고자 할 경우 사용 결과는 A와 B의 AND 연산 A레지스터의 하위 2비트를 삭제 할 경우 B레지스터의 마스크의 하위 2비트를 00로 둠

제 4 장 비수치 연산 논리 연산 Selective Complement 연산 B 레지스터의 1에 대응하는 A 레지스터의 비트를 보수로 만듦 레지스터 내의 일부 비트를 보수로 만들 때 사용 결과는 A와 B의 XOR 연산 A레지스터의 상위 2비트를 보수로 만들기 위해 B레지스터의 마스크 의 하위 2비트를 11로 둠

제 4 장 비수치 연산 논리 연산 Selective Clear 연산 B 레지스터의 1에 대응하는 A 레지스터의 비트를 클리어 레지스터 내의 일부 비트를 클리어 시킬 때 사용 결과는 A ← A ∧ B'

제 4 장 비수치 연산 논리 시프트와 로테이트 논리 시프트 서로 이웃한 비트들을 좌측 혹은 우측으로 자리 이동 첨가되는 비트 : ‘0’ 올림수를 포함한 논리 시프트 (a) 논리 좌측 시프트 첨가 되는 비트는 항상 0 (b) 논리 우측 시프트 (a) 올림수와 함께 좌측 시프트 (b) 올림수와 함께 우측 시프트

제 4 장 비수치 연산 논리 시프트의 예 올림수와 함께 오른쪽 시프트 올림수와 함께 왼쪽 시프트 C C x 1100000111000010 0 0 0 x110000011100001 올림수와 함께 왼쪽 시프트 C x 1100000111000010 x 0 1 1000001110000100 오른쪽 시프트 1100000111000010 0 0 0110000011100001 왼쪽 시프트 1100000111000010 1 0 1000001110000100

제 4 장 비수치 연산 로테이트 한쪽 끝에서 밀려나간 비트들이 다른 쪽으로 다시 입력 레지스터 내의 특정 비트를 검사 혹은 문자의 위치 교환 시 시프트에 의한 자료 전송 시 사용 (a) 우측 로테이트 (b) 좌측 로테이트

제 4 장 비수치 연산 로테이트의 예 올림수와 함께 오른쪽 로테이트 C x 1100000111000010 올림수와 함께 왼쪽 로테이트 C x 1100000111000010 1 100000011100010x 오른쪽 로테이트 1100000111000010 0110000011100001 왼쪽 로테이트 1100000111000010 1000001110000101