--- schema_version: 1 exam_id: "sose26-probeklausur" aufgabe: 3 unit_id: "3-1" source_group_id: "3" official_exam: true official_solution: true language: "ko" --- # 3-1 — `swap`: 두 주소 계산 > **학습 목표:** `int` array index를 4-Byte offset으로 scale하고 서로 다른 temporary를 사용해 `&arr[i]`와 `&arr[j]`를 동시에 만든다. > > **왜 따로 배우는가:** RISC-V address arithmetic은 element index가 아니라 Byte 주소를 다룹니다. scaling과 temporary lifetime을 분리해 추적해야 load/store 전에도 두 주소를 잃지 않고 이후 swap 단계를 안전하게 이어갈 수 있습니다. > > **범위:** 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](../../assets/exam-p07.png) *공식 시험 원문: `exam-p07.png` · Probeklausur.pdf · PDF p.7* ![공식 시험 원문 — exam-p08.png](../../assets/exam-p08.png) *공식 시험 원문: `exam-p08.png` · Probeklausur.pdf · PDF p.8* ### 이 unit에서 풀 항목 `arr[i]`와 `arr[j]`의 주소를 만드세요. ## 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에 해당하는 최소 작업 `arr[i]`와 `arr[j]`의 주소를 만드세요. 이 문제에서 최종 결과만 맞히는 것보다 중요한 것은 `3-1`에 필요한 중간 판단을 답안지에 남기는 것입니다. ## 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의 학습 목표 - **관찰 가능한 목표:** `int` array index를 4-Byte offset으로 scale하고 서로 다른 temporary를 사용해 `&arr[i]`와 `&arr[j]`를 동시에 만든다. - **출제 의도:** RISC-V address arithmetic은 element index가 아니라 Byte 주소를 다룹니다. scaling과 temporary lifetime을 분리해 추적해야 load/store 전에도 두 주소를 잃지 않고 이후 swap 단계를 안전하게 이어갈 수 있습니다. - **공식 근거 범위:** SoSe26 Probeklausur 시험 p7 Aufgabe 3 `swap`의 주소 계산 부분과 공식 해설 p8의 `slli/add` 두 주소 생성 범위. - **Aufgabe 공통 선수지식:** C variable을 register에 배치하고, array index를 byte offset으로 바꾸고, loop 조건을 ‘끝나면 탈출’ branch로 뒤집습니다. 다른 함수를 부르면 ra와 오래 살아야 하는 값을 stack/s-register로 보호합니다. ## 4. 선수 개념과 핵심 용어 ### byte offset - **뜻:** array base에서 목표 element까지 떨어진 거리를 Byte 단위로 나타낸 값입니다. - **이 문제에서:** `int` index에 4를 곱해 address addition에 사용합니다. ### slli - **뜻:** register 값을 immediate만큼 논리적으로 왼쪽 shift하는 instruction입니다. - **이 문제에서:** `slli index,2`로 index를 `2^2=4`배 합니다. ### base address - **뜻:** array 첫 element `arr[0]`의 memory address입니다. - **이 문제에서:** a0에 든 arr base에 scaled offset을 더해 각 element 주소를 만듭니다. ### temporary lifetime - **뜻:** 중간값이 생성된 뒤 마지막으로 사용될 때까지 보존되어야 하는 구간입니다. - **이 문제에서:** 두 element 주소가 동시에 필요하므로 t0와 t2를 서로 덮지 않게 합니다. ### 이 문제에 적용할 풀이 규칙 ### 규칙 1. element→Byte 변환 규칙 element 크기가 S Byte이면 `&arr[k]=base+k×S`입니다. `int`는 4 Byte이므로 k를 2 bit shift합니다. - **시험지에 남길 것:** `offset_i=i×4`, `offset_j=j×4`를 주소 계산 전에 씁니다. ### 규칙 2. base 불변 규칙 두 주소 계산 모두 같은 arr base에서 시작해야 하므로 a0를 덮지 않고 temporary에 결과를 둡니다. - **시험지에 남길 것:** register 표에 `a0=arr base (keep)`를 표시합니다. ### 규칙 3. 동시 생존 규칙 나중에 두 값을 load/store하려면 `&arr[i]`와 `&arr[j]`가 모두 살아 있어야 합니다. - **시험지에 남길 것:** t0=`&arr[i]`, t2=`&arr[j]`라고 서로 다른 상자를 그립니다. ### 공식 문제 전에 푸는 작은 유사 예제 **문제:** base `0x1000`의 `short v[]`에서 k=6인 `&v[k]`를 계산하고 RISC-V 두 instruction으로 만드세요. `short=2 Byte`입니다. **주어진 것** - base는 a0, k는 a1에 있습니다. - 결과 주소는 t0에 둡니다. ### 예제 단계 1. element 크기 2를 shift amount로 바꿉니다. - **왜:** `2 Byte = 2^1`이므로 index를 1 bit left shift하면 Byte offset입니다. - **종이에:** `offset=6×2=12`, `shift=1` ### 예제 단계 2. scaled offset을 t0에 만듭니다. - **왜:** base a0와 original index a1을 보존하면서 address arithmetic을 준비합니다. - **종이에:** `slli t0,a1,1 # t0=12` ### 예제 단계 3. base와 offset을 더합니다. - **왜:** array address 공식 `base+k×size`를 완성합니다. - **종이에:** `add t0,a0,t0 # 0x1000+12=0x100C` **예제 정답:** `slli t0,a1,1; add t0,a0,t0`이며 `&v[6]=0x100C`입니다. **독립 검산:** k=0을 넣으면 offset 0이고 결과가 base `0x1000` 그대로인지 확인합니다. ## 5. 공식 정답 요약 **공식 결론:** `slli t0,a1,2; add t0,a0,t0`와 `slli t2,a2,2; add t2,a0,t2`. ### 시험지 문장별 정답 해설 아래는 시험지의 항목 순서를 그대로 유지합니다. 각 항목에서 원문 → 한국어 번역 → 정답 → 판단 근거 → 실제로 쓸 답을 바로 이어서 읽으세요. ### 현재 소문제의 요구·판단·답을 한 흐름으로 연결 ### `3-1`에서 정확히 답할 대상 - **시험지가 요구하는 답:** `arr[i]`와 `arr[j]`의 주소를 만드세요. - **이 소문제의 공식 답:** `slli t0,a1,2; add t0,a0,t0`와 `slli t2,a2,2; add t2,a0,t2`. ### 판단 1. i를 2 bit left shift해 `i×4` Byte offset을 만듭니다. - **왜:** `int` element 하나가 4 Byte이므로 element index를 그대로 주소에 더할 수 없습니다. - **이 판단에서 답안지에 남길 것:** `slli t0,a1,2 # t0=i*4` ### 판단 2. arr base a0를 더해 `&arr[i]`를 만듭니다. - **왜:** scaled offset은 상대 거리일 뿐이며 실제 memory address에는 base가 필요합니다. - **이 판단에서 답안지에 남길 것:** `add t0,a0,t0 # t0=&arr[i]` ### 판단 3. j도 같은 방식으로 scale하고 arr base를 더합니다. - **왜:** 두 번째 index도 동일한 element 크기와 같은 base를 사용합니다. - **이 판단에서 답안지에 남길 것:** `slli t2,a2,2; add t2,a0,t2 # t2=&arr[j]` ### 판단 4. 두 주소를 서로 다른 temporary에 유지합니다. - **왜:** 다음 단계에서 두 값을 load한 뒤 반대 주소에 store하려면 t0와 t2가 동시에 필요합니다. - **이 판단에서 답안지에 남길 것:** register 표에 `t0=&arr[i] (live)`, `t2=&arr[j] (live)`를 적습니다. ### 위 판단이 최종 답으로 이어지는 이유 `int` 하나는 4 Byte이므로 index×4가 byte offset입니다. `slli index,2`는 4배와 같습니다. ### 답안 작성 시 주의 index를 그대로 base에 더하면 element가 아니라 byte 단위로 잘못 이동합니다. ![공식 Musterlösung/Hinweise — solution-p08.png](../../assets/solution-p08.png) *공식 Musterlösung/Hinweise: `solution-p08.png` · Probeklausur Musterlösung und Hinweise.pdf · PDF p.8* ## 6. 풀이 전략 1. i를 2 bit left shift합니다. 2. arr base를 더해 &arr[i]를 만듭니다. 3. j도 같은 방식으로 &arr[j]를 만듭니다. 4. 두 주소를 동시에 잃지 않도록 다른 temporary를 씁니다. ## 7. 단계별 상세 풀이 ### 단계 1. i를 2 bit left shift해 `i×4` Byte offset을 만듭니다. - **이유:** `int` element 하나가 4 Byte이므로 element index를 그대로 주소에 더할 수 없습니다. - **종이에 남길 것:** `slli t0,a1,2 # t0=i*4` - **완료 기준:** t0의 단위가 element가 아니라 Byte로 표시되어 있습니다. - **막힐 때 힌트:** 4는 `2^2`입니다. - **가장 흔한 첫 오류:** `slli` 없이 i를 base에 직접 더하거나 4 bit shift해 16배 하는 것입니다. ### 단계 2. arr base a0를 더해 `&arr[i]`를 만듭니다. - **이유:** scaled offset은 상대 거리일 뿐이며 실제 memory address에는 base가 필요합니다. - **종이에 남길 것:** `add t0,a0,t0 # t0=&arr[i]` - **완료 기준:** t0가 offset에서 absolute element address로 바뀌었다고 표시되어 있습니다. - **막힐 때 힌트:** 주소 공식의 `base + offset` 두 항을 확인하세요. - **가장 흔한 첫 오류:** shift 결과를 이미 완전한 address라고 보고 base addition을 생략하는 것입니다. ### 단계 3. j도 같은 방식으로 scale하고 arr base를 더합니다. - **이유:** 두 번째 index도 동일한 element 크기와 같은 base를 사용합니다. - **종이에 남길 것:** `slli t2,a2,2; add t2,a0,t2 # t2=&arr[j]` - **완료 기준:** t2가 j의 scaled offset이 아니라 `&arr[j]`로 표시되어 있습니다. - **막힐 때 힌트:** i 계산의 register만 복사하지 말고 source를 a2로 바꾸세요. - **가장 흔한 첫 오류:** 두 번째 계산에서도 a1을 사용해 두 주소가 모두 `&arr[i]`가 되는 것입니다. ### 단계 4. 두 주소를 서로 다른 temporary에 유지합니다. - **이유:** 다음 단계에서 두 값을 load한 뒤 반대 주소에 store하려면 t0와 t2가 동시에 필요합니다. - **종이에 남길 것:** register 표에 `t0=&arr[i] (live)`, `t2=&arr[j] (live)`를 적습니다. - **완료 기준:** 어느 instruction도 t0나 t2를 다른 용도로 덮지 않고 다음 load 단계로 넘어갑니다. - **막힐 때 힌트:** 한 주소를 만든 뒤 같은 destination register로 두 번째 주소를 계산하지 마세요. - **가장 흔한 첫 오류:** t0를 j 주소 계산에 재사용해 `&arr[i]`를 잃는 것입니다. ## 8. 문제와 공식 해설의 비교·검증 - **문제가 요구하는 것:** `arr[i]`와 `arr[j]`의 주소를 만드세요. - **공식 해설이 제시하는 결론:** `slli t0,a1,2; add t0,a0,t0`와 `slli t2,a2,2; add t2,a0,t2`. - **결론을 재현하는 핵심 논리:** `int` 하나는 4 Byte이므로 index×4가 byte offset입니다. `slli index,2`는 4배와 같습니다. - **검증 방법:** 위 micro-step의 `종이에 남길 것`을 순서대로 만들고 각 `완료 기준`을 확인합니다. 최종 산출물이 공식 결론과 같은지 대조합니다. - **전제와 주의 범위:** index를 그대로 base에 더하면 element가 아니라 byte 단위로 잘못 이동합니다. - **채택할 시험 답:** 이 가이드에서는 공식 Musterlösung의 결론을 시험 답으로 유지하며, 일반 ISA 또는 다른 구현과 달라질 수 있는 부분은 위 전제와 주의 범위에서 분리합니다. ## 9. 시험장에서 쓸 최종 답안 `slli t0,a1,2; add t0,a0,t0`와 `slli t2,a2,2; add t2,a0,t2`. 아래는 이 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. 자주 하는 실수와 검산 체크리스트 ### 대표 실수 - index를 그대로 base에 더하면 element가 아니라 byte 단위로 잘못 이동합니다. - `slli` 없이 i를 base에 직접 더하거나 4 bit shift해 16배 하는 것입니다. - shift 결과를 이미 완전한 address라고 보고 base addition을 생략하는 것입니다. - 두 번째 계산에서도 a1을 사용해 두 주소가 모두 `&arr[i]`가 되는 것입니다. - t0를 j 주소 계산에 재사용해 `&arr[i]`를 잃는 것입니다. ### 빠른 self-check - **회상 질문:** 64-bit long array라면 index scaling은 어떻게 달라지나요? - [ ] 자료형 크기가 바뀌어도 index scaling shift를 스스로 정할 수 있다. - [ ] 두 주소의 register lifetime을 표로 추적해 서로 덮지 않는 code를 만들 수 있다. ## 11. 짧은 확인 문제와 전이 연습 ### 개념 재구성 **문제:** element 크기가 S Byte인 array에서 `&arr[k]` 공식을 복원하고 S가 2의 거듭제곱일 때 slli shift amount를 구하는 법을 설명하세요. **힌트:** S=`2^m`이면 곱셈과 shift의 관계를 쓰세요.
정답과 채점 기준 보기 **모범 답:** `&arr[k] = base + k×S`입니다. S=`2^m`이면 `k×S = k< ### 변형 문제 **문제:** base=`0x4000`인 64-bit `long a[]`에서 p=3, q=7이다. 두 주소를 계산하고 a0=base, a1=p, a2=q일 때 RISC-V address code를 쓰세요. **힌트:** 64 bit는 8 Byte이고 `8=2^3`입니다.
정답과 채점 기준 보기 **모범 답:** `&a[3]=0x4000+24=0x4018`, `&a[7]=0x4000+56=0x4038`입니다. code는 `slli t0,a1,3; add t0,a0,t0; slli t2,a2,3; add t2,a0,t2`입니다. **채점 기준** - 0x4018 - 0x4038 - slli t0,a1,3 - add t0,a0,t0 - slli t2,a2,3 - add t2,a0,t2
### 오답 진단 **문제:** 학생 code는 `add t0,a0,a1; add t0,a0,a2`이고 마지막 t0를 두 주소 모두로 사용하려 합니다. 첫 산술 오류와 이어지는 lifetime 오류를 각각 고치세요. **힌트:** index 단위와 두 결과 register 수를 따로 점검하세요.
정답과 채점 기준 보기 **모범 답:** 첫 산술 오류는 int index를 4 Byte로 scale하지 않은 것입니다. `slli t0,a1,2`와 `slli t2,a2,2`가 필요합니다. 이어지는 lifetime 오류는 두 번째 add가 t0의 첫 주소를 덮는 것이므로 `add t0,a0,t0`와 `add t2,a0,t2`로 두 주소를 분리해야 합니다. **채점 기준** - 4 byte - slli t0,a1,2 - slli t2,a2,2 - lifetime - 덮 - add t0,a0,t0 - add t2,a0,t2
## 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`의 주소 계산 부분과 공식 해설 p8의 `slli/add` 두 주소 생성 범위.` - `[개념 근거 · 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`로 표시했습니다. 페이지 번호를 추측해서 만들지 않았습니다.