컴퓨터 구조: 캐시, 파이프라인, 메모리 계층

같은 O(n)인 코드가 왜 몇 배씩 차이 나는지 하드웨어에서 답을 찾아요. 64바이트 줄 단위로 움직이는 캐시를 직접 흉내 내서 행을 따라 읽으면 적중률 87.5%, 열을 따라 읽으면 0%가 되는 모습을 보고, 넘파이로 같은 원소를 순서만 바꿔 읽어 실제 속도 차이를 재요. 명령을 겹쳐 처리하는 파이프라인, 정렬된 데이터에서 거의 틀리지 않는 분기 예측, 여러 코어와 SIMD, 그리고 이 모든 것을 코드에 살리는 데이터 배치 요령까지 다뤄요.

고급강의 1 / 6약 11분

컴퓨터 과학 심화 트랙의 첫 강의예요. 이론 트랙에서 계산을 수학으로 봤다면, 이 트랙에서는 실제 기계와 시스템이 계산을 어떻게 해내는지 봐요. 컴퓨터 기초 트랙에서 메모리 계층의 대략적인 속도를 봤어요. L1 캐시를 1초로 치면 메인 메모리는 1분 40초였죠. 알고리즘 트랙의 복잡도는 이런 차이를 상수로 보고 버렸지만, 실제 프로그램의 속도에서는 이 상수가 몇 배에서 몇십 배의 차이를 만들어요. 그 이유를 캐시, 파이프라인, 분기 예측으로 하나씩 열어 봐요.

캐시는 줄 단위로 움직여요

CPU가 메모리에서 값 하나를 읽을 때, 캐시는 그 값만 가져오지 않고 주변을 묶은 캐시 줄(보통 64바이트)을 통째로 가져와요. 8바이트 실수라면 이웃한 8개가 한꺼번에 들어와요. 이 설계는 프로그램의 두 가지 버릇, 즉 지역성에 기대고 있어요.

  • 공간 지역성: 방금 읽은 곳의 옆을 곧 읽을 가능성이 커요. 배열을 차례로 훑을 때가 그래요.
  • 시간 지역성: 방금 읽은 것을 곧 다시 읽을 가능성이 커요. 반복문 안에서 계속 쓰는 변수가 그래요.

캐시가 가득 차면 가장 오래 안 쓴 줄부터 내보낸다고 치고, 작은 캐시(32KB)를 흉내 내 볼게요. 1024 × 1024 행렬은 한 행이 메모리에 이어져 있는 행 우선 방식으로 저장돼 있어요. 같은 원소들을 행을 따라 읽을 때와 열을 따라 읽을 때를 비교해요.

from collections import OrderedDict

class Cache:                                         # 64바이트 줄 단위로 가져오고, 가장 오래 안 쓴 줄부터 내보내요
    def __init__(self, size_bytes=32 * 1024, line_bytes=64):
        self.capacity, self.line_bytes = size_bytes // line_bytes, line_bytes
        self.lines, self.hits, self.misses = OrderedDict(), 0, 0

    def access(self, address):
        line = address // self.line_bytes            # 이 주소가 속한 줄 번호
        if line in self.lines:
            self.hits += 1
            self.lines.move_to_end(line)             # 방금 썼다고 표시해요
        else:
            self.misses += 1
            self.lines[line] = True                  # 메모리에서 줄 전체를 가져와요
            if len(self.lines) > self.capacity:
                self.lines.popitem(last=False)       # 가장 오래 안 쓴 줄을 내보내요

N, SIZE = 1024, 8                                    # 1024 × 1024 행렬, 원소 하나는 8바이트 실수

def address(i, j):                                   # 행 우선 저장: 한 행이 메모리에 이어져 있어요
    return (i * N + j) * SIZE

orders = {
    "행을 따라 읽기(i 바깥, j 안쪽)": lambda: ((i, j) for i in range(N) for j in range(N)),
    "열을 따라 읽기(j 바깥, i 안쪽)": lambda: ((i, j) for j in range(N) for i in range(N)),
}
for label, order in orders.items():
    cache = Cache()
    for i, j in order():
        cache.access(address(i, j))
    print(f"{label}: 적중률 {cache.hits / (cache.hits + cache.misses):.1%}, 메모리에서 가져온 줄 {cache.misses:,}개")
행을 따라 읽기(i 바깥, j 안쪽): 적중률 87.5%, 메모리에서 가져온 줄 131,072개
열을 따라 읽기(j 바깥, i 안쪽): 적중률 0.0%, 메모리에서 가져온 줄 1,048,576개

행을 따라 읽으면 줄 하나를 가져올 때마다 8개를 연달아 쓰니, 8번 중 7번은 캐시에서 바로 찾아요(87.5%). 열을 따라 읽으면 다음 원소가 한 행(8KB) 뒤에 있어서 매번 다른 줄이 필요해요. 게다가 한 열에 필요한 줄 1,024개가 캐시(512줄)에 다 들어가지 않아서, 다음 열로 넘어갔을 땐 이미 쫓겨나 있어요. 결국 매번 메모리까지 가야 해요(0%). 계산은 똑같고 순서만 다른데 메모리에서 가져오는 양이 8배예요.

C로 짠 행렬 곱셈에서 반복문 세 개의 순서만 바꿔도 몇 배씩 빨라지는 이유가 이거예요. 파이썬에서도 넘파이처럼 실제 메모리 배치가 드러나는 도구에서는 같은 일이 일어나요. 같은 원소들을 순서만 바꿔 읽어 볼게요.

import time
import numpy as np

rng = np.random.default_rng(0)
data = np.arange(2**24, dtype=np.int64)              # 128MB: 캐시보다 훨씬 커요
in_order = np.arange(2**24)
shuffled = rng.permutation(2**24)                    # 같은 번호들을 순서만 섞었어요

def seconds(indices):
    start = time.perf_counter()
    data[indices].sum()
    return time.perf_counter() - start

t_seq = min(seconds(in_order) for _ in range(3))
t_rand = min(seconds(shuffled) for _ in range(3))
print("같은 원소를 읽는데 무작위 순서가 두 배 넘게 느린가요?", t_rand / t_seq > 2)
같은 원소를 읽는데 무작위 순서가 두 배 넘게 느린가요? True

약 1,700만 개의 같은 원소를 읽어 더했을 뿐인데, 무작위 순서는 차례로 읽을 때보다 몇 배 느려요(이 컴퓨터에서는 5배쯤이었어요). 차례로 읽으면 줄 하나로 8개를 얻고, CPU가 다음 줄을 미리 가져다 두기도(프리페치) 해요. 무작위로 읽으면 거의 매번 메모리까지 다녀와야 해요. 알고리즘 트랙에서 연결 리스트가 이론보다 느린 경우가 많다고 한 것도, 파이썬의 딕셔너리가 이어진 배열 안에서 빈칸을 찾는 개방 주소법을 쓰는 것도 이 때문이에요.

파이프라인: 명령을 겹쳐 처리하기

CPU는 명령 하나를 여러 단계로 나눠 처리해요. 교과서에서 흔히 쓰는 다섯 단계로 보면, 명령을 가져오고(F), 무슨 명령인지 해석하고(D), 계산하고(E), 메모리를 읽거나 쓰고(M), 결과를 레지스터에 저장해요(W). 빨래를 세탁, 건조, 개기로 나눠 하듯, 앞 명령이 둘째 단계로 넘어가면 다음 명령이 첫째 단계를 시작할 수 있어요.

stages = "FDEMW"                                     # 가져오기, 해석, 실행, 메모리, 저장
n = 5
cycles = n + len(stages) - 1
print("cycle " + " ".join(f"{c:>2}" for c in range(1, cycles + 1)))
for k in range(n):
    row = ["  "] * cycles
    for s, name in enumerate(stages):
        row[k + s] = f" {name}"
    print((f"I{k + 1}    " + " ".join(row)).rstrip())
print(f"파이프라인 없이 {n * len(stages)}박자, 파이프라인으로 {cycles}박자")
cycle  1  2  3  4  5  6  7  8  9
I1     F  D  E  M  W
I2        F  D  E  M  W
I3           F  D  E  M  W
I4              F  D  E  M  W
I5                 F  D  E  M  W
파이프라인 없이 25박자, 파이프라인으로 9박자

I1부터 I5는 첫째부터 다섯째 명령이에요. 명령 하나가 끝나는 데는 여전히 5박자가 걸리지만, 파이프라인이 차고 나면 박자마다 명령이 하나씩 끝나요. 명령이 많을수록 거의 5배 빨라지는 셈이에요. 요즘 CPU는 단계를 10개 넘게 나누고, 한 박자에 명령을 여러 개 시작하고, 순서를 바꿔서라도 놀고 있는 계산 장치를 채워요.

하지만 파이프라인이 늘 꽉 차 있는 건 아니에요.

  • 데이터 의존: 다음 명령이 앞 명령의 결과를 써야 하면 그 결과가 나올 때까지 기다려야 해요.
  • 캐시 미스: 메모리에서 값을 기다리는 동안 수백 박자를 놀 수 있어요. 앞의 실험이 바로 이 상황이에요.
  • 분기: if나 반복문의 끝처럼 다음에 실행할 명령이 조건에 따라 갈리면, 조건이 계산될 때까지 무엇을 가져와야 할지 몰라요.

분기 예측: 미리 짐작해서 달리기

분기 때마다 멈추면 파이프라인이 소용없으니, CPU는 조건의 결과를 짐작해서 그쪽 명령을 미리 실행해요. 맞으면 그대로 가고, 틀리면 미리 해 둔 일을 버리고 다시 시작해요. 틀릴 때마다 보통 십수 박자를 잃어요. 가장 단순한 예측기 하나를 흉내 내서, 같은 데이터를 정렬하기 전과 후에 얼마나 틀리는지 볼게요.

import random

def mispredict_rate(outcomes):                       # 2비트 예측기: 두 번 연속 틀려야 예측을 바꿔요
    state, wrong = 2, 0                              # 0과 1은 "안 간다", 2와 3은 "간다"로 예측해요
    for taken in outcomes:
        if (state >= 2) != taken:
            wrong += 1
        state = min(state + 1, 3) if taken else max(state - 1, 0)
    return wrong / len(outcomes)

random.seed(0)
values = [random.randrange(256) for _ in range(100_000)]
for label, data in [("무작위 순서", values), ("정렬한 뒤", sorted(values))]:
    outcomes = [v >= 128 for v in data]              # if v >= 128: 이 조건이 참인지 거짓인지의 나열
    print(f"{label}: 분기 예측이 틀린 비율 {mispredict_rate(outcomes):.2%}")
무작위 순서: 분기 예측이 틀린 비율 50.06%
정렬한 뒤: 분기 예측이 틀린 비율 0.00%

무작위 순서에서는 조건이 동전 던지기라 절반을 틀려요. 정렬한 뒤에는 앞부분은 내내 거짓, 뒷부분은 내내 참이라 경계에서 한두 번만 틀려요. 그래서 C나 자바로 "128 이상인 값만 더하기"를 짜면, 같은 데이터를 정렬해 두기만 해도 몇 배 빨라지는 일이 실제로 일어나요. 실제 CPU의 예측기는 과거의 분기 기록을 훨씬 정교하게 써서 대부분의 분기를 맞혀요.

여러 코어와 SIMD

코어 하나를 더 빠르게 만들기 어려워지자, 칩에 코어를 여러 개 넣는 쪽으로 발전했어요. 하지만 코어가 8개라고 프로그램이 저절로 8배 빨라지지는 않아요. 일을 나눠 맡기는 코드를 짜야 하고, 그 방법은 동시성 강의에서 다뤄요.

코어 하나 안에도 병렬성이 있어요. SIMD는 명령 하나로 여러 값을 한꺼번에 계산하는 기능이에요. 예를 들어 256비트 레지스터에 8바이트 실수 4개를 담아 덧셈 한 번에 네 쌍을 더해요. 넘파이가 파이썬 반복문보다 수십 배 빠른 건 인터프리터를 거치지 않는 데다, 이어진 배열을 SIMD로 한꺼번에 처리하기 때문이에요. GPU는 이 생각을 끝까지 밀어붙여서 수천 개의 작은 계산 장치가 같은 계산을 동시에 해요. 딥러닝이 GPU에서 돌아가는 이유예요.

코드에 살리는 법

  • 저장된 순서대로 읽어요. 2차원 데이터는 저장된 방향(행 우선이면 행)을 따라 돌아요.
  • 함께 쓰는 것을 함께 둬요. 100만 명의 나이만 평균 낼 거라면, 사람마다 객체를 만들어 이름, 주소, 나이를 묶어 두기보다 나이만 모은 배열이 훨씬 빨라요. 필요한 값만 연달아 읽으니까요. 분석용 데이터베이스와 Parquet 같은 파일 형식이 열 단위로 저장하는 이유예요.
  • 주소를 따라다니는 구조를 줄여요. 연결 리스트나 객체의 리스트는 메모리 여기저기를 뛰어다녀요. 숫자가 많으면 넘파이 배열처럼 값을 이어서 담아요.
  • 예측하기 쉬운 분기를 만들어요. 자주 도는 반복문 안의 분기를 줄이거나, 데이터를 정렬하거나 묶어서 같은 쪽으로 가게 해요.
  • 추측하지 말고 재요. 복잡도 강의에서 말한 순서 그대로, 먼저 재고 병목을 찾은 뒤 고쳐요. 리눅스의 perf 같은 도구는 캐시 미스와 분기 예측 실패 횟수까지 보여 줘요.

실습

  1. Cache의 크기를 64KB로 바꿔 열을 따라 읽는 실험을 다시 해 보세요. 적중률이 어떻게 바뀌고, 왜 하필 그 크기에서 바뀔까요?
  2. N을 256으로 줄이면 32KB 캐시에서도 열을 따라 읽을 때의 적중률이 높아져요. 왜 그런지 줄 수로 설명해 보세요.
  3. 넘파이 실험에서 무작위 대신 4,096칸씩 건너뛰며 읽는 순서를 만들어 보세요. 차례대로와 무작위 사이 어디쯤일까요?
  4. 파이프라인 표에 "3번 명령이 2번 명령의 결과를 기다리느라 두 박자 쉰다"를 그려 넣고, 전체 박자 수를 다시 세어 보세요.
  5. 2비트 예측기 대신 "직전 결과와 같다고 예측하는" 1비트 예측기를 만들어, 참과 거짓이 번갈아 나오는 데이터에서 둘을 비교해 보세요.

자주 하는 오해

  • 복잡도가 같으면 속도도 비슷하다. 메모리를 읽는 순서만으로 몇 배씩 차이 나요.
  • 메모리는 어디든 똑같은 속도로 읽힌다. 캐시에 있으면 몇 박자, 없으면 수백 박자예요. RAM의 R(Random)은 "어디든 접근할 수 있다"는 뜻이지 "어디든 똑같이 빠르다"는 뜻이 아니에요.
  • CPU는 명령을 하나씩 차례로 실행한다. 겹쳐서, 여러 개를 동시에, 때로는 순서를 바꿔 실행하고, 결과만 차례로 실행한 것처럼 보여 줘요.
  • 코어가 많으면 무엇이든 빨라진다. 일을 나누도록 짠 프로그램만 빨라져요.
  • 이건 C 개발자만의 이야기다. 파이썬에서도 넘파이, 판다스, 데이터베이스를 쓸 때 데이터 배치가 속도를 좌우해요.

점검 문제

  1. 캐시가 값 하나가 아니라 줄 단위로 가져오는 이유는?
  2. 행 우선으로 저장된 행렬을 열을 따라 읽으면 왜 느린가요?
  3. 같은 원소를 읽는데 무작위 순서가 차례대로보다 느린 이유 두 가지는?
  4. 파이프라인은 명령 하나의 시간을 줄이나요, 단위 시간당 처리량을 늘리나요?
  5. 파이프라인을 멈추게 하는 세 가지 상황은?
  6. 분기 예측이란 무엇이고, 데이터를 정렬하면 왜 빨라질 수 있나요?
  7. SIMD란 무엇이고, 넘파이가 빠른 이유와 어떤 관계가 있나요?
  8. 100만 명의 나이 평균을 빠르게 내려면 데이터를 어떻게 담는 게 좋을까요?

정답

  1. 방금 읽은 곳의 옆을 곧 읽을 가능성이 큰 공간 지역성 때문이에요. 이웃을 한꺼번에 가져오면 다음 읽기를 캐시에서 바로 해결할 수 있어요.
  2. 다음 원소가 한 행만큼 떨어져 있어서 매번 다른 캐시 줄이 필요하고, 가져온 줄에서 하나만 쓰고 버리게 되기 때문이에요. 한 열에 필요한 줄이 캐시보다 많으면 다음 열로 넘어갔을 때 이미 쫓겨나 있어요.
  3. 차례로 읽으면 한 줄에서 여러 원소를 얻고, CPU가 다음 줄을 미리 가져다 둘 수 있기 때문이에요. 무작위로 읽으면 거의 매번 메모리까지 다녀와야 해요.
  4. 처리량을 늘려요. 명령 하나가 끝나는 시간은 그대로지만, 파이프라인이 차면 박자마다 명령이 하나씩 끝나요.
  5. 앞 명령의 결과를 기다려야 하는 데이터 의존, 메모리에서 값을 기다리는 캐시 미스, 다음 명령이 조건에 따라 갈리는 분기예요.
  6. 조건의 결과를 짐작해서 그쪽 명령을 미리 실행하는 거예요. 정렬하면 조건의 결과가 한동안 같은 쪽으로 이어져서 짐작이 거의 틀리지 않으니, 버리고 다시 하는 일이 줄어요.
  7. 명령 하나로 여러 값을 한꺼번에 계산하는 기능이에요. 넘파이는 이어진 배열을 인터프리터 없이 SIMD로 한꺼번에 처리해서 파이썬 반복문보다 훨씬 빨라요.
  8. 사람마다 객체를 만들기보다 나이만 모은 배열(예를 들어 넘파이 배열)로 담는 게 좋아요. 필요한 값만 이어서 읽으니 캐시를 잘 쓰고 SIMD도 쓸 수 있어요.

다음 강의

캐시가 하드웨어 수준에서 "무엇을 가까이 둘지"를 고른다면, 운영체제는 더 큰 수준에서 비슷한 일을 해요. 어떤 프로그램에 CPU를 줄지, 메모리가 모자랄 때 무엇을 디스크로 내보낼지요. 다음 강의에서는 운영체제가 여러 프로그램을 동시에 돌리는 스케줄링과, 프로그램마다 자기만의 메모리를 가진 것처럼 보이게 하는 가상 메모리를 다뤄요.