RISC-V에서 ALU(arithmetic logic unit) 기능을 구현하는 방법을 알아보자.
ALU란?
연산을 하는 논리 장치이다.
CPU의 가장 핵심적인 기능이라고 볼 수 있다.
다양한 논리 연산자로 ALU를 구성할 수 있다. 간단한 유닛부터 차례대로 알아보자.
1-bit ALU for ADD
덧셈에 쓰이는 ALU는 Full-Adder 라고도 불린다. 기호로는 컨테이너 안에 + 기호를 써서 나타낸다.
입력값으로 a값, b값, 그리고 CarryIn이 존재한다.
여기서 Carry는 받아올림을 의미한다. 입력값 a, b가 모두 1이라고 해보자.
그럼 1+1=10인데, output이 1비트 크기밖에 안 되므로 1을 받아올림해야 한다.
이 값을 다음 유닛에 넘겨주기 위해 carryout이 쓰인다.
마찬가지로 carryin은 이전 유닛에서 받아올림한 값을 의미한다. 그래서 덧셈 계산을 할 때 a, b, CarryIn을 모두 더한다.
예를 들어 a=1, b=1, carryin=1이라고 해보자. 세 값을 더하면 11이다.
따라서 output인 sum값은 1이고, carryout도 1이 되며 이 값은 다음 유닛에 전해진다.
이제 이 계산을 논리적으로 나타내어보자.
CarryOut
CarryOut이 1이려면 a, b, CarryIn중에 1이 두 개 이상 존재하면 된다.
따라서 다음 식이 성립한다.
CarryOut (b*CarryIn) + (a*CarryIn) + (a*b)
여기에서 덧셈 기호는 OR, 곱셈 기호는 AND이다.
Sum
sum의 경우 1이 홀수개이면 1, 짝수개이면 0이다.
따라서 a만 1이거나, b만 1이거나, CarryIn만 1이거나, 셋 다 1인 경우로 총 4가지에 OR연산을 취해서 답을 얻을 수 있다.
32-bit ALU
1비트 값으로 만든 계산 컴포넌트를 쭉 연결해서 32비트 ALU를 설계할 수 있다.
이 때 이전 값의 CarryOut과 다음 값의 CarryIn을 연결하고, 각 컴포넌트마다 결과값을 ALU의 출력으로 정하면 된다. 레지스터로 치면 rd값이다.
32-bit ALU에서 마지막 비트의 CarryOut은 어떻게 되는지, 첫 번째 비트의 CarryIn은 자동으로 0 고정인건지?
Subtraction
뺄셈의 경우, 빼는 연산이 따로 있는 것이 아니라 음수를 더하는 식으로 구현한다.
따라서 빼는 수를 2의 보수로 변환한 후 더한다.
2의 보수는 기존 숫자의 비트를 반전한 다음 1을 더하여 구한다.
따라서 a-b를 구현하려고 한다면,
- not연산으로 b를 반전(1의보수)
- carry-in을 이용하여 b에 1을 더해서 2의보수 완성
- 덧셈과 같이 계산
하는 과정이 필요하다. 이를 위해 1번째 유닛의 carry-in으로 1을 넣는다.
1번 과정의 경우 b가 들어올 자리에 멀티플렉서를 하나 둔다.
여기서 Binvert값을 받아 Binvert=true라면 b가 not게이트를 통과하고 0이면 통과하지 않는 식으로 구현한다.
뺄셈에서는 자리올림이 없고 자리내림을 쓴다. 그러면 ALU가 줄지어 있을 때, 이전 유닛에서 가져온 Carry-in을 덧셈과 동일하게 계산해도 되나?
NOR
nor의 경우 or의 반대로, 둘 다 0인 경우에만 1을 출력하고 나머지는 0을 출력하는 계산이다.
Binvert와 마찬가지로 Ainvert MUX를 만들 수 있다.
따라서 Ainvert=1, Binvert=1, Operation은 AND를 진행하는 쪽으로 고르면 된다.
(헷갈릴 수 있지만 NOR에는 AND연산이 필요하다)
NAND
nand는 둘 다 참일 경우에만 거짓을 내보내는 게이트이다. 0이 되려면 A, B가 모두 1이어야 한다.
A와 B에 모두 역을 취한 다음, 이 값이 0/0이면 0, 나머지는 1을 내보낸다. 따라서 실제로 사용하는 게이트는 OR에 해당한다.
SLT instruction
SLT 란 set-less-than 의 약자이다.
SLT rd, rs1, rs2 처럼 작성하며 rs1 < rs2일 경우 rd를 1로 set하고 다른 경우에는 0으로 set하라는 의미이다.
이것을 좀 더 풀어서 설명해보면 rd의 31부터 1번 비트까지는 어차피 0이고, 0번 비트 값만 결정하면 되는 명령어인 것을 알 수 있다.
이제 rs1과 rs2를 비교해보자. rs1 - rs2 < 0이라면 주어진 조건이 성립한다.
그러면 rs1-rs2의 sign bit를 확인해서 크기 비교를 할 수 있을 것이다.
따라서 우선 뺄셈을 한 후, 31번째 비트가 1이라면 rd를 1로, 0이라면 0으로 set해서 구현할 수 있다.
따라서 31번째 ALU의 출력값(Set)을 0번째 ALU의 Less로 받으면 된다
여기로 Less란 연산에 상관 없는 비트를 0으로 만들기 위해 새로 추가한 값으로, 0번 비트를 제외한 자리는 모두 set값 대신 less를 result로 쓴다.
최적화
지금까지 첫 번째 유닛의 carry-in을 명시한 명령어는 sub과 slt로, 둘 다 b값을 negative로 만들려고 하기 때문에 Binvert는 1이고 carry-in도 1이 된다. 뺄셈을 사용하지 않는 연산에서는 이 두 값이 항상 0으로 고정이다.
최적화를 위해서는 이 두 값을 합쳐서 입력하는 것이 낫다.
계산 속도
31개의 유닛을 계산하고 마지막에 피드백까지 있으면 계산 속도가 길어서 한 cycle에 처리하기 어렵다. 실제 연산은 이런 식으로 구현하지 않는다.
unsigned
SLT와 SLTU는 명령어를 따로 구분한다.
SLT에서는 최상위 비트의 result를 set으로 선택했지만, SLTU에서는 최상위 비트의 carry-out(sign bit처럼 생각)을 set으로 선택하면 된다.
4비트 alut에서 a=0111, b=1001이면 slt가 작동하는지 알아보자.
b를 2의 보수로 바꾸면 0111, a+(b의 2의보수) = 1110
이 때 오버플로우가 발생해서 sign bit 가 음수가 된다.
이것을 해결하려면 set값과 오버플로우 플래그로 XOR을 취해서, 오버플로우가 일어났을 때 set을 뒤집으면 된다.
BEQ instruction
beq의 경우 두 값이 같은 경우만 걸러내야 하기 때문에 a-b=0이어야 한다.
이를 위해 a-b에 nor를 활용해서 뺄셈한 값의 모든 비트가 0인 경우를 찾아주자.
따로 멀티플렉서를 만들 필요는 없고 result값에 nor를 수행해주면 된다.
이 값은 주로 Zero 플래그를 set하는 데 쓰인다.
ALU Symbol
다음 그림은 alu를 간단하게 나타낸 심볼이다.
그림에는 없지만 result가 빠져나가는 부분에 zero 플래그가 있다.
overflow 판단법
마지막 alu의 carryin과 carryout으로 XOR을 진행한다.
둘이 일치하면 오버플로우가 일어나지 않고 다르면 일어난다고 볼 수 있다.
명령어를 생각보다 많이 구현할 수 있는데?
지금 만든 멀티플렉서는 총 3~4개의 input operation을 가지고 있다.
하지만 이 4개의 인풋을 가지고 총 10개의 명령어(and, or, nand, nor, sub, slt...등등)를 구현해냈는데, 이것은 하드웨어가 여러 번 재활용되고 있기 때문이다.
nand와 nor는 and와 or에 not연산을 취해서 만들었으며 sub, slt도 입력이 조금 다를 뿐 동작은 add와 다르지 않다.
이런 식으로 하드웨어를 재활용할 수 있는 한 최대한 여러 번 써서 비용을 절감하는 것이 CPU 성능 개선의 목표이다.
