[Computer Architecture] Instructions

"Instructions"

[Von Neumann Architecture]

· Processing Unit과 Memory가 분리되어 있는 구조

→ Memory에서 Processing Unit으로 Program을 Load하여 실행한 후, 결과를 다시 Memory에 저장

[ISA]

· Instruction : Computer 언어

· Instruction Set Architecture : 명령어 집합 구조 → HW를 쉽게 사용하기 위함

CISC(Complex Instruction Set Computers)

· HW 강조, 가변 길이 명령어, 복잡한 Decoder

→ HW를 복잡하게 만들어 코드 길이를 줄이는 것이 목표

RISC(Reduced Instruction Set Computers)

· SW 강조, 고정 길이 명령어, 간단한 Pipeline

→ 간단한 명령어를 조합해(코드 길이 증가) 복잡한 일을 수행하며 간단한 명령어를 실행하므로 HW가 단순

[RISC-V]

[Arithmetic Operation]

f = (g + h) - (i + j);

(g = x19, h = x20, i = x21, j = x22 Register)

↓

add x5, x19, x20    // x5 = g + h;

add x6, x21, x22    // x6 = i + j;

sub x7, x5, x6    // x7 = x5 - x6;

· 임시 결과는 Register에 저장

· 64-bit 크기의 Register 32개(x0~x31)

  → Register가 너무 많으면 물리적으로 멀어지고 찾는데 시간이 걸려 속도가 느려짐/너무 적으면 Workspace 크기가 작아짐

· 32-bit 운영 

· Compiler의 역할 : 변수를 어떤 Register에 할당할지 결정하며, HW는 주어진 명령어를 단순히 실행만 함

** 32-bit CPU Architecture 환경 → 32-bit 운영체제 → Register의 크기 = 32-bit(처리 단위) + 주소 공간 = 2³²B(=4GB)

** 64-bit CPU Architecture 환경 → 64-bit 운영체제 → Register의 크기 = 64-bit(처리 단위) + 주소 공간 = 2⁶⁴B(=16EB)

    → But, 실제로 64-bit 환경에서 64-bit를 다 쓰지 않고 48-bit, 52-bit 정도만 사용 → 주소 공간 = 2⁴⁸B(=256TB)

[Memory]

· 배열이나 구조체처럼 큰 데이터는 Register에 다 들어가지 않으므로 Main Memory에 저장

  → But, RISC-V 명령어는 Register에 저장된 데이터만 처리 가능

  → 메모리에 있는 데이터는 먼저 CPU Register로 Load 되어 처리

· 주소가 0번부터 시작하는 1차원 배열이며, 현대 Computer는 1 Address = 1 Byte

[Data Transfer Instructions]

· 데이터를 한 위치에서 다른 위치로 전송하는 명령어

· Data Transfer Instuctions은 메모리 주소를 알아야 함

· 메모리 주소 지정은 항상 Byte 단위를 사용

a[12] = h + a[8];

(h = x21 Register)

ld x9, 64(x22)    // x9 = a[8];

add x20, x21, x9    // x9 = h + x9;

sd x9, 96(x22)    // a[12] = x9;

· x22 Register에 저장된 시작 주소(Base)로부터 64-Byte 떨어진 곳의 데이터를 x9에 임시 저장

· 계산한 결과 데이터를 x22 Register에 저장된 시작 주소(Base)로부터 96-Byte 떨어진 곳에 저장

** ld - 8B / lw - 4B / lh - 2B / lb - 1B

[Big Endian & Little Endian]

<0x01234567>

· Big Endian : 숫자가 가장 낮은 메모리 주소부터 저장되므로, 최상위 Byte가 가장 낮은 메모리 주소에 저장

  (01 - 0x100 → 23 - 0x101 → 45 - 0x102 → 67 - 0x103)

· Little Endian : 숫자가 가장 큰 메모리 주소부터 저장되므로, 최상위 Byte가 가장 높은 메모리 주소에 저장

  (67 - 0x100 → 45 - 0x101 → 23 - 0x102 → 01 - 0x103)

  → IBM System을 제외한 대부분의 Computer는 Little Endian 방식 사용

[Register vs Memory Operands]

· 대부분의 Program은 CPU에서 사용할 수 있는 Register 수보다 더 많은 변수 사용

→ 자주 사용되는 변수만 Register에 유지하고, 나머지 변수는 멀리 떨어진 메모리에 저장 =  Spilling

※ Spilling : 사용 빈도가 낮은 변수를 메모리로 옮기는 과정

[Constant (or Immediate) Operands]

addi x22, x22, 4    // x22 = x22 + 4;

· 상수 피연산자를 사용하는 Arithmetic Instructions

→ 상수를 포함시키면 메모리에서 변수를 불러오는 것보다 읽기 속도가 훨씬 빠르고 에너지 효율 증

· 0은 자주 사용하여 x0 Regsiter는 상수 0으로 고정

[Overflow & Underflow]

· Overflow : Arithmetic 결과가 주어진 bit 수로 표현 불가한 경우

· Underflow : 부동 소수점 연산 결과가 부동 소수점 데이터 형식이 표현할 수 있는 범위보다 작은 숫자 = 0에 가까운 숫자

[음수 표현 & 부호 확장]

· 음수 표현 : 2's Complement 표현을 사용

· 양수 부호 확장 : MSB까지 0으로 채움

· 음수 부호 확장 : MSB까지 1로 채움

[Instruction]

<add x9, x20, x21>

· Machine Language : 0/1로 이루어진 Binary Code

· Assembly Language : 사람이 읽을 수 있는 언어(like add x9, x20, x21)

▣ R-Type

· Arithmetic Operation

· 2 Source Register Operands

▣ I-Type

<addi x9, x9, 1>

· 1 Constant Operand(addi, ld) + 1 Source Register Operand

▣ S-Type

<sd x9, 64(x10)>

· 1 Constant Operand + 2 Source Register Operands

· rs1 = Base Address(x10) / rs2 = 메모리에 저장할 값(x9)

· immediate[4:0] 사용 X

▣ Logical Operation

<AND / OR / XOR>

· NOT은 XOR -1(111…111)로 처리

<Shift>

· srai : 오른쪽으로 Shift 후 MSB는 Shift하기 전 부호와 같은 것으로 확장

· srli : 오른쪽으로 Shift 후 MSB는 부호와 상관없이 0으로 확장

▣ Conditional Branch

· beq : Branch If Equal / bne : Branch If Not Equal

· blt : Branch If Less Than / bltu : Branch If Less Than & Unsigned

· bge : Branch If Greater Than Or Equal / bgeu : Branch If Less Than Or Equal & Unsigned

** bgt, ble가 없는 이유 : rs1과 rs2의 순서만 바꾸면 조건을 확인 가능

▶ if - else

if (i == j) {f = g + h;}

else        {f = g - h;}

· "Not Equal" 조건 만족 시 분기문(ELSE)으로 가서 "sub" 실행, 그렇지 않으면 "add" 실행 후 Exit (∵ 0 == 0)

▶ Loop

while (array[i] != k) {i += 1;}

· 반복 조건(0 == 0)이 만족하므로 처음으로(LOOP) 돌아가 실행

· (x10 == x24)인 경우 Exit

▶ Switch - Case

· if - else Chain : 여러 개의 조건 분기(Branch)를 연속으로 수행 → Case가 많아질수록 느려짐

· Branch Table : 각 Case의 주소들을 배열처럼 저장 후 해당 Index를 활용해 빠르게 Jump

** jalr rd, offset(rs1) : 간접 점프

· rs1 : 점프할 주소가 들어있는 Register

· rd : Return Address 저장

· offset : 추가 Offset

▣ Basic Block & Branch Stall

· Basic Block : 한 번 들어가면 중간에 빠져나가지 않는 Code → 흐름 예측 가능 & Pipeline 유지 가능

· Branch : 결과를 알아야 다음 Instruction 결정 → Pipeline 멈춤 = Branch Stall → 성능 저하

▣ Jump to/from Functions

· jal x1, FUNC : PC = FUNC 주소 & x1 = PC + 4 → 돌아올 위치를 x1에 저장

· jalr x0, 0(x1) : PC = x1 + 0 → x1 위치로 복귀

** jal x0 FUNC → Return Address 필요 X

▣ PC (Program Counter)

· 현재 실행 중인 Instruction의 주소

· 기본 증가 : PC = PC + 4 (∵ RISC-V Instruction = 4-Byte 고정 길이)

** Branch/Jump 시 PC 덮어쓰여짐 (beq : PC = Label / jal : PC = FUNC)

[Function Call]

▣ Register Spilling

· 변수 개수 계속 증가 → But, Register는 32개 밖에 없어서 모든 변수 저장 불가능

∴ 일부 값을 메모리(Stack)에 저장

Ex. sp = 1000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

# func1    addi   sp,   sp,    -24             → Stack에서 8 x 3 = 24-Byte 공간 확보 → 현재 sp = 976    sd     x10,  0(sp)       # a 저장   → sp = 976    sd     x11,  8(sp)       # b 저장   → sp = 984    sd     x12,  16(sp)      # c 저장   → sp = 992   # func2    addi   sp,   sp,    -24            → 현재 sp = 952    sd     x10,  0(sp)       # d 저장   → sp = 952    sd     x11,  8(sp)       # e 저장   → sp = 960    sd     x12,  16(sp)      # f 저장   → sp = 968   # func3    addi   sp,   sp,    -24            → 현재 sp = 928    sd     x10,  0(sp)       # g 저장   → sp = 928    sd     x11,  8(sp)       # h 저장   → sp = 936    sd     x12,  16(sp)      # i 저장   → sp = 944 Colored by Color Scripter

cs

· 최신 함수(func3)가 맨 위 → LIFO(Last In First Out)

** RISC-V의 "x2" Register = Stack의 현재 위치(sp)

** Stack : 아래로 증가 / Heap : 위로 증가

※ Stack Pointer : 다음 데이터를 어디에 저장할지 알려주는 역할 (Push : 저장 → sp 감소 / Pop : 복원 → sp 증가)

∴ Register 부족 문제를 해결하기 위해, 함수 호출 시 Stack을 사용하고 sp(x2 Register)가 해당 위치를 관리

▣ Memory Space Organization

· Stack : 함수의 지역 변수와 반환 주소가 저장되며, 낮은 주소 방향으로 성장 & Compiler에 의해 자동으로 관리

· Heap : 동적 메모리 할당 영역으로, 높은 주소 방향으로 성장 & Programmer가 "malloc & free"를 이용해 명시적으로 관리

                → free( ) 누락 시 Memory Leak 발생

▣ Function Call Translation

① Stack Pointer인 x2 Register를 -24만큼 이동해 3개의 공간 확보

② 기존 함수가 사용 중이던 x18, x19, x20을 Stack에 임시 저장

③ add, sub 명령어로 수식 계산 후, 반환 값은 x10 Register에 복사

④ Stack에 저장해둔 기존 Register 값들을 다시 Load(ld)하여 복원한 후, Stack Pointer를 제자리로 되돌림

⑤ jalr 명령어로 호출자에게 복귀

▣ Calling Convention for Registers

· x0 : 항상 0으로 고정

· x1 : 반환 주소 (ra)

· x2 : Stack Pointer (sp)

· x3 : Global Pointer (gp)

· x4 : Thread Pointer (tp)
· x5 ~ x7 : 임시 Register (마음대로 변경 가능)
· x8 ~ x9 : 반드시 함수 종료 전에 원래 상태로 복구해야 하는 보존 Register

· x10 ~ x17 : 임시 Register (마음대로 변경 가능)

· x18 ~ x27 : 반드시 함수 종료 전에 원래 상태로 복구해야 하는 보존 Register

· x28 ~ x31 : 임시 Register (마음대로 변경 가능)

▣ Nested Function Calls (중첩 함수 호출)

· 함수 내부에서 자기 자신을 다시 호출해야 하는 재귀 함수

→ 복귀할 주소가 담긴 x1과 인자 n이 담긴 x10 Register를 Stack에 지속적으로 보존(sd) 필수
· 재귀 호출 분기(jal x1, factorial)를 다녀온 후, Stack에서 n과 복귀 주소를 복원(ld)하고 두 값을 곱하여 반환

▣ Function Frame & Frame Pointer

· Register에 모두 담을 수 없는 큰 지역 변수(배열, 구조체 등)는 Stack의 일부인 Function Frame에 저장

· RISC-V는 "x8" Register를 Frame Pointer(fp)로 지정하여, 현재 함수 Frame의 기준점(첫 번째 Double Word)을 가리키게 함

> Stack Pointer : Stack의 최상단 위치를 알려줌 → 함수 실행 중 위치가 변할 수 있어 상수 Offset만으로 변수의 위치 추적 어려움

> Frame Pointer : 위치가 고정되어 있어 Frame 내의 데이터 주소를 훨씬 안정적으로 계산 가능

▣ Arrays vs Pointers

<Array Indexing>

· Loop를 돌 때마다 Index에 8을 곱하는 연산(slli)과 기준 주소에 더하는 연산(add)을 매번 수행

<Pointer>

· Pointer 변수 값 자체를 매 Loop마다 8-Byte씩 바로 증가 → Loop 내 명령어 수가 Array Indexing 방식보다 적음

∴ 배열 크기가 클수록 Pointer를 사용하는 방식이 더 빠르게 실행

[Handling Data]

▣ Character Data

· 문자는 8-bit ASCII Code로 표현 → Size = 1-Byte

lbu x12, 0(x10)

· lbu(부호 없는 Byte Load) : 메모리에서 1-Byte만 가져오는 명령어

→ 하위 1-Byte를 채우고 상위 7-Byte는 0으로 채워짐

sb x12, 0(x10)

· sb(Byte 저장) : Register의 최하위 1-Byte만 메모리에 저장할 때 사용하는 명령어

▣ String Data

· 문자열은 가변적인 문자들의 그룹이며, ASCII 규약상 맨 마지막에 NULL 문자(\0)를 배치해 문자열의 끝을 표시

· strcpy(문자열 복사) : "lbu"로 원본 문자를 하나씩 읽고, "sb"로 복사본에 저장하는 과정을 반복

→ Loop 진행 중 방금 Load한 문자가 0인지 확인(beq x6, x0, EXIT)하여 문자열의 끝에 도달 시 Loop 종료

[Instruction Format]

▣ U-Type Format

· 명령어 자체에 상수를 담는 I-Type(Ex. addi)은 공간이 12-bit밖에 되지않아 큰 상수를 담기 불가능 (Load 3,998,976)

· lui : 20-bit 상수 값을 대상 Register의 32-bit 중 상위 20-bit에 채우고, 하위 12-bit는 0으로 남김 (3,997,696)

→ 이후 addi로 결합(+1280)하여 나머지 하위 12-bit를 채워 32-bit 상수를 완성 (3,998,976)

** 하위 12-bit의 MSB가 1로, 음수를 유발(부호 확장 시 1로 채움)할 경우 "lui" 값에 미리 1을 더해 보정하는 기술 사용

▣ SB-Type Format

· 조건 분기 명령어는 SB-Type 형식 사용 (상수를 분리하여 rs1, rs2, opcode의 위치를 다른 명령어 형식과 동일하게 고정)

· -4096 ~ +4094 Byte까지 2의 배수로 주소 지정 가능

** 2의 배수 단위로만 이동 = LSB가 항상 0

→ imm[0]을 제외하고 이진수 작성 & MSB는 부호 확장(0 → 0 / 1 → 1)

    (Ex. -16 = 1111_1111_0000 → 1111111 + 10001)

** RISC-V의 기본 명령어 길이는 32-bit(= 4-Byte)

→ 명령어들이 4-Byte 간격으로 메모리에 저장되어 있다면 점프도 당연히 4의 배수 단위로 주소를 지정하는 것이 합리적

→ But, 코드 용량을 줄이기 위해 16-bit(= 2-Byte) 길이의 압축 명령어 확장을 지원할 수 있도록 2의 배수 단위로 주소를 지정

▣ UJ-Type Format

· 점프를 수행하는 jal 명령어는 UJ-Type 형식 사용 (상수를 분리하여 rd와 opcode의 위치를 다른 명령어 형식과 동일하게 고정)

· 상수를 담을 수 있는 공간이 총 20-bit → ± 2²⁰ - Byte 범위 내의 메모리 주소 표현 가능 

** 20-bit로 주소를 0번지부터 가리키면 도달할 수 있는 최대 한계치가 약 2MB

∴ 절대 주소를 사용하지 않고 현재 위치(PC)로부터 얼마나 떨어져 있는지를 기준으로 하는 PC 상대 주소 지정 방식을 사용

[PC Relative Addressing]

<Address = PC + Offset>

· Program 크기의 한계를 없애기 위해 분기 명령어는 직접 주소 대신 PC 상대 주소 지정 방식 사용

· SB-Type : PC 기준 ± 2¹⁰ - Word / UJ-Type : PC 기준 ± 2¹⁸ - Word 범위 내의 명령어 위치로 이동 가능

▣ Branching Far Away

· 호출해야 할 함수가 PC 상대 주소로 닿지 않는 아주 먼 곳에 있는 경우

① "lui" 명령어로 32-bit 목표 주소의 상위 20-bit를 임시 Register에 Load

② "jalr" 명령어가 나머지 하위 12-bit를 더해 해당 주소로 점프

[Addressing Mode]

▣ Immediate Addressing

· 명령어의 Field 안에 데이터 상수 값이 직접 포함

▣ Register Addressing

· 해당 Register ID를 이용해 Register 파일 내부의 데이터를 사용

▣ Base Addressing

· Register에 들어 있는 기준 주소에 명령어 안의 상수 Offset을 더해 최종 메모리 주소 찾기

▣ PC Relative Addressing

· 현재 실행 중인 PC 값에 명령어 안의 Offset을 더해 분기할 목적지 메모리 주소를 지정

[Pseudo Instructions]

[Appendix]

[Reference]

· 2_instructions (Computer Architecture) - William J. Song