명령어 컴퓨터 언어
명령어
하드웨어가 알아들을 수 있는 언어로 말하는 것
명령어 집합(ISA)
특정한 구조가 이해할 수 있는 명령들의 집합
RISC
- CISC와 비교했을 때 적은 수의 명령어를 가진다는 것
- RISC에서는 메모리 연산에 대한 별도의 명령어가 있음
- 로드(load)와 스토어(store)를 위한 별도의 명령어를 사용함으로써 CISC와 달리 명령어의 길이를 줄일 수 있음
- RISC는 파이프라이닝(pipelining) 기술을 사용
- 실행 중인 명령어와 다음에 실행될 명령어를 겹치게 처리함으로써 처리량을 높임
- RISC-V 명령어
- 32비트 명령어 워드(Instruction word)로 인코딩됩니다.
- 소수의 포맷으로 인코딩됩니다.
연산
RISC-V 연산
add a, b, c
b와 c를 더해 a에 저장하라
더해질 숫자 2개와 2개의 합을 기억할 장소(총 3개의 피연산자 필요)
addi x22, x22, 4 //x22 = x22 + 4
피연산자 중 하나가 상수인 산술연산 명령어를 지원
- 단점
- 오버플로우
- addi 명령어는 레지스터에 값을 더하는 명령어이기 때문에, 레지스터 값이 최대값을 넘어가는 경우 오버플로(overflow)가 발생
- 큰수를 더할 경우 여러번 사용해야함
- 큰 숫자를 더하는 경우에는 여러 개의 명령어를 사용해야 합니다. 이는 불필요한 명령어의 실행으로 인해 프로그램 실행 시간이 늘어나는 문제가 발생할 수 있습니다. 이러한 경우, 더 큰 범위의 값을 더하는 다른 명령어를 사용하는 것이 더 효율적
- 명령어 칸 중 하나를 차지
- 오버플로우
❗️변수 초기화 메서드
add x5 x0 x0 .... 1️⃣
addi x5 x0 7 .... 2️⃣
1️⃣ : 이렇게 되면 x5에 0이라는 값이 들어가게됨
2️⃣ : 이렇게 되면 x5에 7이 들어가게 됨
ld rd, offset(rs1)
메모리에서 데이터를 읽어와 레지스터에 저장하는 명령어
- ld x3 4(x1)
- 레지스터 x1에 저장된 값에 4를 더한 메모리 주소에서 8바이트 데이터를 읽어와 레지스터 x3에 저장
- ld : doubel word(8byte)
- lw : word(4byte)
- lh : half word(2byte)
- lb : byte(1byte)
sd x3 4(x1)
레지스터 x3의 값을 8바이트 크기의 더블워드(doubleword)로 가져와서, 레지스터 x1의 값에 4를 더한 메모리 주소 위치에 해당 값을 저장합니다. 만약 x1 레지스터의 값이 0x1000이라면, 프로세서는 x3 레지스터의 값으로부터 8바이트를 가져와 0x1004에서 시작하는 메모리 위치에 저장합니다.
- d, w, h b 순서로 동일하게 이용가능
레지스터
프로세서 내부에서 ALU(산술 논리 장치)에서 사용되는 피연산자(operand)를 저장하는 곳
SRAM으로 만들어짐
- 32bit를 word, 64bit는 double word라고 하는데 RISC-V구조에서는 double word를 자주 사용
- 산술 명령어의 모든 피연산자는 32개의 64bit 레지스터 중 하나여야 한다는 제약 추가
- CPU 내부에 위치해 있어서 데이터 접근이 빠르고 작은 양의 데이터를 보관
- sram을 사용하는 이유(작지만 빠른)
- 특별한 레지스터
- x0 : 항상 0이 저장
RAM(메모리)
RAM은 컴퓨터의 주기억장치로서, 프로그램과 데이터를 일시적으로 저장하는 용도로 사용
- CPU 밖에 위치
- CPU는 RAM에 저장된 데이터를 필요에 따라 읽어들이거나 쓰기 위해 메모리 버스를 통해 RAM과 통신
- dram으로 구성됨(sram에 비해 느리지만 큰양의 데이터 보관)
- 배열, 구조체, 동적 데이터와 같은 복합적인 데이터를 저장하는데 사용
- 산술 연산을 수행하려면 메모리에서 값을 레지스터로 로드하고 레지스터에서 결과를 다시 메모리로 저장해야합니다.(LOAD, STORE)
- 주소는 4의 배수
- 주로 RAM(메모리)의 주소는 8byte
MIPS나 ARM 같은 일부 ISA는 워드가 정렬되지 않으면 오류가 발생하지만, RISC-V는 정렬되지 않은 워드도 허용합니다. 이러한 정렬 제한은 메모리에서 데이터를 로드하거나 저장할 때 유용합니다.(대부분의 프로세서(ARM, MIPS 등)는 워드 정렬을 요구합니다. 즉, 워드(4바이트)의 시작 주소는 4의 배수))
❗️레지스터와 메모리 차이점
레지스터는 메모리보다 접근 속도가 빠릅니다.
메모리 데이터를 조작하려면 로드와 저장이 필요합니다.
이로 인해 더 많은 명령어가 실행되어야 합니다.
컴파일러는 변수를 가능한 한 레지스터에 할당해야 합니다.
덜 자주 사용되는 변수에 대해서만 메모리에 저장하도록 합니다.
레지스터 최적화는 중요합니다!
레지스터 수는 32개
CPU가 데이터를 처리하는 과정에서 메모리보다 빠른 속도로 데이터에 접근할 수 있는 작은 기억장치입니다. 반면에 메모리는 레지스터보다 접근 속도가 느리며, 데이터를 조작하려면 로드(load)와 저장(store) 명령어가 필요합니다. 이로 인해 더 많은 명령어가 실행되어야 하기 때문에 레지스터를 사용하는 것이 메모리를 사용하는 것보다 더 효율적입니다. 따라서 컴파일러는 변수를 가능한 한 레지스터에 할당하고, 덜 자주 사용되는 변수만 메모리에 저장하도록 합니다. 이러한 레지스터 최적화 작업은 프로그램의 실행 속도와 성능에 큰 영향을 미칩니다.
register spilling은 레지스터 개수가 정해져있기에 일어나는 현상
- 잘 겹치는 변수를 overlap해서 register에 저장
Endian
Big-endian은 데이터의 가장 중요한 바이트(Most Significant Byte, MSB)를 가장 낮은 주소에 배치하는 방식을 말합니다. 즉, 가장 큰 값이 메모리의 가장 작은 주소에 저장됩니다.
Little-endian은 데이터의 가장 중요한 바이트(Most Significant Byte, MSB)를 가장 높은 주소에 배치하는 방식을 말합니다. 즉, 가장 큰 값이 메모리의 가장 큰 주소에 저장됩니다. - RISC-V
RISC-V의 경우 데이터의 크기가 1byte보다 큰 경우
컴파일러
- 변수를 레지스터와 연관 짓기
- 배열이나 구조체 같은 자료구조를 메모리에 할당
- 더블워드 주소는 8byte 주소
- 연속된 더블 워드 주소는 8byte씩 차이가 남
- 자주 사용하는 변수를 레지스터에 배치하고 자주 사용하지 않는 것을 메모리에 넣음
- 스필링(spilling)
부호있는 수와 없는 수
(signed) int a; //부호 있음
(unsigned) (int) b; //부호 없음- 2의 보수 표현
- MSB가 양수일땐 0, 음수일땐 1
- 부호 바꾸기(간단한 예를 위해 여기서는 8bit 사용)
- 2 = 00000010
-2 = 11111101 + 1 = 11111110
즉, 보수를 구할때 양수에서 0과 1을 뒤집고 1을 더해주면 됨(반대도 동일)
부호 확장(Sign Extension)은 숫자를 표현할 때 더 많은 비트를 사용하는 것입니다. 이 때, 숫자의 값을 보존하기 위해 왼쪽에 있는 부호 비트를 복제합니다. 부호가 있는 값에 대해서는 부호를 확장하면 되지만, 부호가 없는 값에 대해서는 0으로 확장하면 됩니다.
예를 들어, 8비트에서 16비트로 숫자를 확장하는 경우, +2는 0000 0010에서 0000 0000 0000 0010으로, -2는 1111 1110에서 1111 1111 1111 1110으로 확장됩니다.
RISC-V 명령어 집합에서는, lb와 lh 명령어는 부호 있는 바이트와 하프워드를 확장하는 데 사용되며, lbu와 lhu 명령어는 부호 없는 바이트와 하프워드를 0으로 확장합니다.
RISC-V 명령어 필드
R-Format
- add, sub
field당 bit 할당
- opcode : 명령어가 실행할 연산의 종류, 연산자라 부름
- rd: 목적지(destination register)
- funct3 : 추가 opcode 필드
- rs1 : 첫 번째 근원지 피연산자 레지스터(index)
- rs2 : 두 번째 근원지 피연산자 레지스터
- funct7 : 추가 opcode 필드
I-Format
- ld, addi
load doubleword 명령어는 레지스터필드 2개와 상수 필드 1개가 필요
- 5bit보다 작은 필드를 쓰면 32보다 작은 값만 사용 가능
- 모든 명령어의 길이를 같게 하되, 명령어 종류에 따라 형식을 다르게함
- 즉, doubleword인 경우 명령어 형식이 다름
S-Type
- store
- immediate가 나눠진 이유
- 위 형태를 R-Type 형태와 공유가능하기에 위와 같이나눔
- immediate에 들어갈 숫자를 32(2^5)로 나누고 나머지는 5bit, 몫은 7bit에 작성
- ex) 240 / 32 = 7 ... 16
- 0000111 + 10000
shift(자리이동)
<<(slli), >>(srli)
- immed: 시프트할 위치 수
- Shift left logical
- 왼쪽으로 시프트하고 0 비트로 채웁니다
- i 비트만큼 slli를 하면 2의 i승을 곱합니다
- Shift right logical
- 오른쪽으로 시프트하고 0 비트로 채웁니다
- i 비트만큼 srli를 하면 2의 i승으로 나눕니다 (양수만 해당)
❓Why does immed field have 6 bits?
- 6bit shift = 2^6 = 64bit 이동(이 이상 이동하면 의미가 다시 원래대로 돌아가기에 의미가 없음)
AND, OR, NOT, XOR
- bitmask로 활용 가능
- 64bit중 특정 bit만 관심있는 경우 해당 부분만 1로 넣고 나머지를 0으로 넣으면 해당 부분의 bit만 뽑아내는것이 가능
- XOR : 두 bit가 같을때 0, 다를 때 1
- xor를 1로 다 두면 not의 연산을 할 수 있음
판단을 위한 명령어
if 문장과 같이 조건문 분기를 가짐
beq rs1, rs2, L1
▪ 만약 (rs1 == rs2) 이면, L1로 레이블된 명령어로 분기합니다.
bne rs1, rs2, L1
▪ 만약 (rs1 != rs2) 이면, L1로 레이블된 명령어로 분기합니다
blt rs1, rs2, L1
▪ if (rs1 < rs2) branch to instruction labeled L1
bge rs1, rs2, L1
▪ if (rs1 >= rs2) branch to instruction labeled L1
순환문
Loop: slli x10, x22, 3 //3bit 왼쪽으로 이동하면 2^3을 곱한것과 동일
- slli를 3칸 한 것은 메모리에서 한 주소를 이동한 것과 동일
프로시저 콜 명령어
jal x1, ProcedureLabel
- Address of following instruction put in x1
- Jumps to target address labeled ProcedureLabel
jalr x0, 0(x1)
- Like jal, but jumps to 0 + address in x1 ▪ Use x0 as rd (x0 cannot be changed) ▪ Can also be used for computed jumps
하드웨어의 프로시저 지원
프로시저
이해하기 쉽고 재사용 가능하도록 프로그램을 구조화 시키는 방법 중 하나
제공되는 인수에 따라 특정 작업을 수행하는 서브루틴
함수(라이브러리에 모듈화된 것들)
함수 바디에 뭐가들어가는지 아래에만 보여주고 싶다면 위에는 선언부분만 간단히 보여주고 아래에서 채워도 됨.
Steps required
- Place parameters in registers x10 to x17
- Transfer control to procedure
- Acquire storage for procedure
- Perform procedure’s operations
- Place result in register for caller
- Return to place of call (address in x1)
int foo(int); //함수명만 먼저 선언
int main(){
...
foo(3);
}
int bar(){
...
}
inf foo(int a){
...
bar()
}- main => foo => bar
- foo : caller와 callee 둘다 됨
- bar : 말단이라 callee
Memory layout
4Byte로 주소 표현
- text : program code
- static data
- 영구히 저장, 전역 area
- lifetime이 프로그램 전체에 걸침(프로그램이 종료되어야 없어짐)
- Dynamic data : heap 영역 저장
- return value of malloc을 잘 체크해야함(stack과 heap이 만나 터지지 않도록)
- Stack
- stack pointer를 활용한 stack영역에 데이터 저장
- stack pointer는 high address에서 시작해서 low address로 내려감
- statck에 저장하는 내용
- 매개변수 저장
- 함수가 끝나고 돌아갈 주소(호출지점)
- 함수 내에서 사용되는 변수(Local variable)
- 함수가 끝나게 되면 함수가 시작하기 전의 sp의 위치가 끝난 후와 동일하게 됨
- 즉, 함수가 돌아가는 동안에만 변수나 주소값이 저장됨
레지스터 할당
- x5 – x7, x28 – x31: temporary registers
- Not preserved by the callee
- x8 – x9, x18 – x27: saved registers
- If used, the callee saves and restores them
- x10 – x17: registers for parameters or return values in a function
- x1: return address register (i.e., link register)
- Used in jal and jalr
- 함수를 호출한 문장 다음 문장의 레지스터 주소를 가르킴
- 인스트럭션의 주소
- jal x1, ProcedureLabel
- Address of following instruction put in x1
- Jumps to target address labeled ProcedureLabel
- jalr x0, 0(x1)
- jump and link register
- register의 링크를 받아와 점프하라
- Like jal, but jumps to 0 + address in x1
- Use x0 as rd (x0 cannot be changed)
- Can also be used for computed jumps
- e.g., for case/switch statements
Branch Addressing
상대적인 위치로 표현
offset을 본인문장으로 두고 돌아가야할 장소가 현 문장에서 3문장 뒤라면 +12
6문장 전이라면 -24
- 루프나 탈출로 갈때 사용
- +12 -> +6
- 00..00110 = 6 // 6 x 12 + pc
- -20 -> -10
- 00..01010 = 10
- 10의 보수 = 11.110101 + 1 = 11..10110
- 따라서 나머지 immed의 bit는 1이고 뒤의 4bit만 보면 6이라
- 파란색 6으로 표시
- 만약 범위를 넘어가서 상대적 주소로 표시 못할 경우?
- loop으로 2개를 나눠서 2번 loop함
메모리 연산 문제
기본적인 덧셈
A가 Long이라 가정(8byte)
C code: g = h + A[8];
g in x23, h in x21, base address of A in x22
x5 is temporary registerIndex 8 requires offset of 64
8 bytes per word
ld x5,64(x22) // reg x5 gets A[8]
add x23, x21, x5 // g = h + A[8]
❓추가질문
offset base register 만약 A가 int(4byte라면)
lw $t0, 32($s3)
add $s1, $s2, $t0
만약 A가 short(2byte라면)
lh x5 16(x22)
배열 값 꺼내보기
C code:
long A[100]; # def in the 1st endition. int A[100]; according to the def of 2nd ed.
#우리는 int 4, long 8로 생각하고 ㄱㄱ
A[12] = h + A[8];
▪ h in x21, base address of A in x22
▪ x5 is temporary register
▪ Index 8 requires offset of 32
ld x5, 64(x22) // reg x5 gets A[8], A[8]의 데이터를 메모리에서 값을 x5레지스터 저장
add x5, x21, x5 // reg x5 gets h+A[8], x5의 값과 x21의 값을 더함, 그리고 값을 x5 저장
sd x5, 96(x22)
// Stores h+A[8] to A[12], 12인덱스, A는 long type 더블워드라 64+8*4 = 96
//A[12]에 더한 값을 저장해야 함으로 A[12]의 주소(96(x22))값에 x5값을 저장
if문
if (i==j) f = g+h;
else f = g-h;
▪ f, g in x19, x20 bne x22, x23, Else
add x19, x20, x21
beq x0, x0, Exit // unconditional
Else: sub x19, x20, x21
x22와 x23가 다르면 Else로 이동, 같으면 그냥 다음문장으로 넘어감(add문)
둘다 beq x0 x0 Exit으로 옴
while문과 배열 사용
C code:
while (save[i] == k) i += 1;
▪ i in x22, k in x24, address of save in x25Loop: slli x10, x22, 3 //왼쪽으로 shift한 값을 x10에 저장
add x10, x10, x25
ld x9, 0(x10) //x9에는 offset이 0인곳에서 x(10)만큼 이동한 주소값을 넣음
bne x9, x24, Exit //x9와 x24가 다르다면 Exit으로 이동
addi x22, x22, 1
beq x0, x0, Loop
Exit: …
slli x10, x22, 3: x22 레지스터의 값을 2진수로 표현했을 때 왼쪽으로 3칸 시프트한 값을 x10 레지스터에 저장합니다. 이는 x22를 8배한 것과 같습니다. long type이라 index에 8배해서 주소값에 더하면 save[i]를 표현할 수 있음add x10, x10, x25: x10 레지스터의 값을 x25 레지스터의 값과 더한 결과를 다시 x10 레지스터에 저장합니다. 이는 이전에 x22 레지스터를 8배한 값에 x25를 더한 결과를 의미합니다. 현재 x10은 save[i]에 해당하는 메모리 주소임. load를 통해 해당 값을 가져와야 연산가능ld x9, 0(x10): x10 레지스터의 값이 가리키는 주소에 있는 값을 메모리에서 로드하여 x9 레지스터에 저장합니다. 이는 x10 레지스터의 값이 가리키는 메모리 주소에 있는 값을 x9 레지스터에 저장하는 것을 의미합니다.bne x9, x24, Exit: x9 레지스터의 값과 x24 레지스터의 값이 다르면 Exit로 분기합니다. 이는 x9 레지스터에 저장된 값이 x24 레지스터에 저장된 값과 다르면 Exit로 분기하는 것을 의미합니다.addi x22, x22, 1: x22 레지스터의 값을 1 증가시킵니다. 이는 이전에 8배한 값을 가진 x22 레지스터에 1을 더한 것과 같습니다.beq x0, x0, Loop: 항상 참이므로, Loop로 분기합니다. 이는 항상 Loop로 분기하는 것을 의미합니다.
따라서 위 코드에서 각 레지스터는 다음과 같은 값을 나타냅니다.
- x22: while 루프에서 사용되는 i 변수의 값을 저장합니다.
- x24: while 루프에서 사용되는 k 변수의 값을 저장합니다.
- x25: save 배열의 주소를 저장합니다.
- x9: save[i] 변수의 값을 저장합니다.
- x10 레지스터는 save 배열의 인덱스를 계산하는 데 사용됩니다. C 코드에서
save[i]는save배열의i번째 인덱스를 참조하는 것이므로, RISC-V 어셈블리어에서는i * sizeof(int)값을 계산하여 save 배열의 인덱스를 구합니다. 따라서 slli 명령어를 사용하여 x22 값을 8배한 다음, x25 값과 더한 결과가 x10 레지스터에 저장됩니다. 이는 save 배열의 i번째 인덱스를 가리키는 주소를 계산하기 위한 작업입니다.
leaf 예제
long long : 8byte
C code: long long int leaf_example (
long long int g, long long int h, long long int i, long long int j) {
long long int f;
f = (g + h) - (i + j);
return f;
}
+ Arguments g, …, j in x10, …, x13
+ f in x20
+ temporaries x5, x6
+ Need to save x5, x6, x20 on stackleaf_example: #Leaf Procedure Example
addi sp,sp,-24 #(변수 3개치?)
sd x5,16(sp) #Save x5, x6, x20 on stack
sd x6,8(sp)
sd x20,0(sp)
add x5,x10,x11 #x5 = g + h
add x6,x12,x1 #x6 = i + j
sub x20,x5,x6 # f = x5 – x6
addi x10,x20,0 //f값을 x10으로 옮기는 이유 : 이게 약속이기 때문(반환값을 이곳으로 넣겠다는)
ld x20,0(sp) # Restore x5, x6, x20 from stack
ld x6,8(sp)
ld x5,16(sp)
addi sp,sp,24
jalr x0,0(x1) # Return to caller
- 함수가 연쇄호출될 경우
- x1과 같은 return address나 변수들을 stack 메모리에 저장하고 새로운 함수를 부름
- 새로운 함수의 return address는 다시 x1에 저장됨
- 함수 호출이 끝나면 이전 return address를 다시 register에 load(ld)
non_leaf example(재귀적)
하위 호출을 포함하는 프로시저(함수)에 대한 설명입니다. 만약 하위 호출이 더 깊은 수준으로 중첩된 경우, 호출자는 다음과 같은 일을 수행해야 합니다.
- 호출자는 호출 이후에 필요한 모든 인자(argument)와 임시 값(temporary)을 스택에 저장합니다.
- 호출자는 다음에 실행할 명령어 주소인 반환 주소(return address)를 스택에 저장합니다.
- 호출자는 하위 호출을 수행합니다.
- 하위 호출이 완료되면, 호출자는 스택에서 반환 주소와 필요한 인자/임시 값들을 가져옵니다.
- 호출자는 이전에 수행되었던 위치로 되돌아갑니다.
이렇게 하위 호출이 중첩될 때마다, 호출자는 반환 주소와 필요한 값들을 스택에 저장하고, 하위 호출이 완료될 때마다 스택에서 가져와야 합니다. 이것은 재귀 호출(recursive call)에서도 유용하게 사용됩니다. 이러한 호출 구조는 메모리 사용량을 증가시키기 때문에, 메모리 효율성을 높이기 위해 호출이 더 깊은 수준으로 중첩되지 않도록 주의해야 합니다.
C code:
long long int fact (long long int n)
{
if (n < 1) return 1;
else return n * fact(n - 1);
}
+ Argument n in x10
+ Result in x10
Leaf Procedure Example
fact:
addi sp,sp,-16
sd x1,8(sp) # Save return address and n on stack
sd x10,0(sp)
addi x5,x10,-1 # x5 = n - 1
bge x5,x0,L1 # if n >= 1, go to L1
addi x10,x0,1 # Else, set return value to 1
addi sp,sp,16 # Pop stack, don’t bother restoring values
jalr x0,0(x1) # Return
L1: addi x10,x10,-1 # n = n - 1
jal x1,fact # call fact(n-1)
addi x6,x10,0 # move result of fact(n - 1) to x6, fact 함수의 return 주소
ld x10,0(sp) # Restore caller’s n
ld x1,8(sp) # Restore caller’s return address
addi sp,sp,16 # Pop stack
mul x10,x10,x6 # return n * fact(n-1)
jalr x0,0(x1) # return
스택 포인터를 16바이트 만큼 조정합니다.
호출자 레지스터 $x1과 $x10에 저장된 값들을 스택에 저장합니다.
$x5 레지스터에 $x10 - 1의 값을 저장합니다.
$x5가 0보다 크거나 같은지 확인하는 분기 명령어(bge)를 수행합니다. $x5가 0보다 작으면 라벨 L1로 분기합니다.
$x10에 1을 저장합니다.
스택 포인터를 16바이트 만큼 되돌립니다.
호출자에게 반환합니다. 이때 $x1 레지스터에 저장된 값으로 점프합니다.
라벨 L1로 분기합니다.
$x10에 $x10 - 1의 값을 저장합니다.
$x1 레지스터에 "fact" 라벨이 가리키는 위치로 점프합니다. 이는 자기 자신을 재귀적으로 호출합니다.
$x6에 $x10의 값을 저장합니다.
스택에 저장된 값들을 다시 복원합니다.
$x10 레지스터에 스택의 0번지 주소에 저장된 값으로 복원합니다.
$x1 레지스터에 스택의 8번지 주소에 저장된 값으로 복원합니다.
스택 포인터를 16바이트 만큼 되돌립니다.
$x10에 $x10과 $x6을 곱한 값을 저장합니다.
호출자에게 반환합니다. 이때 $x1 레지스터에 저장된 값으로 점프합니다.
String Copy
void strcpy (unsigned char x[], unsigned char y[])
{
size_t i; //assume size_t is defined as long long int 8byte
i = 0;
while ((x[i]=y[i])!='\0') //null character
i += 1;
}
i in x19strcpy:
addi sp,sp,-8 // adjust stack for 1 doubleword
sd x19,0(sp) // push x19 == i
add x19,x0,x0 // i=0
L1: add x5,x19,x11 // x5 = addr of y[i] // x11 : second parameter
lbu x6,0(x5) // x6 = y[i] lbu u:unsinged
add x7,x19,x10 // x7 = addr of x[i]
sb x6,0(x7) // x[i] = y[i]
beq x6,x0,L2 // if y[i] == 0 then exit
addi x19,x19,1 // i = i + 1
beq x0, x0, L1 // next iteration of loop
L2: ld x19,0(sp) // restore saved x19
addi sp,sp,8 // pop 1 doubleword from stack
jalr x0,0(x1) // and return
x0: 항상 0 값을 가리키는 레지스터입니다.
x1: 함수의 리턴 주소를 저장하는 레지스터입니다.
x5: 문자열 y의 i번째 인덱스를 가리키는 레지스터입니다.
x6: y[i]의 값을 저장하는 레지스터입니다.
x7: 문자열 x의 i번째 인덱스를 가리키는 레지스터입니다.
x10: 문자열 x의 시작 주소를 가리키는 레지스터입니다.
x11: 문자열 y의 시작 주소를 가리키는 레지스터입니다.
x19: i 값(반복문 인덱스)을 저장하는 레지스터입니다.
위 코드에서는 strcpy() 함수의 구현을 위해 먼저 y 문자열의 i번째 인덱스를 가리키는 x5 레지스터를 계산하고, 해당 인덱스의 값을 x6 레지스터에 저장합니다. 그리고 x7 레지스터를 사용하여 x[i]에 y[i] 값을 복사합니다.
그리고, 만약 y[i] 값이 0이라면 문자열 복사가 끝난 것으로 판단하고, L2 레이블로 분기합니다. 그렇지 않다면 i 값을 1 증가시켜 반복문을 계속 진행합니다.
마지막으로, x19 레지스터를 사용하여 함수 호출 이전 i 값으로 복원하고, 스택에서 복원된 x19 값을 제거한 뒤, jalr 명령어를 사용하여 함수 호출 이전 주소로 복귀합니다.
Data race
다른 두 스레드가 동일한 메모리 위치에 접근하면서 적어도 하나의 스레드가 쓰기 작업을 수행하는 경우(병렬 처리)
- 두 개의 프로세서가 메모리 영역을 공유하는 경우
- 프로세서 1이 값을 쓰고, 그 다음에 프로세서 2가 값을 읽는다면, 만약 프로세서 1과 2가 동기화를 하지 않으면 데이터 레이스가 발생
- 접근 순서에 따라 결과가 달라질 수 있습
- 스레드 간의 동기화가 필요
int cnt = 0;
thread1() {
cnt++; }
thread2() {
cnt++; }thread1이 5번 실행되고 thread2가 3번 실행된다면 cnt의 최종 값은 8이 됩니다. 하지만 이 값이 보장되지는 않습니다.
❓why?
"cnt++" 연산은 실제로 "cnt = cnt + 1"로 해석됩니다. 이 경우, 메모리에서 cnt 값을 읽어와 1을 증가시킨 후 다시 메모리에 저장해야 합니다. 만약 thread1이 cnt 값을 읽어와 1을 증가시키는 도중, 이전에 실행되었던 thread2가 아직 cnt 값을 쓰기 전에 다시 실행된다면, thread1이 읽은 cnt 값은 이전 값으로 유효하지 않게 됩니다. 이러한 상황에서는 최종 cnt 값이 예상과 다를 수 있습니다.
- 스레드 간의 동기화가 필요
- 락(locks)과 같은 메커니즘을 사용하여 여러 스레드가 동시에 접근하지 못하도록 방지
- 원자적(atomic)인 메모리 읽기와 쓰기 연산이 필요
- 원자적 연산이란, 해당 연산이 한 번에 수행되는 것을 의미합니다. 즉, 다른 연산이 중간에 끼어들 수 없으며, 전체가 하나의 단위로 수행됩니다.(트랜잭션)
예시
atomic swap(원자적 교환) 연산
레지스터와 메모리 간의 값을 원자적으로 교환합니다. 이 연산은 레지스터와 메모리의 값을 동시에 읽어들인 다음, 서로의 값을 교환하고 다시 메모리에 쓰는 과정을 한 번에 수행합니다. 이렇게 하면 다른 연산이 중간에 끼어들어 값을 변경하는 경우를 방지할 수 있습니다.
원자적인 쌍(pair)의 연산
이 경우 두 개의 연산이 원자적으로 수행되어야 합니다. 예를 들어, compare-and-swap(CAS) 연산은 먼저 메모리에서 값을 읽어서 레지스터에 저장한 후, 레지스터의 값을 새로운 값으로 업데이트하려고 시도합니다. 그러나 이 때 메모리에서 읽어온 값이 여전히 이전 값과 같은지 비교하고, 같다면 새로운 값을 메모리에 쓰는 작업을 수행합니다. 이 과정에서 다른 연산이 끼어들어 값을 변경하는 경우를 방지할 수 있습니다.
- 하드웨어적으로 지원되어야 하며, 일반적으로 하드웨어 명령어의 형태로 제공
Load Reserved와 Store Conditional
- Load Reserved(lr.d)
- lr.d rd,(rs1)
- rs1이 가리키는 메모리 주소에서 데이터를 읽어와 rd에 저장하고, 해당 주소에 대한 예약(reservation)을 설정
- 다른 스레드가 해당 주소를 변경하면, 이 예약이 해제되어 Store Conditional 연산이 실패하게 됩니다.
- lr.d rd,(rs1)
- Store Conditional(sc.d)
- sc.d rd,(rs1),rs2
- rs1이 가리키는 메모리 주소에 rs2의 값을 저장하고, 이때 예약된 주소인지 확인
- 만약 예약된 주소가 변경되지 않았다면, Store Conditional 연산은 성공하고 rd에 0을 저장
- 다른 스레드가 해당 주소를 변경했다면, Store Conditional 연산은 실패하고 rd에 0이 아닌 값이 저장됩니다.
- sc.d rd,(rs1),rs2
- 두 개 이상의 스레드가 동시에 같은 메모리 주소에 접근하더라도, 예약 기능을 통해 경합 상태(race condition)를 방지
again: lr.d x10,(x20)
lr.d 명령어는 x20 주소에서 메모리 값을 읽어 x10 레지스터에 저장하면서 해당 메모리 주소에 대한 예약을 생성
sc.d x11,(x20),x23 // X11 = status
sc.d 명령어는 x20 주소에 rs2(x23) 레지스터의 값을 저장하고 이전에 생성된 예약이 존재하는지 확인, x11에는 예약이 존재하지 않으면 성공으로 0, 실패하면 0이외의 수를 넣음
bne x11,x0,again // branch if store failed
sc.d 명령어가 실패하면(즉, 이전에 x20 주소에 대한 예약이 취소되었거나 다른 스레드가 해당 주소에 쓰기 작업을 수행했을 때), 다시 lr.d 명령어로 다시 시도
addi x23,x10,0 // X23 = loaded value
sc.d 명령어가 실패하면(즉, 이전에 x20 주소에 대한 예약이 취소되었거나 다른 스레드가 해당 주소에 쓰기 작업을 수행했을 때), 다시 lr.d 명령어로 다시 시도
+1 연산이 빠져있음
Data Race Example
뮤텍스는 공유 자원을 여러 스레드가 사용할 때, 동시에 공유 자원에 접근하지 못하도록 보호하는 방법 중 하나
Lock:
addi x12,x0,1 // copy locked value
again:
lr.d x10,(x20) // read lock
bne x10,x0,again // check if it is 0 yet
sc.d x11,(x20),x12 // attempt to store
bne x11,x0,again // branch if fails
Unlock:
sd x0,0(x20) // free lock
Lock:
x12 레지스터에 1을 저장하는 `addi x12,x0,1` 명령어가 실행
again:
x20 레지스터에 있는 값을 읽어와 x10 레지스터에 저장하는 명령어인
`lr.d x10,(x20)`가 실행
`bne x10,x0,again` 명령어가 실행되어 x10 레지스터에 있는 값이 0이 아닐 경우에는
`again` 레이블로 분기(다른 스레드가 이미 뮤텍스 락을 획득한 경우)
`sc.d x11,(x20),x12` 명령어를 통해 x20 레지스터가 가리키는 메모리 위치에
x12 레지스터에 있는 값을 쓰려고 시도(`sc.d` 명령어는 `lr.d` 명령어로 읽은
값을 비교하여 이전의 값과 같으면 쓰기를 시도)
이전 값과 다른 경우에는 쓰기를 실패하고 `bne x11,x0,again` 명레이어가 실행되어
`again` 레이블로 분기, 값이 같아다면 성공 후 쓰레드 내 함수 실행
Unlock:
`sc.d` 명령어가 성공하면, `sd x0,0(x20)` 명령어를 실행하여 x20 레지스터가 가리키는
메모리 위치에 0 값을 씀(성공)
- x10: lock 변수의 값을 복사
- x11: Store conditional(sc.d) 작업 결과 값 (0: 성공, 1: 실패)
- x12: 값 1
- x20: lock 변수의 주소값을 가짐
뮤텍스를 사용하여 공유 자원에 대한 액세스를 제어하는 방법
- Lock: 뮤텍스 변수를 읽고, 그 값이 0이 아니면 다시 시도합니다.
- Unlock: 뮤텍스 변수를 0으로 설정합니다.
'컴퓨터 구조' 카테고리의 다른 글
| 컴퓨터 구조 6(병렬 프로그래밍, GPU&CPU 비교) (0) | 2023.06.28 |
|---|---|
| 컴퓨터 구조 5(캐시) (0) | 2023.06.28 |
| 컴퓨터 구조 4(파이프라이닝) (0) | 2023.06.28 |
| 컴퓨터 구조 3(Datapath) (0) | 2023.05.03 |
| 컴퓨터 구조 1(구성 요소 및 CPU TIME) (0) | 2023.05.03 |