BubbleSort
RISC-V환경에서 bubble sort를 구현해보자.
caller(sort) : 한 칸씩 이동하며 인접한 숫자의 크기를 비교한다.
조건을 충족할 시 swap()을 호출하는 non-leaf 함수이다.
callee(swap) : 배열 array와 현재 인덱스 k를 인자로 받아서 array[k]와 array[k+1]의 위치를 바꾸는 leaf 함수이다.
배열 array는 x10에, k는 x11에, temp는 x5에 저장한다.
이제 위 내용을 구현해보자.
// swap
slli x6, x11, 2 // k값에 2번 shift(x4)하여 x6에 저장(offset)
add x6, x10, x6 // array주소에 오프셋 더한 값(=&array[k]) x6에 저장
lw x5, 0(x6) // x5에 array[k] 저장
lw x7, 4(x6) // x7에 array[k+1] 저장
sw x7, 4(x6)
sw x5, 0(x6)
jalr x0, 0(x1)
// sort
x1, x19~22 저장
addi x19, x0, 0 // for문의 i 선언
// 바깥 루프
outer:
bge x19, x11, exit1 // i >= n 인 경우 exit
addi x20, x19, -1 // j=i-1 선언
// 안쪽 루프
inner:
blt x20, x0, exit2
.
.
.
jal x1, swap
addi x20, x20, 01
jal x0, inner
addi x19, x19, 1 // 한 바퀴 돌았으면 i++
jal x0, outer // blt x19, x11, sort라고 적어도 된다
exit1:branch addressing
컴퓨터에서 브랜치 위치는 고유 인덱스 값으로 구별하지 않고 현재 주소에서 얼마나 떨어져있느냐로 구분한다.
예를 들어 bne x10, x11, 2000 같은 명령어를 쓴다면,
2000번 주소로 가라는 것이 아니고 현재 PC값 + 2000번째 주소로 이동하라는 뜻이다.
이렇게 PC값을 기준으로 생각하는 방법을 PC-relative addressing 이라고 한다.
target address = PC + immediate[12:1] x 2
브랜치 주소를 이동하는 머신 코드는 S-format과 유사하게 생겼다. 정확히는 SB-format이다.
| imm[12:6] | rs2 | rs1 | funct3 | imm[5:1] | opcode |
|---|---|---|---|---|---|
| 7bit | 5bit | 5bit | 3bit | 5bit | 7bit |
하지만 자세히 살펴 보면 다른 점이 있는데 immed 값에서 0번 비트를 사용하지 않는다.
이유는 RISC-V에서 주소값의 가장 오른쪽 비트 2개가 항상 0이기 때문이다.
그러면 1번 비트는 왜 사용하나요?
현재는 명령어가 전부 4바이트 단위이지만 나중에 2바이트 단위로 바뀔 수 있으므로 0으로 고정인 1번 비트도 그냥 사용한다.
branch jump
jal 등에서 브랜치를 이동하는 예제를 살펴보자.
bge x8, x9, exit이라고 하자.
bge일 때 PC가 80012이고 exit의 주소가 80024라면 주소 차이는 12이다.
이를 2진수로 변환하면 1100이다. 그런데 immed에서 0번 비트는 보지 않는다고 했으므로 건너뛸 거리는 110, 즉 6이 된다. 따라서 imm[12:1]이 6이 되는 것이다.
비트의 부호 주의
jump addressing
jal에서도 PC-relative addressing을 사용한다.
jal의 머신 코드는 U-format과 비슷하다.
| imm[20:1] | rd | opcode |
|---|---|---|
| 20bit | 5bit | 7bit |
긴 거리를 jump할 때는 PC를 기준으로 두지 않고 절대 주소(absolute address)를 사용한다. 이 때 사용하는 명령어가 LUI와 JALR이다.
LUI
| imm[31:12] | rd | opcode |
|---|---|---|
| 20bit | 5bit | 7bit |
imm값을 rd에 넣는 immediate 명령어이다.
특이하게 imm이 12~31비트를 본다. 이 때 비는 하위 12비트[11:0]은 jalr 명령어를 통해 전달받는다.
예를 들어 PC을 0x80000300으로 이동시킨다고 해보자.
이 때 jalr x0, 0x300(x20)이 주어졌다. 이것은 x20레지스터의 300번째 주소로 이동하라는 뜻이다. 그런데 jalr이 하위 12비트 주소를 담당한다고 했으므로 lui에서는 x20에 주소 할당(80000)의 주소를 제공해주면 된다.
따라서 lui x20, 0x80000
메모리 접근 방식 요약
- immediate addressing : immed값 사용
- register addressing : rs1, rs2값 등 레지스터 그대로 사용
- base addressing : 레지스터에 있던 값 + immed (jalr, lw, sw)
- PC-relative addressing : pc 기준으로 거리를 주소로 표현 (jal, beq, bne, blt, bge)
CISC
Complex Instruction Set Computer의 약자이다. RISC와 비교해보자.
CISC
- Instruction 종류가 많다. 한 Instruction이 좀 더 복잡한 연산을 수행한다.
- 프로그램을 구현할 때 Instruction개수가 적게 필요해서 코드 사이즈가 줄어든다.
- 복잡한 명령어를 한 사이클에 넣는 것이 불가능하다. 멀티 사이클이 필수이다.
- 명령어를 위한 많은 트랜지스터, 복잡한 명령어를 decoding하는 로직이 필요하다.
RISC
- Instruction 종류가 적다.
- 명령어 decoding이 간편해서 clock cycle을 줄일 수 있다.
- 간단한 명령어를 모두 한 사이클에 구현할 수 있어서 CPI가 낮다.
- 데이터에 바로 접근하는 기능이 없어서 load/store 명령어 사용이 잦다.
- 레지스터를 많이 사용하기 때문에 이를 위한 트랜지스터가 많이 필요하다.
어느 쪽이 나은지?
항상 한 쪽이 더 좋다고 말할 수 없다.
데스크탑이나 서버는 CISC, 모바일과 임베디드는 RISC가 강세로 상황에 맞춰 사용할 수 있다.
퀴즈 공지 : 27일 수업까지, 계산기/컨닝페이퍼x
