왜 이 소문제를 따로 배우는가
loop 모양만 보고 locality를 판정하면 ‘반복이 있으니 temporal’이라는 오답이 나옵니다. 실제 주소열을 두 개만 계산하는 습관은 Cache line 활용과 loop interchange 최적화를 함께 설명하게 해 줍니다.
이 페이지는 Aufgabe 1의 공통 템플릿이 아니라 1d 2차원 Array의 Lokalität에 필요한 내용만 담습니다. 챕터 전체 배경이 필요하면 Aufgabe 1 개념 수업을 먼저 읽으세요.
이 소문제에서 실제로 쓰는 용어
정의뿐 아니라 이 문제의 어느 판단에 쓰이는지까지 연결합니다.
- 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 간격을 계산합니다.
이 소문제 전용 규칙과 종이 작업
주소열 우선 규칙
locality는 loop variable 이름이 아니라 실제 memory address sequence로 판정합니다.
종이에: 안쪽 loop의 첫 두 접근을 `주소 A`, `주소 A+Δ`로 써서 Δ를 계산합니다.
spatial/temporal 질문 분리
이웃 주소를 곧 쓰는지는 spatial, 같은 주소를 다시 쓰는지는 temporal입니다.
종이에: `이웃?`와 `같은 주소 재사용?` 두 질문에 각각 예/아니오를 씁니다.
row-major offset 규칙
`int arr[R][C]`에서 `arr[r][c]`의 byte offset은 `(r×C+c)×4`입니다.
종이에: 첫 두 index 쌍을 offset 식에 대입해 stride를 눈에 보이게 남깁니다.
Aufgabe 전체 흐름은 챕터 흐름도에서 확인할 수 있습니다. 여기서는 현재 판단에 직접 필요한 규칙만 적용합니다.
이 소문제 전용 작은 예제
`int m[8][16]`에서 안쪽 loop가 `r`을 증가시키며 `m[r][3]`을 읽습니다. 두 연속 접근의 stride와 주로 손상되는 locality를 구하세요.
주어진 것
- `int`는 4 Byte입니다.
- C array는 row-major입니다.
- `m[r][3]`의 byte offset 식을 씁니다.
행 길이 16을 반영해야 실제 주소 이동량을 알 수 있습니다.
종이 산출물: `offset(r)=(16r+3)×4`
- 다음 접근 `m[r+1][3]`과의 차이를 계산합니다.
연속 접근 차이가 바로 stride입니다.
종이 산출물: `Δ=[16(r+1)+3-(16r+3)]×4=64 Byte`
- 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가 되는지 계산합니다.
이제 실제 시험 문제를 micro-work로 풀기
공식 시험이 요구하는 것
`arr[j][i]` 접근이 spatial/temporal 중 무엇을 나쁘게 만드는지 설명하세요.
공식 답을 보기 전, 내 답 먼저 남기기
완성 문장이 아니어도 좋습니다. 중간값·register·cycle·cache state처럼 채점 가능한 흔적을 먼저 적으세요.
각 작업의 중간 산출물을 직접 적고 완료 조건을 만족한 뒤 체크하세요. 단계별 이유·산출물·오류가 현재 소문제에 맞게 따로 작성되어 있습니다.
안쪽 loop에서 실제로 변하는 index를 찾습니다.
- 왜 하는가
- 가장 자주 변하는 index가 연속 memory 접근 방향과 stride를 결정합니다.
- 종이 산출물
- `inner: j 변화, i 고정`이라고 표시합니다.
- 완료 조건
- 연속 두 접근을 `arr[j][i]`, `arr[j+1][i]`로 쓸 수 있습니다.
막혔을 때 단계 힌트·대표 오류
힌트: 중괄호 안의 access에서 매 iteration마다 +1 되는 변수를 찾으세요.
이 단계의 대표 오류: array 표기의 오른쪽 index가 항상 변한다고 가정하는 것입니다.
연속된 두 접근의 주소 차이 `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만 증가한다고 쓰는 것입니다.
같은 값의 반복이 아니라 이웃 주소를 활용하지 못하는 문제인지 판별합니다.
- 왜 하는가
- spatial과 temporal의 정의를 적용해야 locality 종류를 정확히 이름 붙일 수 있습니다.
- 종이 산출물
- `같은 주소 재사용: 아니오`, `인접 주소 접근: 아니오`를 적습니다.
- 완료 조건
- 나쁜 räumliche Lokalität라는 결론과 temporal이 아닌 이유가 함께 있습니다.
막혔을 때 단계 힌트·대표 오류
힌트: 두 접근의 주소가 같은지, 단지 loop가 반복되는지만 보지 마세요.
이 단계의 대표 오류: loop 반복 자체를 zeitliche Lokalität라고 부르는 것입니다.
`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는 같다고 생각하는 것입니다.
공식 답을 열기 전 마지막 회상
`arr[i][j]`로 바꾸면 왜 Cache line을 더 잘 활용하나요?
내 풀이 후 공식 결론·이유·대표 함정 확인
공식 결론
나쁜 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개 원소만큼 건너뜁니다.
대표 함정
‘loop가 반복되므로 temporal’이라고 쓰지 마세요. 같은 주소를 곧 다시 쓰는지와 이웃 주소를 쓰는지를 구분합니다.
명령어와 식을 줄 단위로 읽기
본문 속 code를 한 줄씩 분리했습니다. 각 줄에서 source, operation, destination을 표시하세요.
arr[j][i]
arr[0][0], arr[0][1], ...새 문제로 전이하기
세 문항은 앞 문장의 반복이 아닙니다. 직접 답을 입력하면 rubric의 필수 기준을 하나씩 검사하고, 첫 누락 기준을 알려 줍니다.
1. 개념 재구성
`int a[R][C]`의 row-major byte offset 식을 복원하고, spatial locality와 temporal locality의 판정 질문을 각각 하나씩 만드세요.
행을 몇 개의 원소만큼 건너야 다음 행이 되는지 생각하세요.
제출 후 모델 답 보기
`a[r][c]`의 byte offset은 `(r×C+c)×4`입니다. spatial은 ‘곧 이웃 주소를 쓰는가?’, temporal은 ‘같은 주소를 곧 다시 쓰는가?’로 판정합니다.
2. 변형 문제
`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가 나쁩니다.
3. 오류 진단
학생이 `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가 나쁩니다.
이 소문제를 끝냈다고 말할 수 있는 기준
이 소문제의 정확한 공식 페이지와 대조하기
왼쪽은 문제를 읽을 때, 오른쪽은 자신의 풀이를 끝낸 뒤에 확인하세요. 해설 이미지를 먼저 보면 중간 과정을 스스로 만드는 연습이 사라집니다.
Source: Probeklausur.pdf / Probeklausur Musterlösung und Hinweise.pdf · 시험 p3–5 · 공식 해설 p3–6 · SoSe26 Probeklausur 시험 p4 Aufgabe 1d 및 공식 해설 p4의 `arr[j][i]` row-major Lokalität 분석 범위.