---
schema_version: 1
exam_id: "sose26-probeklausur"
aufgabe: 3
unit_id: "3-2"
source_group_id: "3"
official_exam: true
official_solution: true
language: "ko"
---
# 3-2 — `swap`: load 두 번, store 두 번
> **학습 목표:** 두 element 값을 먼저 별도 temporary에 load한 뒤 반대 주소로 store해 loss 없이 swap하고 leaf function을 반환한다.
>
> **왜 따로 배우는가:** swap의 핵심은 instruction 수가 아니라 값의 lifetime입니다. 첫 store 전에 두 원본 값을 확보해야 하며, 주소와 값을 서로 다른 register로 추적하면 alias 상황에서도 올바른 순서를 설명할 수 있습니다.
>
> **범위:** Aufgabe 3 · 8점 Aufgabe의 최소 학습 단위 · 시험 p7–8 · 공식 해설 p8–11
## 1. 문제 원문 (Deutsch)
이 unit은 공식 Teilaufgabe 또는 표의 한 행·한 access를 학습 가능한 최소 단위로 다시 나눈 것입니다. 아래 전사는 source group `3`의 공식 독일어 문제 원문이며, 페이지 이미지를 바로 뒤에 함께 두어 코드·표·도식을 대조할 수 있게 했습니다.
~~~text
Aufgabe 3: C in RISC-V übersetzen
void swap(int *arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void bubbleSort(int *arr, int n)
{
for (int i = 0; i < n - 1; i++){
for (int j = 0; j < n - i - 1; j++){
if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
}
}
Implementieren Sie die vorgestellten Funktionen in Assembler. Der von Ihnen geschriebenen Code muss die gleiche Funktionalität haben und möglichst nah an der Implementierung von C sein.
Hinweise:
• Es ist garantiert, dass das Array arr mindestens ein Element enthält.
• Variable n speichert die Länge von arr.
• Verwenden Sie innerhalb der Funktionen folgende Registerbelegung zur Speicherung der Variablen: s0 = arr, s1 = n, s2 = i, s3 = j
• Jede Funktion muss man als Unterprogramm betrachten.
Lösung:
~~~
*공식 시험 원문: `exam-p07.png` · Probeklausur.pdf · PDF p.7*
*공식 시험 원문: `exam-p08.png` · Probeklausur.pdf · PDF p.8*
### 이 unit에서 풀 항목
두 원소를 실제로 바꾸세요.
## 2. 쉬운 한국어 해석
문제 3: C를 RISC-V로 번역하기
void swap(int *arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
void bubbleSort(int *arr, int n)
{
for (int i = 0; i < n - 1; i++){
for (int j = 0; j < n - i - 1; j++){
if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
}
}
위에 제시된 함수들을 어셈블리로 구현하시오. 작성한 코드는 C 구현과 동일한 기능을 가져야 하며, 가능한 한 C 구현에 가깝게 작성해야 한다.
주의사항:
• 배열 arr에는 적어도 한 개의 원소가 있음이 보장된다.
• 변수 n에는 배열 arr의 길이가 저장되어 있다.
• 함수 안에서 변수를 저장할 때 다음 레지스터 배치를 사용하시오: s0 = arr, s1 = n, s2 = i, s3 = j.
• 각 함수는 하나의 서브루틴으로 간주해야 한다.
답안:
### 이 unit에 해당하는 최소 작업
두 원소를 실제로 바꾸세요.
이 문제에서 최종 결과만 맞히는 것보다 중요한 것은 `3-2`에 필요한 중간 판단을 답안지에 남기는 것입니다.
## 3. 무엇을 묻는 문제인가
### 공식 문제의 요구사항
- C 함수 swap을 동일한 동작의 RISC-V 어셈블리 서브루틴으로 구현한다.
- C 함수 bubbleSort를 중첩 반복문, 조건문, swap 호출까지 보존하여 RISC-V 어셈블리로 구현한다.
- 배열 원소 주소 계산, 함수 호출, 레지스터 보존, 반환 동작을 포함해 C 의미와 RISC-V 호출 규약을 함께 만족시킨다.
### 조건과 제약
- arr에는 최소 한 원소가 있다.
- n은 arr의 길이이다.
- 함수 내부 변수 배치는 s0=arr, s1=n, s2=i, s3=j로 지정되어 있다.
- swap과 bubbleSort를 각각 독립적인 Unterprogramm으로 취급한다.
- 작성한 어셈블리의 기능은 C와 같아야 하며 가능한 한 C 구조에 가깝게 작성해야 한다.
### 원문 오탈자·도식 관련 주의
- 시험 PDF p7에 문제와 코드가 있고 p8은 'Lösung:'만 있는 빈 답안 페이지이다.
- 원문의 'Jede Funktion muss man als Unterprogramm betrachten.'는 다소 어색한 독일어 표현이지만 의미를 수정하지 않고 보존했다.
- [문제–공식 해설 차이] 원문은 'innerhalb der Funktionen'에서 s0=arr, s1=n, s2=i, s3=j를 사용하라고 읽히지만, 공식 swap 해설은 a/t-register만 사용하고 이 지정 배치를 bubbleSort의 장기 상태에 적용한다. 공식 코드는 ABI상 유효하나 문구를 문자 그대로 적용한 답과는 차이가 있다.
- 코드 들여쓰기는 PDF 시각 확인 결과에 맞춰 정리했으며 식, 조건, 레지스터 이름과 상수는 변경하지 않았다.
### 도식 시각 확인 상태
- **도식 의존 여부:** 이 최소 unit의 핵심 판정은 텍스트·수식·코드로 재현할 수 있습니다.
- **공식 페이지 상태:** exam-p07.png, exam-p08.png, solution-p08.png가 원문 대조용으로 렌더되어 연결되어 있습니다.
### 이 unit의 학습 목표
- **관찰 가능한 목표:** 두 element 값을 먼저 별도 temporary에 load한 뒤 반대 주소로 store해 loss 없이 swap하고 leaf function을 반환한다.
- **출제 의도:** swap의 핵심은 instruction 수가 아니라 값의 lifetime입니다. 첫 store 전에 두 원본 값을 확보해야 하며, 주소와 값을 서로 다른 register로 추적하면 alias 상황에서도 올바른 순서를 설명할 수 있습니다.
- **공식 근거 범위:** SoSe26 Probeklausur 시험 p7 Aufgabe 3 `swap`의 load/store 부분과 공식 해설 p8의 네 memory instruction 및 leaf `ret` 범위.
- **Aufgabe 공통 선수지식:** C variable을 register에 배치하고, array index를 byte offset으로 바꾸고, loop 조건을 ‘끝나면 탈출’ branch로 뒤집습니다. 다른 함수를 부르면 ra와 오래 살아야 하는 값을 stack/s-register로 보호합니다.
## 4. 선수 개념과 핵심 용어
### lw
- **뜻:** memory의 32-bit word를 register로 읽는 load instruction입니다.
- **이 문제에서:** `&arr[i]`와 `&arr[j]`에서 원본 두 값을 t1과 t3에 보존합니다.
### sw
- **뜻:** register의 32-bit word를 memory address에 쓰는 store instruction입니다.
- **이 문제에서:** 두 load가 끝난 뒤 t3를 i 주소, t1을 j 주소에 씁니다.
### value lifetime
- **뜻:** 원본 값이 마지막 store에 사용될 때까지 register에 남아 있어야 하는 기간입니다.
- **이 문제에서:** 첫 값을 overwrite하기 전에 t1에 보존해야 하는 이유입니다.
### leaf function
- **뜻:** 실행 중 다른 함수를 호출하지 않는 함수입니다.
- **이 문제에서:** `swap`이 ra를 덮지 않으므로 별도 Prolog 없이 `ret`할 수 있음을 설명합니다.
### 이 문제에 적용할 풀이 규칙
### 규칙 1. load-load-store-store 규칙
두 원본 값을 모두 register에 확보한 뒤에야 어느 memory 위치도 안전하게 overwrite할 수 있습니다.
- **시험지에 남길 것:** instruction 왼쪽에 `L1, L2, S2→1, S1→2` 순서를 표시합니다.
### 규칙 2. 주소와 값 register 분리
t0/t2는 주소, t1/t3는 값으로 역할을 고정하면 store operand를 뒤집는 실수를 줄입니다.
- **시험지에 남길 것:** `t0=&i, t1=old_i, t2=&j, t3=old_j` register 표를 유지합니다.
### 규칙 3. leaf return 규칙
다른 함수를 `jal`로 호출하지 않으면 incoming ra가 덮이지 않으므로 이 단순 swap은 저장 없이 ret할 수 있습니다.
- **시험지에 남길 것:** call instruction이 없음을 확인한 뒤 마지막에 `ret`을 둡니다.
### 공식 문제 전에 푸는 작은 유사 예제
**문제:** 주소 p와 q의 초기 값이 각각 7과 19이고 p는 t0, q는 t2에 있다. t1과 t3를 값 temporary로 써서 교환 code와 각 단계 memory 상태를 적으세요.
**주어진 것**
- `memory[p]=7`, `memory[q]=19`입니다.
- p와 q는 서로 다른 주소입니다.
### 예제 단계 1. p와 q의 값을 모두 load합니다.
- **왜:** memory를 바꾸기 전에 두 원본을 register에 보존해야 합니다.
- **종이에:** `lw t1,0(t0) # t1=7; lw t3,0(t2) # t3=19`
### 예제 단계 2. q의 원본 t3를 p에 store합니다.
- **왜:** p의 원본 7은 이미 t1에 보존되어 있어 overwrite해도 잃지 않습니다.
- **종이에:** `sw t3,0(t0) # memory[p]=19`
### 예제 단계 3. p의 원본 t1을 q에 store합니다.
- **왜:** 두 번째 반대 방향 write로 swap을 완성합니다.
- **종이에:** `sw t1,0(t2) # memory[q]=7`
**예제 정답:** `lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2)`이고 최종 값은 p=19, q=7입니다.
**독립 검산:** 최종 두 값의 multiset `{7,19}`가 초기와 같고 위치만 바뀌었는지 확인합니다.
## 5. 공식 정답 요약
**공식 결론:** `lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2); ret`.
### 시험지 문장별 정답 해설
아래는 시험지의 항목 순서를 그대로 유지합니다. 각 항목에서 원문 → 한국어 번역 → 정답 → 판단 근거 → 실제로 쓸 답을 바로 이어서 읽으세요.
### 현재 소문제의 요구·판단·답을 한 흐름으로 연결
### `3-2`에서 정확히 답할 대상
- **시험지가 요구하는 답:** 두 원소를 실제로 바꾸세요.
- **이 소문제의 공식 답:** `lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2); ret`.
### 판단 1. `arr[i]`의 원본 값을 t1에 load합니다.
- **왜:** i 위치가 나중에 overwrite되어도 원래 값을 j 위치에 쓸 수 있게 보존합니다.
- **이 판단에서 답안지에 남길 것:** `lw t1,0(t0) # t1=old arr[i]`
### 판단 2. `arr[j]`의 원본 값을 t3에 load합니다.
- **왜:** 첫 store 전에 두 번째 원본도 확보해야 두 값 중 하나를 잃지 않습니다.
- **이 판단에서 답안지에 남길 것:** `lw t3,0(t2) # t3=old arr[j]`
### 판단 3. t3의 `arr[j]` 원본을 i 주소에 store합니다.
- **왜:** swap에서는 각 값을 반대편 주소에 써야 합니다.
- **이 판단에서 답안지에 남길 것:** `sw t3,0(t0) # arr[i]=old arr[j]`
### 판단 4. t1의 `arr[i]` 원본을 j 주소에 store합니다.
- **왜:** 남은 원본을 반대편에 써서 교환을 완성합니다.
- **이 판단에서 답안지에 남길 것:** `sw t1,0(t2) # arr[j]=old arr[i]`
### 판단 5. 다른 함수를 호출하지 않은 leaf function에서 `ret`합니다.
- **왜:** swap 내부에서 ra를 덮는 jal이 없으므로 caller가 준 return address가 그대로 남아 있습니다.
- **이 판단에서 답안지에 남길 것:** 마지막 줄에 `ret # jal 없음, ra unchanged`를 씁니다.
### 위 판단이 최종 답으로 이어지는 이유
교환은 첫 값을 temporary에 보존해야 합니다. 먼저 두 값을 모두 load하고, 반대 주소로 store합니다.
### 답안 작성 시 주의
첫 값을 보존하기 전에 overwrite하면 두 원소가 같은 값이 됩니다.
*공식 Musterlösung/Hinweise: `solution-p08.png` · Probeklausur Musterlösung und Hinweise.pdf · PDF p.8*
## 6. 풀이 전략
1. arr[i]를 t1에 load합니다.
2. arr[j]를 t3에 load합니다.
3. t3를 arr[i] 주소에 store합니다.
4. t1을 arr[j] 주소에 store합니다.
5. leaf function이므로 ret합니다.
## 7. 단계별 상세 풀이
### 단계 1. `arr[i]`의 원본 값을 t1에 load합니다.
- **이유:** i 위치가 나중에 overwrite되어도 원래 값을 j 위치에 쓸 수 있게 보존합니다.
- **종이에 남길 것:** `lw t1,0(t0) # t1=old arr[i]`
- **완료 기준:** t1이 주소가 아니라 첫 원본 값으로 register 표에 기록되어 있습니다.
- **막힐 때 힌트:** t0에는 이미 `&arr[i]`가 있습니다.
- **가장 흔한 첫 오류:** `lw t0,0(t0)`로 주소 register 자체를 덮어 이후 store 주소를 잃는 것입니다.
### 단계 2. `arr[j]`의 원본 값을 t3에 load합니다.
- **이유:** 첫 store 전에 두 번째 원본도 확보해야 두 값 중 하나를 잃지 않습니다.
- **종이에 남길 것:** `lw t3,0(t2) # t3=old arr[j]`
- **완료 기준:** t1=old_i와 t3=old_j가 동시에 live입니다.
- **막힐 때 힌트:** 아직 store를 실행하지 마세요.
- **가장 흔한 첫 오류:** 첫 load 직후 store해 j의 원본을 읽기 전에 덮는 것입니다.
### 단계 3. t3의 `arr[j]` 원본을 i 주소에 store합니다.
- **이유:** swap에서는 각 값을 반대편 주소에 써야 합니다.
- **종이에 남길 것:** `sw t3,0(t0) # arr[i]=old arr[j]`
- **완료 기준:** store data=t3, base=t0의 역할이 주석과 일치합니다.
- **막힐 때 힌트:** 첫 destination 주소는 `&arr[i]`, data는 j에서 load한 값입니다.
- **가장 흔한 첫 오류:** `sw t1,0(t0)`로 원래 값을 같은 위치에 다시 써 아무 변화가 없는 것입니다.
### 단계 4. t1의 `arr[i]` 원본을 j 주소에 store합니다.
- **이유:** 남은 원본을 반대편에 써서 교환을 완성합니다.
- **종이에 남길 것:** `sw t1,0(t2) # arr[j]=old arr[i]`
- **완료 기준:** 두 memory 위치가 서로의 old 값을 가지며 원본 둘이 보존되었습니다.
- **막힐 때 힌트:** 두 번째 destination은 t2가 가리키는 j 주소입니다.
- **가장 흔한 첫 오류:** store base를 또 t0로 사용해 i 위치만 두 번 쓰는 것입니다.
### 단계 5. 다른 함수를 호출하지 않은 leaf function에서 `ret`합니다.
- **이유:** swap 내부에서 ra를 덮는 jal이 없으므로 caller가 준 return address가 그대로 남아 있습니다.
- **종이에 남길 것:** 마지막 줄에 `ret # jal 없음, ra unchanged`를 씁니다.
- **완료 기준:** 네 memory instruction 뒤에 ret가 있고 불필요한 stack frame을 만들지 않았습니다.
- **막힐 때 힌트:** 함수 본문에 call instruction이 있는지 찾아보세요.
- **가장 흔한 첫 오류:** ret를 생략하거나 leaf라는 이유만으로 a/t register 값을 caller에게 보존해야 한다고 가정하는 것입니다.
## 8. 문제와 공식 해설의 비교·검증
- **문제가 요구하는 것:** 두 원소를 실제로 바꾸세요.
- **공식 해설이 제시하는 결론:** `lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2); ret`.
- **결론을 재현하는 핵심 논리:** 교환은 첫 값을 temporary에 보존해야 합니다. 먼저 두 값을 모두 load하고, 반대 주소로 store합니다.
- **검증 방법:** 위 micro-step의 `종이에 남길 것`을 순서대로 만들고 각 `완료 기준`을 확인합니다. 최종 산출물이 공식 결론과 같은지 대조합니다.
- **전제와 주의 범위:** 첫 값을 보존하기 전에 overwrite하면 두 원소가 같은 값이 됩니다.
- **채택할 시험 답:** 이 가이드에서는 공식 Musterlösung의 결론을 시험 답으로 유지하며, 일반 ISA 또는 다른 구현과 달라질 수 있는 부분은 위 전제와 주의 범위에서 분리합니다.
## 9. 시험장에서 쓸 최종 답안
`lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2); ret`.
아래는 이 unit의 register/label 전제를 모두 포함한 완성 답안입니다. 현재 unit에서 다룬 block을 위 micro-step과 대조하세요.
```asm
swap:
slli t0, a1, 2
add t0, a0, t0
lw t1, 0(t0)
slli t2, a2, 2
add t2, a0, t2
lw t3, 0(t2)
sw t3, 0(t0)
sw t1, 0(t2)
ret
bubbleSort:
addi sp, sp, -32
sw ra, 0(sp)
sw s0, 4(sp)
sw s1, 8(sp)
sw s2, 12(sp)
sw s3, 16(sp)
mv s0, a0
mv s1, a1
addi s2, zero, 0
outer_loop:
addi t0, s1, -1
bge s2, t0, done
li s3, 0
inner_loop:
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
mv a0, s0
mv a1, s3
addi a2, s3, 1
jal ra, swap
inner_inc:
addi s3, s3, 1
j inner_loop
outer_inc:
addi s2, s2, 1
j outer_loop
done:
lw ra, 0(sp)
lw s0, 4(sp)
lw s1, 8(sp)
lw s2, 12(sp)
lw s3, 16(sp)
addi sp, sp, 32
ret
```
답안지에는 결과만 쓰지 말고, 7절의 중간 산출물 가운데 판정을 증명하는 식·bit field·register 상태·cycle·cache 상태를 함께 남기세요.
## 10. 자주 하는 실수와 검산 체크리스트
### 대표 실수
- 첫 값을 보존하기 전에 overwrite하면 두 원소가 같은 값이 됩니다.
- `lw t0,0(t0)`로 주소 register 자체를 덮어 이후 store 주소를 잃는 것입니다.
- 첫 load 직후 store해 j의 원본을 읽기 전에 덮는 것입니다.
- `sw t1,0(t0)`로 원래 값을 같은 위치에 다시 써 아무 변화가 없는 것입니다.
- store base를 또 t0로 사용해 i 위치만 두 번 쓰는 것입니다.
- ret를 생략하거나 leaf라는 이유만으로 a/t register 값을 caller에게 보존해야 한다고 가정하는 것입니다.
### 빠른 self-check
- **회상 질문:** 두 index가 같아도 이 code가 안전한 이유는 무엇인가요?
- [ ] 주소 register와 값 register 네 개의 역할을 trace 표에 유지할 수 있다.
- [ ] store 순서가 잘못된 code에서 처음 원본이 사라지는 instruction을 정확히 지적할 수 있다.
## 11. 짧은 확인 문제와 전이 연습
### 개념 재구성
**문제:** 두 memory 위치를 swap할 때 왜 `load A, load B, store B→A, store A→B` 순서가 필요한지 value lifetime으로 설명하세요.
**힌트:** 첫 store 순간에도 마지막에 필요한 두 원본이 어디에 있는지 추적하세요.
정답과 채점 기준 보기
**모범 답:** 첫 store는 memory 원본 하나를 overwrite하므로 그 전에 old A와 old B를 각각 register에 load해야 합니다. 두 value lifetime은 각 반대편 store까지 이어집니다. 그래서 `load A, load B, store B→A, store A→B` 순서가 원본 손실을 막습니다.
**채점 기준**
- overwrite
- old a
- old b
- register
- value lifetime
- load a, load b, store b→a, store a→b|load a, load b, store b->a, store a->b
### 변형 문제
**문제:** p와 q가 같은 주소이고 초기 값이 42일 때 위 네 instruction을 trace하세요. 각 load 값과 최종 memory 값을 적으세요.
**힌트:** 두 load는 어느 store보다 먼저 일어납니다.
정답과 채점 기준 보기
**모범 답:** 두 주소가 같아도 첫 `lw`와 둘째 `lw`는 모두 42를 읽습니다. 이어 두 store도 같은 주소에 42를 쓰므로 최종 memory 값은 42입니다. 따라서 i=j인 경우에도 안전합니다.
**채점 기준**
- 모두 42
- 두 store
- 같은 주소
- 최종 memory 값은 42
- i=j
- 안전
### 오답 진단
**문제:** 학생 code는 `lw t1,0(t0); sw t1,0(t2); lw t3,0(t2); sw t3,0(t0)`입니다. p=7, q=19에서 첫 오류와 최종 잘못된 상태를 trace해 고치세요.
**힌트:** 두 번째 load가 읽는 q는 이미 어떤 값으로 바뀌었나요?
정답과 채점 기준 보기
**모범 답:** 첫 오류는 q의 원본을 load하기 전에 `sw t1,0(t2)`로 q를 7로 overwrite한 것입니다. 이후 t3도 7을 읽어 최종 p=7, q=7이 됩니다. 두 load를 먼저 실행한 뒤 반대 순서 store를 해야 합니다.
**채점 기준**
- 원본
- overwrite
- q를 7
- t3도 7
- p=7
- q=7
- 두 load
## 12. 근거 자료
- `[문제 출처] current:Probeklausur.pdf` — 시험 p7–8 · 공식 해설 p8–11
- `[공식 해설] current:Probeklausur Musterlösung und Hinweise.pdf` — 시험 p7–8 · 공식 해설 p8–11
- `[정확한 원문 group] 3` — 시험 p.7, p.8 · 공식 해설 p.8, p.9, p.10, p.11
- `[소문항 범위] SoSe26 Probeklausur 시험 p7 Aufgabe 3 `swap`의 load/store 부분과 공식 해설 p8의 네 memory instruction 및 leaf `ret` 범위.`
- `[개념 근거 · file-level] current:Vorlesung/Rechnerorganisation - Teil 1.pdf` — RISC-V assembler와 C translation
- `[개념 근거 · file-level] current:Uebung/Übung 2 Musterlösung/Rechnerorganisation_Übung2_Lösung.pdf` — assembler programming과 array access
- `[개념 근거 · file-level] current:Uebung/Übung 3 Musterlösung.pdf` — calling convention과 stack frame
- `[개념 근거 · file-level] current:Uebung/RISC-V Reference.pdf` — instruction과 ABI register 이름
### 이 파일에서 직접 대조한 공식 이미지
- `exam-p07.png` — Probeklausur.pdf · PDF p.7
- `exam-p08.png` — Probeklausur.pdf · PDF p.8
- `solution-p08.png` — Probeklausur Musterlösung und Hinweise.pdf · PDF p.8
정확한 강의 슬라이드 한 페이지를 확정하지 못한 개념 자료는 `file-level`로 표시했습니다. 페이지 번호를 추측해서 만들지 않았습니다.