컴퓨터 구조론 3장 [컴퓨터 산술과 논리 연산4]
정수의 산술 연산
컴퓨터가 처리하는 기본적인 산술 연산들의 종류를 마이크로-연산으로 표현
덧셈
2의 보수로 표현된 수들 간의 덧셈 방법은 먼저 두 수를 더하고, 만약 올림수가 발생하면 버리면 된다.
이러한 과정은 더 많은 비트들로 이루어진 데이터에 대해서도 동일하게 적용된다. 만약 덧셈 결과값의 부호가 1이라면 그 값은 2의 보수로 표현된 음수를 나타낸다.
병렬 가산기(parallel adder)
여러 비트들로 이루어진 두 개의 데이터에 대한 덧셈을 수행하는 회로로서, 비트 수만큼의 전가산기(full adder)들로 구성
덧셈을 수행하는 하드웨어는 병렬 가산기(parallel adder)라고 부른다.
ex) 4-비트 병렬 가산기는 네 개의 전가산기들로 이루어진다. 전가산기들은 올림수 비트(carry bit)를 전송하는 선에 의해 연결되는데, 하위 단계의 전가산기에서 발생한 올림수가 상위 단계 전가산기의 올림수 입력으로 들어가도록 연결된다. 비트 수가 더 많은 데이터들을 위한 가산기는 같은 방법으로 전가산기를 계속 연결함으로써 구성할 수 있다.
덧셈 연산 결과에 따라 해당 조건 플래그들(condition flags) 을 세트
- C 플래그 : 올림수(carry)
- S 플래그 : 부호(sign)
- Z 플래그 : 0(zero)
- V 플래그 : 오버플로우(overflow)
점선으로 표시된 부분이 병렬 가산기이며, 그 외는 덧셈 결과에 따라 상태 레지스터에 포함된 플래그들을 세트해주는 회로들이다. 먼저, 합의 최상위 비트는 부호 비트이므로 부호(S) 플래그로 직접 연결된다. 따라서 양수이면 S플래그가 0으로 음수이면 1로 세트된다. 덧셈 결과에 대한 올림수(C) 플래그는 최상위 단계의 전가산기로부터 발생하는 올림수(C4)에 의해 세트된다. 또한 합의 모든 비트들을 NOR 게이트를 통과시켜서, 영(zero)을 나타내는 z플래그를 세트한다.
즉, 합의 모든 비트들이 0이면 Z 플래그가 1로 세트된다.
그런데 덧셈 과정에서 수의 표현 범위를 초과하는 경우에는 전혀 틀린 결과를 산출하게 된다.
ex) 2의 보수로 표현된 4-비트 데이터의 표현 범위는 -8부터 +7까지이지만, 덧셈 결과가 그 범위를 초과하게 되면 결과값이 틀리게 되는데, 이것을 오버플로우(overflow)라고 한다.
검출 방법
오버플로우는 덧셈 과정에서 최상위 비트들 및 그 다음 비트들의 덧셈 과정에서 발생하는 올림수들이 서로 다른 경우에 발생한다. 따라서 덧셈 과정에서의 오버플로우(V)는 두 올림수들 간의 exclusive-OR을 수행하여 검출할 수 있다.
오버플로우가 검출되면 V 플래그가 1로 세트되며, CPU는 그 결과 값이 다른 연산에 사용되지 않도록 적절한 조치를 취해야 한다.
뺄셈
정수들의 뺄셈은 다음과 같이 덧셈을 이용하여 수행할 수 있다. 즉, A(피감수:minuend)로부터 B(감수 : subtrahend)를 빼려면, B를 음수화 한 다음에 A와 더하면 된다.
- A - (+B) = A + (-B)
A - (-B) = A + (+B) - 2의 보수로 표현되 수들의 뺄셈도 같은 방법으로 처리할 수 있다.
- 감수 B에 대한 2의 보수를 구하여 피감수 A와 더하면 된다.
- 덧셈과 마찬가지로 올림수는 버린다.
뺄셈은 덧셈을 이용하여 수행된다. 그러므로 일반적으로 ALU에 뺄셈을 위한 회로를 별도로 두지 않고 가산기를 이용하여 뺄셈을 수행한다.
이 회로에서 A 레지스터로부터 들어오는 수(A)는 병렬 가산기로 직접 입력되고, B 레지스터로부터 들어오는 수(B)는 보수기(Complementer)를 통하여 병렬 가산기로 들어온다. 보수기는 입력 데이터에 대한 2의 보수를 출력하는 회로이다. 그리고 병렬 가산기는 모든 회로들을 포함하고 있다.
보수기(Complementer)
입력 데이터에 대하여 보수 연산을 수행하는 회로 모듈
보수기로는 제어 신호가 가해지는데, 덧셈인 경우에는 그 신호가'0'이 되어서 입력 데이터 B를 그대로 통과시킨다. 뺄셈인 경우에는 제어 신호로 '1'이 가해져서 B가 보수기에 의해 2의 보수로 변환된 다음에 병렬 가산기로 입력된다. 덧셈 결과는 일반적으로 다른 레지스터가 아닌, 두 레지스터들 중의 어느 하나에 저장된다.
4-비트 병렬 가감산기
4-비트 데이터들 간의 덧셈(A+B) 및 뺄셈(A-B)을 모두 수행하는 조합 회로
제어신호 M = 0 : 덧셈, M = 1 : 뺄셈(입력 B의 비트들을 반전하고, 최 하위 올림수로서 M 을 입력)
뺄셈에서도 그 결과가 표현 가능한 범위를 초과하는 경우에는 오버플로우가 발생하는데, 뺄셈도 가산기를 이용하여 이루어지므로, 뺄셈 과정에서 발생하는 오버플로우도 덧셈에서와 같은 검출 회로를 이용하여 검출할 수 있다.
곱셈
- 덧셈이나 뺄셈에 비하여, 곱셈은 하드웨어로 처리되든 소프트웨어로 처리되든 복잡한 연산이다.
- 곱셈을 위한 여러 가지 알고리즘들이 제안되어 왔다.
- 부호 없는 정수들을 곱셈하는 간단한 경우
- 곱셈은 승수(multiplier)의 최하위 비트에 대한 검수부터 시작되는데, 만약 그 비트의 값이 1이면 부분 적(partial product)은 피승수(multiplicand)와 같아지고, 0이면 부분적은 0000이 된다. 이와 같은 과정은 승수의 각 비트들에 대하여 차례대로 수행되는데, 승수의 각 비트에 대하여 한자리씩 좌측으로 시프트 되면서 발생되는 부분 적들을 모두 더하면 최종 결과가 산출된다.
- 따라서 두 개의 n-비트 정수들을 곱하면 결과값의 길이는 최대 2n 비트가 된다.
마지막 단계에서 모든 부분 적들을 더하여 최종 결과를 구하는 것으로 표시되었다. 이 계싼을 컴퓨터에서 수행할 때는 부분 적이 발생할 때마다 합을 계산함으로써, 중간 결과인 부분 적을 저장해두기 위한 레지스터를 별도로 사용하지 않도록 하고 있다. 또한 검사하는 승수의 비트가 1일 경우 덧셈과 시프트를 수행하지만, 0인 경우에는 시프트만 하면 되기 때문에 처리 시간을 더욱 단축시킬 수 있다.
부호 없는 정수 곱셈기의 하드웨어 구성도
M 레지스터
피승수(multiplicand) 저장
Q 레지스터
승수(multiplier) 저장
두 배 길이의 결과값은 A 레지스터와 Q 레지스터에 저장
곱셈이 수행되는 과정에서의 레지스터 내용들
2의 보수들 간의 곱셈은 상당히 복잡하기 때문에 특별한 알고리즘이 개발되어 있다. 가장 널리 사용되고 있는 Booth 알고리즘(Booth's algorithm)
Booth 알고리즘
2의 보수들 간의 곱셈 알고리즘
이것은 양수와 음수의 어떤 조합들에 대해서도 적용될 수 있다.
하드웨어 구성
- 부호 없는 정수 승산기의 하드웨어에 다음 부분을 추가
- M 레지스터와 병렬 가산기 사이에 보수기(complementer) 추가
- Q 레지스터의 우측에 Q-1 이라고 부르는 1-비트 레지스터를 추가하고, 출력을 Q0와 함께 제어 회로로 입력
Booth알고리즘의 흐름도
이러한 과정은 승수의 비트 수 만큼인 n번 반복된다. 이를 위하여 초기화 단계에서 계수(count) 값을 n으로 세트하고, 각 승수 비트에 대한 연산이 종료되면 계수 값을 1씩 감소시킨다.
ex) Booth 알고리즘을 이용한 곱셈의 예(-7x3)
나눗셈
나눗셈은 곱셈도다 다소 더 복잡하지만 같은 원리에 근거를 두고 있다. 즉, 곱셈에서와 마찬가지로 나눗셈의 알고리즘도 반복적인 시프트와 덧셈 또는 뺄셈으로 이루어진다.
나눗셈을 수식으로 표현 : A÷B=q ····· r
A는 나누어지는 수인 피제수(dividend)이고, B는 나누는 수인 제수(divisor)이다. 그리고 q와 r은 각각 몫(quotient)과 나머지 수(remainder)를 나타낸다.
부호 없는 2진 나눗셈
나눗셈은 사이클 형태를 이룬다. 각 사이클에서 피제수로부터의 한 비트씩이 부분 나머지 수에 추가되며, 그 결과값이 제수와 같거나 커질 때까지 그 과정이 반복된다. 그리고 새로운 부분 나머지 수를 얻기 위하여, 그 수로부터 제수를 뺀다. 이 과정은 피제수의 모든 비트들에 대하여 적용될 때까지 계속된다.
부호 없는 2진 나눗셈 알고리즘의 흐름도
나눗셈에 대한 컴퓨터 알고리즘으로 제수는 M 레지스터에, 피제수는 Q 레지스터에 각각 저장한다. 각 단계에서 A와 Q 레지스터 모두 왼쪽으로 한 비트씩 시프트 된다. A가 나머지 수를 나눌 수 있는지 알기 위하여 A로부터 M을 뺀다.
만약 나눌 수 있는 경우에는 Q0는 1의 값을 가진다. 그렇지 않은 경우에는 Q0은 0이 되고, A의 이전 값을 복구시키기 위하여 M을 A에 다시 더한다. 이 과정이 끝나면 계수(count) 값에서 1을 뺀다. 이와 같은 과정을 n번 반복하면, 최종적으로 몫(q)은 Q 레지스터에, 나머지 값(r)은 A레지스터에 남게 된다.
위의 알고리즘을 약간 수정하면 제수나 피제수가 음수인 경우에도 적용할 수 있다.
2의 보수로 표현된 수들 간의 나눗셈 과정
Refernece
컴퓨터 구조론 개정 5판
https://yz-zone.tistory.com/75
[ 컴퓨터구조 ] 3.5.2 정수의 산술 연산 (계속)
부호 없는 정수의 곱셈 ▣ 방법 ▪ 각 비트에 대하여 부분 적(partial product) 계산 ▪ 부분 적들을 모두 더하여 최종 결과를 얻음 부호 없는 정수 곱셈기의 하드웨어 구성도 ▣ M 레지스터 ▪ 피승수
yz-zone.tistory.com
레지스터 마이크로 연산
레지스터와 마이크로 연산에 대해 공부한 내용
velog.io