메모리 계층 설계

프로세서는 빠르고 메모리는 느립니다. 이 문장은 너무 자주 등장해서 별 감흥이 없지만, 현대 컴퓨터의 많은 복잡도가 바로 여기서 태어납니다. CPU는 매 사이클 다음 일을 하고 싶은데, DRAM은 수십에서 수백 사이클 뒤에 대답합니다. 둘을 그대로 붙여 놓으면 빠른 코어가 메모리 앞에서 줄을 섭니다. 메모리 계층은 그 줄을 짧아 보이게 만드는 기술입니다.

2.1 지역성과 메모리 계층

캐시가 성립하는 이유는 프로그램이 완전히 무작위로 메모리를 쓰지 않기 때문입니다. 방금 쓴 데이터를 곧 다시 쓰는 경향을 시간적 지역성, 어떤 주소를 쓰면 그 근처 주소도 곧 쓰는 경향을 공간적 지역성이라고 합니다. 캐시는 이 두 습관에 기대어 작고 빠른 저장소를 큰 메모리 앞에 세웁니다.

2.2 AMAT: 평균 메모리 접근 시간

캐시 이야기를 숫자로 묶는 가장 기본 식은 AMAT입니다. 평균적으로 메모리 접근 하나가 얼마나 걸리는지 보는 식입니다.

AMAT = Hit time + Miss rate × Miss penalty

Hit time은 캐시에서 찾았을 때 걸리는 시간입니다. Miss rate는 못 찾을 확률, Miss penalty는 못 찾았을 때 아래 계층에서 가져오느라 추가로 내는 비용입니다. 세 항 중 하나만 나빠도 전체가 무너집니다. 빠른 L1을 만들려고 작게 했더니 미스율이 오를 수 있고, 미스율을 낮추려고 크게 했더니 히트 시간이 길어질 수 있습니다.

다단계 캐시의 AMAT

L1 뒤에 L2가 있으면 식은 조금 길어집니다. 하지만 감각은 같습니다. 앞 계층에서 실패한 접근만 다음 계층으로 내려갑니다.

AMAT = L1 hit time
     + L1 miss rate × (L2 hit time + L2 miss rate × L2 miss penalty)

2.3 캐시 미스의 네 가지 얼굴

캐시 미스는 그냥 “없음”이 아닙니다. 왜 없었는지에 따라 처방이 달라집니다. 감기와 근육통을 둘 다 “몸이 별로”라고 부르면 약을 고르기 어렵듯, 미스도 분류해야 합니다.

2.4 캐시 설계의 기본 선택지

캐시는 주소를 블록 단위로 저장합니다. 주소가 들어오면 태그를 비교해 이 블록이 원하는 데이터인지 확인하고, 맞으면 hit, 아니면 miss입니다. 여기서 중요한 선택지는 블록 크기, 캐시 크기, 연관도, 교체 정책, 쓰기 정책입니다.

블록 크기

블록을 크게 하면 공간적 지역성을 더 잘 이용할 수 있습니다. 배열을 순서대로 읽는다면 한 번 가져온 블록 안에 다음 원소들이 같이 들어옵니다. 하지만 너무 크면 쓸모없는 바이트까지 끌고 와서 대역폭을 낭비하고, 캐시에 들어갈 블록 수가 줄어 capacity 미스가 늘 수 있습니다.

연관도

직접 사상 캐시는 주소마다 들어갈 자리가 하나뿐이라 빠르고 단순합니다. 대신 두 블록이 같은 자리를 번갈아 원하면 계속 밀어냅니다. 완전 연관 캐시는 아무 곳에나 둘 수 있어 conflict 미스가 적지만 비교가 비싸고 느립니다. 집합 연관 캐시는 둘 사이의 현실적인 타협입니다.

쓰기 정책

write-through는 캐시에 쓸 때 아래 계층에도 바로 씁니다. 단순하지만 쓰기 트래픽이 늘어납니다. write-back은 캐시에서만 바꾸고 나중에 밀려날 때 아래 계층에 씁니다. 트래픽은 줄지만 dirty 상태를 관리해야 합니다. write allocate 여부도 중요합니다. 쓰기 미스 때 블록을 캐시에 가져올지, 그냥 아래 계층에만 쓸지 결정합니다.

2.5 캐시 최적화 감각

교재에는 캐시 최적화 기법이 길게 나옵니다. 이름은 많지만 큰 방향은 세 가지입니다. 히트 시간을 줄이기, 미스율을 줄이기, 미스 페널티를 줄이기. AMAT 식의 세 항을 각각 겨냥한다고 보면 됩니다.

Hit time 줄이기

작고 단순한 L1, way prediction, trace cache 같은 접근이 여기에 들어갑니다.

Miss rate 줄이기

큰 캐시, 높은 연관도, victim cache, 컴파일러의 데이터 배치 개선이 도움을 줍니다.

Miss penalty 줄이기

다단계 캐시, critical word first, early restart, nonblocking cache가 대표적입니다.

특히 nonblocking cache는 미스 하나가 나는 동안 독립적인 다른 메모리 접근을 계속 진행하게 해줍니다. 고성능 코어에서는 메모리 미스를 하나씩 얌전히 기다리는 것이 너무 비쌉니다. 여러 미스를 동시에 떠안고, 준비된 일부터 처리해야 파이프라인이 숨을 쉽니다.

2.6 프리패치와 블로킹

프리패치는 앞으로 필요할 데이터를 미리 가져오는 기술입니다. 잘 맞으면 compulsory 미스와 긴 지연을 줄입니다. 틀리면 필요 없는 데이터를 가져와 대역폭을 쓰고 캐시를 오염시킵니다. 미래를 맞히는 일은 늘 보상이 크고, 틀렸을 때의 표정도 큽니다.

// 순차 접근은 하드웨어 프리패처가 좋아하는 냄새입니다.
for (i = 0; i < n; i++) {
  sum += A[i];
}

// 일정한 stride도 어느 정도 예측할 수 있습니다.
for (i = 0; i < n; i += 4) {
  sum += A[i];
}

블로킹은 큰 작업을 캐시에 들어갈 만한 작은 타일로 나누는 방법입니다. 행렬 곱처럼 같은 데이터를 여러 번 재사용하는 계산에서 특히 중요합니다. 한 번 가져온 데이터를 캐시 안에서 충분히 써먹고 내보내자는 전략입니다.

// 개념적 타일링: C의 작은 블록을 잡고 A/B의 필요한 조각을 반복 사용합니다.
for (ii = 0; ii < N; ii += B)
  for (jj = 0; jj < N; jj += B)
    for (kk = 0; kk < N; kk += B)
      multiply_block(C[ii:ii+B][jj:jj+B],
                     A[ii:ii+B][kk:kk+B],
                     Bm[kk:kk+B][jj:jj+B]);

2.7 가상 메모리와 TLB

가상 메모리는 각 프로그램에게 자기만의 크고 연속적인 주소 공간이 있는 것처럼 보이게 합니다. 실제 물리 메모리는 운영체제가 페이지 단위로 나누어 관리하고, 하드웨어는 가상 주소를 물리 주소로 변환합니다. 이 변환 정보는 페이지 테이블에 있지만, 매 접근마다 페이지 테이블을 읽으면 너무 느립니다. 그래서 TLB가 있습니다. TLB는 최근 주소 변환 결과를 저장하는 작은 캐시입니다.

가상 주소
  ├─ VPN: 가상 페이지 번호  → TLB/페이지 테이블로 물리 페이지 번호 찾기
  └─ offset: 페이지 안 위치 → 그대로 사용

물리 주소 = 물리 페이지 번호 + offset

TLB hit이면 주소 변환이 빠르게 끝납니다. TLB miss이면 페이지 테이블을 찾아야 하고, 필요한 페이지가 메모리에 없으면 page fault가 발생해 운영체제가 저장장치에서 페이지를 가져옵니다. 캐시 미스가 “느림”이라면, page fault는 “잠깐 나갔다 오겠습니다”에 가깝습니다. 단위가 훨씬 큽니다.

큰 페이지의 유혹

페이지가 크면 TLB 한 엔트리가 커버하는 주소 범위가 커집니다. 이를 TLB reach 또는 coverage라고 부릅니다. 큰 페이지는 대용량 배열이나 데이터베이스처럼 넓은 메모리를 훑는 작업에서 유리할 수 있습니다. 대신 내부 단편화가 늘고, 페이지 관리가 둔해질 수 있습니다. 역시 한쪽을 누르면 다른 쪽이 올라옵니다.

2.8 메모리 성능을 읽는 법

메모리 성능 문제를 보면 먼저 현상을 분리해야 합니다. L1 miss인지, LLC miss인지, TLB miss인지, 대역폭이 꽉 찬 것인지, coherence 트래픽이 많은 것인지가 다릅니다. 모두 “메모리가 느려요”로 들리지만 처방은 완전히 달라집니다.

그래서 이 장의 결론은 단순합니다. 메모리 계층은 빠른 저장소를 많이 붙이는 장식이 아니라, 프로그램의 지역성을 숫자로 이용하는 설계입니다. 좋은 코드는 캐시에게 힌트를 줍니다. 좋은 캐시는 그 힌트를 놓치지 않습니다.