🖥️ 개요
컴퓨터 과학에서 참조 지역성(Reference Locality; 지역성의 원리)은 프로세서가 짧은 시간 동안 반복적으로 동일한 메모리 위치 집합에 액세스하는 것이다.
지역성은 컴퓨터 시스템에서 발생하는 예측 가능한 동작 유형이다. 참조 지역성이 강한 시스템은 성능 최적화를 위해 캐싱, 메모리 프리페칭, 고급 분기 예측기 등의 기술을 활용한다.
🖥️ 지역성(Locality)의 유형
지역성은 '시간적 지역성'과 '공간적 지역성' 이 두 가지 기본 유형이 있다.
-
시간적 지역성(Temporal locality): 비교적 짧은 시간 동안 특정 데이터나 리소스를 재사용하는 것을 의미하며, 한 시점에서 특정 메모리 위치가 참조된 경우, 그 위치가 가까운 미래에 다시 참조될 가능성이 높다.
동일한 메모리 위치에 대한 연속 참조 사이에 시간적 근접성이 있다. 이 경우, 참조된 데이터의 사본을 더 빠른 메모리 저장소에 저장하여 이후 참조의 대기 시간을 줄이기 위해 노력하는 것이 일반적이다.
시간적 지역성은 공간적 지역성의 특수한 경우로, 즉 예상 위치가 현재 위치와 동일한 경우이다. -
공간적 지역성(Spatial locality): 상대적으로 가까운 저장 위치 내의 데이터 요소를 사용하는 것을 의미한다.
특정 시간에 특정 저장 위치가 참조되면 가까운 메모리 위치가 가까운 미래에 참조될 가능성이 높다. 이 경우, 현재 참조 주변의 영역의 크기와 모양을 추측하여 이후 참조를 위한 더 빠른 액세스를 준비하는 것이 일반적이다. -
메모리 지역성(또는 데이터 지역성): 메모리에 명시적으로 관련된 공간적 지역성이다. -
분기 지역성(Branch locality): 공간-시간 좌표 공간에서 예상 경로의 일부에 가능한 대안이 거의 없는 경우 발생한다. 이는 명령 루프가 간단한 구조를 가지거나 조건 분기 명령의 가능한 결과가 일부 가능성의 작은 집합으로 제한되는 경우에 해당한다.
분기 지역성은 일반적으로 공간 지역성이 아니며, 몇 가지 가능성은 서로 멀리 떨어져 있을 수 있다. -
등거리 지역성(Equidistant locality): 공간 지역성과 분기 지역성의 중간 지점이다. 등거리 패턴으로 위치에 액세스하는 루프를 생각해보면, 공간-시간 좌표 공간에서의 경로가 점선이다. 이 경우, 단순한 선형 함수가 가까운 미래에 액세스될 위치를 예측할 수 있다.
시간적 및 공간적 지역성을 활용하기 위해, 이러한 지역성이 자주 발생하는 경우 대부분의 정보 저장 시스템이 계층적이다. 등거리 지역성은 일반적으로 프로세서의 다양한 복잡한 증가 명령에 의해 지원된다.
분기 지역성의 경우, 현대적인 프로세서에는 정교한 분기 예측기가 있으며, 이 예측을 기반으로 프로세서의 메모리 관리자가 가능한 대안의 데이터를 수집하고 전처리를 시도한다.
🖥️ 지역성(Locality)의 장점
지역성은 보통 일맥상통하지만, 달성할 목표 또는 받아들여야 하는 상황에 따라 여러 가지 이점이 존재한다.
-
예측 가능성(Predictability): 지역성은 컴퓨터 시스템에서의 예측 가능한 동작의 일종에 불과하다. -
프로그램의 구조(Structure of the program): 지역성은 주로 결정 가능한 문제를 처리하기 위해 컴퓨터 프로그램이 작성된 방식 때문에 자주 발생한다.
일반적으로 관련된 데이터는 저장 공간 내의 인접한 위치에 저장된다. 컴퓨팅에서 일반적인 패턴 중 하나는 여러 항목을 한 번에 하나씩 처리하는 것이다.
이는 많은 처리가 수행될 경우 단일 항목이 한 번 이상 액세스될 것이므로 시간적 참조 지역성으로 이어진다. 또한, 다음 항목으로 이동하는 것은 다음 항목이 읽힐 것이라는 의미이므로, 메모리 위치가 일반적으로 일괄적으로 읽힌다. 따라서 공간적 참조 지역성이 발생한다. -
선형 데이터 구조(Linear data structures): 지역성은 종종 코드에 루프가 포함되어 인덱스를 사용하여 배열이나 다른 데이터 구조를 참조하는 경우 발생한다.
순차 지역성은 관련 데이터 요소가 순차적으로 배열되어 액세스될 때 발생하는 공간적 참조 지역성의 특수한 경우이다. 예를 들어, 일차원 배열의 요소를 기본 주소부터 가장 높은 요소까지 단순히 순회하는 것은 메모리 내 배열의 순차 지역성을 활용한다.
등거리 지역성은 선형적인 트래버스가 상응하는 각 구조의 요소 대신 각 구조 전체를 액세스하는 인접한 데이터 구조의 넓은 영역을 통해 이루어질 때 발생한다. 이는 행렬이 행의 순차적 행렬로 표현되고 행렬의 단일 열에 액세스해야 하는 경우이다. -
메모리 계층 구조의 효율성(Efficiency of memory hierarchy use): 랜덤 액세스 메모리는 프로그래머에게 언제 어디서든 읽거나 쓸 수 있는 능력을 제공하지만, 실제로는 캐시의 효율에 따라 대기 시간과 처리량이 영향을 받는다.
참조 지역성을 증가시켜 캐시의 효율을 높이는 것이 중요한데, 참조 지역성이 부족하면 캐시 충돌과 캐시 오염이 발생하기 때문에 이를 피하기 위해 참조 지역성이 낮은 데이터 요소는 캐시에서 우회될 수 있다.
🖥️ 사용법
일반적으로, 참조의 상당 부분이 클러스터로 집계되고 클러스터 시스템의 형태를 잘 예측할 수 있다면, 이를 활용하여 성능을 최적화할 수 있다.
지역성을 활용하기 위한 최적화 기술은 여러 가지가 있으며, 주요 기술은 다음과 같다.
참조의 지역성 증가(일반적으로 소프트웨어 측면)
- 소프트웨어 측면에서 참조의 지역성을 증가시키는 것이다.참조의 지역성 활용(일반적으로 하드웨어 측면)
- 시간적 및 공간적 지역성은 계층적 저장 하드웨어에 의해 활용될 수 있으며, 등거리 지역성은 프로세서의 적절히 특화된 명령어에 의해 활용될 수 있다. 이 가능성은 하드웨어뿐만 아니라 소프트웨어도 책임지며, 해당 특화된 명령어를 호출하는 이진 프로그램을 컴파일하는 데 적합한 구조인지 여부에 따라 달라진다.
분기 지역성은 더 복잡한 가능성이므로 더 많은 개발 노력이 필요하지만, 이러한 종류의 지역성에서는 나머지 지역성보다 훨씬 큰 탐색 여지가 있다.
🖥️ 공간적 및 시간적 지역성 사용
- 계층적 메모리
계층적 메모리는 공간적, 시간적 지역성의 이점을 활용하는 하드웨어 최적화이다. 페이징은 시간적, 공간적 지역성에서 이점을 얻는다.
임시 지역성을 활용하는 대표적인 예로 '캐시'가 있다. 캐시는 최근에 참조된 데이터와 그 주변 데이터를 유지하는데 사용된다. 이는 더 빠르지만 더 작은 메모리 공간에 저장되어 성능을 향상시킬 수 있다.
캐시의 데이터 요소는 주 메모리에서 공간적으로 가까운 데이터 요소와 일치하지 않아도 된다. 그러나 데이터 요소는 한 번에 한 캐시 라인씩 캐시로 가져온다. 이는 공간적 지역성이 여전히 중요하다는 것을 의미한다. 다시 말해, 하나의 요소가 참조되면 인접한 여러 요소도 캐시로 가져오게 된다.
마지막으로, 시간적 지역성은 가장 낮은 수준에서 역할을 한다. 매우 최근에 참조된 결과는 기계 레지스터에 저장될 수 있기 때문이다. 일부 프로그래밍 언어(예: C)를 사용하면 프로그래머가 특정 변수를 레지스터에 보관하도록 제안할 수 있다.
출처 :
https://en.wikipedia.org/wiki/Locality_of_reference
https://www.geeksforgeeks.org/locality-of-reference-and-cache-operation-in-cache-memory/
