지역성

왜 배우는가: 지역성은 캐시, 가상 메모리, 디스크 버퍼 등 현대 메모리 계층구조가 성능을 내는 근거다. 메모리 접근 패턴을 이해해야 성능 저하 원인을 찾고 설계를 바꿀 수 있다. 1교시 용어 문제와 4교시 응용 문제에 모두 반복해서 출제되는 기초 개념이다.

출제 이력: 제111회 4교시 6번, 제101회 1교시 8번

1. 한 줄 정의와 핵심 키워드

답안 첫 줄에 쓸 정의: 지역성은 프로세서가 짧은 시간 동안 특정 기억 위치 집합을 집중적으로 반복 참조하는 경향이다.

핵심 키워드

• 지역성(Locality of Reference)
• 시간 지역성(Temporal Locality)
• 공간 지역성(Spatial Locality)
• 순차 지역성(Sequential Locality)
• 메모리 계층구조(Memory Hierarchy)
• 캐시 적중률(Hit Rate)
• 작업 집합(Working Set)

2. 개념 풀이

쉬운 말로 풀면, 프로그램은 메모리를 골고루 쓰지 않는다. 방금 쓴 곳과 그 근처를 계속 다시 쓰는 편이다. 이 성질이 지역성이다.

정식 정의는 위와 같다. 지역성은 시간 지역성과 공간 지역성으로 나뉜다. 두 성질은 서로 독립적으로도, 함께도 나타난다.

시간 지역성(Temporal Locality)은 한 번 참조한 데이터나 명령어가 짧은 시간 안에 다시 참조되는 성질이다. 반복문의 제어 변수 i 가 대표 예다. 같은 변수가 매 반복마다 읽히고 쓰인다.

공간 지역성(Spatial Locality)은 참조한 주소와 가까운 주소의 데이터가 곧 참조되는 성질이다. 배열 원소는 메모리에 연속으로 배치되므로, 0번 요소부터 9번 요소까지 순서대로 접근하는 코드가 전형적인 예다.

순차 지역성(Sequential Locality)은 공간 지역성의 특수한 경우다. 데이터가 일차원으로 나란히 놓여 선형으로 접근되는 경우를 말한다. 명령어 인출이 대표적이다. 프로그램의 명령어는 대부분 주소 순서대로 실행되기 때문이다.

지역성이 성능으로 이어지는 원리는 다음과 같다. 캐시는 한 주소를 접근할 때 그 주소만 가져오지 않는다. 주변 주소를 포함한 캐시 라인 단위 블록을 함께 가져온다. 따라서 근처 주소를 곧 쓰는 프로그램은 두 번째 접근부터 캐시에서 해결된다. 반대로 흩어진 주소를 무작위로 접근하면 블록을 가져와도 쓰지 못하고 버려져 미스가 늘어난다.

3. 등장 배경과 필요성

프로세서의 연산 속도는 메모리 접근 속도보다 훨씬 빠르게 발전해 왔다. 이 격차 때문에 메모리 접근이 시스템 성능의 병목이 되었다. 모든 데이터를 빠른 기억장치로 만드는 것은 비용과 전력 면에서 현실적이지 않다.

메모리는 용량, 접근 속도, 비용 사이에 절충 관계가 있다. 이를 해결하는 구조가 메모리 계층구조(Memory Hierarchy)다. 계층을 아래로 내려갈수록 비트당 비용은 줄고 용량은 커지지만 접근 시간은 길어진다. 프로세서가 메모리에 접근하는 횟수는 위 계층일수록 줄어든다.

계층구조는 지역성이 있을 때만 성립한다. 프로그램은 루프와 서브루틴을 많이 포함한다. 루프에 진입하면 적은 수의 명령어 집단이 반복 참조된다. 자주 쓰이는 데이터를 작고 빠른 상위 계층에 두면 대부분의 접근이 상위에서 끝난다.