메모리 지역성으로 캐시 효율을 설계하는 방법

캐시는 프로그램의 참조 습관을 이용한다

프로그램은 메모리를 완전히 무작위로 읽지 않는다. 실행 중에는 일부 주소를 반복해서 사용하고, 이미 접근한 주소 주변을 이어서 읽으며, 명령어 역시 대체로 저장된 순서에 따라 실행된다. 이런 참조 경향을 메모리 지역성(Memory Locality)이라 한다.

지역성은 CPU와 메모리 사이의 속도 차이를 완화하는 캐시의 전제가 된다. 접근 시간을 줄이고 CPU 대기 시간을 낮추며, 캐시 적중률(Hit Ratio)과 평균 메모리 접근 시간(AMAT)을 개선하는 데 연결된다. 메모리 버스 대역폭을 어떻게 활용할지도 이 패턴에 영향을 받는다.

반복·인접·순차 실행에서 나타나는 지역성

시간적 지역성(Temporal Locality)은 최근에 읽거나 쓴 주소를 가까운 시점에 다시 참조할 가능성이 높다는 뜻이다. 반복문의 카운터 변수, 함수 안에서 여러 번 쓰는 지역 변수, 재귀 호출의 매개변수, 자주 호출되는 함수 코드는 이 성질을 보인다. LRU(Least Recently Used) 알고리즘도 이러한 재참조 가능성을 바탕으로 한다.

공간적 지역성(Spatial Locality)은 참조한 주소 가까이에 있는 주소를 이어서 사용할 가능성이 높다는 특성이다. 배열을 순서대로 읽거나 구조체와 객체의 연속된 멤버에 접근할 때 흔하다. 캐시가 Cache Line 단위로 데이터를 가져오고, 메모리 프리페칭(Prefetching)을 활용하는 배경이기도 하다. 문자열 처리와 버퍼 작업도 대표적인 사례다.

순차적 지역성(Sequential Locality)은 분기 없이 명령어가 순서대로 실행될 때 나타난다. 명령어 인출과 실행이 메모리에 저장된 순서를 따르므로 Instruction Cache 효율에 큰 영향을 준다. 공간적 지역성의 특수한 형태로 볼 수 있으며, 분기문이 적을수록 높아진다. 파이프라인 효율, Instruction Prefetch, Branch Prediction과도 맞물린다.

캐시 위치를 정하는 방식의 차이

직접 사상(Direct Mapping)에서는 메모리 블록이 캐시의 한 위치에만 들어갈 수 있다. 하드웨어 구현이 단순하고 검색이 빠르며 비용도 낮지만, 같은 위치를 두고 블록이 경쟁하면 Conflict Miss가 발생할 수 있다.

Cache Index = (Block Address) mod (Number of Cache Blocks)

완전 연관 사상(Fully Associative Mapping)은 메모리 블록을 캐시의 어느 위치에나 배치할 수 있게 한다. Conflict Miss를 최소화하고 캐시 활용률을 높일 수 있지만, 모든 캐시 라인을 병렬로 검색해야 한다. CAM(Content Addressable Memory)을 사용하므로 하드웨어 비용, 검색 시간, 전력 소모 측면의 부담이 커진다.

집합 연관 사상(Set Associative Mapping)은 두 방식 사이의 절충안이다. 각 세트에 N개의 캐시 라인을 두고, 세트 내부에서는 완전 연관 방식으로 동작한다. 2-way, 4-way, 8-way 구성이 일반적이며, 현대 프로세서에서 표준 방식으로 쓰인다.

Set Index = (Block Address) mod (Number of Sets)

이 방식은 적절한 적중률과 구현 복잡도 사이의 균형을 노린다. 직접 사상은 단순성과 빠른 Hit Time이 필요한 경우, 완전 연관 사상은 TLB 등 특수 용도, 집합 연관 사상은 L1/L2/L3 캐시에서 활용할 수 있다.

계층별 캐시 전략과 작업 집합

기억장치 계층은 속도와 용량, 비용 사이의 트레이드오프를 구성한다.

• Register는 CPU 내부에 있으며 < 1 cycle로 가장 빠르다.
• L1 Cache는 CPU 코어별 전용이며 1-3 cycles 수준이다.
• L2 Cache는 코어별 또는 공유 형태이고 10-20 cycles 수준이다.
• L3 Cache는 칩 레벨에서 공유되며 40-75 cycles 수준이다.
• Main Memory는 DRAM으로, 200-300 cycles가 걸린다.
• Secondary Storage는 SSD/HDD이며 수십만 cycles로 매우 느리다.

L1 Cache는 32KB - 64KB의 작은 용량, 2-way, 4-way의 낮은 Associativity, Instruction/Data를 나누는 Split Cache를 통해 Hit Time 최소화에 집중한다. L2/L3 Cache는 256KB - 수MB의 더 큰 용량과 8-way, 16-way의 높은 Associativity, Code/Data를 통합하는 Unified Cache로 Miss Rate 감소에 초점을 둔다.

Way Prediction은 Hit Time을 줄이고, Victim Cache는 Conflict Miss를 완화한다. Prefetching은 Miss Penalty를 줄이며, Non-blocking Cache는 병렬 처리를 지원한다.

작업 집합(Working Set)은 프로그램이 특정 시간 동안 집중적으로 참조하는 페이지의 집합이다. 이 집합이 물리 메모리에 모두 상주해야 Thrashing을 피할 수 있다. 지역성을 기준으로 작업 집합 크기를 예측하고, 페이지 교체 알고리즘과 결합해 관리한다. Working Set Window 크기 조정, 페이지 부재율 모니터링, 다중 프로그래밍 수준 제어, 메모리 할당량의 동적 조정이 여기에 포함된다.

적중률만으로는 부족한 성능 판단

Hit Ratio는 전체 메모리 참조 중 캐시에서 데이터를 찾은 비율이다.

Hit Ratio = (Cache Hits) / (Total Memory References)

값이 높을수록 캐시는 효과적으로 작동하며, 일반적으로 95% 이상을 목표로 한다. 지역성이 좋아질수록 Hit Ratio도 높아진다.

평균 메모리 접근 시간은 Hit Time, Miss Rate, Miss Penalty를 함께 반영한다.

AMAT = Hit Time + (Miss Rate × Miss Penalty)

계층형 캐시에서는 이 값을 재귀적으로 계산한다. 예를 들어 L1 Hit Time이 1 cycle, L1 Miss Rate가 5%, L2 Hit Time이 10 cycles, L2 Miss Rate가 20%, Main Memory Access Time이 200 cycles일 때 다음과 같이 계산한다.

AMAT = 1 + 0.05 × (10 + 0.20 × 200) = 1 + 0.05 × 50 = 3.5 cycles

지역성 자체는 동일 데이터를 다시 참조하기까지의 거리인 Reuse Distance, 시간 윈도우 안의 고유 페이지 수인 Working Set Size, 캐시 크기에 따른 Miss Rate 변화를 보는 Miss Rate Curve, Temporal Reuse Pattern의 재사용 간격 분포로 평가할 수 있다.

데이터 배치와 순회 방식에서 챙길 점

배열은 Row-major order에 맞춰 행 우선으로 순회하고, Cache Line 크기를 고려해 데이터 구조를 설계한다. 구조체 배열보다 배열 구조체(Array of Structures vs Structure of Arrays)를 검토하며, Loop Blocking/Tiling 기법도 적용 대상이 된다.

함수 호출에서는 Inline 함수로 호출 오버헤드를 낮추고, 자주 실행되는 Hot Path에 필요한 코드를 배치한다. Function Inlining은 Instruction Locality 향상에도 도움이 된다.

데이터 구조는 Cache-friendly한 레이아웃으로 구성해야 한다. 멀티스레드 환경에서는 False Sharing을 피하고, Data Alignment와 Padding을 통한 Cache Line 경계 조정도 함께 고려한다. 프로그램 설계 단계에서부터 지역성을 반영해야 하드웨어 자원을 효율적으로 활용할 수 있다.