지역성을 시간으로 재어 본다

목표

같은 데이터를 같은 횟수만큼 읽는데도 읽는 순서 하나로 시간이 몇 배 갈리는 것을 직접 재어 봅니다. 보폭, 행 우선과 열 우선, 타일링 세 가지 실험을 지나면 지역성이 추상적인 말이 아니라 손에 잡히는 숫자가 됩니다.

왜 중요한가

메모리 계층은 프로그램이 지역성을 갖는다는 가정 위에 서 있습니다. 그 가정을 어기는 코드는 하드웨어가 준비해 둔 도움을 하나도 못 받습니다. 캐시는 데이터를 64바이트 라인 단위로 가져오고, 선반입기는 일정한 간격으로 나아가는 접근을 미리 읽어 두며, TLB 는 최근에 쓴 페이지의 주소 변환을 기억합니다. 보폭을 키우면 이 셋이 차례로 무력해집니다.

여기서 재는 것은 파이썬의 속도가 아닙니다. 파이썬은 느리지만 그 느림은 어느 실험에나 똑같이 붙으므로, 읽는 횟수를 고정해 두면 남는 차이는 메모리 때문입니다. 이 설계가 이 실습의 전부라고 해도 됩니다.

숫자의 절대값은 기계마다 다릅니다. 채점기도 절대값은 보지 않고 어느 쪽이 얼마나 더 느린가만 봅니다.

단계

1. 이 파드가 도는 CPU 의 캐시 라인 크기와 캐시 계층을 확인해 /root/mem/01-cache.txt 에 남깁니다.
2. /root/mem/stride.py 를 만듭니다. 보폭을 인자로 받아 읽기 한 번당 나노초를 숫자만 한 줄 출력합니다.
3. 보폭 1, 16, 65536 을 재어 /root/mem/03-stride.txt 에 세 줄로 남깁니다.
4. stride.py 에 rand 갈래를 더하고, 순차와 무작위를 재어 /root/mem/04-random.txt 에 두 줄로 남깁니다.
5. /root/mem/matrix.py 를 만듭니다. N 과 순회 방향을 인자로 받아 원소 하나당 나노초를 출력합니다.
6. N 을 2048 로 두고 행 우선과 열 우선을 재어 /root/mem/06-order.txt 에 두 줄로 남깁니다.
7. matrix.py 에 block 갈래를 더하고, 열 우선과 타일링을 재어 /root/mem/07-block.txt 에 두 줄로 남깁니다.
8. 세 실험을 한 문장씩 정리해 /root/mem/08-notes.md 에 남깁니다.

참고

• 산출물은 모두 /root/mem/ 아래에 둡니다. mkdir -p /root/mem 을 먼저 해 두세요.
• 시간은 time.perf_counter() 로 잽니다. time.time() 은 해상도가 모자랍니다.
• 재기 전에 1,000번쯤 미리 읽어 워밍업하세요. 첫 접근에는 배열을 만드는 비용과 페이지 폴트가 섞입니다.
• 흔한 실수 1: 배열을 작게 잡는 것입니다. 캐시에 들어가는 크기면 보폭을 아무리 바꿔도 차이가 나지 않습니다.
• 흔한 실수 2: 갈래마다 인덱스 식을 다르게 쓰는 것입니다. 한쪽에서 곱셈을 빼면 그 차이가 측정값에 섞여, 메모리를 재는지 산술을 재는지 알 수 없게 됩니다.
• 배열은 96MB 쯤 됩니다. 파드는 메모리 2Gi 를 받으므로 여유가 있지만, 여러 프로그램을 동시에 돌리지는 마세요.

단계 8개

1. 이 기계의 캐시 계층을 읽는다
2. 보폭을 바꿔 재는 도구를 만든다
3. 보폭을 1, 16, 65536 으로 바꿔 재기
4. 크기는 그대로, 순서만 바꾼다
5. 행렬을 두 방향으로 훑는 도구를 만든다
6. 행 우선과 열 우선의 차이를 잰다
7. 타일로 잘라 열 우선의 손해를 줄인다
8. 세 실험을 한 문장씩으로 정리한다