캐시의 시간 지역성과 공간 지역성

Summary: 캐시는 빠른 장치와 느린 장치 사이의 속도 차로 발생하는 병목을 완화하기 위한 임시 저장소이며, 그 효율은 CPU가 앞으로 참조할 데이터를 얼마나 예측할 수 있는지에 달려 있다. 이 예측의 근거가 데이터 지역성(Locality)이며, 지역성은 최근 사용한 데이터의 재사용에 주목하는 시간 지역성과 인접 데이터의 연속 사용에 주목하는 공간 지역성으로 구분된다. 이 글은 두 지역성의 정의·판단 방식·선택 기준과, 프로세서가 빨라질수록 캐시의 중요성이 오히려 커지는 이유를 정리한다.

캐시란?

캐시 흐름

캐시(Cache)는 자주 사용하는 데이터나 값을 미리 복사해 두는 임시 저장소다. 도입 목적은 접근 속도가 빠른 장치와 느린 장치 사이의 속도 차에서 발생하는 병목 현상을 줄이는 데 있다.

 

캐시가 이득을 주는 상황은 제한적이며, 다음 조건에서 효과가 크다.

• 원본 데이터보다 빠르게 접근할 수 있을 때
• 같은 데이터에 반복적으로 접근할 때
• 잘 변하지 않는 데이터를 주로 사용할 때

캐시와 주 기억장치 사이에서 정보를 옮기는 규칙을 매핑(Mapping)이라 한다. 매핑 방식은 블록을 어느 위치에 적재할 수 있는지(적재 자유도)와 적중 여부를 판별하는 비용 사이의 절충으로 구분된다.

 

매핑 방식 적재 규칙 특성

직접 매핑	주 기억장치의 블록을 지정된 한 개의 캐시 라인에만 대응시킨다	구조가 간단하고 구현 비용이 적으나, 캐시 적중률이 낮아질 수 있다
연관 매핑	데이터를 캐시의 빈자리 어디에나 저장하고, 모든 태그를 병렬로 검사한다	적재 자유도가 높지만 구조가 복잡하고 비용이 높다
집합 연관 매핑	정해진 블록의 집합 내라면 어디든 매핑한다	직접 매핑과 연관 매핑의 장점을 절충한 방식이다

 

캐시의 지역성이란?

캐시가 제 역할을 하려면 CPU가 앞으로 어떤 데이터를 참조할지 어느 정도 예측할 수 있어야 한다. 캐시 용량은 제한적이므로, 성능은 그 제한된 공간에 "이후에 실제로 사용될" 데이터가 얼마나 많이 들어 있는지에 따라 결정된다. 즉 캐시의 유효성은 본질적으로 예측의 정확도 문제다.

 

이 예측의 근거가 데이터 지역성(Locality)이다. 지역성이란 프로그램이 코드나 데이터를 전 영역에 균등하게 접근하지 않고, 특정 시간 동안 특정 영역의 데이터나 명령어를 집중적으로 참조하는 경향을 말한다.

 

지역성은 캐시 적중률을 끌어올리는 핵심 원리다. 프로그램이 최근 사용한 데이터나 그 주변 데이터를 다시 사용할 가능성이 높다는 경험적 특성을 전제로, 캐시는 해당 데이터를 미리 보관해 CPU가 빠르게 접근하도록 한다. 지역성은 다시 시간 지역성과 공간 지역성으로 나뉜다.

 

시간 지역성이란?

시간 지역성은 최근에 사용된 데이터나 명령어가 가까운 미래에 다시 사용될 가능성이 높다는 특성이다. 핵심은 동일한 메모리 주소가 짧은 시간 안에 반복적으로 참조된다는 점에 있다.

 

전형적인 사례는 반복문 안에서 동일한 변수(sum, i, count 등)를 계속 읽고 쓰는 경우다.

int sum = 0;

for (int i = 0; i < 1000; i++) {
    sum += i; // sum을 계속 불러옴 => 같은 메모리 주소를 호출함
}

 

위 코드에서 sum은 반복문이 도는 동안 매 반복마다 접근된다. 이 변수를 매번 DRAM에서 가져온다면 접근 지연이 누적되어 비효율적이다. 한 번 캐시에 적재된 sum을 반복해서 재사용하면 그만큼 메모리 접근 시간이 줄어든다. 시간 지역성은 이처럼 같은 데이터에 대한 반복 접근에서 이득이 발생한다.

 

시간 지역성의 판단 방식

캐시는 제한된 공간만 가지므로 모든 데이터를 보관할 수 없다. 따라서 어떤 데이터를 남기고 어떤 데이터를 내보낼지(교체) 결정해야 하며, 이때 시간 지역성이 판단 기준이 된다.

판단	관점 의미
최근에 사용되었는가	최근 사용된 데이터는 다시 사용될 가능성이 높다고 본다
반복적으로 접근되는가	같은 데이터가 반복적으로 사용되면 캐시에 유지할 가치가 크다
오래 사용되지 않았는가	오랫동안 접근되지 않은 데이터는 사용 가능성이 낮다고 보고 교체 대상으로 삼는다

 

이 기준은 교체 정책과 직접 연결된다. 자주 언급되는 LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 데이터를 먼저 제거하는 방식으로, "최근 사용 여부"를 중심에 둔다는 점에서 시간 지역성의 직접적인 구현에 해당한다. 다만 실제 CPU 캐시가 완전한 LRU를 그대로 구현하지는 않는다는 점에 유의해야 한다. 완전 LRU는 구현 비용이 크기 때문에, 하드웨어는 이를 근사하는 방식이나 다른 교체 정책으로 대체하기도 한다. 그럼에도 "최근 사용 여부를 중요하게 본다"는 기본 발상은 동일하게 유지된다. 정리하면서 가장 구분이 필요했던 지점도 여기였다. LRU는 시간 지역성의 "개념적 모델"로 두되, 실제 하드웨어의 교체 구현과 동일시하지는 않아야 한다.

 

공간 지역성이란?

공간 지역성은 기억 장치 내에서 인접하여 저장된 데이터들이 연속적으로 사용될 가능성이 높다는 특성이다. 시간 지역성이 "같은 주소"의 반복에 주목한다면, 공간 지역성은 "인접한 주소"의 연쇄 접근에 주목한다.

 

배열을 순차적으로 읽고 쓰는 코드가 대표적이다.

int arr[1000];

for (int i = 0; i < 1000; i++) {
    arr[i] = arr[i] + 1; // 다음 배열의 값을 가져옴 => 연속적 메모리 주소를 호출함
}

 

위 코드는 arr[0], arr[1], arr[2]처럼 연속된 주소를 순서대로 접근한다. CPU가 arr[0] 하나만 가져오는 대신 그 주변 데이터까지 한 번에 적재해 두면, 뒤이은 arr[1], arr[2] 접근에서 캐시 히트가 발생할 가능성이 커진다. 공간 지역성의 이점은 이처럼 인접 데이터를 묶어서 미리 가져오는 데서 나온다.

공간 지역성의 판단 방식

판단	관점 의미
현재 접근한 주소 주변인가	현재 주소 근처의 데이터는 곧 접근될 가능성이 높다
연속된 메모리 접근인가	배열 순회처럼 주소가 순차적으로 증가하면 캐시 효율이 높다
한 번에 블록 단위로 가져올 가치가 있는가	단일 데이터만이 아니라 주변 데이터까지 함께 캐시에 적재한다

 

공간 지역성은 배열, 구조체 배열, 문자열 처리, 버퍼 처리처럼 데이터가 메모리에 연속적으로 배치되는 경우에 특히 효과적이다. 반대로 연결 리스트처럼 메모리 주소가 흩어져 있는 자료구조는 공간 지역성이 낮다. 다음 노드가 메모리상 멀리 떨어져 있을 수 있어 인접 데이터 적재의 이점을 살리기 어렵고, 그만큼 캐시 효율이 떨어진다. 즉 공간 지역성은 자료구조의 메모리 배치 방식에 크게 좌우된다.

 

그럼 시간 지역성과 공간 지역성 중 어떤걸 선택해야 되는가?

두 지역성은 서로 다른 접근 패턴을 가정하므로, 어느 쪽을 우선 최적화할지는 워크로드의 지배적인 접근 패턴에 따라 결정된다. 선택의 기준은 "같은 데이터를 반복해서 쓰는가"와 "연속된 데이터를 순서대로 훑는가"라는 두 질문으로 요약된다.

시간 지역성을 우선해야 하는 경우

• 핵심 활용처: 반복문, 변수 재사용, 함수 호출 등.
• 선택 기준: 동일한 데이터나 명령어를 빈번하게 읽고 쓰는 로직이 많다면 시간 지역성을 우선으로 최적화한다.
• 근거: 이런 패턴에서는 같은 주소가 짧은 시간 안에 반복 접근된다. 따라서 한 번 적재한 데이터를 오래 유지하는 것이 이득이며, 앞서 본 판단 관점(최근성·반복성)과 LRU 계열 교체 정책이 그대로 효과를 낸다. sum 누적 반복문이 이 경우의 대표 사례다.

공간 지역성을 우선해야 하는 경우

• 핵심 활용처: 배열(Array) 순차 탐색, 연속된 파일 읽기 등.
• 선택 기준: 데이터가 메모리에 연속적으로 저장되어 있고 순차적으로 접근하는 패턴이 주를 이룬다면 공간 지역성을 극대화한다.
• 근거: 이런 패턴에서는 인접 주소가 잇따라 사용되므로, 주변 데이터를 블록 단위로 미리 적재해 두는 전략이 적중률을 높인다. 단, 연결 리스트처럼 주소가 흩어진 자료구조에서는 이 전략의 이점이 약해진다는 점을 함께 고려해야 한다. arr 순차 갱신 반복문이 이 경우의 대표 사례다.

비교 정리

구분	시간 지역성	공간 지역성
정의의 요지	최근 사용한 데이터/명령어가 곧 다시 사용됨	인접하여 저장된 데이터가 연속적으로 사용됨
주목 대상	같은 메모리 주소의 반복 접근	인접 메모리 주소의 연쇄 접근
핵심 활용처	반복문, 변수 재사용, 함수 호출	배열 순차 탐색, 연속된 파일 읽기
선택 기준	동일 데이터/명령어를 빈번히 읽고 쓰는 로직이 많을 때	데이터가 연속 저장·순차 접근되는 패턴이 주를 이룰 때
대표 코드	sum 누적 반복문	arr 순차 갱신 반복문
관련 판단 관점	최근성·반복성(LRU 계열 교체와 연결)	주소 인접성·연속성·블록 단위 적재
불리한 경우	루프(반복문)가 없는 코드, 순차적 데이터 탐색	연결 리스트처럼 주소가 흩어진 자료구조

 

선택 기준이 "로직이 많다면", "패턴이 주를 이룬다면"이라는 표현을 전제로 한다는 점에 주의할 필요가 있다. 이는 두 지역성을 배타적으로 고르는 문제라기보다, 지배적인 접근 패턴을 식별해 최적화의 우선순위를 정하는 문제에 가깝다. 처음에는 "둘 중 하나를 선택한다"는 표현 때문에 양자택일로 읽었으나, 소스의 선택 기준을 다시 보면 결국 워크로드의 접근 패턴을 먼저 분석하라는 요구로 정리된다.

 

그럼 우린 왜 아직도 캐시를 사용하는가?

프로세서의 연산 성능은 크게 향상되었지만, CPU 내부 연산 속도와 DRAM 접근 속도 사이에는 여전히 큰 간극이 있다. CPU가 명령어를 아무리 빠르게 처리해도 필요한 데이터가 늦게 도착하면 CPU는 그 시간 동안 대기할 수밖에 없다.

 

이 현상을 메모리 병목 또는 메모리 월(memory wall) 문제라고 한다. 프로그램 성능이 CPU 연산 능력만으로 결정되지 않고, 메모리 접근 지연 시간과 대역폭에 의해 제한되는 상황을 가리킨다. 캐시는 이 간극을 메우는 중간 계층으로서 다음과 같은 효과를 낸다.

이유	설명
CPU와 DRAM의 속도 차이 완화	CPU가 매번 DRAM에 접근하지 않도록 중간에 빠른 저장 공간을 둔다
평균 메모리 접근 시간 감소	자주 쓰는 데이터를 캐시에 보관하여 접근 시간을 줄인다
반복문 성능 향상	반복적으로 쓰는 변수와 명령어를 캐시에 유지한다(시간 지역성)
배열·버퍼 처리 성능 향상	연속된 데이터를 캐시 라인 단위로 가져온다(공간 지역성)
전력 효율 개선	먼 메모리 계층까지 접근하는 횟수를 줄여 불필요한 데이터 이동 비용을 낮춘다
멀티코어 환경 대응	여러 코어가 데이터를 효율적으로 공유하고 일관성을 유지하기 위해 캐시 계층이 필요하다

 

주목할 점은 프로세서가 빨라질수록 캐시가 오히려 더 중요해진다는 것이다. CPU가 빠를수록 데이터를 기다리는 대기 시간이 전체 성능에서 차지하는 비중이 커지기 때문이다. 결국 캐시는 CPU의 대기 시간을 줄여 실제 성능을 끌어올리는 핵심 장치이며, 그 전제가 바로 시간 지역성과 공간 지역성이다.