Measure Locality in Time

목표

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

왜 중요한가

메모리 계층은 프로그램이 지역성을 갖는다는 가정 위에 서 있습니다. 그 가정을 어기는 코드는 하드웨어가 준비해 둔 도움을 하나도 못 받습니다. 캐시는 데이터를 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 를 받으므로 여유가 있지만, 여러 프로그램을 동시에 돌리지는 마세요.

이 기계의 캐시 계층을 읽는다

이 파드가 도는 CPU 의 캐시 라인 크기와 캐시 계층(L1/L2/L3)을 확인해 /root/mem/01-cache.txt 에 남깁니다. int32 가 한 줄에 몇 개 실리는지도 계산해서 함께 적습니다.

캐시 라인 크기는 /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size 에 있고, 같은 디렉터리의 level, type, size 를 읽으면 계층이 보입니다. int32 는 4바이트이므로 라인 크기를 4로 나누면 한 줄에 몇 개가 실리는지 나옵니다. 이 숫자가 뒤 단계에서 보폭을 고르는 기준이 됩니다.

보폭을 바꿔 재는 도구를 만든다

/root/mem/stride.py 를 만듭니다. python3 /root/mem/stride.py <보폭> 으로 부르면 int32 24,000,001 개짜리 배열(약 96MB)을 만들어 500,000번 읽고, 읽기 한 번에 걸린 나노초를 소수점 한 자리로 숫자만 한 줄 출력해야 합니다.

핵심은 읽는 횟수를 보폭과 무관하게 고정하는 것입니다. 그래야 파이썬 자체의 느림이 양쪽에서 똑같이 상쇄되고 메모리 차이만 남습니다.

인덱스를 미리 목록으로 만들어 두고 재는 구간에서는 그 목록만 도세요. 다음 인덱스는 i = (i + 보폭) % 배열길이 로 옮깁니다. 배열 길이가 홀수라서 보폭이 커도 같은 자리를 금방 다시 밟지 않습니다.

측정 전에 1,000번쯤 미리 읽어 워밍업하세요. 첫 실행에는 배열을 만드는 비용이 섞입니다.

보폭을 1, 16, 65536 으로 바꿔 재기

2단계의 도구로 보폭 1, 16, 65536 을 각각 재어 /root/mem/03-stride.txt 에 보폭 나노초 형식으로 세 줄 남깁니다.

for s in 1 16 65536; do echo "$s $(python3 /root/mem/stride.py $s)"; done 처럼 돌리면 세 줄이 한 번에 나옵니다.

보폭 16 은 int32 기준으로 캐시 라인 하나만큼 건너뛰는 크기이고, 보폭 65536 은 256KB 라서 페이지 경계도 선반입기(prefetcher)가 따라오는 범위도 훌쩍 넘어섭니다. 선반입기는 페이지 경계를 넘지 못하기 때문에 여기서 값이 크게 뜁니다.

크기는 그대로, 순서만 바꾼다

/root/mem/stride.py 가 인자로 rand 를 받으면 무작위 순서로 읽도록 고칩니다. 그다음 순차(보폭 1)와 무작위를 각각 재어 /root/mem/04-random.txt 에 seq 나노초, rand 나노초 두 줄로 남깁니다.

배열 크기도 읽는 횟수도 그대로 두고 읽는 순서만 바꾸는 것이 이 단계의 요점입니다. 크기가 같으니 용량 때문이라고 말할 수 없고, 남는 설명은 공간 지역성뿐입니다.

무작위 인덱스는 재기 전에 미리 만들어 두세요. random.Random(1) 처럼 씨앗을 고정하면 다시 돌려도 같은 순서가 나옵니다.

행렬을 두 방향으로 훑는 도구를 만든다

/root/mem/matrix.py 를 만듭니다. python3 /root/mem/matrix.py <N> <row|col|block> 으로 부르면 int32 N×N 을 평평한 배열 하나(a[i * N + j])에 담아 지정한 방향으로 전부 훑고, 원소 하나당 나노초를 소수점 한 자리로 숫자만 한 줄 출력해야 합니다.

row 는 i 가 바깥, j 가 안쪽입니다. col 은 반대입니다. 두 갈래 모두 인덱스 식은 a[i * N + j] 로 똑같이 두세요. 한쪽만 곱셈을 빼면 측정 차이에 파이썬 연산 비용이 섞여 무엇을 재고 있는지 알 수 없게 됩니다.

block 은 7단계에서 씁니다. 지금은 row 와 col 만 되어도 이 단계는 통과합니다.

행 우선과 열 우선의 차이를 잰다

N 을 2048 로 두고 행 우선과 열 우선을 각각 재어 /root/mem/06-order.txt 에 row 나노초, col 나노초 두 줄로 남깁니다.

같은 원소를 같은 횟수만큼 읽는데 순서만 다릅니다. 그래도 열 우선이 몇 배 느립니다. N 이 2048 이면 열 방향 한 칸이 8KB 이고, 이것은 페이지 하나(4KB)를 넘는 거리입니다.

차이가 잘 안 나면 N 을 키워 보세요. 행렬이 캐시 안에 들어가면 어느 방향으로 읽어도 비슷해집니다.

타일로 잘라 열 우선의 손해를 줄인다

matrix.py 에 block 갈래를 더합니다. 순서는 열 우선 그대로 두되 64×64 조각 안에서만 돌게 합니다. 그다음 N 을 2048 로 두고 열 우선과 타일링을 각각 재어 /root/mem/07-block.txt 에 col 나노초, block 나노초 두 줄로 남깁니다.

바깥 두 겹이 조각의 시작 좌표를 옮기고, 안쪽 두 겹이 조각 안에서 열 우선으로 돕니다. 조각 하나가 64행 × 64열이면 그 안에서 만지는 캐시 라인이 16KB 정도라 L1 에 들어갑니다.

같은 원소를 같은 횟수만큼 읽는데도 빨라지는 이유는 가져온 라인을 버리기 전에 다 쓰기 때문입니다. 행렬 곱셈에서 타일링을 쓰는 이유가 이것입니다.

세 실험을 한 문장씩으로 정리한다

/root/mem/08-notes.md 에 세 줄 이상 적습니다. 보폭을 키우면 왜 느려지는지, 열 우선 순회가 왜 손해인지, 타일링이 무엇을 되돌리는지를 각각 한 문장으로 씁니다.

세 실험은 모두 같은 이야기를 다른 각도에서 합니다. 메모리는 라인 단위로 움직이고, 가져온 라인을 쓰지 않고 버리면 그만큼 손해라는 것입니다.

보폭, 열 우선, 타일 이라는 말이 본문에 들어가야 합니다.