CPU 캐시 구조와 메모리 접근 성능 설계

CPU가 메모리를 기다리지 않게 만드는 계층

CPU Clock은 3-5 GHz(0.2-0.33 ns/cycle)로 동작하지만, DRAM 접근에는 200-300 cycles(60-100 ns)가 걸린다. L1 Cache는 1-3 cycles(0.3-1 ns), L2 Cache는 10-20 cycles(3-7 ns), L3 Cache는 40-75 cycles(13-25 ns) 수준이다. SSD까지 내려가면 접근 시간은 0.1 ms, 수십만 cycles에 이른다.

이 간격 때문에 CPU는 메모리 접근을 기다리며 유휴 상태가 되고, 파이프라인 스톨과 처리량 저하가 발생한다. 흔히 Von Neumann Bottleneck이라 부르는 문제다. 캐시는 CPU와 메인 메모리 사이에 빠른 SRAM을 두고, 다시 필요할 가능성이 높은 데이터를 임시로 보관해 이 대기를 줄인다.

SRAM은 비트당 6개 트랜지스터로 이뤄진 flip-flop 구조이며 1-10 ns의 속도를 낸다. 전원이 공급되는 동안 데이터를 유지하므로 리프레시가 필요 없지만, 비용이 높고 대용량 제작이 어렵다. 반대로 DRAM은 비트당 1개 트랜지스터와 커패시터를 사용한다. 50-100 ns로 더 느리고 주기적 리프레시가 필요하지만, 저비용으로 대용량을 만들 수 있어 메인 메모리에 적합하다.

⤢✕

재사용과 인접 접근을 활용하는 방식

캐시는 프로그램의 메모리 참조가 완전히 무작위가 아니라는 전제에서 작동한다. 시간적 지역성은 최근 참조한 메모리를 가까운 미래에 다시 참조하는 성질이다. 반복문의 변수와 스택 지역 변수가 대표적이며, LRU 교체 정책의 기반이 된다.

for (int i = 0; i < 1000; i++) {
    sum += array[i];  // sum 변수가 반복적으로 참조됨
}

공간적 지역성은 접근한 주소의 인접 주소를 곧 참조하는 성질이다. 배열 순차 접근과 구조체 멤버 접근이 여기에 해당한다. 캐시가 데이터를 캐시 라인 단위로 가져오고, prefetching을 활용하는 근거도 공간적 지역성이다.

for (int i = 0; i < 1000; i++) {
    sum += array[i];  // 인접한 배열 원소를 순차적으로 참조
}

주소를 캐시 라인으로 해석하는 법

캐시 라인은 보통 4 Words(16 bytes), 8 Words(32 bytes), 16 Words(64 bytes), 32 Words(128 bytes) 크기로 구성된다. 16 Words(64 bytes)가 가장 일반적이며, 현대 프로세서는 주로 64B를 사용한다.

라인이 작으면 Miss Penalty는 줄지만 Miss Rate가 늘 수 있다. 반대로 큰 라인은 공간적 지역성을 더 활용할 수 있지만 Miss Penalty가 커진다. 적절한 크기는 워크로드에 따라 달라진다.

주소는 Tag, Index, Offset으로 나뉜다. Tag는 라인에 든 데이터가 어느 메모리 블록인지 식별하고 비교 회로가 Hit/Miss를 판단하는 데 쓴다. Index는 캐시의 위치 또는 세트를 가리키며, Offset은 라인 안의 바이트 위치를 선택한다. 라인 크기가 64B라면 offset은 6비트다(2^6 = 64). Valid Bit는 유효 데이터 여부를 나타내고, Dirty Bit는 Write Back에서 수정된 데이터를 메모리에 써야 하는지를 표시한다.

⤢✕

배치 정책이 만드는 충돌과 비용

Direct Mapped Cache에서는 각 메모리 블록이 캐시의 한 위치에만 들어간다. Cache Index = (Block Address) mod (Number of Cache Lines)로 위치를 정하므로 하드웨어가 단순하고 비교가 1회여서 Hit Time이 가장 빠르다. 비용과 전력 소모도 낮다.

대신 같은 인덱스에 매핑되는 블록이 경쟁하면서 Conflict Miss가 발생한다. 예를 들어 16KB 캐시에 64B 라인이 있으면 256개 라인이 생긴다. 주소 0x0000, 0x1000, 0x2000은 모두 라인 0에 매핑되며, 번갈아 접근하면 Thrashing으로 계속 Miss가 날 수 있다.

Fully Associative Cache는 블록을 어느 위치에나 둘 수 있고, 모든 Tag를 병렬 비교한다. CAM(Content Addressable Memory)을 사용해 Conflict Miss를 완전히 없애고 높은 Hit Rate를 얻지만, 모든 Tag 비교가 필요해 비용·전력 소모·Hit Time이 커진다. 확장성이 제한돼 TLB나 매우 작은 특수 캐시에 주로 사용한다.

Set Associative Cache는 캐시를 여러 세트로 나누고, 세트 내부에서는 Fully Associative 방식으로 동작한다. Set Index = (Block Address) mod (Number of Sets)다. 2-way, 4-way, 8-way 구성이 일반적이고 L3 Cache에는 16-way도 사용된다. 2-way는 Direct Mapped보다 Conflict Miss가 절반이며, 4-way는 대부분의 경우 충분하다. 8-way 이상에서는 추가 효과가 미미하다. 이 방식은 속도와 유연성 사이의 실용적인 균형점으로 L1/L2/L3 D-Cache에 널리 쓰인다.

캐시가 찼을 때 남길 데이터를 고르는 기준

Random Replacement는 교체 대상을 무작위로 정한다. 난수 생성기만 필요해 구현이 단순하고, 예측은 어렵지만 평균적으로 나쁘지 않으며 Thrashing 같은 특수 패턴에 강하다. 반면 지역성을 활용하지 못해 최적 성능과는 거리가 있다.

Round Robin(FIFO)은 포인터나 카운터로 다음 교체 대상을 추적하며 순환한다. 구현은 간단하고 공정하지만 성능은 중간 수준이다. 메모리 페이지 교체의 FIFO와 유사하며 Aging 효과가 있어 LRU의 근사치로 볼 수 있다.

LRU(Least Recently Used)는 가장 오래 사용되지 않은 라인을 내보내 시간적 지역성을 가장 적극적으로 반영한다. 2-way LRU는 MRU(Most Recently Used)를 1로 표시하는 1비트로 구현할 수 있다. 4-way의 완전 LRU는 각 라인에 2비트 카운터(0-3)가 필요하고, Pseudo LRU는 트리 기반으로 3비트를 사용한다. 8-way 이상에서는 완전 LRU가 비현실적이어서 Pseudo LRU, NRU(Not Recently Used) 같은 근사 기법을 쓴다.

Pseudo-LRU는 트리 구조의 선택 비트로 최근 사용하지 않은 라인을 추적한다. 각 노드는 왼쪽·오른쪽 선택 비트를 갖고, 접근하면 경로의 비트를 갱신한다. 교체할 때는 비트를 따라 리프 노드를 선택한다. 8-way에서는 7비트만 필요하며, 완전 LRU는 24비트가 필요하다. Hit Rate는 LRU와 거의 비슷하면서 하드웨어 비용을 낮출 수 있어 L2/L3 Cache에서 일반적이다.

쓰기 경로의 선택

Write Through는 캐시와 메모리에 동시에 쓴다. 두 저장소의 데이터가 항상 일치하고 구현과 복구가 단순하지만, 메모리 쓰기가 많아지고 버스 트래픽과 전력 소모가 늘어난다. Write Buffer로 쓰기 요청을 버퍼링해 CPU 블로킹을 막거나, Write Combining으로 여러 쓰기를 합쳐 성능을 개선한다.

Write Back은 먼저 캐시에만 기록하고 Dirty Bit를 설정한다. 라인을 교체할 때만 메모리에 쓰므로 수정되지 않은 라인은 메모리 쓰기가 필요 없다. 메모리 접근과 버스 트래픽을 줄여 쓰기 성능과 전력 효율이 좋지만, 캐시와 메모리가 일시적으로 불일치할 수 있어 Dirty Bit 및 멀티코어 일관성 처리가 필요하다. 대부분의 프로세서는 L1/L2/L3에서 Write Back을 사용한다.

Write Miss에 대한 선택도 별개다. Write Allocate(Fetch on Write)는 해당 블록을 캐시로 가져온 뒤 쓰며, Write Back과 함께 사용해 공간적 지역성을 활용한다. No-Write Allocate(Write Around)는 캐시를 거치지 않고 메모리에 직접 쓰며, 한 번 쓰고 다시 읽지 않는 경우에 유리하고 Write Through와 함께 사용한다. 일반적인 조합은 Write Back + Write Allocate와 Write Through + No-Write Allocate다.

적중률만으로는 부족한 성능 측정

Hit Rate는 Hits / (Hits + Misses)로, 캐시에서 데이터를 찾은 비율이다. 일반적으로 90-99%를 목표로 한다. Hit Time은 Tag 비교와 데이터 읽기에 걸리는 시간으로 L1은 1-3 cycles, L2는 10-20 cycles, L3는 40-75 cycles다. Miss Penalty는 메모리 접근 시간과 라인 전송 시간을 합친 값이며 일반적으로 200-300 cycles이고, 라인이 커질수록 증가한다.

AMAT(Average Memory Access Time)는 Hit Time, Miss Rate, Miss Penalty를 함께 반영한다.

AMAT = Hit Time + Miss Rate × Miss Penalty

L1 Hit Time이 2 cycles, L1 Miss Rate가 5%, L2 Hit Time이 15 cycles, L2 Miss Rate가 20%, Memory Access가 200 cycles인 경우는 다음과 같다.

L2 AMAT = 15 + 0.20 × 200 = 55 cycles
L1 AMAT = 2 + 0.05 × 55 = 4.75 cycles

계층형 캐시에서는 각 레벨의 AMAT을 재귀적으로 계산하며, 하위 레벨의 Miss Penalty는 상위 레벨의 AMAT이 된다.

Misses Per Instruction(MPI)은 명령어당 캐시 미스 횟수다. MPI = (Cache Misses) / (Instructions Executed)이며, CPI_total = CPI_ideal + MPI × Miss Penalty 관계로 CPI에 직접 영향을 준다.

L1의 분리와 상위 계층의 통합

Split Cache는 Instruction Cache(I-Cache)와 Data Cache(D-Cache)를 분리하는 방식이다. L1에서 일반적이며 각각 독립적인 포트를 둔다. 명령어 fetch와 데이터 read/write를 동시에 수행해 파이프라인 충돌을 줄이고, 명령어와 데이터의 특성에 맞게 최적화할 수 있다. I-Cache는 Read-Only로 단순화할 수 있고 Direct Mapped가 적합하며, 데이터 접근 패턴이 다양한 D-Cache에는 Set Associative가 적합하다. 다만 전체 캐시 크기가 고정돼 있으면 활용률이 낮아질 수 있고 하드웨어 복잡도가 높아진다.

Unified Cache는 명령어와 데이터를 하나의 캐시에 저장한다. L2와 L3에서 일반적이며, 명령어·데이터 비율에 맞춰 공간을 동적으로 할당할 수 있다. 공간 활용률이 높고 구현은 상대적으로 단순하지만, 단일 포트에서는 동시 접근 충돌이 생길 수 있다.

현대 프로세서는 L1에서 I-Cache 32KB와 D-Cache 32KB를 분리하고, L2는 256KB - 1MB의 Unified Cache, L3는 8MB - 64MB의 Unified Cache로 구성하는 형태를 사용한다.

⤢✕

멀티코어에서 캐시 데이터가 어긋나는 순간

멀티코어 시스템에서는 각 코어가 Private L1/L2 Cache를 보유하고, 같은 메모리 주소가 여러 캐시에 존재할 수 있다. 한 코어가 데이터를 수정하면 다른 코어의 캐시 데이터와 불일치할 수 있으므로 일관성 프로토콜이 필요하다.

MESI는 캐시 라인을 Modified, Exclusive, Shared, Invalid 상태로 관리한다.

• Modified(M): 수정됐고 이 캐시만 보유하며 Dirty 상태다.
• Exclusive(E): 이 캐시만 보유한 Clean 상태다.
• Shared(S): 여러 캐시가 보유한 Read-Only 상태다.
• Invalid(I): 유효하지 않은 데이터다.

Read Hit에서는 상태를 유지한다. Write Hit에서는 E/M 상태로 전이하고 다른 캐시는 I가 된다. Read Miss에서는 버스에서 데이터를 가져와 S 또는 E 상태가 되며, Write Miss에서는 M 상태로 전이하면서 다른 캐시를 무효화한다.