메모리 계층 구조
C 언어의 2차원 배열 a[i][j]를 위와 같이 안쪽 루프를 j로 하여 순회하면, 안쪽을 i로 하는 것보다 빨라지기 쉽습니다. 그 이유는 무엇입니까?
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += a[i][j];- A행 우선(row-major)으로 저장되어 있어 연속된 주소를 차례로 읽으므로 캐시 라인을 효율적으로 사용할 수 있기 때문
- B컴파일러가 루프 안의 덧셈을 한데 묶어 제거하여 계산 자체를 실행 시에 생략해 버리기 때문
- C안쪽을 j로 하면 TLB를 전혀 참조하지 않게 되어 가상 주소에서 물리 주소로의 변환이 필요 없어지기 때문
정답과 해설 보기
정답: A. 행 우선(row-major)으로 저장되어 있어 연속된 주소를 차례로 읽으므로 캐시 라인을 효율적으로 사용할 수 있기 때문
C 언어의 2차원 배열은 행 우선(row-major)으로 저장되므로 a[i][0], a[i][1]…이 메모리상에서 서로 인접합니다. 안쪽을 j로 하면 연속된 주소를 차례로 읽기 때문에, 한 번의 미스로 가져온 64바이트 캐시 라인의 나머지 부분도 곧바로 사용됩니다. 안쪽을 i로 하면 한 행 크기만큼 떨어진 주소를 띄엄띄엄 읽게 되어, 라인의 극히 일부만 사용한 채 쫓겨나기 쉽습니다. TLB는 계속 사용되며 주소 변환이 불필요해지는 것은 아닙니다.
- A. 올바릅니다. 연속된 주소를 읽으므로 가져온 라인 전체를 사용할 수 있습니다.
- B. 덧셈은 생략되지 않으며, 어느 순서든 같은 계산을 수행합니다.
- C. TLB는 계속 사용되며 주소 변환도 이루어집니다.