왜 이 소문제를 따로 배우는가
swap의 핵심은 instruction 수가 아니라 값의 lifetime입니다. 첫 store 전에 두 원본 값을 확보해야 하며, 주소와 값을 서로 다른 register로 추적하면 alias 상황에서도 올바른 순서를 설명할 수 있습니다.
이 페이지는 Aufgabe 3의 공통 템플릿이 아니라 3-2 `swap`: load 두 번, store 두 번에 필요한 내용만 담습니다. 챕터 전체 배경이 필요하면 Aufgabe 3 개념 수업을 먼저 읽으세요.
이 소문제에서 실제로 쓰는 용어
정의뿐 아니라 이 문제의 어느 판단에 쓰이는지까지 연결합니다.
- 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`할 수 있음을 설명합니다.
이 소문제 전용 규칙과 종이 작업
load-load-store-store 규칙
두 원본 값을 모두 register에 확보한 뒤에야 어느 memory 위치도 안전하게 overwrite할 수 있습니다.
종이에: instruction 왼쪽에 `L1, L2, S2→1, S1→2` 순서를 표시합니다.
주소와 값 register 분리
t0/t2는 주소, t1/t3는 값으로 역할을 고정하면 store operand를 뒤집는 실수를 줄입니다.
종이에: `t0=&i, t1=old_i, t2=&j, t3=old_j` register 표를 유지합니다.
leaf return 규칙
다른 함수를 `jal`로 호출하지 않으면 incoming ra가 덮이지 않으므로 이 단순 swap은 저장 없이 ret할 수 있습니다.
종이에: call instruction이 없음을 확인한 뒤 마지막에 `ret`을 둡니다.
Aufgabe 전체 흐름은 챕터 흐름도에서 확인할 수 있습니다. 여기서는 현재 판단에 직접 필요한 규칙만 적용합니다.
이 소문제 전용 작은 예제
주소 p와 q의 초기 값이 각각 7과 19이고 p는 t0, q는 t2에 있다. t1과 t3를 값 temporary로 써서 교환 code와 각 단계 memory 상태를 적으세요.
주어진 것
- `memory[p]=7`, `memory[q]=19`입니다.
- p와 q는 서로 다른 주소입니다.
- p와 q의 값을 모두 load합니다.
memory를 바꾸기 전에 두 원본을 register에 보존해야 합니다.
종이 산출물: `lw t1,0(t0) # t1=7; lw t3,0(t2) # t3=19`
- q의 원본 t3를 p에 store합니다.
p의 원본 7은 이미 t1에 보존되어 있어 overwrite해도 잃지 않습니다.
종이 산출물: `sw t3,0(t0) # memory[p]=19`
- 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}`가 초기와 같고 위치만 바뀌었는지 확인합니다.
이제 실제 시험 문제를 micro-work로 풀기
공식 시험이 요구하는 것
두 원소를 실제로 바꾸세요.
공식 답을 보기 전, 내 답 먼저 남기기
완성 문장이 아니어도 좋습니다. 중간값·register·cycle·cache state처럼 채점 가능한 흔적을 먼저 적으세요.
각 작업의 중간 산출물을 직접 적고 완료 조건을 만족한 뒤 체크하세요. 단계별 이유·산출물·오류가 현재 소문제에 맞게 따로 작성되어 있습니다.
`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 주소를 잃는 것입니다.
`arr[j]`의 원본 값을 t3에 load합니다.
- 왜 하는가
- 첫 store 전에 두 번째 원본도 확보해야 두 값 중 하나를 잃지 않습니다.
- 종이 산출물
- `lw t3,0(t2) # t3=old arr[j]`
- 완료 조건
- t1=old_i와 t3=old_j가 동시에 live입니다.
막혔을 때 단계 힌트·대표 오류
힌트: 아직 store를 실행하지 마세요.
이 단계의 대표 오류: 첫 load 직후 store해 j의 원본을 읽기 전에 덮는 것입니다.
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)`로 원래 값을 같은 위치에 다시 써 아무 변화가 없는 것입니다.
t1의 `arr[i]` 원본을 j 주소에 store합니다.
- 왜 하는가
- 남은 원본을 반대편에 써서 교환을 완성합니다.
- 종이 산출물
- `sw t1,0(t2) # arr[j]=old arr[i]`
- 완료 조건
- 두 memory 위치가 서로의 old 값을 가지며 원본 둘이 보존되었습니다.
막혔을 때 단계 힌트·대표 오류
힌트: 두 번째 destination은 t2가 가리키는 j 주소입니다.
이 단계의 대표 오류: store base를 또 t0로 사용해 i 위치만 두 번 쓰는 것입니다.
다른 함수를 호출하지 않은 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에게 보존해야 한다고 가정하는 것입니다.
공식 답을 열기 전 마지막 회상
두 index가 같아도 이 code가 안전한 이유는 무엇인가요?
내 풀이 후 공식 결론·이유·대표 함정 확인
공식 결론
`lw t1,0(t0); lw t3,0(t2); sw t3,0(t0); sw t1,0(t2); ret`.
왜 이 답이 되는가
교환은 첫 값을 temporary에 보존해야 합니다. 먼저 두 값을 모두 load하고, 반대 주소로 store합니다.
대표 함정
첫 값을 보존하기 전에 overwrite하면 두 원소가 같은 값이 됩니다.
명령어와 식을 줄 단위로 읽기
본문 속 code를 한 줄씩 분리했습니다. 각 줄에서 source, operation, destination을 표시하세요.
lw t1,0(t0);
lw t3,0(t2);
sw t3,0(t0);
sw t1,0(t2);
ret;새 문제로 전이하기
세 문항은 앞 문장의 반복이 아닙니다. 직접 답을 입력하면 rubric의 필수 기준을 하나씩 검사하고, 첫 누락 기준을 알려 줍니다.
1. 개념 재구성
두 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` 순서가 원본 손실을 막습니다.
2. 변형 문제
p와 q가 같은 주소이고 초기 값이 42일 때 위 네 instruction을 trace하세요. 각 load 값과 최종 memory 값을 적으세요.
두 load는 어느 store보다 먼저 일어납니다.
제출 후 모델 답 보기
두 주소가 같아도 첫 `lw`와 둘째 `lw`는 모두 42를 읽습니다. 이어 두 store도 같은 주소에 42를 쓰므로 최종 memory 값은 42입니다. 따라서 i=j인 경우에도 안전합니다.
3. 오류 진단
학생 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를 해야 합니다.
이 소문제를 끝냈다고 말할 수 있는 기준
이 소문제의 정확한 공식 페이지와 대조하기
왼쪽은 문제를 읽을 때, 오른쪽은 자신의 풀이를 끝낸 뒤에 확인하세요. 해설 이미지를 먼저 보면 중간 과정을 스스로 만드는 연습이 사라집니다.
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p7–8 · 공식 해설 p8–11 · SoSe26 Probeklausur 시험 p7 Aufgabe 3 `swap`의 load/store 부분과 공식 해설 p8의 네 memory instruction 및 leaf `ret` 범위.