[운영체제] 참조의 지역성(Locality of Reference)이란? 캐시의 지역성이란? 행렬 곱셈 최적화 방법

참조의 지역성(Locality of Reference)

주기억장치와 메모리는 속도 차이가 크다. 이러한 속도의 차이를 극복할 수 있는 게 캐시 메모리이다. 이 캐시 메모리는 주기억장치와 메모리 사이에 위치하며 속도 차이에 따른 병목현상을 줄여준다.

 

그런데 이 캐시 메모리의 효율을 높이려면 캐시 메모리에 어떤 정보가 들어있냐가 중요하다. 어떤 프로그램을 실행할 때  필요한 정보를 캐시 메모리에서 찾는 캐시 적중율(hit-rate)을 높일 수 있기 때문이다.

 

그런데 이러한 캐시 적중율을 높일 수 있는 원리가 있는데, 그것이 바로 참조의 지역성이다. 참조의 지역성은 캐시의 지역성이라고도 불리는데, 정확히는 참조의 지역성이 맞다.

 

참조의 지역성이란 컴퓨터 프로그램이 일정 기간 동안 특정한 메모리 위치 집합에 접근하는 경향이 있는 현상을 뜻한다. 쉽게 말해 참조의 지역성은 주소가 서로 가까운 명령어에 접근하는 경향을 나타낸다. 

 

이러한 참조의 지역성은 크게 공간적 지역성, 시간적 지역성 두 가지로 구분된다.

 

 

공간적 지역성

공간적 지역성은 현재 메모리 위치에 가까운 명령어나 데이터가 곧 필요할 수 있다는 것을 의미한다.

 

예를 들어 원소가 100개인 배열을 탐색하는 프로그램이 있다고 하자. 첫 번째 원소를 탐색하고 나서 순차적으로 두 번째 원소를 탐색할 것이다. 이때 배열은 원소를 메모리에 순차적으로 저장해 둘 것이다. 따라서 메모리 주소를 순차적으로 참조하게 되는 공간적 지역성이 성립된다.

 

참고)

배열처럼 정렬되고 순차적인 접근이 일어나는 데이터 구조는 순차적 지역성(Sequential Locality)라고도 부른다. 순차적 지역성은 공간적 지역성의 종류라고 볼 수 있다.

 

 

시간적 지역성

시간적 지역성은 최근 참조된 명령어나 데이터가 곧 다시 필요할 수 있다는 것을 의미한다.

 

예를 들어 for문 처럼 반복문을 보자. 계속해서 같은 데이터를 반복적으로 참조할 수 있다. 이럴 때 캐시에 같은 데이터가 들어있다면 효율적일 것이다. 

 

시간적 지역성을 활용해 최근에 접근한 데이터를 캐시에 유지한다면 캐시의 효율을 높일 수 있다.

 

 

 

참조의 지역성 예시

참조의 지역성의 효율성을 보여주는 가장 유명한 예시로 배열 곱셈이 있다.

 

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

예를 들어 위와 같이 배열의 곱셈을 하는 코드가 있다고 하자.

 

배열의 마지막 차원에 원소를 연속적으로 정렬하는 언어에서는 루프 순서인 j와 k의 위치를 바꾸는 것만으로도 엄청난 속도 증가를 달성할 수 있다. 특히, 원소가 10만 개가 넘거나 L1, L2 캐시가 감당하지 못할 만큼 큰 배열의 경우 엄청난 효율을 자랑한다.

 

첫 번째 코드는 A[i][k] 배열이 캐시에 있다. k가 마지막 차원에서 연속적으로 증가하기 때문이다. 하지만 B[k][j]는 첫 번째 차원에서 k가 증가하므로 캐시 미스가 나게 된다. 

 

for i in 0..n
  for k in 0..p
    for j in 0..m
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

반면, 위와 같이 코드를 바꾸는 것만으로도 프로그램 속도를 향상시킬 수 있다. A[i][k]는 내부 루프에서 고정되어 있고, B[k][j]는 마지막 차원에서 j가 증가하므로 공간적 지역성을 충분히 활용하며 캐시 적중율을 높일 수 있다. 물론 수학적으로도 옳은 식이다. 다만 순서가 다를 뿐이다.

 

이처럼 참조의 지역성 원리를 잘 이해하고 사용할 수 있다면, 프로그램의 성능을 개선하는 데 큰 도움을 줄 수 있다.

 

 

---

참조

 

1. https://www.geeksforgeeks.org/locality-of-reference-and-cache-operation-in-cache-memory/

2. https://en.wikipedia.org/wiki/Locality_of_reference