캐시와 메모리 계층

기다림의 사다리

컴퓨터의 기억 장치는 한 가지가 아니다. 빠른 것은 비싸고 작으며, 크고 싼 것은 느리다. 이 둘을 동시에 가질 수 없으니, 설계자는 여러 종류를 층층이 쌓아 메모리 계층(Memory hierarchy)을 만든다. 맨 위의 레지스터는 코어가 매 클럭 바로 쓰는 수십 개의 칸이고, 그 아래로 L1, L2, L3 캐시, 칩 전체가 함께 쓰는 시스템 캐시(SLC), 칩 밖의 DRAM, 그리고 전원을 꺼도 지워지지 않는 플래시 저장장치가 이어진다.

각 층의 지연을 막대로 늘어놓으면 한 화면에 담기지 않는다. 그래서 아래 그림은 가로축을 로그 눈금으로 그렸다. 한 칸이 10배다. 층을 눌러 보고, "사람 시간"으로 바꿔 1클럭(0.25 ns)을 1초로 늘렸을 때 각 층이 얼마나 먼지 느껴 보자.

사다리에서 눈여겨볼 것은 간격이 일정하지 않다는 점이다. L1에서 L3까지는 열 배 남짓 느려지지만, 칩 밖 DRAM으로 나가는 순간 다시 열 배, 플래시로 가면 거기서 또 수백 배가 뛴다. 칩 경계를 넘는 일이 그만큼 비싸다(1장에서 본 "데이터 이동이 비싸다"는 원칙). 그래서 캐시의 목표는 단순하다. 코어가 원하는 데이터를 가능한 한 사다리 위쪽에서 찾게 하는 것.

캐시는 무엇으로 만드나: 6T SRAM 셀

캐시의 비트 하나는 트랜지스터 여섯 개로 만든 SRAM 셀(Static RAM cell, 6T)에 저장된다. 가운데에 인버터 두 개가 서로의 출력을 입력으로 물고 있다. 한쪽 노드 Q가 1이면 반대쪽 QB는 0이고, 이 상태는 전원이 있는 한 스스로 유지된다(그래서 "정적" RAM이다. DRAM처럼 새로 고칠 필요가 없다. 7장). 나머지 트랜지스터 두 개는 접근 트랜지스터로, 가로로 지나가는 워드라인(Wordline, WL)이 켜질 때만 셀을 세로 방향의 비트라인(Bitline, BL/BLB) 한 쌍에 연결한다.

아래 셀을 직접 조작해 보자. WL 선을 누르면 워드라인이 켜지고 꺼진다. 비트라인 아래의 상자를 누르면 그 비트라인을 "프리차지(1로 미리 충전 후 떠 있음)"와 "0으로 강하게 구동" 사이에서 바꾼다. 버튼은 이 조작을 정해진 순서로 대신 해 준다.

읽기에서 비트라인 전압이 끝까지 내려가기를 기다리지 않는다는 점이 중요하다. 감지 증폭기는 수십~100 mV의 작은 차이만 보고 판단하므로, 그만큼 빨리 읽을 수 있다. 대신 셀 트랜지스터의 크기 비율을 신중하게 맞춰야 한다. 읽는 동안 0 쪽 노드가 비트라인 쪽으로 끌려 올라가 값이 뒤집히면 안 되고(읽기 안정성), 쓰는 동안에는 접근 트랜지스터가 셀 안의 PMOS를 이길 만큼 세야 한다(쓰기 능력). 공정이 미세해질수록 트랜지스터 특성의 편차가 커져 이 균형을 맞추기 어려워진다.

셀 하나가 1비트이니, 64 KB L1 데이터 캐시에는 데이터 셀만 52만 개가 넘고, 여기에 뒤에서 볼 태그·상태 비트가 더해진다. 셀들은 수백 행 × 수백 열의 작은 배열(서브어레이)로 묶이고, 주소의 일부가 행(워드라인)을, 일부가 열을 고른다.

캐시가 통하는 이유: 지역성

캐시는 메인 메모리의 아주 작은 일부만 담는다. 스마트폰 DRAM이 12 GB라면 L1은 그 20만분의 1도 안 된다. 그런데도 실제 프로그램에서 L1 적중률은 흔히 95%를 넘는다. 이유는 프로그램의 메모리 접근이 무작위가 아니기 때문이다.

• 시간 지역성(Temporal locality): 방금 쓴 데이터는 곧 다시 쓰일 가능성이 높다. 반복문의 합계 변수, 자주 부르는 함수의 명령어가 그렇다.
• 공간 지역성(Spatial locality): 방금 쓴 주소 근처가 곧 쓰일 가능성이 높다. 배열을 차례로 훑는 경우가 대표적이다.

캐시는 공간 지역성을 이용하려고 바이트 하나가 아니라 캐시 줄(Cache line, 블록) 단위로 데이터를 가져온다. 요즘 CPU는 대부분 64바이트, 애플의 일부 코어는 128바이트 줄을 쓴다. 아래는 여러 코드 패턴이 메모리를 건드리는 모습이다. 가로가 시간, 세로가 주소이고, 점 색은 1 KB짜리 작은 캐시에서 적중(초록)했는지 미스(빨강)였는지를 뜻한다.

주소를 쪼개 데이터를 찾는다

캐시는 "이 주소의 데이터가 내 안에 있나?"를 1 ns 안에 답해야 한다. 모든 칸을 하나씩 뒤질 시간은 없다. 그래서 주소를 세 조각으로 나눈다.

• 오프셋(Offset): 줄 안에서 몇 번째 바이트인가. 줄이 64 B면 아래 6비트.
• 인덱스(Index): 몇 번 세트(Set)를 볼 것인가. 이 비트들이 SRAM 배열의 행을 바로 고른다.
• 태그(Tag): 나머지 윗비트. 같은 세트로 오는 여러 주소를 구분하는 이름표로, 데이터와 함께 저장했다가 비교한다.

한 세트에 줄을 몇 개 둘 수 있는지가 연관도(Associativity, way 수)다. 1이면 직접 사상(Direct-mapped), 세트가 하나뿐이고 모든 줄이 어디든 들어갈 수 있으면 완전 연관(Fully associative), 그 사이가 A-way 집합 연관이다. A-way 캐시는 세트를 고른 뒤 A개의 태그를 동시에 비교한다. 비교기가 A개 필요하고 전력이 들지만, 같은 세트로 몰리는 주소끼리 서로 쫓아내는 일이 줄어든다.

연관도를 1에서 16으로 올리면 세트 수가 1/16로 줄고, 인덱스 비트 4개가 태그로 넘어간다. 줄 크기를 키우면 오프셋이 늘고 줄 수가 줄어 태그 부담이 작아진다. 이처럼 세 매개변수는 서로 얽혀 있다. 실제 L1은 4~8-way, L2는 8~16-way, 큰 L3·SLC는 12~16-way 정도가 흔하다. L1이 연관도를 무작정 키우지 못하는 이유는 태그 비교와 데이터 선택이 1클럭 남짓에 끝나야 하기 때문이다.

캐시 시뮬레이터와 미스의 세 가지 이유

이제 부품을 모아 캐시 하나를 돌려 보자. 미스는 세 종류로 나누면 원인과 처방이 분명해진다. Mark Hill이 정리한 3C 모델이다.

• 강제 미스(Compulsory): 그 줄을 처음 건드릴 때. 캐시가 무한히 커도 생긴다. 처방: 줄 크기 키우기, 프리페치.
• 용량 미스(Capacity): 쓰는 데이터 전체(작업 집합)가 캐시보다 커서 생기는 미스. 같은 크기의 완전 연관 캐시에서도 생기는 미스로 정의한다. 처방: 캐시 키우기, 작업 집합 줄이기(타일링).
• 충돌 미스(Conflict): 캐시 전체에는 자리가 있는데 하필 같은 세트로 몰려서 생기는 미스. 완전 연관이면 없었을 미스다. 처방: 연관도 올리기, 데이터 배치 바꾸기.

교체 정책

세트가 꽉 찼을 때 누구를 내보낼지 정하는 것이 교체 정책(Replacement policy)이다. LRU(Least recently used)는 가장 오래 쓰지 않은 줄을 내보낸다. 시간 지역성에 잘 맞지만, 정확한 LRU 순서를 저장하려면 way가 많을수록 비트가 많이 들어 실제로는 트리 의사 LRU 같은 근사를 쓴다. FIFO는 가장 먼저 들어온 줄을, 무작위는 아무 줄이나 내보낸다. 시뮬레이터에서 "배열 반복 훑기"의 작업 집합을 캐시보다 조금 크게(1.25배) 하고 LRU와 무작위를 비교해 보자. 놀랍게도 LRU가 0%로 망가진다. 순환 접근에서는 LRU가 언제나 "곧 다시 쓸 줄"을 골라 내보내기 때문이다. 최근 캐시가 RRIP 같은 적응형 정책을 쓰는 이유다.

쓰기는 어떻게 하나: 즉시 쓰기와 나중 쓰기

읽기는 캐시에 사본을 두기만 하면 되지만, 쓰기는 문제가 생긴다. 캐시의 값을 바꾸면 메모리의 원본과 달라진다. 해결책은 두 가지다.

• 즉시 쓰기(Write-through): 캐시와 메모리를 함께 고친다. 메모리가 늘 최신이라 단순하지만, 쓰기마다 아래 계층으로 트래픽이 나간다. 보통 쓰기 미스 때 줄을 가져오지 않는(no-write-allocate) 방식과 짝을 이룬다.
• 나중 쓰기(Write-back): 캐시만 고치고 그 줄에 더티 비트(Dirty bit)를 켠다. 줄이 쫓겨날 때 더티면 그때 한 번 메모리에 쓴다. 같은 줄에 여러 번 쓰면 트래픽이 크게 준다. 보통 쓰기 미스 때 줄을 가져오는(write-allocate) 방식과 짝을 이룬다.

아래는 4줄짜리 직접 사상 캐시 두 개다. 같은 명령을 두 캐시에 동시에 보내고 메모리 트래픽을 비교한다. A와 E, B와 F, C와 G, D와 H가 각각 같은 세트를 쓴다.

스마트폰 SoC의 L1 데이터 캐시와 L2·L3는 거의 모두 나중 쓰기다. 다만 L1과 L2 사이에는 쓰기 버퍼(Write buffer)를 두어, 코어가 쓰기가 끝나기를 기다리지 않고 다음 명령으로 넘어가게 한다. 이 버퍼가 메모리 순서를 미묘하게 바꾸는 이야기도 6장에서 다룬다.

여러 층을 합치면: 평균 메모리 접근 시간

캐시 계층의 성능은 평균 메모리 접근 시간(AMAT, Average memory access time) 하나로 요약할 수 있다. L1에서 적중하면 L1 지연만, 미스하면 그 아래 층에서 걸리는 시간이 더해진다. 아래 층에도 똑같은 식을 재귀적으로 적용한다.

AMAT 막대를 보면 왜 캐시 설계가 어려운지 알 수 있다. DRAM까지 가는 접근이 1%도 안 되는데 시간은 수십 %를 차지한다. 그래서 마지막 층의 미스율을 몇 %포인트 줄이는 일이 L1 지연을 1클럭 줄이는 것만큼, 혹은 그보다 더 중요할 수 있다. 실제 코어는 비순차 실행(4장)으로 미스를 기다리는 동안 다른 명령을 실행하고, 여러 미스를 동시에 보내서(메모리 수준 병렬성) 지연의 일부를 숨긴다. 그래도 숨길 수 없는 DRAM 지연이 많은 프로그램의 성능 한계가 된다.

표의 값은 2023~2025년 플래그십 스마트폰 칩의 공개 사양·분석 자료를 바탕으로 한 대략값이다. 예를 들어 Arm Cortex-X4(2023)는 L1 명령·데이터 각 64 KB, 코어 전용 L2 최대 2 MB를 두고, 클러스터 공유 L3는 DSU에서 최대 32 MB까지 구성할 수 있다. 회사마다 층을 나누는 방식이 달라서, 애플처럼 L2를 클러스터가 크게 공유하고 L3 없이 SLC로 가는 설계도 있다. SB-1은 L3 약 4.8 mm²와 SLC 약 5.3 mm²를 합쳐 다이의 10%가량을 캐시에 쓴다.

소프트웨어와 하드웨어가 손을 맞추면: 타일링과 프리페치

같은 계산이라도 데이터를 건드리는 순서만 바꾸면 미스가 몇 배 줄어든다. 가장 유명한 예가 행렬 곱셈의 타일링(Tiling, Blocking)이다. \(C = A \times B\)를 그대로 계산하면 B를 열 방향으로 훑어야 해서, 행렬이 캐시보다 크면 B의 줄이 재사용되기 전에 쫓겨난다. 행렬을 T×T 크기의 작은 타일로 나눠, 타일 세 개(A, B, C 하나씩)가 캐시에 들어가게 하면 한 번 가져온 데이터를 T번씩 재사용할 수 있다.

타일이 너무 작으면 재사용 횟수 T가 작아 이득이 적고, 너무 크면 타일 세 개가 캐시를 넘쳐 다시 미스가 늘어난다. 그래프의 바닥이 대략 점선 근처에 있는 것을 확인하자. 고성능 수학 라이브러리(BLAS)는 이런 타일링을 L1, L2, L3 각 층에 대해 겹겹이 하고, NPU 컴파일러도 같은 일을 온칩 SRAM 크기에 맞춰 한다(10장).

하드웨어가 미리 가져오기: 프리페처

소프트웨어를 고치지 않아도 하드웨어가 접근 패턴을 알아채고 데이터를 미리 가져올 수 있다. 이것이 프리페처(Prefetcher)다. 가장 기본적인 보폭 프리페처(Stride prefetcher)는 주소가 일정한 간격(보폭)으로 늘어나는 것을 두 번 연속 보면, 같은 간격으로 앞의 줄 몇 개를 미리 요청한다. 얼마나 멀리 앞서 요청할지가 프리페치 거리다.

프리페치 거리는 \(d \approx \lceil t_{\text{mem}} / t_{\text{line}} \rceil\)이면 충분하다. 여기서 \(t_{\text{line}}\)은 줄 하나를 소비하는 데 걸리는 계산 시간이다. 너무 멀리 앞서 가져오면 아직 쓰지 않은 데이터가 캐시를 차지해 쓸모 있는 줄을 쫓아내고(캐시 오염), 쓸모없는 요청이 DRAM 대역폭을 낭비한다. 실제 코어에는 보폭, 공간 패턴, 포인터 추적 등 여러 프리페처가 함께 있고, 정확도를 스스로 측정해 공격성을 조절한다.