---
schema_version: 1
exam_id: "sose26-probeklausur"
aufgabe: 1
unit_id: "1d"
source_group_id: "1d"
official_exam: true
official_solution: true
language: "ko"
---
# 1d — 2차원 Array의 Lokalität
> **학습 목표:** C row-major 2차원 array의 연속 접근 주소 차이를 계산해 räumliche Lokalität와 zeitliche Lokalität를 구분한다.
>
> **왜 따로 배우는가:** loop 모양만 보고 locality를 판정하면 ‘반복이 있으니 temporal’이라는 오답이 나옵니다. 실제 주소열을 두 개만 계산하는 습관은 Cache line 활용과 loop interchange 최적화를 함께 설명하게 해 줍니다.
>
> **범위:** Aufgabe 1 · 15점 Aufgabe의 최소 학습 단위 · 시험 p3–5 · 공식 해설 p3–6
## 1. 문제 원문 (Deutsch)
이 unit은 공식 Teilaufgabe 또는 표의 한 행·한 access를 학습 가능한 최소 단위로 다시 나눈 것입니다. 아래 전사는 source group `1d`의 공식 독일어 문제 원문이며, 페이지 이미지를 바로 뒤에 함께 두어 코드·표·도식을 대조할 수 있게 했습니다.
~~~text
1d) Speicherlokalität in C
Gegeben ist der folgende Code-Ausschnitt in C:
```c
int len = 100;
int arr[100][100];
int sum = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
sum += arr[j][i];
}
}
```
a) Geht es beim Zugriff auf das Array arr um eine schlechte räumliche oder eine schlechte zeitliche Lokalität?
b) Begründen Sie Ihre Auswahl in maximal drei Sätzen.
Lösung:
~~~
*공식 시험 원문: `exam-p04.png` · Probeklausur.pdf · PDF p.4*
### 이 unit에서 풀 항목
`arr[j][i]` 접근이 spatial/temporal 중 무엇을 나쁘게 만드는지 설명하세요.
## 2. 쉬운 한국어 해석
1d) C에서의 메모리 지역성(Speicherlokalität)
다음 C 코드가 주어져 있다.
```c
int len = 100;
int arr[100][100];
int sum = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
sum += arr[j][i];
}
}
```
a) 배열 arr에 접근할 때 나쁜 공간 지역성(räumliche Lokalität)의 문제인가, 아니면 나쁜 시간 지역성(zeitliche Lokalität)의 문제인가?
b) 선택한 답의 근거를 최대 세 문장으로 설명하시오.
풀이:
### 이 unit에 해당하는 최소 작업
`arr[j][i]` 접근이 spatial/temporal 중 무엇을 나쁘게 만드는지 설명하세요.
이 문제에서 최종 결과만 맞히는 것보다 중요한 것은 `1d`에 필요한 중간 판단을 답안지에 남기는 것입니다.
## 3. 무엇을 묻는 문제인가
### 공식 문제의 요구사항
- arr[j][i] 접근이 나쁜 공간 지역성과 나쁜 시간 지역성 중 어느 것인지 고른다.
- 선택의 이유를 설명한다.
### 조건과 제약
- b)의 설명은 최대 세 문장이다.
- 주어진 C의 2차원 배열 배치와 실제 반복문의 접근 순서를 근거로 삼는다.
### 원문 오탈자·도식 관련 주의
- PDF에서 중첩 for 문의 들여쓰기가 텍스트로 추출되지 않아, 중괄호 구조를 바꾸지 않는 범위에서 들여쓰기만 복원했다.
### 도식 시각 확인 상태
- **도식 의존 여부:** 이 최소 unit의 핵심 판정은 텍스트·수식·코드로 재현할 수 있습니다.
- **공식 페이지 상태:** exam-p04.png, solution-p04.png, solution-p05.png가 원문 대조용으로 렌더되어 연결되어 있습니다.
### 이 unit의 학습 목표
- **관찰 가능한 목표:** C row-major 2차원 array의 연속 접근 주소 차이를 계산해 räumliche Lokalität와 zeitliche Lokalität를 구분한다.
- **출제 의도:** loop 모양만 보고 locality를 판정하면 ‘반복이 있으니 temporal’이라는 오답이 나옵니다. 실제 주소열을 두 개만 계산하는 습관은 Cache line 활용과 loop interchange 최적화를 함께 설명하게 해 줍니다.
- **공식 근거 범위:** SoSe26 Probeklausur 시험 p4 Aufgabe 1d 및 공식 해설 p4의 `arr[j][i]` row-major Lokalität 분석 범위.
- **Aufgabe 공통 선수지식:** 용어를 외우기 전에 ‘무엇을 입력받아 무엇을 출력하는가’, ‘CPU 내부가 겹쳐 일하는가’, ‘memory에서 다음 접근이 얼마나 가까운가’를 묻는 습관을 만듭니다.
## 4. 선수 개념과 핵심 용어
### row-major
- **뜻:** C에서 같은 행의 열 index가 연속으로 증가할 때 원소가 memory에 연속 배치되는 방식입니다.
- **이 문제에서:** `arr[j][i]`의 안쪽 index 변화가 연속 memory 방향과 일치하는지 판별합니다.
### räumliche Lokalität
- **뜻:** 한 주소를 사용한 뒤 그 주변 주소를 곧 사용하는 성질입니다.
- **이 문제에서:** 연속 접근 stride가 Cache line 안의 이웃 원소를 활용하는지 설명할 때 씁니다.
### zeitliche Lokalität
- **뜻:** 같은 주소 또는 data를 짧은 시간 안에 다시 사용하는 성질입니다.
- **이 문제에서:** `arr[j][i]`의 문제가 같은 값을 재사용하지 못하는 것인지 구분할 때 씁니다.
### stride
- **뜻:** 연속된 두 memory access 주소 사이의 byte 간격입니다.
- **이 문제에서:** 열 방향 접근에서 `열 개수 × 원소 크기`로 400 Byte 간격을 계산합니다.
### 이 문제에 적용할 풀이 규칙
### 규칙 1. 주소열 우선 규칙
locality는 loop variable 이름이 아니라 실제 memory address sequence로 판정합니다.
- **시험지에 남길 것:** 안쪽 loop의 첫 두 접근을 `주소 A`, `주소 A+Δ`로 써서 Δ를 계산합니다.
### 규칙 2. spatial/temporal 질문 분리
이웃 주소를 곧 쓰는지는 spatial, 같은 주소를 다시 쓰는지는 temporal입니다.
- **시험지에 남길 것:** `이웃?`와 `같은 주소 재사용?` 두 질문에 각각 예/아니오를 씁니다.
### 규칙 3. row-major offset 규칙
`int arr[R][C]`에서 `arr[r][c]`의 byte offset은 `(r×C+c)×4`입니다.
- **시험지에 남길 것:** 첫 두 index 쌍을 offset 식에 대입해 stride를 눈에 보이게 남깁니다.
### 공식 문제 전에 푸는 작은 유사 예제
**문제:** `int m[8][16]`에서 안쪽 loop가 `r`을 증가시키며 `m[r][3]`을 읽습니다. 두 연속 접근의 stride와 주로 손상되는 locality를 구하세요.
**주어진 것**
- `int`는 4 Byte입니다.
- C array는 row-major입니다.
### 예제 단계 1. `m[r][3]`의 byte offset 식을 씁니다.
- **왜:** 행 길이 16을 반영해야 실제 주소 이동량을 알 수 있습니다.
- **종이에:** `offset(r)=(16r+3)×4`
### 예제 단계 2. 다음 접근 `m[r+1][3]`과의 차이를 계산합니다.
- **왜:** 연속 접근 차이가 바로 stride입니다.
- **종이에:** `Δ=[16(r+1)+3-(16r+3)]×4=64 Byte`
### 예제 단계 3. 64 Byte 이동을 locality 정의와 연결합니다.
- **왜:** 같은 행의 이웃 int 4 Byte가 아니라 한 행 전체를 건너뛰므로 인접 Cache data 활용이 나쁩니다.
- **종이에:** `räumliche Lokalität 나쁨; temporal 판단 근거 아님`
**예제 정답:** stride는 64 Byte이며 주로 나쁜 räumliche Lokalität입니다.
**독립 검산:** 접근을 `m[3][c]`에서 c 증가로 바꾸면 stride가 4 Byte가 되는지 계산합니다.
## 5. 공식 정답 요약
**공식 결론:** 나쁜 räumliche Lokalität입니다. `arr[j][i]`는 열 방향으로 접근하여 memory의 연속 원소 대신 100개 원소 간격으로 이동합니다.
### 시험지 문장별 정답 해설
아래는 시험지의 항목 순서를 그대로 유지합니다. 각 항목에서 원문 → 한국어 번역 → 정답 → 판단 근거 → 실제로 쓸 답을 바로 이어서 읽으세요.
### a) 지역성 종류 · 정답: schlechte räumliche Lokalität
- **시험지 원문:** Geht es beim Zugriff auf das Array arr um eine schlechte räumliche oder eine schlechte zeitliche Lokalität?
- **한국어 번역:** 배열 arr 접근은 나쁜 공간 지역성인가, 나쁜 시간 지역성인가?
- **왜 이 답인가:** 안쪽 loop에서 j가 바뀌므로 접근은 arr[0][i]→arr[1][i]→arr[2][i] 순서입니다. C의 row-major 배치에서는 이 주소들이 이웃하지 않고 한 row 전체인 100개 int, 즉 400 Byte씩 떨어져 있으므로 공간 지역성이 나쁩니다.
- **답안지에 쓸 문장:** a) Schlechte räumliche Lokalität.
### b) 최대 3문장 근거 · 정답: row-major 배치와 100-element stride를 근거로 설명
- **시험지 원문:** Begründen Sie Ihre Auswahl in maximal drei Sätzen.
- **한국어 번역:** 선택한 답의 근거를 최대 세 문장으로 설명하시오.
- **왜 이 답인가:** 배열의 같은 row 안 원소는 연속 배치되지만 arr[j][i]는 column 방향으로 이동합니다. 연속 access가 100 elements를 건너뛰므로 cache line의 인접 원소를 활용하지 못합니다. 같은 주소를 곧 재사용하지 않는다는 사실보다 핵심은 이웃 주소를 사용하지 못한다는 점입니다.
- **답안지에 쓸 문장:** b) In C liegen die Elemente einer Zeile zusammenhängend im Speicher. Bei arr[j][i] ändert sich in der inneren Schleife j, daher springt jeder Zugriff um 100 int-Elemente. Dadurch wird die räumliche Lokalität verletzt.
### 현재 소문제의 요구·판단·답을 한 흐름으로 연결
### `1d`에서 정확히 답할 대상
- **시험지가 요구하는 답:** `arr[j][i]` 접근이 spatial/temporal 중 무엇을 나쁘게 만드는지 설명하세요.
- **이 소문제의 공식 답:** 나쁜 räumliche Lokalität입니다. `arr[j][i]`는 열 방향으로 접근하여 memory의 연속 원소 대신 100개 원소 간격으로 이동합니다.
### 판단 1. 안쪽 loop에서 실제로 변하는 index를 찾습니다.
- **왜:** 가장 자주 변하는 index가 연속 memory 접근 방향과 stride를 결정합니다.
- **이 판단에서 답안지에 남길 것:** `inner: j 변화, i 고정`이라고 표시합니다.
### 판단 2. 연속된 두 접근의 주소 차이 `100×4 Byte`를 계산합니다.
- **왜:** row-major에서 행 index가 1 늘면 한 행 100개 전체를 건너뛰기 때문입니다.
- **이 판단에서 답안지에 남길 것:** `stride = 100 elements × 4 Byte = 400 Byte`를 적습니다.
### 판단 3. 같은 값의 반복이 아니라 이웃 주소를 활용하지 못하는 문제인지 판별합니다.
- **왜:** spatial과 temporal의 정의를 적용해야 locality 종류를 정확히 이름 붙일 수 있습니다.
- **이 판단에서 답안지에 남길 것:** `같은 주소 재사용: 아니오`, `인접 주소 접근: 아니오`를 적습니다.
### 판단 4. `arr[i][j]` 접근과 stride를 비교합니다.
- **왜:** 열 index j가 안쪽에서 변하면 row-major의 연속 4 Byte 원소를 사용해 Cache line을 더 잘 활용합니다.
- **이 판단에서 답안지에 남길 것:** `arr[i][j]: stride 4 Byte ↔ arr[j][i]: stride 400 Byte` 비교를 남깁니다.
### 위 판단이 최종 답으로 이어지는 이유
C의 2차원 array는 row-major라 `arr[0][0], arr[0][1], ...` 순서로 연속 배치됩니다. 안쪽 loop에서 j를 바꾸며 `arr[j][i]`를 읽으면 매번 100개 원소만큼 건너뜁니다.
### 답안 작성 시 주의
‘loop가 반복되므로 temporal’이라고 쓰지 마세요. 같은 주소를 곧 다시 쓰는지와 이웃 주소를 쓰는지를 구분합니다.
*공식 Musterlösung/Hinweise: `solution-p04.png` · Probeklausur Musterlösung und Hinweise.pdf · PDF p.4*
*공식 Musterlösung/Hinweise: `solution-p05.png` · Probeklausur Musterlösung und Hinweise.pdf · PDF p.5*
## 6. 풀이 전략
1. 안쪽 loop에서 실제로 변하는 index를 찾습니다.
2. 연속된 두 접근 주소 차이를 계산합니다: 100 × 4 Byte.
3. 같은 값을 반복하는 문제가 아니라 이웃 주소를 못 쓰는 문제임을 확인합니다.
4. `arr[i][j]`와 비교해 답을 씁니다.
## 7. 단계별 상세 풀이
### 단계 1. 안쪽 loop에서 실제로 변하는 index를 찾습니다.
- **이유:** 가장 자주 변하는 index가 연속 memory 접근 방향과 stride를 결정합니다.
- **종이에 남길 것:** `inner: j 변화, i 고정`이라고 표시합니다.
- **완료 기준:** 연속 두 접근을 `arr[j][i]`, `arr[j+1][i]`로 쓸 수 있습니다.
- **막힐 때 힌트:** 중괄호 안의 access에서 매 iteration마다 +1 되는 변수를 찾으세요.
- **가장 흔한 첫 오류:** array 표기의 오른쪽 index가 항상 변한다고 가정하는 것입니다.
### 단계 2. 연속된 두 접근의 주소 차이 `100×4 Byte`를 계산합니다.
- **이유:** row-major에서 행 index가 1 늘면 한 행 100개 전체를 건너뛰기 때문입니다.
- **종이에 남길 것:** `stride = 100 elements × 4 Byte = 400 Byte`를 적습니다.
- **완료 기준:** 주소 간격이 원소 수와 byte 둘 다로 표시되어 있습니다.
- **막힐 때 힌트:** `offset=(row×100+column)×4`에 j와 j+1을 넣으세요.
- **가장 흔한 첫 오류:** index가 1 증가했으므로 주소도 1 Byte 또는 4 Byte만 증가한다고 쓰는 것입니다.
### 단계 3. 같은 값의 반복이 아니라 이웃 주소를 활용하지 못하는 문제인지 판별합니다.
- **이유:** spatial과 temporal의 정의를 적용해야 locality 종류를 정확히 이름 붙일 수 있습니다.
- **종이에 남길 것:** `같은 주소 재사용: 아니오`, `인접 주소 접근: 아니오`를 적습니다.
- **완료 기준:** 나쁜 räumliche Lokalität라는 결론과 temporal이 아닌 이유가 함께 있습니다.
- **막힐 때 힌트:** 두 접근의 주소가 같은지, 단지 loop가 반복되는지만 보지 마세요.
- **가장 흔한 첫 오류:** loop 반복 자체를 zeitliche Lokalität라고 부르는 것입니다.
### 단계 4. `arr[i][j]` 접근과 stride를 비교합니다.
- **이유:** 열 index j가 안쪽에서 변하면 row-major의 연속 4 Byte 원소를 사용해 Cache line을 더 잘 활용합니다.
- **종이에 남길 것:** `arr[i][j]: stride 4 Byte ↔ arr[j][i]: stride 400 Byte` 비교를 남깁니다.
- **완료 기준:** 두 access order의 stride와 Cache line 활용 차이를 한 문장으로 설명했습니다.
- **막힐 때 힌트:** 같은 행 안에서 다음 열로 갈 때 offset 식에서 얼마가 늘어나는지 보세요.
- **가장 흔한 첫 오류:** 두 표현의 index 이름만 바뀌고 address order는 같다고 생각하는 것입니다.
## 8. 문제와 공식 해설의 비교·검증
- **문제가 요구하는 것:** `arr[j][i]` 접근이 spatial/temporal 중 무엇을 나쁘게 만드는지 설명하세요.
- **공식 해설이 제시하는 결론:** 나쁜 räumliche Lokalität입니다. `arr[j][i]`는 열 방향으로 접근하여 memory의 연속 원소 대신 100개 원소 간격으로 이동합니다.
- **결론을 재현하는 핵심 논리:** C의 2차원 array는 row-major라 `arr[0][0], arr[0][1], ...` 순서로 연속 배치됩니다. 안쪽 loop에서 j를 바꾸며 `arr[j][i]`를 읽으면 매번 100개 원소만큼 건너뜁니다.
- **검증 방법:** 위 micro-step의 `종이에 남길 것`을 순서대로 만들고 각 `완료 기준`을 확인합니다. 최종 산출물이 공식 결론과 같은지 대조합니다.
- **전제와 주의 범위:** ‘loop가 반복되므로 temporal’이라고 쓰지 마세요. 같은 주소를 곧 다시 쓰는지와 이웃 주소를 쓰는지를 구분합니다.
- **채택할 시험 답:** 이 가이드에서는 공식 Musterlösung의 결론을 시험 답으로 유지하며, 일반 ISA 또는 다른 구현과 달라질 수 있는 부분은 위 전제와 주의 범위에서 분리합니다.
## 9. 시험장에서 쓸 최종 답안
나쁜 räumliche Lokalität입니다. `arr[j][i]`는 열 방향으로 접근하여 memory의 연속 원소 대신 100개 원소 간격으로 이동합니다.
답안지에는 결과만 쓰지 말고, 7절의 중간 산출물 가운데 판정을 증명하는 식·bit field·register 상태·cycle·cache 상태를 함께 남기세요.
## 10. 자주 하는 실수와 검산 체크리스트
### 대표 실수
- ‘loop가 반복되므로 temporal’이라고 쓰지 마세요. 같은 주소를 곧 다시 쓰는지와 이웃 주소를 쓰는지를 구분합니다.
- array 표기의 오른쪽 index가 항상 변한다고 가정하는 것입니다.
- index가 1 증가했으므로 주소도 1 Byte 또는 4 Byte만 증가한다고 쓰는 것입니다.
- loop 반복 자체를 zeitliche Lokalität라고 부르는 것입니다.
- 두 표현의 index 이름만 바뀌고 address order는 같다고 생각하는 것입니다.
### 빠른 self-check
- **회상 질문:** `arr[i][j]`로 바꾸면 왜 Cache line을 더 잘 활용하나요?
- [ ] 새 array 크기와 원소 크기를 주면 첫 두 주소를 써서 stride를 계산할 수 있다.
- [ ] loop가 반복된다는 이유만으로 temporal이라고 하지 않고 같은 주소 재사용 여부를 확인할 수 있다.
## 11. 짧은 확인 문제와 전이 연습
### 개념 재구성
**문제:** `int a[R][C]`의 row-major byte offset 식을 복원하고, spatial locality와 temporal locality의 판정 질문을 각각 하나씩 만드세요.
**힌트:** 행을 몇 개의 원소만큼 건너야 다음 행이 되는지 생각하세요.
정답과 채점 기준 보기
**모범 답:** `a[r][c]`의 byte offset은 `(r×C+c)×4`입니다. spatial은 ‘곧 이웃 주소를 쓰는가?’, temporal은 ‘같은 주소를 곧 다시 쓰는가?’로 판정합니다.
**채점 기준**
- r
- c
- 4
- 이웃 주소|nearby address
- 같은 주소|same address
### 변형 문제
**문제:** `short x[30][50]`에서 안쪽 loop가 첫 index를 증가시키며 `x[k][7]`을 읽습니다. `short=2 Byte`일 때 stride와 주로 나빠지는 locality를 구하세요.
**힌트:** 한 행의 byte 크기를 먼저 구하세요.
정답과 채점 기준 보기
**모범 답:** 한 행은 `50×2=100 Byte`이므로 stride는 100 Byte이고, 열 방향으로 행을 건너뛰어 räumliche Lokalität가 나쁩니다.
**채점 기준**
- 100 byte|100byte
- räumliche lokalität|spatial locality
- 나쁩니다|bad
### 오답 진단
**문제:** 학생이 `arr[j][i]`의 stride를 4 Byte라고 계산하며 ‘j가 1씩 증가하므로 다음 int로 간다’고 했습니다. offset 식을 사용해 첫 오류와 수정값을 제시하세요.
**힌트:** j가 row index일 때 +1은 열 하나가 아니라 무엇 하나를 넘나요?
정답과 채점 기준 보기
**모범 답:** 첫 오류는 row index j의 +1을 연속 열 하나로 본 것입니다. `offset=(j×100+i)×4`이므로 다음 접근 차이는 `100×4=400 Byte`이고, räumliche Lokalität가 나쁩니다.
**채점 기준**
- row|행
- j×100|100j
- 400 byte|400byte
- räumliche lokalität|spatial locality
## 12. 근거 자료
- `[문제 출처] current:Probeklausur.pdf` — 시험 p3–5 · 공식 해설 p3–6
- `[공식 해설] current:Probeklausur Musterlösung und Hinweise.pdf` — 시험 p3–5 · 공식 해설 p3–6
- `[정확한 원문 group] 1d` — 시험 p.4 · 공식 해설 p.4, p.5
- `[소문항 범위] SoSe26 Probeklausur 시험 p4 Aufgabe 1d 및 공식 해설 p4의 `arr[j][i]` row-major Lokalität 분석 범위.`
- `[개념 근거 · file-level] current:Vorlesung/Rechnerorganisation - Teil 1.pdf` — toolchain, processor architecture, RISC-V
- `[개념 근거 · file-level] current:Vorlesung/Rechnerorganisation - Teil 2.pdf` — Eintakt, Mehrtakt, Pipeline와 고정 datapath timing
- `[개념 근거 · file-level] current:Vorlesung/Rechnerorganisation - Teil 3.pdf` — Speicherhierarchie와 Lokalität
- `[개념 근거 · file-level] current:Uebung/Übung C Musterlösung.pdf` — C memory layout와 row-major array
- `[개념 근거 · file-level] current:Uebung/Übung 0 Musterlösung.pdf` — Zweierkomplement와 수 표현
### 이 파일에서 직접 대조한 공식 이미지
- `exam-p04.png` — Probeklausur.pdf · PDF p.4
- `solution-p04.png` — Probeklausur Musterlösung und Hinweise.pdf · PDF p.4
- `solution-p05.png` — Probeklausur Musterlösung und Hinweise.pdf · PDF p.5
정확한 강의 슬라이드 한 페이지를 확정하지 못한 개념 자료는 `file-level`로 표시했습니다. 페이지 번호를 추측해서 만들지 않았습니다.