Aufgabe 3 · 8 Punkte · trace
C in RISC-V übersetzen
C variable을 register에 배치하고, array index를 byte offset으로 바꾸고, loop 조건을 ‘끝나면 탈출’ branch로 뒤집습니다. 다른 함수를 부르면 ra와 오래 살아야 하는 값을 stack/s-register로 보호합니다.
공식 시험지와 공식 Musterlösung을 기준으로 작성했습니다. 그림 문제는 렌더된 원본 페이지도 함께 대조합니다.
BEGINNER CONCEPT LESSON
문제 풀이 전에 개념부터 배우기
용어를 모르는 상태에서 답을 외우지 않도록, 비유·그림·작은 예제·시험용 풀이 알고리즘을 별도 수업으로 만들었습니다.
원본 그림과 공식 해설 그림
diagram 문제는 text만으로 대체하지 말고 아래 원본을 확대해 선·stage·field를 직접 확인하세요.
MICRO WORK UNITS
6개 작업 단위로 학습
각 카드는 요구사항 → zero-base 개념 → 손풀이 단계 → 공식 결론 → 함정 → active recall 순서입니다.
3-1`swap`: 두 주소 계산
문제가 요구하는 것
`arr[i]`와 `arr[j]`의 주소를 만드세요.
이 카드는 빠른 복습용입니다. 처음 학습한다면 아래 독립 페이지에서 용어·비유·수식·작은 예제부터 읽으세요.
0. 이 소문제에 필요한 핵심 개념
`int` 하나는 4 Byte이므로 index×4가 byte offset입니다. `slli index,2`는 4배와 같습니다.
index 0, 1, 2의 작은 array와 loop 두 번만 손으로 실행해 보세요.
register 표, stack 전후 sp, branch의 참/거짓 target을 각각 대조하세요.
1. 이번 시험 문제에서 실제로 밟는 단계
- i를 2 bit left shift합니다.
- arr base를 더해 &arr[i]를 만듭니다.
- j도 같은 방식으로 &arr[j]를 만듭니다.
- 두 주소를 동시에 잃지 않도록 다른 temporary를 씁니다.
2. 단계가 도착해야 하는 공식 답지 기준 결론
`slli t0,a1,2; add t0,a0,t0`와 `slli t2,a2,2; add t2,a0,t2`.
3. 초보자가 자주 빠지는 오답과 이유
index를 그대로 base에 더하면 element가 아니라 byte 단위로 잘못 이동합니다.
4. 정답을 닫고 스스로 설명하기
64-bit long array라면 index scaling은 어떻게 달라지나요?
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11
3-2`swap`: load 두 번, store 두 번
문제가 요구하는 것
두 원소를 실제로 바꾸세요.
이 카드는 빠른 복습용입니다. 처음 학습한다면 아래 독립 페이지에서 용어·비유·수식·작은 예제부터 읽으세요.
0. 이 소문제에 필요한 핵심 개념
교환은 첫 값을 temporary에 보존해야 합니다. 먼저 두 값을 모두 load하고, 반대 주소로 store합니다.
index 0, 1, 2의 작은 array와 loop 두 번만 손으로 실행해 보세요.
register 표, stack 전후 sp, branch의 참/거짓 target을 각각 대조하세요.
1. 이번 시험 문제에서 실제로 밟는 단계
- arr[i]를 t1에 load합니다.
- arr[j]를 t3에 load합니다.
- t3를 arr[i] 주소에 store합니다.
- t1을 arr[j] 주소에 store합니다.
- leaf function이므로 ret합니다.
2. 단계가 도착해야 하는 공식 답지 기준 결론
`lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2); ret`.
3. 초보자가 자주 빠지는 오답과 이유
첫 값을 보존하기 전에 overwrite하면 두 원소가 같은 값이 됩니다.
4. 정답을 닫고 스스로 설명하기
두 index가 같아도 이 code가 안전한 이유는 무엇인가요?
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11
3-3`bubbleSort` Prolog
문제가 요구하는 것
swap을 부르기 전에 무엇을 stack에 저장해야 하나요?
이 카드는 빠른 복습용입니다. 처음 학습한다면 아래 독립 페이지에서 용어·비유·수식·작은 예제부터 읽으세요.
0. 이 소문제에 필요한 핵심 개념
`jal`은 ra를 덮고 caller-saved t/a register는 보존되지 않습니다. bubbleSort의 arr,n,i,j는 swap 뒤에도 필요하므로 s0–s3에 두고, callee인 bubbleSort가 원래 s-register 값을 저장합니다.
index 0, 1, 2의 작은 array와 loop 두 번만 손으로 실행해 보세요.
register 표, stack 전후 sp, branch의 참/거짓 target을 각각 대조하세요.
1. 이번 시험 문제에서 실제로 밟는 단계
- 16-byte alignment를 만족하는 frame 크기를 고릅니다.
- ra와 s0–s3를 stack에 저장합니다.
- a0→s0, a1→s1로 옮깁니다.
- i를 s2=0으로 초기화합니다.
2. 단계가 도착해야 하는 공식 답지 기준 결론
공식안: `addi sp,sp,-32`, `sw ra,0(sp)`, `sw s0,4(sp)` … `sw s3,16(sp)`, 그 뒤 s0=arr, s1=n, s2=0.
3. 초보자가 자주 빠지는 오답과 이유
저장할 값은 20 Byte지만 frame을 -20으로 만들면 16-byte alignment가 깨집니다.
4. 정답을 닫고 스스로 설명하기
왜 swap을 호출하지 않는 leaf function은 ra를 저장하지 않아도 될 수 있나요?
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11
3-4바깥 loop 조건
문제가 요구하는 것
`i < n-1`을 branch로 구현하세요.
이 카드는 빠른 복습용입니다. 처음 학습한다면 아래 독립 페이지에서 용어·비유·수식·작은 예제부터 읽으세요.
0. 이 소문제에 필요한 핵심 개념
Assembly loop는 보통 계속 조건의 반대를 써서 done으로 탈출합니다.
index 0, 1, 2의 작은 array와 loop 두 번만 손으로 실행해 보세요.
register 표, stack 전후 sp, branch의 참/거짓 target을 각각 대조하세요.
1. 이번 시험 문제에서 실제로 밟는 단계
- n-1을 temporary에 계산합니다.
- i>=n-1이면 done으로 갑니다.
- 새 바깥 반복마다 j=0으로 초기화합니다.
2. 단계가 도착해야 하는 공식 답지 기준 결론
`addi t0,s1,-1; bge s2,t0,done; li s3,0`.
3. 초보자가 자주 빠지는 오답과 이유
`blt i,n-1,body`도 가능하지만 label 구조가 달라집니다. 조건과 target의 의미를 함께 검산하세요.
4. 정답을 닫고 스스로 설명하기
n=1이면 body가 한 번도 실행되지 않는 이유를 trace해 보세요.
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11
3-5안쪽 loop와 비교
문제가 요구하는 것
`j < n-i-1`과 `arr[j] > arr[j+1]`을 구현하세요.
이 카드는 빠른 복습용입니다. 처음 학습한다면 아래 독립 페이지에서 용어·비유·수식·작은 예제부터 읽으세요.
0. 이 소문제에 필요한 핵심 개념
매 반복에서 현재 upper bound를 계산하고, 이웃 두 word는 같은 base address에서 offset 0과 4로 읽을 수 있습니다.
index 0, 1, 2의 작은 array와 loop 두 번만 손으로 실행해 보세요.
register 표, stack 전후 sp, branch의 참/거짓 target을 각각 대조하세요.
1. 이번 시험 문제에서 실제로 밟는 단계
- n-i-1을 t0에 계산합니다.
- j>=bound이면 outer_inc로 갑니다.
- j×4와 arr base로 &arr[j]를 만듭니다.
- 0(t1), 4(t1)에서 이웃 값을 읽습니다.
- arr[j]<=arr[j+1]이면 swap을 건너뜁니다.
2. 단계가 도착해야 하는 공식 답지 기준 결론
`sub t0,s1,s2; addi t0,t0,-1; bge s3,t0,outer_inc; slli t1,s3,2; add t1,s0,t1; lw t2,0(t1); lw t3,4(t1); ble t2,t3,inner_inc`.
3. 초보자가 자주 빠지는 오답과 이유
`j+1` 주소를 다시 처음부터 계산할 필요 없이 현재 주소+4를 쓸 수 있습니다.
4. 정답을 닫고 스스로 설명하기
왜 bubble sort의 안쪽 upper bound는 반복마다 1씩 줄어드나요?
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11
3-6swap 호출과 Epilog
문제가 요구하는 것
argument를 놓고 swap을 호출한 뒤 loop와 function을 끝내세요.
이 카드는 빠른 복습용입니다. 처음 학습한다면 아래 독립 페이지에서 용어·비유·수식·작은 예제부터 읽으세요.
0. 이 소문제에 필요한 핵심 개념
ABI에서 첫 세 argument는 a0,a1,a2입니다. s0–s3는 호출 뒤에도 유지되어 loop 상태를 계속 쓸 수 있습니다.
index 0, 1, 2의 작은 array와 loop 두 번만 손으로 실행해 보세요.
register 표, stack 전후 sp, branch의 참/거짓 target을 각각 대조하세요.
1. 이번 시험 문제에서 실제로 밟는 단계
- a0=arr, a1=j, a2=j+1을 만듭니다.
- `jal ra,swap`을 실행합니다.
- j를 증가하고 inner_loop로 돌아갑니다.
- inner loop 종료 후 i를 증가합니다.
- done에서 s-register와 ra를 복원하고 sp를 되돌립니다.
2. 단계가 도착해야 하는 공식 답지 기준 결론
공식안은 `mv a0,s0; mv a1,s3; addi a2,s3,1; jal ra,swap`, 이후 j++/i++, 마지막에 저장한 register를 역으로 load하고 `addi sp,sp,32; ret`.
3. 초보자가 자주 빠지는 오답과 이유
swap 호출 뒤 t-register 값은 믿지 마세요. loop에서 계속 필요한 값은 s-register에 있습니다.
4. 정답을 닫고 스스로 설명하기
Epilog에서 sp를 먼저 복원한 뒤 load하면 왜 잘못되나요?
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11