[리눅스 커널] cache - basic

글의 참고

- https://zhuanlan.zhihu.com/p/102326184

- https://blog.naver.com/lucky777a/100045967545

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.

- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

- Overview

: 아래와 같은 코드가 있다고 가정하자.

// https://zhuanlan.zhihu.com/p/102326184
int arr[10][128];

for (i = 0; i < 10; i++)
        for (j = 0; j < 128; j++)
                arr[i][j] = 1;

 

: 그리고, 위 코드에서 몇 가지만 수정해 보았다.

// https://zhuanlan.zhihu.com/p/102326184
int arr[10][128];

for (i = 0; i < 128; i++)
        for (j = 0; j < 10; j++)
                arr[j][i] = 1;

 

: 일반적으로, 위 코드중에 어느 것이 더 성능이 좋다고 말할 수 있을까 ? 캐쉬에 대한 기본적이 지식이 있다면, 이 질문에 대한 답을 쉽게 할 수 있다. 이 글은 캐쉬 시리즈의 첫 번째 글로, 앞으로 4 편정도 추가적으로 올릴 계획이다. 먼저, 이 글은 아래의 내용을 전제로 한다.

1. L1 캐쉬는 64바이트
2. write allocation & write back 정책이 사용 됨.
3. `arr` 배열의 시작 주소는 L1 캐쉬 라인에 정렬되어 있음 

 

 

 

- Problem

1. first code region

: 위에서 제시된 코드를 `cache miss / hit` 상황에서 분석해보자. `arr[0][0] = 1` 코드가 실행될 때, cache controller 는 arr[0][0] 가 cache 없다는 것을 알게된다. 즉, cache miss 가 발생하는 것이다. 이 때, cache controller 는 RAM 에서 arr[0][0] ~ arr[0][15] 만큼을 캐쉬로 옮겨온다. 이제부터 `arr[0][1] = 1 , arr[0][2] = 1 .... arr[0][15] = 1` 가 실행되면, cache hit 가 된다.  즉, 이 시점부터는 액세스가 속도가 굉장히 빨라진다.

 

 

: 그러나, arr[0][16]  = 1 가 실행될 때, 다시 cache miss 가 발생한다. 그리고, 다시 arr[0][31] 까지는 cache hit 가 된다. 그리고, 또 cache[0][32] 에서 cache miss 가 발생한다. 즉, 첫 번째 코드는 L1 캐쉬 라인(64 바이트)의 경계 부분에서만 cache miss 가 발생한다. 이럴 경우, cache hit 가 높다고 말할 수 있다.

 

 

 

2. second code region

: 두 번째 코드는 어떨까? arr[0][0] = 1 실행 시, 캐쉬에 해당 데이터가 없으므로, 캐쉬 컨트롤러는 RAM 에서 arr[0][0] ~ arr[0][15] 만큼을 캐쉬로 옮겨온다. 그런데, 두 번째 코드인 arr[1][0] = 1 을 실행하자마자 cache miss 가 발생하게 된다. 이 과정은 arr[2][0] = 1 에서도 발생한다. 심지어, arr[9][0] = 1 까지 계속 발생한다. 그렇다면, 여기서 arr[0][1] = 1 이 실행되면, 어떻게 될까?

 

 

: 여기서 캐쉬 사이즈에 따라 시나리오가 달라진다. 

1. 만약, 캐쉬 사이즈가 안쪽 루프문에서 발생하는 캐쉬 미스를 커버할 수 있는 사이즈라면, 그 이후에 접근은 cache hit 을 보장한다. 예를 들어, arr[0][0] ~ arr[9][0] 에 접근할 때, 총 10 번의 cache miss 가 발생한다. 이게 초반에는 좋아보이지 않지만, 9번에 cache miss 가 발생 대신에, 캐쉬가 배열로 꽉 채워졌다. 이제 arr[0][1] ~ arr[9][1], arr[0][2] ~ arr[9][2] .... arr[0][15] ~ arr[9][15] 까지 모두 cache hit 이 발생한다. 그리고, arr[0][16] ~ arr[9][16] 에서 또 10 번의 cache miss 가 발생할 것이다. 이와 같은 경우는 `first code region` 과 동일한 성능을 낼 수 있다.

2. 그러나, 만약에 캐쉬가 안쪽 루프문에서 발생하는 캐쉬 미스를 커버할 수 없는 사이즈라면, 성능이 떨어진다. 왜냐면, cache replacement 때문이다. 만약에 cache 사이즈가 64 * 8 라면, 아래와 같이 마지막 arr[9][0] ~ arr[9][15] 를 캐쉬할 수 가 없다. 이 때, 기존 캐쉬에 있던 데이터를 제거하게 된다(아래 그림에서 가장 먼저 들어온 캐쉬를 제거했다).
이제 arr[0][0] ~ arr[0][15] 가 캐쉬에서 사라졌다. 그런데, 바깥 루프를 다시 수행한다. 안쪽 루프에서는 arr[0][1] = 1 이 실행되는데, 이 때, cache miss 가 발생한다.

 

: 첫 번째 코드는 위와 같은 문제가 없을까? 없다. 왜냐면, 메모리에 연속적으로 접근하기 때문이다. 캐쉬의 기본 속성은 locality 이기 때문에, 즉, 데이터를 가져올 때 뭉텅이로 가져오기 때문에 프로그램이 데이터에 연속적으로 접근할 수 록, 퍼포먼스도 좋아질 수 밖에 없다. 2 번째 코드의 문제가 뭔지 알겠는가? 메모리에 연속적으로 접근하지 않는다는 것이다.